• Articles posted by Conan Zhang
    • (Page 78)

Author Archives: Conan Zhang

About Conan Zhang

http://www.fens.me
Programmer(Java,R,PHP,Javascript)
Posted:
Jul 11, 2012
Tags:
Comments:
0 Comments

[转] CAP定理的证明

CAP定理指在设计分布式系统时，一致性（Consistent）、可用性（Availability）、Partition Tolerance（分区容忍性）三个属性不可能同时满足，该定理也叫做布鲁尔定理。CAP定理明确了分布式系统所能实现系统的局限性，目前互联网中的很多分布式系统是基于首要满足可用性和分区容忍性而设计的。在这里，不打算提及目前火热的Cassandra、Voldemort等分布式存储系统，而是打算介绍一下CAP定理。
形式化描述

一致性：
所有在分布式系统上的操作有一个总体上的顺序，每一个操作看起来就像是在一个单独的瞬间完成的。这就要求分布式系统的运行就像是在一个单节点上一样，在一个时间响应一个操作。
可用性
：对于一个可用性的分布式系统，每一个非故障的节点必须对每一个请求作出响应。也就是，该系统使用的任何算法必须最终终止。当同时要求分区容忍性时，这是一个很强的定义：即使是严重的网络错误，每个请求必须终止。

分区容忍性
：为了定义分区容忍性，假定网络满足如下条件：网络是可能丢失从一个节点发往另一个节点的任意消息，当网络被分区（隔断）时，所有从一个分区的节点发往另一个分区的消息将会丢失。一致性要求每个响应必须是一致的，即使系统内部的消息没有被正确地发送。可用性要求从客户端接收请求的任一节点必须被响应，即使任意的消息可能没有被正确地发送。

异步网络
在异步网络模型中，没有统一时钟，所有节点仅根据接收到的消息和本地的计算进行决策。

定理一：在一个异步网络模型中，没有可能实现一个满足以下属性的读写数据对象：
1、可用性
2、一致性
对于所有对等运算（包括消息会丢失的）
证明：
假设存在一个算法A满足这些条件：一致性、可用性、分区容忍性。我们构造一次A的执行，包括一个返回非一致结果的请求。假设网络包含至少两个节点，那么它可以被分为不相关的非空集合：{G，H}。假设所有G和H之间的通讯消息都丢失，这是可能的。如果这时在G上有一个写操作，接着H上有一个读操作，那么读操作将无法返回早些的写操作。

推论一：在一个异步网络模型中，没有可能实现一个满足以下属性的读写数据对象：
1、可用性，所有对等运算
2、一致性，所有对等运算，但消息不会丢失
证明：
主要问题是在异步网络模型中一个算法没有办法去判断一个消息是否丢失或者在传输通道中被延迟。因此，如果在运算中不会丢失任何消息的前提下存在一个能够保证一致性的算法，那么该算法也能够在所有运算（消息可能丢失）情况下保证一致性。这将与定理一矛盾。

部分同步网络
假设一个部分同步的网络模型，在这里，所有的节点都有一个时钟，并且所有的时钟以一个相同的速度增长。然而，这些时钟并不是同步的，在相同的时间，它们显示不同的时间值。事实上，时钟扮演计时器的角色：处理器可以根据本地状态变量去衡量流逝了多少时间。一个本地的计时器可以用来调度某事件之后的多长时间间隔进行另一个操作。进一步地，假设每一个消息要么在给定的时间s内到达，要么丢失。并且，所有的节点在给定时间t内处理完一个接收到的消息。

 

定理二：在一个部分同步网络模型中，没有可能实现一个满足以下属性的读写数据对象：

1、可用性
2、一致性

对于所有对等运算（包括消息会丢失的）

证明：
证明方法与定理一一样。
但是在部分同步模型中，类似与异步模型推论一的结论就不存在了，因此推论一的假设基于节点无法判断一个消息是否丢失。而在部分同步模型中，存在部分同步算法可以在所有消息传送正常的情况下返回一致性的数据，而仅仅在消息丢失时返回非一致性数据。对于读或写请求，节点发送一个消息给另一个节点，如果消息返回了，那么节点发送请求的数据；如果消息在给定的2s+t时间内没有返回，那么该节点断定消息丢失了，节点就可能返回一个不一致的请求数据。

