Cydu's Blog Keep it Simple & Stupid!

[WeiDesign]微博计数器的设计(下)

09 Sep 2012

Contents

更新

  • Update: 更新了数据持久化和一致性保证相关的内容，多谢 @lihan_harry @郑环Zheng @51刘达 等同学的提醒。
  • Update2: 更新了 对于weibo_id key的优化，使用前缀压缩，可以节省近一半的空间。 感谢 @吴廷彬 @drdrxp 的建议！
  • Update3: 更新了 对于value 使用二维数组，多列进行压缩编码的优化思路， 再次感谢 @吴廷彬 的建议，
  • Update4: 更新Redis方案下内存使用的估算, 感谢 @刘浩bupt 的提醒。

背景

上周挖了一个坑 微架构设计 微博计数器的设计(上)

虽然挖这个坑的动机是很不纯的(很明显的招聘软文, 非常欣慰的是确实收到了不少靠谱的简历, 希望简历来得更猛烈一些! ), 但是和大家讨论的过程中，还是收获很大的, 也认识了不少新朋友。

方案

对于一个简单的计数服务来说，确实非常的简单，我们可以有很多的解决方案:

方案一 直接上mysql

这个不用多说了吧，足够的简单暴力。 但是在产品发展的初期快速迭代的阶段，他能够解决很多的问题，也不失为一个不错的解决方案。

数据量过大怎么办?

对于一亿甚至几亿以下的数据规模来说，拆表能够解决很多问题，对于微博计数器来说至少有两种经典的拆法:

  • 按id取模，把数据拆分到N个表当中去。 这个方案的悲剧是: 扩展性不好，不好加表，数据一旦满了，加起来很郁闷。虽然可以预先多分一些表，但是对于weibo这种快速增长的业务来说，严重影响了业务的快速增长需求。
  • 按id的时间来分段拆表，满了就建新表。 这个方案的悲剧是: 冷热不均，最近的weibo肯定是被访问最频繁的，而老的库又基本没有访问。 可以通过冷热库混合部署的方案来缓解，但是部署和维护的成本非常大。

数据量从亿上升到千亿后，这个问题的本质就发生了变化，维护上千张表，热点还各不相同需要经常切换调整，这是一件非常悲剧的事情。。。

访问量太大怎么办?

应对访问量，也有很多的经典的方法:

  • 上Cache(Eg: Memcache), 访问时先访问Cache，不命中时再访问mysql. 这样做有两个郁闷点: 空数据也得Cache(有一半以上的微博是没有转发也没有评论的，但是依然有大量的访问会查询他); Cache频繁失效(由于计数更新非常快，所以经常需要失效Cache再重种，还会导致数据不一致);做为最基础的服务，使用复杂，客户端需要关注的东西更多
  • 更好的硬件解决。 上FusionIO + HandleSocket + 大内存 优化. 通过硬件的方式也能够解决问题，但是这是最典型的Scale up的方案。虽然完全不用开发，但是硬件成本不低，且对于更复杂的需求，以及流量快速的增长，也很难应对。

优点

  • 不用开发, 码农们可以用写代码的时间出去泡泡妞。
  • 方案成熟, 数据复制，管理，修复方案都很成熟。

缺点

  • 对大数据量和高并发访问支持不好，非常的力不从心。
  • 维护成本和硬件成本都很高。

总的来说

  • Mysql分表 + Cache/硬件 加速的方案 对于数据规模和访问量不是特别巨大的情况下，非常不错的解决方案，但是量大了之后非常不合事宜.

既然 Mysql不行，那用NoSQL 呢？

方案二: Redis

做为一个简单的内存数据结构来说，Redis提供非常简单易用的访问接口，而且有相当不错的单机性能。 通过incr实现的 Counter Pattern，用来做计数器服务，更是简单轻松。 通过上层的分表，增加slave等方式，堆一些机器，也能够解决大数据量和高并发访问的问题。

