redis 作为目前最风行的 nosql 缓存数据库,凭借其优异的性能、丰盛的数据结构已成为大部分场景下首选的缓存工具。
因为 redis 是一个纯内存的数据库,在寄存大量数据时,内存的占用将会十分可观。那么在一些场景下,通过选用适合的数据结构来存储,能够大幅缩小内存的占用,甚至于能够缩小 80%-99% 的内存占用。
利用 zipList 来代替大量的 Key-Value
先来看一下场景,在 Dsp 广告零碎、海量用户零碎常常会碰到这样的需要,要求依据用户的某个惟一标识迅速查到该用户的 id。譬如依据 mac 地址或 uuid 或手机号的 md5,去查问到该用户的 id。
特点是数据量很大、千万或亿级别,key 是比拟长的字符串,如 32 位的 md5 或者 uuid 这种。
如果不加以解决,间接以 key-value 模式进行存储,咱们能够简略测试一下,往 redis 里插入 1 千万条数据,1550000000 – 1559999999,模式就是 key(md5(1550000000))→ value(1550000000)这种。
而后用 info memory 看一下内存占用。
能够看到,这 1 千万条数据,占用了 redis 共计 1.17G 的内存。当数据量变成 1 个亿时,实测大概占用 8 个 G。
同样的一批数据,咱们换一种存储形式,先来看后果:
在咱们利用 zipList 后,内存占用为 123M,大概缩小了 85% 的空间占用,这是怎么做到的呢?咱们来从 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,替换原来的。
计划毛病:
hash 构造不反对对单个 field 的超时设置。但能够通过代码来管制删除,对于那些不须要超时的长期寄存的数据,则没有这种顾虑。
存在较小的 hash 抵触概率,对于对数据要求极其准确的场合,不适宜用这种压缩形式。
基于上述计划,我改写了 springboot 源码的 redisTemplate,提供了一个 CompressRedisTemplate 类,能够间接当成 redisTemplate 应用,它会主动将 key-value 转为 hash 进行存储,以达到上述目标。
后续,咱们会基于更极其一些的场景,如统计独立访客等,来看一下 redis 的不常见的数据结构,是如何将内存占用由 20G 升高到 5M。
欢送关注公众号【码农开花】一起学习成长
我会始终分享 Java 干货,也会分享收费的学习材料课程和面试宝典
回复:【计算机】【设计模式】【面试】有惊喜哦