上文分析了《sina微博计数器的设计》一文提到的Mysql/cache实现方式,这里继续其他方案的学习,包括redis和微博自己开发的couter计数器。

Redis实现计数器

对于Redis,我也只是耳闻未曾亲用,但NoSQL的原理大致相似吧。它作为一种NoSQL数据库,一般认为其读写速度都优于传统关系型数据库。按照原文分析,存储64位key+32位value,还需要其他辅助存储空间,故每个key-value对需要76字节的空间(该估算,需要了解Redis数据结构)。如果是百万级别的数据,需要百M级别的存储空间;千万级别,是G级别的存储空间,都还可以接受。但是对于微博这种千亿级别的数据,7600G的存储空间就难以接受了。更何况还要考虑主从备份的问题呢?

即使按照原文下面的分析,0评论0转发的微博占多数,故不存储这些0数据了呢?也只是存储空间降低到3040G。分析该方法,读写性能和复杂度应该都是可以接受的,但问题出在内存消耗过多。这里有一个疑问,之前用tokyo cabinet的hash类型数据库时,是可以指定需要缓存多少数据在内存中,而整体数据持久化在文件里。这样的话,内存其实不会真的消耗到那么多。Redis应该也支持吧?如果不支持,换其他NoSQL呢?其实原文下面的counter计数器也是基于这种思路,并简化了存储struct。

(这里也激发一个兴趣:PHP存储一个int、字符、数组、对象都需要多少空间呢?我虽然会去了解其源码,但是没有这么细致的分析过。)

开发Counter实现计数器

先列举其优化方法如下:

  1. 应对稀疏数据
  2. 合并转发、评论数目为一个结构体,定长
  3. 初始化时开辟大内存空间,采用二次hash的方式解决碰撞
  4. 转发、评论数 32位 -> 16位
  5. 改变数据结构,压缩value,定长->变长
  6. 优化key
  7. 批量查询
  8. 内存+磁盘,冷热数据分别处理
  9. 定期备份内存数据,配合append log,应对故障
  10. 分布式

1. 应对稀疏数据:

不存储转发、评论数为0的微博,该思路虽然简单,但是很重要!我们之前做推荐算法时,也是使用类似的思路过滤了不活跃用户,从而将数据量降低了一个数量级。(再罗嗦一下,为什么cache+存储时,cache里就必须存储0呢?是因为如果不存储,会导致cache不命中,进而继续访问DB。)

2. 合并转发、评论数目为一个结构体,定长:

这个是结合业务需求的直观想法,既然转发、评论数经常一起获取,那就存储在一起。写操作也是原子的,转发数+1应该是:偏移至weibo_id对应的item->ptr.repost_num++。

3. 初始化时开辟大内存空间,采用二次hash的方式解决碰撞

数组偏移是最快的操作。一次读取请求,处理流程可能是:计算其整数类型的hash key,偏移数组下标,读取,比较key是否一致,若一致则返回,否则处理碰撞。写操作类似。

hash碰撞有两种解决思路:不断探测;hash链表。原文采用的是“不断探测”的方法。到这里,存储40G条有效微博数据,其内存使用空间是640GB=16B×40G。

4. 转发、评论数 32位 -> 16位

这个思路很直接,内存还是大,就再想办法,这里是结合业务需求,搞了value,将32位正整数变成16位short。对于超出16位存储的数据,另外开辟内存存储。虽然略微增加了复杂度,但是内存变成了480G=12B×40G。(所以,优化一方面是技术,另一方面也是对业务需求的深入了解和思考)

5. 改变数据结构,压缩value,定长->变长

这一条还是在减少内存,采取的是压缩数据的思路。我对压缩算法和压缩比不了解,只能推测(学无止境啊!)。其原先的思路是针对每个item做变长压缩:

struct直接压缩

在这种思路下,为了保证可直接偏移数组下标,就要求每个item定长,所以如其所述,节省出来的空闲空间也没什么用。而将一维变成二维甚至更多维,并针对value做压缩后,效果就不一样了:

变长压缩value