但是Redis是纯内存的(vm机制不成熟而且即将被废弃,我们线上肯定是不敢直接使用的！)，所以成本也不算低，我们简单的来估算一下数据存储量(下面都是按照Redis 2.4.16的实现，在64位系统，指针为8字节来估算的) :

假设 key 为8字节，value为 4字节，通过incr存储的话:

  • 一个 value 通过 createStringObjectFromLongLong 创建一个robj，由于value在LONG_MIN 和LONG_MAX 之间，所以可以将value用 ptr指针来存储，需要占用 sizeof(robj) = 16 字节;
  • 一个key(即微博id) 最长64位数字(Eg: 5612814510546515491)，但通过 sdsdup 以字符串的形式存储，至少需要 8(struct sdshdr)+19+1 = 28字节;
  • 为了存到Redis 的dict里面，需要一个dictEntry对象，继续 3*8 = 24字节;
  • 放到db->dict->ht[0]->table中存储dictEntry的指针，再要 8个字节;
  • 存储一个64位key，32位value的计数，Redis也至少需要耗费: 16 + 28 + 24 + 8 = 76 字节。
  • 1000亿个key全内存的话，就至少需要 100G * 76 = 7.6TB 的内存了(折算76G内存机器也需要100台！)。
  • 我们的有效数据其实是 1000亿*32位 = 400GB，但是却需要7.6TB来存储，内存的有效利用率约为: 400GB/7600GB = 5.3%.

即使这样，对于很多热点的数据，只有一个副本，单机性能不够，系统的稳定性也无法保证(单机Down掉咋办？)， 还需要复制多份。 再算上为了避免内存碎片引入的jemalloc的内存开销; 再算了dictExpand等需要的临时内存空间; 再算上系统要用的内存开销。。。那要的机器就更多了，保守估计需要300-400台以上的机器。

总的来说:

  • Redis做为优秀的内存数据结构，接口方便，使用简单，对于小型数据量的中高访问量的计数类服务来说，是一个很不错的选择，但是对于微博计数器这种极端的应用场景，成本还是无法接受！

还有一些同学提出了用 Cassandra，MongoDB 等其他NoSQL的方案，无论是从可维护性的角度，还是从机器利用率的角度，都很难以接受(有兴趣的同学可以仔细分析一下)。

普通的NoSQL也不行，那怎么办？ 尝试定制我们自己的Counter！

Update4:

  • @刘浩bupt @cydu 刚刚仔细阅读了文中redis容量预估的部分，有两点小瑕疵：1.对于value的存储，文中估算了16个字节，其实这部分开销是可以节省的。createStringObjectFromLongLong函数，对于小于REDIS_SHARED_INTEGERS的value值，不会额外分配空间。REDIS_SHARED_INTEGERS默认是10000，调大一些可以满足大部分需求
  • @刘浩bupt @cydu 2.是可以评估下使用zipmap达到的内存利用率。redis不是只有string->string的kv存储，还是有一些可以挖掘的东西的。instagram在其工程博客中介绍过（http://t.cn/S7EUKe），改用zipmap后，其存储1M的数据，内存占用由70M优化到了16M。鉴于新浪微博大量的使用redis，定制redis实现服务也是个思路。

感谢 @刘浩bupt 同学帮我指出对于Redis容量预估的不准确，通过Redis自带的 REDIS_SHARED_INTEGERS 机制确实可能大量节省value所占的内存，但是由于这个方案需要依赖存储shared_int的指针，不太好迁移到方案三里面去。 Zipmap这个优化的思路是相当不错的，对于通用的Redis的使用，我们会持续关注。

方案三: Counter

计数器是一个普通的基础服务，但是因为数据量太大了，从而量变引发了质变。 所以我们做Counter时的一个思路就是: 牺牲部分的通用性，针对微博转发和评论的大数据量和高并发访问的特点来进行定点优化。

1. 大量微博(一半以上)没有转发或没有评论，甚至是都没有