理论参考价值

在Google使用廉价的PC机搭建了强大的、高可靠的计算和存储平台之后，互联网公司一致性地选择使用PC集群支撑全部的业务，这个理论指明了实现满足可用性、分区容忍性的分布式系统是可行的，并且该分布式系统在没有故障的情况下可以提供良好的一致性读写。
参考

Lynch, Nancy, and Seth Gilbert. “Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services.” ACM SIGACT News, v. 33 issue 2, 2002, p. 51-59.

Posted:
Jul 6, 2012
Tags:
Comments:
0 Comments

行列数据存储比较,MyISAM和Brighthouse引擎

测试环境MySQL的MyISAM行式数据库引擎和InfoBright的brightHouse列式数据库引擎.
本机系统：

普通台式机，2CPU，2G内存，硬盘5400转，Linux Ubuntu 12.04 32位

InfoBright按最小默认配置

my-ib.cnf
[mysqld]
27 port = 5029
28 socket = /tmp/mysql-ib.sock
29 skip-locking
30 key_buffer = 16M
31 max_allowed_packet = 500M
32 table_cache = 16
33 sort_buffer_size = 1M
34 read_buffer_size = 1M
35 read_rnd_buffer_size = 4M
36 myisam_sort_buffer_size = 8M
37 net_buffer_length = 8K
38 thread_cache_size = 32
39 thread_stack = 512K
40 query_cache_size = 8M
41 query_cache_type=0
42 # Try number of CPU cores*4 for thread_concurrency
43 thread_concurrency = 8

数据结构DDL：
CREATE TABLE t_user_myISAM(
id INT,
name varchar(32) NOT NULL ,
create_date TIMESTAMP NULL DEFAULT now()
)ENGINE=MyISAM DEFAULT CHARSET=utf8;

CREATE TABLE t_user_righthouse(
id INT,
name varchar(32) NOT NULL ,
create_date TIMESTAMP NULL DEFAULT now()
)ENGINE=Brighthouse DEFAULT CHARSET=utf8;

数据样本：
tail -f /tmp/myisam.csv
14999990,14999990–14999990,2012-07-05 16:56:54
14999991,14999991–14999991,2012-07-05 16:56:54
14999992,14999992–14999992,2012-07-05 16:56:54
14999993,14999993–14999993,2012-07-05 16:56:54
14999994,14999994–14999994,2012-07-05 16:56:54
14999995,14999995–14999995,2012-07-05 16:56:54
14999996,14999996–14999996,2012-07-05 16:56:54
14999997,14999997–14999997,2012-07-05 16:56:54
14999998,14999998–14999998,2012-07-05 16:56:54
14999999,14999999–14999999,2012-07-05 16:56:54

存储比较：数据量分别为50W条，500W条，2500W条
第一行为原始CSV,第二行为tar.gz压缩的CSV，t_user_myISAM.MYD为MyISAM引擎存储的数据文件，t_user_righthouse.bht是brighthouse的存放目录

#50w
-rw-rw-rw- 1 mysql mysql 20666643 7月 5 16:03 /tmp/myisam.csv
-rw-rw-r– 1 mysql mysql 3640018 7月 5 16:20 /tmp/myisam.tar.gz
-rwxr-xr-x 1 mysql mysql 8630 7月 5 15:32 t_user_myISAM.frm*
-rwxr-xr-x 1 mysql mysql 13959580 7月 5 15:32 t_user_myISAM.MYD*
-rwxr-xr-x 1 mysql mysql 1024 7月 5 15:32 t_user_myISAM.MYI*