我的理解是,针对“item”分片,比如1024个item作为一个mini block。将item里的key和value分别存储,repost_num和comment_num可以拆开也可以不拆开。这时,key仍然是连续hash存储的,当定位到key之后,需要获取到其对应的value block指针。一个key block中,该指针值是相同的,所以可以共享。那么怎样获取到这个共享数据的位置呢?我能想到的方案是,将指针存储在每个key block的顶部,故该位置=当前key指针-(当前key指针-初始位置)%(1024+1)。不知道有没有更好的方案?

这种方式,假设value的压缩比是50%,则所需内存为:(8B+2B)*40G=400G是存储key数组和value数组的空间。还需要header的存储空间,假设repost_num和comment_num一起存储,每个分片是1k个item,则=8B*(40G/1k)=320M。如果多拆分列,则会增加header的存储空间,但相对而言,还是很小的。

6. 优化key

以上都是针对value的压缩,其实key也是可以优化的。以上本来key也是被分片了,如果我们能使每个block中,key的高位或者低位有重合,那么这个重合部分,就可以存储到block的header里!更进一步,如果先对weibo_id分区,再hash,一来分区之后便于后面做分布式;二来对hash函数没什么特殊要求;三来,每个分区内数据量减少,也可以降低碰撞的几率。这时,只需要将每个分区内的weibo_id的高位存储在table header里,就可以将weibo_id从64位降低到32位,在不压缩value时内存空间=(4+2+2)*40G=320G;若同时做value压缩,并假设压缩比为0.5,则其内存空间=(4+2)*40G=240G。其数据结构为:

 

7.批量查询:根据原文给出的数据推测,counter会把一次批量查询的10条weibo_id拆分为20次key请求(为什么是20次??即使将repost和comment拆开,也不会影响到key的查询吧?),如果这些key对应value在相同的block里,则解压的操作是可以省略的。

8. 内存+磁盘,冷热数据分别处理

原文在分析热点数据时,提到了LRU导致必须cache 0数据,为什么呢?因为使用LRU意味着,当我们访问cache不命中时,有可能是数据从来没被写入cache,或者超时被expire了,或者由于cache不足根据LRU策略被踢出了。所以,不命中cache,还得再访问持久化存储获取数据。

为了避免存储0值,原文采用的是根据weibo_id区分,半年内的weibo_id肯定在cache中,如果没有则代表其值=0;半年前的weibo_id肯定在持久化存储里,不访问cache,直接去读持久化存储。

一次涉及到持久化存储的写过程是:根据weibo_id判断是否在硬盘,若是,读取内存里的硬盘block索引获取硬盘文件位置,读硬盘取整个block,存储在内存的cold block里,返回数据。

那么写过程呢?由于写之前,肯定得先读(微博页面得先显示,然后才能操作),所以写时数据应该在cold block里(cold block的溢出机制不知道什么样?如果打开页面很久之后再操作呢?)那么根据原文推测,这时仅写cold block。而之后cold block与硬盘文件的merge应该是由其他进程延时/触发独立完成的。

在这种优化思路下,可以设置最大内存,若超过,则flush数据到硬盘,并修改作为标识的weibo_id即可。

9. 定期备份内存数据,配合append log,应对故障:

这里应该是有一个后台进程or线程,定期地把内存里的数据保存到硬盘文件,结合其所说的append log,猜测这个进程可能是根据log来持久化数据,而不一定直接从内存读取吧?因为如果读取内存的话,是否就需要加全局锁呢?即使是分table持久化,也需要对table加锁。

还提到了二级索引。这里可能是对内存分table、分block做二级索引,也有可能是针对硬盘文件的。不过考虑到硬盘文件读取较少,可能不会费这个功夫吧?

(针对分散的旧数据做攻击,会不会造成计数器性能问题?有什么防护措施呢?)

10. 分布式:

跟分table的思路一样,只是粒度会更大,每台服务器负责多个table。既然是master-slave架构,那么主从间如何同步,append log是一种思路。

 

 

 

One Comment

  1. 新浪微博rss says:

    微博的阅读数,在输出微博的时候都会输出,那么是不是每条微博都单独查询转发数,阅读数?还是这个数据和该条微博数据在一起的呢?

Leave a Reply