针对这种情况的优化:

  • 抛弃 存储+Cache 的思路.因为这些为0的数据，也必须进到Cache中(无论是旁路还是穿透).
  • 查询量并不小，这对于我们Cache的利用率影响非常非常的大(有一半的数据是空的。) 而我们采用类似 存储即Cache(存储本身就在内存中) 时，这一类的数据是可以不存储的，当查不到的时候，就返回0。

通过这种优化:

  • 1000亿个数字，我们可以减少3/5，即最多只需要存 400亿个数字。这算是最经典的稀疏数组的优化存储方式了。

2. 微博的评论数和转发数的关联度非常的高。

他们都有相同的主Key, 有大量转发的微博一般也有评论，有大量评论的一般转发量也不小。 而且访问量最大的Feed页基本上取评论数的时候，也会取转发数。。。

针对这种情况的优化:

  • 我们将评论数和转发数 可以考虑存储在一起，这样的话，可以节省大量key的存储空间。 由 微博ID+评论数; 微博ID+转发数 变为: 微博ID+评论数+转发数的结构。
  • PS: 这个优化和上一个优化是有一些小冲突的，部分有转发没有评论的微博，需要多存一个0; 但是经过数据评估，我们发现这个优化还是相当必要的:
    • key存储的空间比评论数还要长，一个8字节，一个4字节;
    • 对于应用层来说，批量请求可以减少一次访问，能够降请求的压力，同时提升响应的时间;

(具体的数字不方便透露，但是这个结论大家可以随机抽取一批公开的微博来验证)

3. 数据结构的优化

通过方案二中Redis对内存使用的分析，我们发现是非常”奢侈”的, 大量的重复存储着指针和预留的字段，而且造成大量的碎片内存的使用， 当然Redis主要是出于通用性的考虑。

针对这种情况:

@果爸果爸 同学设计了一个更轻量更简单的数据结构，能更好的利用内存，核心思路:

a. 通过下面的item结构来存储 转发和评论数:

struct item {
    int64_t weibo_id;
    int repost_num;
    int comment_num; 
};

存储数字，而不是字符串，没有多余的指针存储， 这样的话，两个数字只占 16个字节;

b. 程序启动的时候

开辟一大片的内存 (table_size * sizeof(item)) 并清0他。

c. 插入时:

h1 = hash1(weibo_id);
h2 = hash2(weibo_id);

如果 h1%table_size 是空的，则把item存储到这个位置上; 
否则 s=1 并找 ( h1 + h2*s ) % table_size 的位置，
如果还不空的话，s++继续找空位。。。

d. 查询时:

和插入的过程类似，找到一个数据后，比较weibo_id 和 item.weibo_id 是否一致，一致
则表示查到，否则查到空的则表示为值为0;

e. 删除时:

查找到所在位置，设置特殊的标志; 下次插入时，可以填充这个标志位，以复用内存。。。

经过我们实测，当2亿数据这种长度的数组中，容量不超过95%的时候，冲突率是可以接受的 (最悲剧的时候可能需要做几百次的内存操作才能找到相应的空位, 性能上完全能够接受; )

经过这个优化之后，我们的总数据量变成了:

  • 400亿 * 16B = 640GB; 基本是方案二的 十分之一还少！

4 转发和评论数 Value的优化

继续观察，我们发现大量的微博，虽然有转发和评论，但是值一般都比较小，几百或者几千的， 超过几万的weibo很少(数据调研显示在十万分之一以下)。

所以我们把 item 升级为:

struct item{
    int64_t weibo_id;
    unsigned short repost_num; 
    unsigned short comment_num;
};

对于转发数和评论数大于65535的weibo，我们在这里记录一个特殊的标志位FFFF，然后去 另外的dict中去查找(那边不做这个优化)。事实上，还可以把 unsigned short优化为 int:12 之类的极端情况，但是更复杂，且收益一般，所以我们还是选用unsigned short。

经过这个优化后，我们的总数据量变成了:

  • 400亿 * 12B = 480GB, 这个数据量已经差不多是单机能够存储的容量了。
  • 每秒的查询量由100W变成了50W, 更新量每秒只有数万没有变化，和查询量比可以先忽略。

