首页 > 代码库 > 关系链的特点之读扩散和写扩散

关系链的特点之读扩散和写扩散

之前在网上看到关于Twitter、Sina以及腾讯微薄的一些实现技术,这个简单做个摘要。

1、读扩散还是写扩散?

inbox: 收件箱,你收到的消息,即你所关注的人发布的消息。
outbox: 发件箱,你发布的消息。

写扩散(Push)

该方式为每个用户维护一个订阅列表,记录该用户订阅的消息索引(一般为消息ID、类型、发表时间等一些元数据)。每当用户发布消息时,都会去更新其follower的订阅列表。
优点:读很轻。初始化时仅需要读取自己的inbox即可。
缺点:写很重。每发布一个消息,会导致大量的写操作。
注:一般来说,用户发布消息,并不会更新所有followers的订阅列表,仅更新在线followers即可。

读扩散(Pull)

该方式为每个用户维护一个发送列表,记录该用户所有发表过的消息索引。
优点:写很轻,节省空间。用户每发布一条消息,仅需更新自己的outbox。
缺点:读操作很重,计算量大。假设你收听了1k用户,则初始化时,需要从1k个用户的outbox拉取消息,然后计算获得最新的n条消息。

混合模式(Push+Pull)

该方式既为读写扩散的结合,根据用户followers的数量来决定是读扩散还是写扩散。例如followers大于1k的,则使用读扩散,否则使用写扩散。

从目前现在网上的一些资料来看,Twitter是写扩散,腾讯微薄是读扩散,新浪微薄则是二者结合。

2、关于Cache

对于一个千万级甚至亿级用户的大型网站来说,合理使用Cache至关重要。

一个用户的核心数据由如下几个部分组成:inbox,outbox,关系链,消息内容。

  • inbox:主要缓存消息索引,仅为在线用户缓存,从Timyang的PPT来看,新浪微薄估计是使用redis的list或set实现。
  • outbox:缓存一定数量(例如200)条最近发表的消息。
  • 关系链:following相对于followers来说,缓存容易些,follower加载开销比较大,例如刘翔在腾讯微薄的听众超过1600万。
  • 消息内容:按内容年龄缓存;一般需要多份支持容灾;需要缓存xml,json,rss,atom等多种格式的缓存以供API使用。

以Twitter为例,其将Cache分为四类:Vector Cache,Row Cache,Page Cache,Fragment Cache,均使用memcached实现。其中:

  • Vector Cache主要缓存用户的inbox以及outbox索引,其命中率高达99%;
  • Row Cache主要缓存用户关系链数据,以及Tweets内容,命中率为95%;
  • Fragment Cache缓存Tweet的xml,json,rss,atom四种格式数据,以供API使用,命中率为95%;
  • Page Cache主要原来缓存那些高人气用户的个人主页,命中率仅为40%。

下图为TwitterCache架构图:

Twitter为啥要为API通道设置Fragment Cache和Page Cahce呢?其原因是Twitter的80%流量来自API。

下面以新浪微薄介绍一下Cache流程:

消息发布流程:

  1. 更新自己的outbox
  2. 加载followers列表
  3. 更新followers inbox

获取首页流程:

  1. 检查inbox cache是否可用
  2. 获取关注列表
  3. 聚合内容,获得消息索引
  4. 根据索引,返回最终聚合的消息内容

3、关于存储

目前Twitter和新浪的落地存储,都是使用MySQL。而腾讯微薄则使用采用SSD+大文件存储(每次写操作都是append操作,写操作可以先用内存缓存,达到适当大小合并,尽量减少随机写)。其他细节因不清楚或不方便透露,不做细述。

4、关于洪峰处理。

一般用异步队列处理方式。消息队列产品有:Kestrel(twitter使用Scala实现),RabbitMQ(使用Erlang实现),MemcacheQ。

Twitter 09年时,用户的平均followers数量为126个。按照每秒400消息发布数算,那每秒就需要推送126*400=50400条消息出去。为了削 峰,Twitter自己用Scala实现了一个分布式消息队列Kestrel,其代码仅为1200行,运行在3台机器上,其使用memcached协议, 其Server之间无共享状态,且全内存。新浪使用的是MemcacheQ。


原文地址:http://blog.163.com/xychenbaihu@yeah/blog/static/1322296552013430114959121/

关系链的特点之读扩散和写扩散