#500w
-rw-rw-rw- 1 mysql mysql 221666643 7月 5 16:32 /tmp/myisam.csv
-rw-rw-r– 1 conan conan 36877526 7月 5 16:33 /tmp/myisam.tar.gz
-rw-rw—- 1 mysql mysql 8630 7月 5 16:24 t_user_myISAM.frm
-rw-rw—- 1 mysql mysql 155959580 7月 5 16:30 t_user_myISAM.MYD
-rw-rw—- 1 mysql mysql 1024 7月 5 16:30 t_user_myISAM.MYI

#2500w
-rw-rw-rw- 1 mysql mysql 908333286 7月 5 16:58 /tmp/myisam.csv
-rw-rw-r– 1 conan conan 147507267 7月 5 16:59 /tmp/myisam.tar.gz
-rw-rw—- 1 mysql mysql 8630 7月 5 16:24 t_user_myISAM.frm
-rw-rw—- 1 mysql mysql 631919160 7月 5 16:56 t_user_myISAM.MYD
-rw-rw—- 1 mysql mysql 1024 7月 5 16:56 t_user_myISAM.MYI
drwxrwx–x 2 mysql mysql 4096 7月 5 17:01 t_user_righthouse.bht/
-rw-rw—- 1 mysql mysql 8630 7月 5 16:24 t_user_righthouse.frm
#打开t_user_righthouse.bht/目录
drwxr-xr-x 2 mysql mysql 4096 7月 5 17:01 ./
drwxr-xr-x 3 mysql mysql 4096 7月 5 16:24 ../
-rw-rw—- 1 mysql mysql 0 7月 5 17:01 ab_switch
-rw-rw—- 1 mysql mysql 15344 7月 5 17:01 TA00000000000000.ctb
-rw-rw—- 1 mysql mysql 5616 7月 5 16:34 TA00000000000001.ctb
-rw-rw—- 1 mysql mysql 117 7月 5 16:34 TA00000.ctb
-rw-rw—- 1 mysql mysql 14171 7月 5 17:01 TA00000DPN.ctb
-rw-rw—- 1 mysql mysql 126449126 7月 5 17:01 TA00001000000000.ctb
-rw-rw—- 1 mysql mysql 31428144 7月 5 16:34 TA00001000000001.ctb
-rw-rw—- 1 mysql mysql 103 7月 5 16:34 TA00001.ctb
-rw-rw—- 1 mysql mysql 14171 7月 5 17:01 TA00001DPN.ctb
-rw-rw—- 1 mysql mysql 16962 7月 5 17:01 TA00002000000000.ctb
-rw-rw—- 1 mysql mysql 6015 7月 5 16:34 TA00002000000001.ctb
-rw-rw—- 1 mysql mysql 126 7月 5 16:34 TA00002.ctb
-rw-rw—- 1 mysql mysql 14171 7月 5 17:01 TA00002DPN.ctb
-rw-rw—- 1 mysql mysql 65 7月 5 16:24 Table.ctb
-rw-rw—- 1 mysql mysql 117 7月 5 17:01 TB00000.ctb
-rw-rw—- 1 mysql mysql 103 7月 5 17:01 TB00001.ctb
-rw-rw—- 1 mysql mysql 126 7月 5 17:01 TB00002.ctb

数据存储总结：brighthouse的列式引擎的压缩比，真是相当的高啊！

数据行    csv      csv.tar.gz   MyISAM   brighthouse
50w      20m     3m              14m
500w    222m   37m           156m
2500w  908m   147m         623m      159m

数据查询(2500w)：无索引！
SELECT * FROM infobright.t_user_myISAM
where create_date<‘2012-07-05 16:26:32’ limit 1000000,100;
时间>30s

SELECT * FROM infobright.t_user_righthouse
where create_date<‘2012-07-05 16:26:32’ limit 1000000,100;
时间<1s

SELECT count(id) FROM infobright.t_user_myISAM
where create_date<‘2012-07-05 16:26:32’;
时间>30s

SELECT count(id) FROM infobright.t_user_righthouse
where create_date<‘2012-07-05 16:26:32’;
时间<1s

如此可以，brighthouse引擎查询是很快的,远优于无索引的MyIASM。

在t_user_myISAM表创建索引：
CREATE INDEX t_user_myISAM_IDX_1 on t_user_myISAM(id);