4.1 补充 Value的优化

  • @吴廷彬 另外，64bit value可以用utf-8的类似思想再压缩。最后因为cpu/mem不是瓶颈，可以将weibo_id和后面的value分开放在两个数组里面，对应的index一样即可。然后会发现value数组里面的64bit很多位全是0，或许可以考虑以K为单位的数据做简单数据压缩放入内存里面，这个压缩比应该是惊人的。
  • @吴廷彬 回复 @cydu :value可以用二维数组怎么样。 如果1K为单位压缩则每一行表示1K个数据。然后对数据进行压缩写入。 一般可能每行只用100个字节？
  • @cydu 这样确实可以，变长编码会有意义，反正cpu应该不是瓶颈，有更新的时候整块重新编码，取也是全取出再解压。还一个好处是我加列更方便了，现在我加列的代价其实是很高的。

最早的时候，我也想过用变长压缩，但是思路一直局限在一个value里面做压缩，由于只有两列，我们又是用定长的存储，一方面变长有开销(标志位标志用了多少位来表示)，另一方面定长开给的32位省出来也没有合适的用处(可以和key的优化结合起来，用更少的字段)。 @吴廷彬 一说二维数据，立马变长压缩的好处就显现出来了。

  • 我可以把key单独存储，把value，按 1024个value甚至更多个value 压缩到一个mini block中存储，在定长的情况下，这个mini block的size是 1024*32 = 4K. 但是事实上，这4K中包含了大量的 0, 我不用自己整复杂的变长编码，直接拿这4K的数据做LZF压缩，只存储压缩后的数据就行了, 取的时候先解压缩。 具体的压缩效率得看数据才能定，但是根据一般文本的压缩到 50% 应该是非常轻松的，也就是说，至少可以节省 400亿 * 2 = 80GB的内存。

这个方案最大的一个好处还不在于这80GB的内存的节省，而是：

  1. 我前面优化提到的 大于 65535 的转发和评论，我可以考虑简单做了，反正变长嘛，不影响，整个方案是简化了的。(当然需要具体的数据测试一下，验证哪个更好)
  2. 相当重要！ 对于微博的计数，其实我们是有加列的需求的，比如其他的类似评论数的数字，我原来的方案中，加列的代价是相当高的，需要重开一个大数组，还要事先设好hint(对于新业务来说，hint值的不好选取，但是他对性能和内存的使用率影响又是致命的!)，而这个方案，无论你加多少列都其实没啥关系，用内存的长度只和你真实的数据量相关！

经过这个优化后，我保守的估计:

  • 我们能够在之前的基础上，再节省 80GB 的内存！

5. key的优化

  • @吴廷彬 很好的文章。weibo_id是8byte的，压缩能够压到接近4byte.假如一堆数据是AB,AC,AD,AE,AF, XE,XY,XZ.把他在内存里面A开头放在一坨内存，X开头放在另外一坨，里面只用存B,C,D,E,F和Y,Z. 基本上能减少4个字节。能省掉40G*4=160G？
  • @drdrxp 存储分成2^24个区,weibo_id%(2^24)指到区的号上,记录中再用40bit 存储weibo_id/(2^24),记录中另外12bit 存转发,12bit存评论, 1条记录总共8字节,480G可以优化到320G. 如果能实际考察下评论转发数的分布应该可以更加优化1些.

感谢@吴廷彬 @drdrxp 提的这个建议，这一块的优化空间确实非常的大。后面其实有提到，我们会根据时间段或者根据weibo id把大的table 划分成多个小的table(主要是为了能够序列化到磁盘腾空间给更热的数据)。 所以在一个小table里面的数据都是weibo_id比较接近的，Eg: 5612814510546515491， 5612814510546515987， 我们可以把这64位key中相同的高32位归并起来。做为小table的属性(prefix)，就不必每一条都存储了。 8字节的key，至少能够节省 4字节。

struct item{ 
    int weibo_id_low;
    unsigned short repost_num;
    unsigned short comment_num;
};

