摘要.
# 01 前言
redis 作为目前最流行的 nosql 缓存数据库，凭借其优异的性能、丰富的数据结构已成为大部分场景下首选的缓存工具。
由于 redis 是一个纯内存的数据库，在存放大量数据时，内存的占用将会非常可观。那么在一些场景下，通过选用合适数据结构来存储，可以大幅减少内存的占用，甚至于可以减少 80%-99% 的内存占用。
# 02 利用 zipList 来替代大量的 Key-Value
先来看一下场景，在 Dsp 广告系统、海量用户系统经常会碰到这样的需求，要求根据用户的某个唯一标识迅速查到该用户 id。譬如根据 mac 地址或 uuid 或手机号的 md5，去查询到该用户的 id。
特点是数据量很大、千万或亿级别，key 是比较长的字符串，如 32 位的 md5 或者 uuid 这种。
如果不加以处理，直接以 key-value 形式进行存储，我们可以简单测试一下，往 redis 里插入 1 千万条数据，1550000000 - 1559999999，形式就是 key（md5（1550000000））→ value(1550000000) 这种。
然后在 Redis 内用命令 info memory 看一下内存占用。
可以看到，这 1 千万条数据，占用了 redis 共计 1.17G 的内存。当数据量变成 1 个亿时，实测大约占用 8 个 G。
同样的一批数据，我们换一种存储方式，先来看结果：
在我们利用 zipList 后，内存占用为 123M，大约减少了 85% 的空间占用，这是怎么做到的呢？
# 03 redis 的底层存储来剖析
（1）redis 数据结构和编码方式
（2）redis 如何存储字符串
string 是 redis 里最常用的数据结构，redis 的默认字符串和 C 语言的字符串不同，它是自己构建了一种名为 “简单动态字符串 SDS” 的抽象类型。
具体到 string 的底层存储，redis 共用了三种方式，分别是 int、embstr 和 raw。
譬如 set k1 abc 和 set k2 123 就会分别用 embstr、int。当 value 的长度大于 44（或 39，不同版本不一样）个字节时，会采用 raw。
int 是一种定长的结构，占 8 个字节（注意，相当于 java 里的 long），只能用来存储长整形。
embstr 是动态扩容的，每次扩容 1 倍，超过 1M 时，每次只扩容 1M。
raw 用来存储大于 44 个字节的字符串。
具体到我们的案例中，key 是 32 个字节的字符串（embstr），value 是一个长整形（int），所以如果能将 32 位的 md5 变成 int，那么在 key 的存储上就可以直接减少 3/4 的内存占用。
这是第一个优化点。
（3）redis 如何存储 Hash
从 1.1 的图上我们可以看到 Hash 数据结构，在编码方式上有两种，1 是 hashTable，2 是 zipList。
hashTable 大家很熟悉，和 java 里的 hashMap 很像，都是数组 + 链表的方式。java 里 hashmap 为了减少 hash 冲突，设置了负载因子为 0.75。同样，redis 的 hash 也有类似的扩容负载因子。细节不提，只需要留个印象，用 hashTable 编码的话，则会花费至少大于存储的数据 25% 的空间才能存下这些数据。它大概长这样：
zipList，压缩链表，它大概长这样：
可以看到，zipList 最大的特点就是，它根本不是 hash 结构，而是一个比较长的字符串，将 key-value 都按顺序依次摆放到一个长长的字符串里来存储。如果要找某个 key 的话，就直接遍历整个长字符串就好了。
所以很明显，zipList 要比 hashTable 占用少的多的空间。但是会耗费更多的 cpu 来进行查询。
那么何时用 hashTable、zipList 呢？在 redis.conf 文件中可以找到：
就是当这个 hash 结构的内层 field-value 数量不超过 512，并且 value 的字节数不超过 64 时，就使用 zipList。
通过实测，value 数量在 512 时，性能和单纯的 hashTable 几乎无差别，在 value 数量不超过 1024 时，性能仅有极小的降低，很多时候可以忽略掉。
而内存占用，zipList 可比 hashTable 降低了极多。
这是第二个优化点。
（4）用 zipList 来代替 key-value
通过上面的知识，我们得出了两个结论。用 int 作为 key，会比 string 省很多空间。用 hash 中的 zipList，会比 key-value 省巨大的空间。
那么我们就来改造一下当初的 1 千万个 key-value。
第一步：
我们要将 1 千万个键值对，放到 N 个 bucket 中，每个 bucket 是一个 redis 的 hash 数据结构，并且要让每个 bucket 内不超过默认的 512 个元素（如果改了配置文件，如 1024，则不能超过修改后的值），以避免 hash 将编码方式从 zipList 变成 hashTable。
1 千万 / 512 = 19531。由于将来要将所有的 key 进行哈希算法，来尽量均摊到所有 bucket 里，但由于哈希函数的不确定性，未必能完全平均分配。所以我们要预留一些空间，譬如我分配 25000 个 bucket，或 30000 个 bucket。
第二步：
选用哈希算法，决定将 key 放到哪个 bucket。这里我们采用高效而且均衡的知名算法 crc32，该哈希算法可以将一个字符串变成一个 long 型的数字，通过获取这个 md5 型的 key 的 crc32 后，再对 bucket 的数量进行取余，就可以确定该 key 要被放到哪个 bucket 中。
第三步：
通过第二步，我们确定了 key 即将存放在的 redis 里 hash 结构的外层 key，对于内层 field，我们就选用另一个 hash 算法，以避免两个完全不同的值，通过 crc32（key） % COUNT 后，发生 field 再次相同，产生 hash 冲突导致值被覆盖的情况。内层 field 我们选用 bkdr 哈希算法（或直接选用 Java 的 hashCode），该算法也会得到一个 long 整形的数字。value 的存储保持不变。
第四步：
装入数据。原来的数据结构是 key-value，0eac261f1c2d21e0bfdbd567bb270a68 → 1550000000。
现在的数据结构是 hash，key 为 14523，field 是 1927144074，value 是 1550000000。
通过实测，将 1 千万数据存入 25000 个 bucket 后，整体 hash 比较均衡，每个 bucket 下大概有 300 多个 field-value 键值对。理论上只要不发生两次 hash 算法后，均产生相同的值，那么就可以完全依靠 key-field 来找到原始的 value。这一点可以通过计算总量进行确认。实际上，在 bucket 数量较多时，且每个 bucket 下，value 数量不是很多，发生连续碰撞概率极低，实测在存储 50 亿个手机号情况下，未发生明显碰撞。
测试查询速度：
在存储完这 1 千万个数据后，我们进行了查询测试，采用 key-value 型和 hash 型，分别查询 100 万条数据，看一下对查询速度的影响。
key-value 耗时：10653、10790、11318、9900、11270、11029 毫秒
hash-field 耗时：12042、11349、11126、11355、11168 毫秒。
可以看到，整体上采用 hash 存储后，查询 100 万条耗时，也仅仅增加了 500 毫秒不到。对性能的影响极其微小。但内存占用从 1.1G 变成了 120M，带来了接近 90% 的内存节省。
# 总结
大量的 key-value，占用过多的 key，redis 里为了处理 hash 碰撞，需要占用更多的空间来存储这些 key-value 数据。
如果 key 的长短不一，譬如有些 40 位，有些 10 位，因为对齐问题，那么将产生巨大的内存碎片，占用空间情况更为严重。所以，保持 key 的长度统一（譬如统一采用 int 型，定长 8 个字节），也会对内存占用有帮助。
string 型的 md5，占用了 32 个字节。而通过 hash 算法后，将 32 降到了 8 个字节的长整形，这显著降低了 key 的空间占用。
zipList 比 hashTable 明显减少了内存占用，它的存储非常紧凑，对查询效率影响也很小。所以应善于利用 zipList，避免在 hash 结构里，存放超过 512 个 field-value 元素。
如果 value 是字符串、对象等，应尽量采用 byte[]来存储，同样可以大幅降低内存占用。譬如可以选用 google 的 Snappy 压缩算法，将字符串转为 byte[]，非常高效，压缩率也很高。
为减少 redis 对字符串的预分配和扩容（每次翻倍），造成内存碎片，不应该使用 append，setrange 等。而是直接用 set，替换原来的。
作者：锐玩道
原文链接：https://juejin.im/post/5df98a0d6fb9a016091df481 https://zhuanlan.zhihu.com/p/98033960 https://zhuanlan.zhihu.com/p/98033960