引言
小小的 Redis 大大的不简单，本文将结合风控名单服务在使用 Redis 存储数据时的数据结构设计及优化，并详细分析 redis 底层实现对数据结构选型的重要性。
背景
先来交代下使用场景，在风控场景下，名单服务每时每刻都需要承受海量数据查询。
名单检索内容涉及维度非常广：用户业务标识（UID）、手机号、身份证号、设备号、IMEI（International Mobile Equipment Identity, 国际移动设备识别码）、Wifi Mac、IP 等等。用户的一次业务请求，在风控的中会扩散到多个名单维度，同时还需要在 RT（Response-time） 上满足业务场景诉求。
这就导致名单服务的构建需要承受住如下挑战:
- 海量数据存储：维度多，存储内容尚可（是否命中），按照 X 个用户，Y 个维度，Z 个业务线（隔离），量级非常大
- 大流量、高并发：业务场景下任何存在风险敞口的点都需要评估过风控，每天决策峰值 TPS 过万
- 极低耗时：留给名单服务的时间不多了，如果整体业务系统给风控决策的耗时是 200 ms，名单服务必须要在 30 ~ 50 ms 就得得到结果，否则将极大影响后续规则引擎的运算执行进度
如上系统要求其实在大数据系统架构下都是适用的，只是名单服务要的更极致而已。
在上一篇 《风控核心子域——名单服务构建及挑战》 文章中已经介绍了名单服务设计，选用了 Redis 作为存储，目前也只能是 Redis 能满足名单服务场景的高性能诉求。同时也介绍了选择用 Redis 中遇到的数据异常及高可用设计架构，忘了或者感兴趣的朋友可以再回顾一遍。
名单数据的存储结构选用的是 Hash 存储，结构如下：
在此我提出几个疑问（不知道读者看完后是否也有~）：
- 为何使用 Hash? 使用
set key-value结构可以么？ - 过期时间如何维护？set key-val 可以直接基于
expire设置， hash 结构内过期的数据是如何删除的？ - 当前设计架构，对 Redis 的内存消耗大概在什么水位？可预见的未来能够满足业务的增长需求么？
如果你也有这些疑问，那么本篇文章将为你解惑，希望能有收获。
Redis 是如何存储数据的？
工欲善其事必先利其器，我们先将常用的 Redis 结构底层实现摸透，才能在使用上游刃有余，由于本文在用的 redis 结构只会涉及到 string 和 hash，笔者仅分析这两种，其它的读者们感兴趣可以自行搜索。
字符串存储
string 是 redis 中最常用的存储结构，redis 实现是是基于 C 语言，此处的字符串并不是直接使用 c 中的字符串，而是自己实现了一套 “SDS”（简单动态字符串）。
struct sdshdr(
//记录 buf 数组中已使用字节的数量
//等于 SDS 保存字符串的长度
int len;
//记录 buf 数组中未使用字节的数量
int free;
//字节数组，用于保存字符串
char buf[];
}redis 的底层存储会使用三种方式来存储数据：**int**、**raw**和**embstr**
int 类型
存储值：整形，且可以用 long 类型来表示的。举例如下：
redis> OBJECT ENCODING number
"int"
raw 类型
存储值：字符串值，且字符串长度 > 39 字节的。举例如下：
redis> SET story "Long, long, long ago there lived a king ..."
OK
redis> STRLEN story
(integer) 43
redis> OBJECT ENCODING story
"raw"
embstr 类型
存储值：字符串值，且字符串长度 <= 39 字节的。
embstr 编码的字符串对象在执行命令时， 产生的效果和 raw 编码的字符串对象执行命令时产生的效果是相同的， 但使用 embstr 编码的字符串对象来保存短字符串值有以下好处：
- embstr 编码将创建字符串对象所需的内存分配次数从 raw 编码的两次降低为一次。
- 释放 embstr 编码的字符串对象只需要调用一次内存释放函数， 而释放 raw 编码的字符串对象需要调用两次内存释放函数。
- 因为 embstr 编码的字符串对象的所有数据都保存在一块连续的内存里面， 所以这种编码的字符串对象比起 raw 编码的字符串对象能够更好地利用缓存带来的优势。
举例如下：
redis> SET msg "hello"
OK
redis> OBJECT ENCODING msg
"embstr"
总结如下（redis version > 3.2）：
| 值 | 编码 | 占用内存 |
|---|---|---|
| 可以用 long 类型保存的整数。 | int | 定长 8 字节 |
| 可以用 long double 类型保存的浮点数。 | embstr 或者 raw | 动态扩容的，每次扩容 1 倍，超过 1M 时，每次只扩容 1M。 |
| 字符串值， 或者因为长度太大而没办法用 long 类型表示的整数， 又或者因为长度太大而没办法用 long double 类型表示的浮点数。 | embstr 或者 raw | 用来存储大于 44 个字节的字符串。 |
Hash 存储
哈希对象的编码可以是 ziplist 或者 hashtable 。
ziplist 类型
ziplist 编码的哈希对象使用压缩列表作为底层实现， 每当有新的键值对要加入到哈希对象时， 程序会先将保存了键的压缩列表节点推入到压缩列表表尾， 然后再将保存了值的压缩列表节点推入到压缩列表表尾， 因此：
- 保存了同一键值对的两个节点总是紧挨在一起， 保存键的节点在前， 保存值的节点在后；
- 先添加到哈希对象中的键值对会被放在压缩列表的表头方向， 而后来添加到哈希对象中的键值对会被放在压缩列表的表尾方向。
举例如下：
redis> HSET profile name "Tom"
(integer) 1
redis> HSET profile age 25
(integer) 1
redis> HSET profile career "Programmer"
(integer) 1
hashtable 类型
哈希对象中的每个键值对都使用一个字典键值对来保存：
- 字典的每个键都是一个字符串对象， 对象中保存了键值对的键；
- 字典的每个值都是一个字符串对象， 对象中保存了键值对的值。
如果上述例子的底层存储方式是 hashtable，那么对象结构会如图所示：
总结如下（redis version < 3.2，新版本的优化了使用 quicklist，更新的版本使用 listpack，道理一样，此处以 ziplist 总结）:
| 值 | 编码 | 占用内存 |
|---|
| 哈希对象保存的所有键值对的键和值的字符串长度都小于 64 字节； 哈希对象保存的键值对数量小于 512 个； | ziplist | 本质是一个字符串；寻值需要遍历字符串；缺点是耗费更多的 cpu 来查询（如果值很少，可以忽略不计） | | 不满足上述 ziplist 条件的值 | hashtable | 类似 java HashMap 实现；空间换时间；需要多花费本身存储的 25%内存 |
注意：ziplist 两个条件的上限值是可以修改的， 具体请看配置文件 redis.conf 中关于 hash-max-ziplist-value 选项和 hash-max-ziplist-entries 选项的说明。
两种数据结构，按照解释，当 value 数量控制在 512 时，性能和单纯的使用 hashtable 基本一致，value 数量在不超过 1024 时，性能只有极小的降低，然而内存的占用 ziplist 比 hashtable 降低了 80% 左右。
名单服务改造
通过如上的分析，我们得出两个重要结论：
- key 或者 val 使用编码是 int 类型时（8 个字节），要比编码使用 string 即 raw|embstr 要省很多空间
- 使用 ziplist 存储，要比使用 key-value 节省巨大的空间
分析一下名单服务支撑的业务数据量，假设有 5 亿个用户（可能非活跃，就假设全量），每个用户衍生出 10 个名单维度（手机号、身份证、设备等等），每个维度再衍生出 10 个沙盒隔离环境（业务线、渠道等等），那么总的数据量级在： 500 亿左右。
分桶
500 亿个值如果都存放在 hash 结构中，需要分散到不同的桶（bucket）中，每个桶最大不超过 512 个（这个可以自行配置，最好不超 1024 个，不然损失了查询性能，配置过大后需要实际压测检验）。从而避免 hash 的编码从 ziplist 切换至 hashtable。
bucket 数量 = 500 亿 / 512 = 97,656,250，即需要这么多桶来承载，如果是 1024 个，则桶的量可缩小一倍，但是意义不大。
hash 算法选择
需要将这么多维度的数据通过 hash 算法，均匀、离散的分摊到这些个 bucket 内，必须选择业内比较有名且碰撞率不高的优秀算法。可以选择 crc32(key) % bucketNum，得到该存在哪个 bucket 内，此时再使用 hash 算法（需要考虑前后两次 hash 的碰撞率，建议选择与分桶算法不一致）或者直接使用 Java 对象的 hashcode 作为 field 即可，整体效果如图：
新老数据比对
我将用三种数据作比对，分别是：字符串直插、老的名单服务数据、新的数据结构
字符串直插
key = deviceHash-${名单类型}-${设备指纹}-${沙盒隔离标识}
val = 过期时间戳
模拟在同一个设备指纹下有 10 个业务域隔离，即需要插入 10 条数据
## 插入 10 条数据，此处省略剩余 9 条
127.0.0.1:6379> set deviceHash-3-a313633418103bf58fe65b56bef28884e0ada768d20c94d69fc49ad618d92724-100000 1678157018608
OK
## 单条占用内存大小（字节）
127.0.0.1:6379> memory usage deviceHash-3-a313633418103bf58fe65b56bef28884e0ada768d20c94d69fc49ad618d92724-100000
(integer) 136
## 编码类型
127.0.0.1:6379> debug object deviceHash-3-a313633418103bf58fe65b56bef28884e0ada768d20c94d69fc49ad618d92724-100000
Value at:0xffffb9a7c0c0 refcount:1 encoding:int serializedlength:14 lru:439622 lru_seconds_idle:745整体占用内存（字节） = 136 * 10 = 1360
老名单服务数据结构
key = deviceHash-${名单类型}-${设备指纹}
field = ${沙盒隔离标识}
val = 过期时间戳
模拟在同一个设备指纹下有 10 个业务域隔离，即需要插入 10 条数据
## 插入 10 条数据，此处省略剩余 9 条
127.0.0.1:6379> hset deviceHash-3-a313633418103bf58fe65b56bef28884e0ada768d20c94d69fc49ad618d92724 100000 1678157018608
(integer) 1
## 单条占用内存大小（字节）
memory usage deviceHash-3-a313633418103bf58fe65b56bef28884e0ada768d20c94d69fc49ad618d92724
(integer) 296
## 编码类型
127.0.0.1:6379> debug object deviceHash-3-a313633418103bf58fe65b56bef28884e0ada768d20c94d69fc49ad618d92724
Value at:0xffffb9a7c0d0 refcount:1 encoding:ziplist serializedlength:75 lru:439622 lru_seconds_idle:1168整体占用内存（字节） = 296 注：此处 hash 的 field 和 val 都为超 64 字节，满足 ziplist 要求。
新名单服务数据结构
key = bucket_${取余}
field = hash_long_method(deviceHash-${名单类型}-${设备指纹}-${沙盒隔离标识})
val = 过期时间戳
模拟在同一个设备指纹下有 10 个业务域隔离，即需要插入 10 条数据
## 插入 10 条数据，此处省略剩余 9 条
127.0.0.1:6379> hset bucket_11 206652428 1678157018608
(integer) 1
## 单条占用内存大小（字节）
127.0.0.1:6379> memory usage bucket_11
(integer) 248
## 编码类型
127.0.0.1:6379> debug object bucket_11
Value at:0xffffb9a7c050 refcount:1 encoding:ziplist serializedlength:76 lru:439622 lru_seconds_idle:1214整体占用内存（字节） = 248（此处实际节省的是原始字符串作直接作为 key 所带来的消耗）
可见，如上按照 500 亿数据计算的话，去除 10 个沙盒隔离维度，则老方案需要 50 亿个 hash 结构来存储，新方案只需要不到 1 亿个 结构来存储，节省的内存还是很客观的。
由于名单服务比较特殊，field 和 val 都不大，假设业务上存储的值超 64 字节或者 filed 个数超 512，转变为 hashtable 的话，则新方案节省的就是巨量的内存。
总结
新的数据设计结构规避了如下几个问题：
- 使用 Hash 是有代价的，底层如果是 hashtable 实现的话，会多用 25% 内存空间，毕竟空间换时间嘛
- key 最好不用原始的字符串，更有胜者，长短不一，导致内存碎片，占用空间情况更加严重
- 部分开发者喜欢原始字符串加 MD5 后得到 32 位字符，解决了内存碎片问题，但是相比于编码是 int 类型，emstr 更占用空间，毕竟前者只需固定 8 个字节
- 如上
value我们只存储了时间戳，即是 long 类型整数，没有什么好优化的，假设业务中需要存储的是 字符串，序列化 JSON 串等，应采用高效的 byte[] 压缩算法，如Protocol Buffers等等
同时，在实施过程中也要注意一些问题：
- hash 算法终归是有碰撞率的，在一些不容许错误的（比如金融、风控）等场景下，需要一定的取舍
- 才有 hash 结构存储数据，失去了 redis 天然的支持 expire 功能，需要自主维护数据的生命周期，比如在值中追加生命时间戳，整体的高可用也需要保证
往期精彩
欢迎关注公众号：咕咕鸡技术专栏 个人技术博客：https://jifuwei.github.io/
