设计微博系统
架构
信息流聚合一般有三种架构：推模式、拉模式以及推拉结合。
针对关注的粉丝量大的用户采用拉模式，而对于一般用户来说，他们的粉丝量有限，采用推模式问题不大，这样的话一个用户要获取所有关注人的微博，一方面要请求粉丝量大的关注人的发件箱列表，另一方面要请求自己的收件箱列表，再把两者聚合在一起就可以得到完整的 Feed 了。虽然推拉结合的方式看似更加合理，但是由此带来的业务复杂度就比较高了，因为用户的粉丝数是不断变化的，所以对于哪些用户使用推模式，哪些用户使用拉模式，维护起来成本就很高了。所以综合考量下来，微博 Feed 采用了拉模式。
前面提到采用拉模式的话，需要拉取所有关注人的发件箱，在关注人只有几十几百个的时候，获取效率还是非常高的。但是当关注人上千以后，耗时就会增加很多，实际验证获取超过 4000 个用户的发件箱，耗时要几百 ms，并且长尾请求（也就是单次请求耗时超过 1s）的概率也会大大增加。为了解决关注人数上千的用户拉取 Feed 效率低的问题，我们采用了分而治之的思想，在拉取之前把用户的关注人分为几组，并行拉取，这样的话就把一次性的聚合计算操作给分解成多次聚合计算操作，最后再把多次聚合计算操作的结果汇总在一起，类似于 MapReduce 的思路。经过我们的实际验证，通过这种方法可以有效地降级关注人数上千用户拉取 Feed 的耗时，长尾请求的数量也大大减少了。
存储
UID range 作为分片
UID hash 作为分片
关系的存储
(1) 最简单的只需要两张表就够了：
用户信息表：
| user_id | user_info | ...
用户关系表，表示，follower_user 关注了 followee_user：
| id | follower_user_id | followee_user_id |
查看 user_a 粉丝多少人：
SELECT COUNT(*) FROM table_relation WHERE followee_user = `user_a`;
查看 user_a 关注了多少人：
SELECT COUNT(*) FROM table_relation WHERE follower_user = `user_a`;
(2) 不过随着用户增长，比如达到1亿，那么平均一对用户关系可能就会有100条关系，那么将会扩展到百亿级别。所以必须水平拆分。用户表好选取拆分的键，就是 user_id。不过关系表，根据 follower_user_id 拆分，那么查询这个人关注了多少人好查询，但是查询某个人有多少粉丝，就需要去所有分片上查询汇总了，相反按照 followee_user_id 拆分，那么这个人查询关注了多少人，就不好查询了。也就是总有一半的场景查询效率低下。
为了应对上面困难，我们可以垂直拆分，一个关系表拆分为 follower 和 followee 两张表，然后再对这两张表进行水平拆分，问题就迎刃而解了。
不过这样带来的问题是，如果新增了关注关系，需要使用事务来保证两张表都插入成功，比如 B 关注了 C：
-- 计算 B, C 的分片索引
START TRANSACTION;
-- table_follower 按照 followerId 拆分即可
INSERT INTO table_follower(userId, followerId) VALUES ('B', 'C');
-- table_followeeId 按照 followeeId 拆分即可
INSERT INTO table_followee(userId, followeeId) VALUES ('B', 'C');
COMMIT;
(3) 问题引入。
- 热点用户查询多少人关注了自己，需要扫描很多行。
- 热点用户关注自己的人很多，那么需要分页展示，
offset越大，那么就越来越低效。
首先 DB 层的每个用户，增加 userInfo 表，存储这个用户关注了多少人，被多少人关注，这两个信息。然后在 DB 之上引入缓存，这个用户关注了谁，被谁关注了，这些用户 ID 列表可以放入缓存中。
帖子的存储
一级索引 postId，二级索引：userId + posttime，那么按照时间查询帖子列表，将会存在严重回表：
SELECT * FROM POST WHERE userId = ? AND posttime BETWEEN ? AND ?
那么可以将 userId 和 posttime 冗余进 postId 中，去掉二级索引，减少回表：
postId 首 6 位为 userId，每一位是 0~9/A~Z 这 36 个字符中的某一个，6 位可以表示 21 亿不同的用户。后续时间戳可以精确到秒。单个用户每秒发的帖子不超过 seq 表达的最大值。其中 timeCompress 可以设计为：帖子发布的时间 - SNS 系统首次发布的时间的中间间隔，进行 36 进制编码。那么查询的 SQL 变成了：
SELECT * FROM post WHERE postId BETWEEN postId1 AND postId2;
-- 或者
SELECT * FROM post WHERE postId like '13A68%';
DB 中相同前缀的数据相邻存放，因此就可以用上 DB 的 range scan。
数据量大了一行，根据 postId 就可以水平切分。不过热点用户会路由到同一个分片上，传统做法是 1 写 N 读，读写分离存在数据延迟问题，98% 的数据一星期之后都不再访问。所以也可以使用缓存存储热点用户。
缓存以什么为 key ，什么为 value，最自然的是以 postId 为 key，帖子内容作为 value。但是，查询某个用户一段时间的帖子是一个常见操作，如果 <postId, content> 设计的话，那么需要 multiple-key 的查询，所以应该如何优化？
一个用户一天发帖通常不超过 10 条，平均 3 条，访问最频繁 1 周以内的帖子数很少超过 100 条，单条帖子长度有限，假设为 1KB，单个用户一周法的帖子很难超过 100KB，极端情况 1MB，远低于 Redis 单 value 的大小上限。因此设计如下：
用 userId + 时间戳(精确到星期) 作为 key，用 hash<postId, postContent> hash 类型作为 value，expire 设置为 1 星期。
这样对某个用户一段时间范围的查找变为针对该用户本周时间戳的 hscan 命令。用户发帖操作同时同步更新 DB 和缓存，DB 变更操作保证一致性。
对于热点用户存在的单点问题，可以用本地缓存解决。
其中 key 为 userId，value 是该用户近期发布的帖子。
时间线的存储
(1) push 模式
其中 postId 的格式由原来的 posterId + time + seq 改为 postId' = time + posterId + seq，我们更加侧重于查询。主键：userId + postId'。
查询 timeline 的 SQL：
SELECT postId FROM timeline WHERE userId = ? AND postId BETWEEN 'time1%' AND 'time2%';
利用前缀进行范围查找。
(2) pull 模式
传统的 pull 模式，每次刷新查询所有分片的做法效率比较低，每个用户的平均 500 个关注用户，分布在全部的 100 个(假设) DB 分片上，那么每次需要 100 次 DB 查询。而 push 模式，如果热点用户德华，那么帖子复制到所有的关注者的 timeline 中也未免太多。此处给出一种 pull/push 结合的方案：
某个用户发布了一个帖子，只同步到 100 个分片的某个表上，假设这张表叫做 post_rep，那么至少要包含三个字段，posterId、postId、postTime。如果数据库按照 timeline 所属用户进行分片，那么这个用户关注的所有用户的帖子全部落在同一个 DB 分片上，那么每次刷新 timeline 的时候，只需要一次 DB 查询。
不过这条 SQL 变得复杂了：
SELECT * FROM post_rep WHERE posterId IN (...平均 500 个 ID) and postTime BETWEEN ... AND ...;