关于重构:减少80存储风控名单服务重构剖析

小小的 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 构造只会波及到 string 和 hash，笔者仅剖析这两种，其它的读者们感兴趣能够自行搜寻。

string 是 redis 中最罕用的存储构造，redis 实现是是基于 C 语言，此处的字符串并不是间接应用 c 中的字符串，而是本人实现了一套“SDS”（简略动静字符串）。

struct sdshdr(
    // 记录 buf 数组中已应用字节的数量
    // 等于 SDS 保留字符串的长度
    int len;
    // 记录 buf 数组中未应用字节的数量
    int free;
    // 字节数组，用于保留字符串
    char buf[];}

redis 的底层存储会应用三种形式来存储数据：**int**、**raw**和**embstr**

存储值：整形，且能够用 long 类型来示意的。举例如下：

redis> OBJECT ENCODING number
"int"

存储值：字符串值，且字符串长度 > 39 字节的。举例如下：

redis> SET story "Long, long, long ago there lived a king ..."
OK

redis> STRLEN story
(integer) 43

redis> OBJECT ENCODING story
"raw"

存储值：字符串值，且字符串长度 <= 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 个字节的字符串。

哈希对象的编码能够是 ziplist 或者 hashtable。

ziplist 编码的哈希对象应用压缩列表作为底层实现，每当有新的键值对要退出到哈希对象时，程序会先将保留了键的压缩列表节点推入到压缩列表表尾，而后再将保留了值的压缩列表节点推入到压缩列表表尾，因而：

保留了同一键值对的两个节点总是紧挨在一起，保留键的节点在前，保留值的节点在后；
先增加到哈希对象中的键值对会被放在压缩列表的表头方向，而起初增加到哈希对象中的键值对会被放在压缩列表的表尾方向。

举例如下：

redis> HSET profile name "Tom"
(integer) 1

redis> HSET profile age 25
(integer) 1

redis> HSET profile career "Programmer"
(integer) 1

哈希对象中的每个键值对都应用一个字典键值对来保留：

字典的每个键都是一个字符串对象，对象中保留了键值对的键；
字典的每个值都是一个字符串对象，对象中保留了键值对的值。

如果上述例子的底层存储形式是 hashtable，那么对象构造会如图所示：

总结如下（redis version < 3.2，新版本的优化了应用 quicklist，更新的版本应用 listpack，情理一样，此处以 ziplist 总结）:

值	编码	占用内存

留神：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 算法，平均、离散的摊派到这些个 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/ >

关于重构:减少80存储风控名单服务重构剖析

引言

背景

Redis 是如何存储数据的？

字符串存储

int 类型

raw 类型

embstr 类型

Hash 存储

ziplist 类型

hashtable 类型

名单服务革新

分桶

hash 算法抉择

新老数据比对

字符串直插

老名单服务数据结构

新名单服务数据结构

总结

往期精彩