计数服务设计

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 5.6k 阅读时长 ≈ 5 分钟

看了微博在2012年 微博计数器的设计 后，现在在想假设自己要设计一个有点赞数、收藏数、评论数、转发数 的计数系统，会怎么做？

微博计数器的设计 文章链接 https://blog.cydu.net/weidesign/2012/09/09/weibo-counter-service-design-2/


(1) 背景

以抖音、微博、微信 为例，推荐的视频、微博、朋友圈 会有点赞数、收藏数、评论数、转发数，假如让你设计，你会怎么做？

微博的比较经典，这里以微博为例，原理都一样。
考虑因素如下：
1、预估用户 14亿
2、预估活跃用户数 0.01 ~ 6亿。
3、假设每个用户每天发13个微博， 每天大概有 0.01亿 ~ 18亿条微博。 每条微博上都有点赞数、收藏数、评论数、转发数。
35年大概有 0.013653 ~ 183653亿条微博，也就是 10.95亿 ~ 1 9710亿条微博。



(2) 信息Id设计

如果只考虑用户信息的ID查询，只要保证动态Id唯一即可；考虑到要按照用户维度去展示用户的信息列表，信息ID里最好包含用户ID，这样方便查询某个用户发布的所有的信息(动态)。
类似于电商场景查询某个用户的所有订单。

信息有个唯一表示，用rec_id表示
根据推荐信息唯一标识rec_id获取点赞数、收藏数、评论数、转发数 是一个简单查询。

(2.1) 用数字表示信息ID

int类型占用4字节，32位，最多可以表示 2^32个数字，考虑上符号，以及0，正数最多有 2^31-1 = 21 4748 3647 个，大概21亿多。

long类型占用8字节，64位，最多可以表示 2^64个数字，考虑到id都是正数，而且一般不用0，所以最多有 2^63-1 = 922 3372 0368 5477 5807 个，大概922亿亿个。

可以用8字节的Long类型表示信息ID(msg_id)，msg_id的设计可以参考雪花算法的思想， 64位可以按照 符号位(1位)、城市(6位)、用户(8-10位)、时间戳()、随机字符()等来设计。


(3) 计数器设计方案

(3.1) 数据库方案

在刚开始阶段，用户较少并且用户发布的信息/动态较少时，可以使用数据库来存储。