经过这个优化后，我们的总数据量变成了:

  • 400亿 * 8B = 320GB， ^_^

也感谢 @drdrxp 的建议，之前也考虑过12bit来存评论数和转发数，确实能够优化不少，但是由于多出来的bit不知道干嘛，就没搞了，呵呵。你的建议和 @吴廷彬 提的建议都主要是在key上做文章，很赞！

6. 批量查询

对于Feed页来说，一次取到N条微博，然后查询他的计数，这里可以很好的批量化查询来优化响应时间。

以一次批量访问10个微博的计数来说，对于Counter碰到的压力就是:

  • 5W requests/second， 100W keys/second;

对于全内存的简单服务来说，单机已经基本能够扛 5W+ 的请求了。

7. 冷热数据

继续看这400亿个数字，我们发现，访问热点非常的集中，大量去年，甚至前年的weibo无人访问。 本能的可能想到经典Cache的做法，热的数据在内存，冷的数据放磁盘。 但是如果引入lru的话，意味 着我们的struct item得膨胀，会占用更多内存。而且对于0数据也得Cache。。。

对于这种情况，我们设计了一个非常简单的内存和磁盘淘汰策略:

  • 根据weiboid的区间（其实是时间）来进行淘汰，按区间划分，超过半年的dump到磁盘上去，半年内的继续留存在内存，当少量用户挖坟的时候
  • (访问很老的微博并转发/评论)，我们去查询磁盘，并将查询的结果放到 Cold Cache当中.
  • 为了方便把旧的数据dump到磁盘，我们把那个大的table_size拆成多个小的table，每个table都是不同的
  • 时间区间内的weibo计数，dump的时候，以小的table为单位。
  • 为了提高磁盘的查询效率，dump之前先排序，并在内存中建好索引，索引建在Block上，而非key上。
  • 一个Block可以是4KB甚至更长，根据索引最多一次随机IO把这个Block取出来，内存中再查询完成;

经过这个优化:

我们可以把将近200G的数据放到磁盘当中, 剩余120GB的数据仍然留在内存当中。 而且即使随着weibo数越来越多，我们也依然只要保存120GB的数据在内存中就行了， 磁盘的数据量会增加，热点的数据也会变化，但是总的热点数据的量是变化很少的！

8. 数据的持久化

对于Sorted 部分的数据:

  • 一旦刷到磁盘后，就只会读，不会修改，除非在做和Cold Block做merge的时候，才会重写 (目前这一块merge的逻辑没有实现，因为必要性不高)。

对于内存中的数据:

  • 我们会定期把 Block 完整的dump到 磁盘中，形成 unsorted block。 然后每一次内存操作都会有相应的Append log， 一旦机器故障了，可以从 磁盘上的Block上加载，再追加Append log中的操作日志来恢复数据。

当然，从整个架构上，一旦Counter崩溃等严重错误，导致数据错误，我们还可以:

  • 通过 具体数据的存储服务上把数据重新计算出来，恢复到Counter当中。
  • 当然这种计数的代价是非常高的，你想想姚晨那么多粉丝，counter一遍很恐怖的， 我们也另外做了一些二级索引之类的简单优化。

9. 一致性保证

  • @lihan_harry 上边文章提到计数对正确性要求高，由于计数不满足幂等性。那么这个问题是怎么解决的
  • @cydu 回复 @lihan_harry 是这样的，前面有一个消息队列，通过类似于transid的方案来做除重，避免多加和少加; 当然这里主要是指用主从的结构，incr累加，即使是最终一致也不至于太离谱; 另外，我们还有做实际的存储数据到Counter的定期数据校验，以后面的数据存储为准
  • @郑环Zheng 貌似还会有写请求单点问题，老数据的删除递减走硬盘，多机房冗余，机器假死宕机数据会不会丢失，删微博的时候还要清空相关计算不呢
  • @cydu 回复 @郑环Zheng 是的，为了incr 的准确性，还是使用Master-Slave的结构，所以Master的单点问题依然存在，需要靠主从切换，以及事后的数据修复来提高数据的准确性。

