传统的图存储了, 早期阅读过, 重新复习记录下.

需求 

论文列举了 使用场景: 用户发布checkin 打卡地点 并 提及 朋友, 朋友之间发布评论. 用户之间的朋友关系维护. 现在面临的问题:

  • edge list
  • 分布式控制逻辑
  • read-after-write consistency

设计

tao以前, 用 mysql + memcache 针对业务做了实现, 但是耦合太重, 后来针对性的 构建模型. 支持 lookside cache、list edge、lease，remote marker（写后读），支持 inverse 耦合操作.

data model & api

tao的数据模型: 将node/edge 抽象成 object 和 association, object存储 用户、checkin、landmark、comments. association 存储 freendiship、authorship(checkin/comment), 比较特殊的是, action 比如 like/acceptance of invitation, 既可以编码成 object, 也可以编码成 association. 另一些比如 frendiship、authorship 都是双向关系.

实现上, object 使用 64bit integer 唯一标识, association 用 source object + association type + destination object 标志, 任意两个 object 只有一种type的关系. object 和 association 用 kv 标识, 如下:

Object: (id) → (otype, (key -> value)∗)
Assoc.: (id1, atype, id2) → (time, (key -> value)∗)

api层面上, object api 支持 allocation、retrive、update、delete 操作. association api 支持 assoc_add、assoc_change、assoc_delete, 以及 assoc_list (从最新到最早)、assoc_get、assoc_count、assoc_range、assoc_time_range

arch

底层存储还是 mysql shard + cache tier(memcached), 每个database server 负责一个或多个shard(一致性hash分配). cache tier 支持完整的 api, 每个请求 映射到 cache tier 的一个cache server(算法和db sahrd一致, 比较有意思的是, 每个 object 都包含了shard id). cache tier 使用LRU 维护内存的 object、association list 和 association count.

对于双向的添加, 接受forward egde 的 cache tier 会先请求 dest object 所在的 cache server 添加反方向的操作, 成功后再添加 forward edge; 中间不一致的状态通过async job 完成 (划重点, 这个设计很关键).

为了处理高吞吐和大流量, 直接的办法就是 水平扩容 cache tier, 但是 cache tier 太大, 更加容易出现热点, 以及 链接数暴涨的问题, 为了更好的解决这个问题, cache tier 分成了 leader tier 和 多个follower tier, leader tier 的 membership 都是leader, 负责 一个或者多个shard, 所有对这个 db shard 的读写 都走这个 leader cache tier; follower tier 的 membership 都是 follower, follower 负责将 read-miss 和 write 转发给 leader tier; 有意思的是, client 永远不会和 leader tier 沟通, 都是和 最近的 follower tier.

问题, leader-follower cache 如何保持一致性? follower tier 需要其他 follower tier 通知, 最终一致性的保证, 通过 leader->multi follower 的 cache-maintenance/invalidation/refill(version number+change set) 消息, follower 同步响应. leader tier 负责 序列化并发 避免惊群.

因为最终一致性的实现, 以及 mysql + cache 同步机制的差异, 会出现 数据来回变动的现象, slave region中, mysql 存储了旧值, cache tier 一开始收到更新提供给client 新值, 但是因为 缓存压力置换出了数据, 再次从 数据库加载 就是 旧值了. 为了保证更强的一致性, 提供了 critical 模式, 会转发读取 master region.

问题: cache cpordinator per database ?

为了应对全球化布局, 单dc内 leader/follower cache tier 的延迟很低, 但是 跨dc的延迟很高, 而且 read-miss 有25倍. facebook 论文的解决方案, 设计了 每个shard的 master/slave region, 每个region都有 自己的数据库 和 leader-follower cache tier, follower region 的 db 复制 leader region db, leader region db 是 ”source of truth“, follower region 是 local-read(read-miss 也是本地), write 是转发到 master region. 每个region都是 完整的副本.

多个shard 会映射到 多个 region上, 每个shard leader 只在一个region上, 一个region有多个 leader shard 和 follower shard. shard 可以在region之间切换.

数据库之间的复制通过 统一的 database replication stream. 复制完成之后, 才会发送 invalidation/refill 同步消息 来保证数据的同步.

后续讨论了 高效的memcache 和 mysql 实现.

特殊的优化:

  1. cache load balance, 通过 cloned shard + client cache(version+data) 解决.
  2. 空结果查询优化, 出度高的obejct, 可以选择入度object 进行查询; 限制时间的查询优化  ( 存在的场景下, dest obj time > edge time)

失败检测

类似熔断的做法 实现失败检测;

细分:

  • db 不可用: master region master db 不可用, 其他 slave db 直接自动升级; slave region db 挂了, 流量到 master region, binlog 同步组件后续会给 slave db 同步消息.
  • leader cache tier 不可用: leader cache tier 的 server 可以互相替代, replacement cache server 会保存 async invalidagtion 给 recovered leader, 同时也会记录到 coordinator 以及 replication stream. recoverd leader 对外提供服务的时候可能提供 stale value
  • refill&invalidation: 内存+磁盘 同步给follower; leader downtime recovery, 会 bulk invalidation; leader permanent replacement, 则 shard对应的数据 全部 invalidation
  • follower tier: follower tier 互相补充提供服务, client 请求会提供 primary/backup tier 实现failover (read-after-write 会受到影响).

个人感受

整体上感觉还是 业务层的抽象, 提供诸多服务的底层抽象. leader/follower tier 的设计思路不错; master/slave region 比较常规

参考