-rw-rw—- 1 mysql mysql 8630 7月 6 10:52 t_user_myISAM.frm
-rw-rw—- 1 mysql mysql 631919160 7月 6 10:53 t_user_myISAM.MYD
-rw-rw—- 1 mysql mysql 226201600 7月 6 10:54 t_user_myISAM.MYI
索引占用空间226m

mysql> SELECT count(id) FROM infobright.t_user_myISAM where id<15484646;
+———–+
| count(id) |
+———–+
| 19999998 |
+———–+
1 row in set (16.17 sec)

mysql> explain SELECT count(id) FROM infobright.t_user_myISAM where id<15484646;
+—-+————-+—————+——-+———————+———————+———+——+———-+————————–+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+—-+————-+—————+——-+———————+———————+———+——+———-+————————–+
| 1 | SIMPLE | t_user_myISAM | index | t_user_myISAM_IDX_1 | t_user_myISAM_IDX_1 | 5 | NULL | 19999998 | Using where; Using index |
+—-+————-+—————+——-+———————+———————+———+——+———-+————————–+
1 row in set (0.01 sec)

按索引的查询，需要16.17s

mysql> SELECT count(id) FROM infobright.t_user_righthouse where id<15484646;
+———–+
| count(id) |
+———–+
| 24999997 |
+———–+
1 row in set (0.00 sec)

mysql> explain SELECT count(id) FROM infobright.t_user_righthouse where id<15484646;
+—-+————-+——————-+——+—————+——+———+——+———-+———————————–+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+—-+————-+——————-+——+—————+——+———+——+———-+———————————–+
| 1 | SIMPLE | t_user_righthouse | ALL | NULL | NULL | NULL | NULL | 24999997 | Using where with pushed condition |
+—-+————-+——————-+——+—————+——+———+——+———-+———————————–+
1 row in set (0.00 sec)

索引总结：即使使用MyISAM的索引查询，对于2500W条数据来说，也不如brighthouse的无索引ALL查询。我们真应该在适合的时间，适合的地点，把列式数据库应用起来！！

Posted:
Jun 8, 2012
Tags:
Comments:
1 Comment

为什么要开发@晒粉丝应用！

logo

从业互联网，软件行业已经多年，疲于做各种的项目、系统。原本走软件架构方向，基于SOA的各种系统集成解决方案。后来又投入互联网在高并发，大数据的背景下，做了云计算，SaaS等。一路跟着时代发展的脚步在前进。

现在的SNS，电子商务，微薄，博客等等的各种网络应用，都已经大众化，积累了大量的用户数据。这些数据怎么处理，便成为下一阶段要考虑的问题。@晒粉丝的应用，其实对于我来说是建立一个数据挖掘算法的运行平台。我会分析数据，但我没有能力采集数据，也没有能力存储数据。微博的开放平台，正好为我提供了一个采集数据和存储数据的平台，我可以专心做算法，解决数据的事情。

大家都知道算法有很多种，有数学，概率，统计的基础理论算法，也有计算世界里的排序算法，数据结构算法，ACM的各种算法，还是一些智能的算法，贝叶斯，神经网络，聚类等。这么多的算法，怎么用来处理微博的数据？其实我也并没有太多的经验，但我愿意努力去尝试。我希望从微博粉丝这个小点开始，发掘微博内在的关系。

晒粉丝的平台，也主要是以我个人的知识去构建的，按照以下的过程执行。

 

  1.  通过每个访问者的微博行为，进行数据采集。
  2.  设计算法模型，对每种数据集进行数据分析。
  3.  通过各种开源算法库去完成计算。
  4.  进行可视化的输出，返回用户能看得懂的数据。

 

这个应用开始只有简简单单地几个功能，粉丝云，粉丝微博年龄，认证比例。。。主要是为了搭建平台前期铺垫。之后会尽我的知识所学，发现微博的各种秘密！！

如果你使用了这个应用，谢谢你的支持。

如果你能提出你的宝贵意见，我会更加高兴！

现在只是刚开始，一切都会更好的！！