redis数据结构-存亿级数据需要耗费多少内存

发表于 2022-01-22 更新于 2023-02-05 分类于 redis 阅读次数： Waline：本文字数： 3.8k 阅读时长 ≈ 3 分钟

　　同事在实现一个弹窗需求时遇到一个问题，找大家讨论方案，产品的需求是小程序首页各种弹窗太多了，用户一进来需要点多个弹窗，要求服务端限制在首页一个用户一天只能弹一次。当时考虑了数据库和缓存，从实现简易程度、扩展性、速度综合考虑最后选了redis缓存。

Redis数据类型

五种数据形式的底层实现
string：简单动态字符串
list：双向链表，压缩列表
hash：压缩列表，哈希表
Sorted Set：压缩列表，跳表
set：哈希表，整数数组

(3) redis常用数据类型/对象

上面介绍了 6 种底层数据结构，Redis 并没有直接使用这些数据结构来实现键值数据库，而是基于这些数据结构创建了一个对象系统，这个系统包含字符串对象、列表对象、哈希对象、集合对象和有序集合这五种类型的对象，每个对象都使用到了至少一种前边讲的底层数据结构。

redis常用的数据对象有以下几种

/* The actual Redis Object */
#define OBJ_STRING 0    /* String object. */
#define OBJ_LIST 1      /* List object. */
#define OBJ_SET 2       /* Set object. */
#define OBJ_ZSET 3      /* Sorted set object. */
#define OBJ_HASH 4      /* Hash object. */

#define OBJ_MODULE 5    /* Module object. */
#define OBJ_STREAM 6    /* Stream object. */

(3.1) 字符串对象 OBJ_STRING

(3.2) 列表对象 OBJ_LIST

(3.3) 集合对象 OBJ_SET

(3.4) 有序集合对象 OBJ_ZSET

Sorted Set内部实现数据结构是跳表和压缩列表。
跳表主要服务范围操作，提供O(logN)的复杂度。
zset有个ZSCORE的操作，用于返回单个集合member的分数，它的操作复杂度是O(1)，这就是收益于你这看到的hash table。这个hash table保存了集合元素和相应的分数，所以做ZSCORE操作时，直接查这个表就可以，复杂度就降为O(1)了。

(3.5) 哈希对象 OBJ_HASH

(2) redis常用数据结构

/* Objects encoding. Some kind of objects like Strings and Hashes can be
 * internally represented in multiple ways. The 'encoding' field of the object
 * is set to one of this fields for this object. */
#define OBJ_ENCODING_RAW 0     /* Raw representation */
#define OBJ_ENCODING_INT 1     /* Encoded as integer */
#define OBJ_ENCODING_HT 2      /* Encoded as hash table */
#define OBJ_ENCODING_ZIPMAP 3  /* Encoded as zipmap */
#define OBJ_ENCODING_LINKEDLIST 4 /* No longer used: old list encoding. */
#define OBJ_ENCODING_ZIPLIST 5 /* Encoded as ziplist */
#define OBJ_ENCODING_INTSET 6  /* Encoded as intset */
#define OBJ_ENCODING_SKIPLIST 7  /* Encoded as skiplist */
#define OBJ_ENCODING_EMBSTR 8  /* Embedded sds string encoding */
#define OBJ_ENCODING_QUICKLIST 9 /* Encoded as linked list of ziplists */
#define OBJ_ENCODING_STREAM 10 /* Encoded as a radix tree of listpacks */

(2.1) 简单动态字符串SDS

　　代码见
　　SDS包括 RAW INT EMDSTR

(2.2) 链表

(2.3) 字典

(2.4) 跳跃表

(2.5) 整数集合

(2.6) 压缩列表

思考

Redis为什么会把整数数组和压缩列表作为底层数据结构?

整数数组和压缩列表在查找时间复杂度方面并没有很大的优势，那为什么 Redis 还会把它们作为底层数据结构呢？

1、内存利用率，数组和压缩列表都是非常紧凑的数据结构，它比链表占用的内存要更少。
Redis是内存数据库，大量数据存到内存中，此时需要做尽可能的优化，提高内存的利用率。

2、数组对CPU高速缓存支持更友好，所以Redis在设计时，集合数据元素较少情况下，默认采用内存紧凑排列的方式存储，同时利用CPU高速缓存不会降低访问速度。当数据元素超过设定阈值后，避免查询时间复杂度太高，转为哈希和跳表数据结构存储，保证查询效率。

数组对cpu缓存友好的原因是: cpu预读取一个cache line大小的数据, 数组数据排列紧凑、相同大小空间保存的元素更多, 访问下一个元素时、恰好已经在cpu缓存了. 如果是随机访问、就不能充分利用cpu缓存了, 拿int元素举例: 一个元素4byte, CacheLine 假设64byte, 可以预读取 16个挨着的元素, 如果下次随机访问的元素不在这16个元素里、就需要重新从内存读取了.

(4) 手动测试过程

　1、flushall 清空所有数据
　2、测试用string类型存 key=1000000，value=1
　3、插入100万uid用了55M左右(实际占用操作系统64M)
　4、插入1000万用了587M(实际占用从操作系统622M)

　感觉不太对，key是long类型 8字节，100万*8=8M， 100万key占8M 100万value占8M 多余的55-8-8=39M去哪了？

(4.1) 测试代码

@Slf4j
public class RedisMemoryTest {

    public Jedis jedis = JedisPoolUtil.getJedis();

    /**
     * 1000万 18位用户id
     */
    @Test
    public void testMemory() {
        // 18位用户id
        long start = 123456789012345678L;
        long end = start + 10000000;
        for (long i = 123456789012345678L; i < end; i++) {
            String res = jedis.set("u" + i, "1");
        }
    }

}

(4.2) redis flushall后 info memory信息

# Memory
used_memory:1180064
used_memory_human:1.13M
used_memory_rss:954368
used_memory_rss_human:932.00K
used_memory_peak:1219088
used_memory_peak_human:1.16M
used_memory_peak_perc:96.80%
used_memory_overhead:1132016
used_memory_startup:1079584
used_memory_dataset:48048
used_memory_dataset_perc:47.82%

(4.3) redis 插入100万数据后的info memory信息


127.0.0.1:6379> info memory
# Memory
used_memory:57558992
used_memory_human:54.89M
used_memory_rss:66695168
used_memory_rss_human:63.61M
used_memory_peak:58020704
used_memory_peak_human:55.33M
used_memory_peak_perc:99.20%
used_memory_overhead:49520624
used_memory_startup:1079584
used_memory_dataset:8038368
used_memory_dataset_perc:14.23%

(4.4) redis 插入100万数据后的info memory信息


# Memory
used_memory:615390352
used_memory_human:586.88M
used_memory_rss:421154816
used_memory_rss_human:401.64M
used_memory_peak:653409248
used_memory_peak_human:623.14M
used_memory_peak_perc:94.18%
used_memory_overhead:535349840
used_memory_startup:1079584
used_memory_dataset:80040512
used_memory_dataset_perc:13.03%

参考资料

[1] redis源码 - github
[2] 十二张图详解Redis的数据结构和对象系统
[3] “万金油”的String，为什么不好用了