CREATE TABLE msg_count (
    `id` bigint(11) unsigned NOT NULL AUTO_INCREMENT COMMENT '主键id',
    `create_time` datetime NOT NULL DEFAULT CURRENT_TIMESTAMP COMMENT '创建时间',
    `update_time` datetime NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP COMMENT '修改时间',
    `user_id` bigint(11) NOT NULL COMMENT '用户id',    
    `msg_id` bigint(11) NOT NULL COMMENT '信息id',
    `like_count` int(11) NOT NULL DEFAULT '0' COMMENT '点赞数',
    `favor_count` int(11) NOT NULL DEFAULT '0' COMMENT '收藏数',
    `repost_count` int(11) NOT NULL DEFAULT '0' COMMENT '转发数',
    `comment_count` int(11) NOT NULL DEFAULT '0' COMMENT '评论数',
    PRIMARY KEY (`id`),
    UNIQUE KEY `uq_idx_msg_id` (`msg_id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COMMENT='信息(动态)计数表';

(3.1.1) 实现业务功能

查询点赞数 UPDATE msg_count SET like_num = like_num + 1 WHERE msg_id = xxx ;
更新点赞数 SELECT msg_count WHERE msg_id = xxx ;

(3.1.2) 存储

按照上面的表设计，一条计数数据占用64字节，MySQL一页可以存储 16K/64=256条数据
MySQL一页可以存储 16K / (主键ID 8字节 + 指针 6字节) = 1170 条数据

假设MySQL查一条数据需要二次IO，读取二页，那么MySQL单表 可以存储 1170 * 256 = 29 9520 条数据。
假设MySQL查一条数据需要三次IO，读取三页，那么MySQL单表 可以存储 1170 * 1170 * 256 = 3 5043 8400 条数据。
从数据存储角度看，MySQL单表存储上亿条数据没问题。

假设一个表存一亿条数据，需要一千多个表就可以存储千亿条数据。
从维护角度看，可以让单表数据量500万，这样单表 数据备份，改表等时间会短一点。

未来扩缩容

按信息ID(msg_id)取模，把数据拆分到N个表(N是2的幂次方)。
如果要扩容，把N个表拆成 N * 2^x，迁移数据时只需要把 1个表拆数据到 2^x个表即可。

(3.1.3) 性能

从查询角度看，百万的查询量，分摊到一千个每个表，每个表查询QPS大概是100左右，从单表查询QPS来看是没什么问题的，但是从 CPU、内存、IO角度看是有资源的问题
每秒百万请求量，那么MySQL需要把数据读取到内存，会有页数据对应的内存淘汰，假设有一半的数据在内存，msg_count表单条计数数据64字节 * 每秒100 0000访问量 / 2 = 6400 0000字节，也就是MySQL至少需要64G内存，

从业务角度看，也是会有问题的，单表平均QPS大概100，但实际上往往一个热点微博可能导致所在表的QPS上万。

(3.1.4) 存储数据量过大怎么办-分库分表

对于一亿甚至几亿以下的数据规模来说，拆表能够解决很多问题。

类似于电商交易场景的订单分库分表，按照uid和order_id分库分表
技术系统可以按照uid或者msg_id分库分表

(3.1.4.1) 按照uid分库分表

  1. 写入时一个用户的所有动态(微博)在一个表里。
  2. 用户在查看自己的动态(微博)列表时，可以批量获取点赞数，评论数、转发数。
  3. 如果用户是一个热点用户，发的动态(微博)比较多，查询压力会在同一个表，这张表可能会成为热点表。
    可以通过mq或日志计数，如果计数结果>设置阈值，把热点动态的计数放到缓存里。
    不过如果一个动态(微博)是热点，可能mq计数还没把数据放到缓存里数据库就挂了。
  4. 如果直接根据msg_id来查，会找不到对应的库表，需要根据uid和msg_id来查。 或者msg_id里可以记录uid的一些信息。

(3.1.4.2) 按照msg_id分库分表

  1. 写入时一个用户的所有动态(微博)在多个表里。
  2. 用户在查看自己的动态(微博)列表时，获取点赞数，评论数、转发数 需要进行多次查询。
  3. 如果用户是一个热点用户，发的动态(微博)比较多，

(3.1.4.3) 按照create_time分库分表

这个一般是数据归档使用
如果按照 create_time 分库分表，在C端高并发场景，同一天的热点数据在同一个表，有热点时单表肯定扛不住。


(3.1.5) 访问量太大怎么办?

使用缓存+数据库，先查缓存，缓存查不到再查数据库。

优点
只需要改少量代码。
方案成熟, 数据复制，管理，修复方案都很成熟。

问题：
1、空数据也得Cache(有一半以上的微博是没有转发也没有评论的，但是依然有大量的访问会查询数据库);
2、Cache频繁失效(由于计数更新非常快，所以经常需要失效Cache再重新缓存，还会导致数据不一致);

更好的硬件解决。 上FusionIO + HandleSocket + 大内存 优化。

总的来说，MySQL分库分表 + Cache加速的方案 对于数据规模和访问量不是特别巨大的情况下，是非常不错的解决方案。


(3.2) Redis缓存方案

Redis作为一个简单的内存数据库，提供了多种数据类型，可以使用string类型的 incr 来计数。
具体命令参考 https://redis.io/commands/incr/

简单的来估算一下数据存储量，按照Redis 6.0的实现，在64位系统，指针为8字节来估算

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

key value 会存储在 dictEntry里，详细的结构: redisServer -> db0 -> dict -> ht[0] -> dictht -> dictEntry

redis索引模型

从后往前

  1. 存储key为8字节数字(64位 8字节 long类型/int64，Eg:9223372036854775807 )，但通过 sdsdup 以字符串的形式存储，至少需要 8(struct sdshdr) + 19(数字转字符串后长度是19) + 1(结束字符) = 28字节;
  2. 存储val为4字节数字(32位 4字节 int类型/int32，Eg: 2147483647 )，通过 createStringObjectFromLongLong 创建一个robj，由于val > REDIS_SHARED_INTEGERS (默认1000), 所以存储时用的 encoding为 REDIS_ENCODING_INT，占用8字节，加上redisObject，一共占用16字节 (这里redis有个优化，把redisObject的指针ptr直接存储int类型，节省了一个指针的开销，所以不是占用 16+8字节 而是16字节)
  3. 为了存储到Redis的dict里，需要一个dictEntry对象，占用 3*8字节=24字节
  4. 放到 db->dict->ht[0]->table 中存储dictEntry的指针，需要8个字节;
  5. 存储一个64位key，32位value的计数，Redis也至少需要耗费: 16 + 28 + 24 + 8 = 76 字节。
  6. 1000亿个key全内存的话，就至少需要 ( 100 * 1000 * 1000 * 1000 ) * 76 = 100G * 76 = 7.6TB 的内存

从技术角度讲
只算value，有效的业务数据其实是 1000亿*32位 = 100G * 4字节 = 400GB，需要7.6TB来存储，内存的有效利用率约为: 400GB/7600GB = 5.3%。
key和value全算上，有效业务数据是 1000亿*(64位+32位) = 100G * 12字节 = 1200GB，需要7.6TB存储，内存有效利用率约为：1200GB/7600GB = 15.7%


(3.3) 计数服务-优化Redis源码

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

(3.3.1) 优化Redis结构体

方案二中Redis对内存使用的分析，我们发现是非常”奢侈”的, 大量的重复存储着指针和预留的字段，而且造成大量的碎片内存的使用，当然Redis主要是出于通用性的考虑。
针对这种情况，设计了一个更轻量更简单的数据结构，能更好的利用内存，核心思路:

改动点

  1. 定制化数据结构。
  2. hash冲突时把链地址法优化为开放寻址法 。
/* 
 * 哈希表节点/Entry实体 
 */
typedef struct updateDictEntry {
    int64_t msg_id;  // 信息ID 对应微博ID  
    int repost_num;  // 转发数
    int comment_num; // 评论数
} dictEntry;

优化前后对比

优化前，存储一条微博评论数 消耗 76 字节
优化前内存占用

优化后，存储一条微博转发数+评论数 消耗 16字节
优化后内存占用

  1. Value的长度短于指针长度
  2. 开放寻址Hash表(双重散列)
  3. 以节省指针存储

优化后一条数据占用内存
业务数据 有效内存利用率为

(3.3.1) 业务维度优化

  1. 大量微博(一半以上)没有转发或没有评论，甚至是都没有
    针对这种情况的优化:

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

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

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

针对这种情况的优化:

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

(3.4) KV存储

(4) 系统安全问题

(4.1) 系统怎么应对爬虫？

网关+风控处理

参考资料

[1] [WeiDesign]微博计数器的设计(上)
[2] [WeiDesign]微博计数器的设计(下)
[3] [WeiDesign]微博计数器的设计 velocity
[4] Velocity分享_微架构设计之微博计数器服务_杜传赢_20121205.pdf
[5] 微博计数:从关系服务到访问计数,Redis持续优化支撑万亿级访问（含PPT）
[6] 微博每日数十亿级业务下的计数器如何扩展Redis？
[7] 高并发系统设计40问 - 37计数系统设计（一）：面对海量数据的计数器要如何做？
[8] Storing hundreds of millions of simple key-value pairs in Redis