10. 分布式化

出于稳定性的数据冗余的考虑，而且考虑到weibo现在数据增长的速度，在可预见的未来，数字会 变成1500亿，2000亿甚至更高。

我们在上层还是做了一些简单的拆分的，

  • 按照weiboid取模，划分到4套上(主要是考虑到后续数据的增长)，
  • 每套Master存储后面又挂2个Slave, 一方面是均摊读的压力，另一方面主要是容灾(当主挂掉的时候，还有副在，不影响读，也能够切换)

所以, 我还是没能单机扛住这1000亿个数字，和每秒100W次的查询。。。只好厚着脸皮问老大申请了十几台机器。

优点: 单机性能真的很好，内存利用率很高，对后续扩展的支持也相当不错。

缺点: 我们码农泡妞的时间少了，得抽空写写代码。。。但是，如果不用写码的话，那码农还能干嘛呢？

对于这种极端的情况，所以我们采用了同样极端的方式来优化，牺牲了部分的通用性。

方案四: Counter Service

方案三出来后, 微博计数的问题是解决了，但是我们还有用户关注粉丝计数呢，好友计数，会员计数… 数字社会嘛，自然是很多数字，每一个数字背后都是一串串的故事。

针对这种情况，我们在Counter的基础上，再把这个模块服务化，对外提供一整套的 Counter Service， 并支持动态的Schema修改(主要是增加)，这个服务的核心接口类似于下面这个样子:

//增加计数, 计数的名字是: "weibo" 
add counter weibo                           

// 向"weibo"这个计数器中增加一列，列名是 weibo_id, 最长为64位，一般也是64位，默认值为0, 而且这一列是key
add column weibo weibo_id hint=64 max=64 default=0 primarykey 

// 向"weibo"这个计数器中增加一列，列名是 comment_num, 最长为32位，一般是16位，默认值为0 
add column weibo comment_num hint=16 max=32 default=0  suffix=cntcm     

// 向"weibo"这个计数器中增加一列，列名是 repost_num, 最长为32位，一般是16位，默认值为0
add column weibo repost_num hint=16 max=32 default=0  suffix=cntrn    

// 向"weibo"这个计数器中增加一列，列名是 attitude_num, 最长为32位，一般是8位，默认值为0
add column weibo attitude_num hint=8 max=32 default=0  suffix=cntan    

.... 

// 设置weibo计数中 weibo_id=1234 的相关计数，包括 comment_num, repost_num, attitude_num
set weibo 1234 111 222 333

// 获取weibo计数中 weibo_id=1234 的相关计数，包括 comment_num, repost_num, attitude_num
get weibo 1234 

// 获取weibo计数中 weibo_id=1234 的相关 comment_num
get weibo 1234.cntcm

// 增加weibo计数中 weibo_id=1234 的相关 comment_num
incr weibo 1234.cntcm

....

当 add column的时候，我们会根据hint值再增加一个大的table (table_size * sizeof(hint)), 但是这里不存储key，只有value，用原来item那个大table的相同key。 对于超过部分依然是走 另外的存储。

通过计数器服务化之后，最大的好处就是，后面我们再要加计数，有可能量没有那么大，可以很快的 创建出来。。。

缺点:

  • 对于非数值类的key名，可能会退化到字符串的存储，我们可以通过简化的base64等机制来缩短空间;
  • 对于频繁修改老的数据，导致cold buffer膨胀的问题，可以通过定期的merge来缓解（类似于Leveldb的机制）;

方案五: 你的方案

对于工程类的问题，其实永远不会有标准的答案，一千个架构师能给出一万个设计方案来，而且没有一个是标准的答案，只有最适合你的那一个！ 这里只简单分享一下我的一个思考过程和不同阶段最核心关注的点，欢迎大家一起讨论。

期待你的思路和方案！ 期待你们的简历， 请私信 @cydu 或者 @微博平台架构。

当然，微博平台除了计数器这一个典型的小Case外，还有更多更大的挑战需要你的方案！

Related Posts