redis数据结构-存亿级数据需要耗费多少内存
在做系统稳定性-下游用户接口的兜底时，当时有2种方案：
第一种是只校验用户uid(18位数字 long类型 8字节)是否合法，这种方案实现简单，但有安全风险；
另一种方案是缓存一份用户信息(uid、城市、运营单元、收货地址id、身份 等) 数据，用户接口异常时用缓存数据校验，这种方案实现稍微复杂点，但是没有安全风险。
当时有2亿多用户，别的组的同学缓存过全量(20多个字段)用户数据，用了200G内存。 由于占用内存太多，收益不高，他们很快就放弃缓存用户数据了。
由于我们并不需要缓存用户的20多个字段，只需要缓存6个字段，想自己计算一下+实验下看需要多大内存，如果占用内存少可以使用方案二。
(1) redis整体存储结构
(1.1) redisServer
/src/server.h
struct redisServer {
/* General */
pid_t pid; /* Main process pid. */
pthread_t main_thread_id; /* Main thread id */
char *configfile; /* Absolute config file path, or NULL */
char *executable; /* Absolute executable file path. */
char **exec_argv; /* Executable argv vector (copy). */
int dynamic_hz; /* Change hz value depending on # of clients. */
int config_hz; /* Configured HZ value. May be different than
the actual 'hz' field value if dynamic-hz
is enabled. */
mode_t umask; /* The umask value of the process on startup */
int hz; /* serverCron() calls frequency in hertz */
int in_fork_child; /* indication that this is a fork child */
redisDb *db;
dict *commands; /* Command table */
...
};(1.2) redisDb
src/server.h
/* Redis database representation. There are multiple databases identified
* by integers from 0 (the default database) up to the max configured
* database. The database number is the 'id' field in the structure. */
typedef struct redisDb {
dict *dict; /* The keyspace for this DB */
dict *expires; /* Timeout of keys with a timeout set */
dict *blocking_keys; /* Keys with clients waiting for data (BLPOP)*/
dict *ready_keys; /* Blocked keys that received a PUSH */
dict *watched_keys; /* WATCHED keys for MULTI/EXEC CAS */
int id; /* Database ID */
long long avg_ttl; /* Average TTL, just for stats */
unsigned long expires_cursor; /* Cursor of the active expire cycle. */
list *defrag_later; /* List of key names to attempt to defrag one by one, gradually. */
} redisDb;redis默认有16个db，每个db里保存了
(1.3) dict
/src/dict.h
typedef struct dict {
dictType *type;
void *privdata;
dictht ht[2];
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
} dict;(1.4) dictht
/src/dict.h
/* This is our hash table structure. Every dictionary has two of this as we
* implement incremental rehashing, for the old to the new table. */
typedef struct dictht {
dictEntry **table;
unsigned long size;
unsigned long sizemask;
unsigned long used;
} dictht;(1.5) dictEntry
src/dict.h
typedef struct dictEntry {
void *key;
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next;
} dictEntry;dictEntry里保存了key指针、value指针、next指针，各8字节
(1.6) redisObject
typedef struct redisObject {
unsigned type:4;
unsigned encoding:4;
unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
* LFU data (least significant 8 bits frequency
* and most significant 16 bits access time). */
int refcount;
void *ptr;
} robj;redisObject保存了
(1.7) redis查找key方法
/src/db.c
/* Low level key lookup API, not actually called directly from commands
* implementations that should instead rely on lookupKeyRead(),
* lookupKeyWrite() and lookupKeyReadWithFlags(). */
robj *lookupKey(redisDb *db, robj *key, int flags) {
dictEntry *de = dictFind(db->dict,key->ptr);
if (de) {
robj *val = dictGetVal(de);
/* Update the access time for the ageing algorithm.
* Don't do it if we have a saving child, as this will trigger
* a copy on write madness. */
if (!hasActiveChildProcess() && !(flags & LOOKUP_NOTOUCH)){
if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
updateLFU(val);
} else {
val->lru = LRU_CLOCK();
}
}
return val;
} else {
return NULL;
}
}/src/dict.c
dictEntry *dictFind(dict *d, const void *key)
{
dictEntry *he;
uint64_t h, idx, table;
if (dictSize(d) == 0) return NULL; /* dict is empty */
if (dictIsRehashing(d)) _dictRehashStep(d);
h = dictHashKey(d, key);
for (table = 0; table <= 1; table++) {
idx = h & d->ht[table].sizemask;
he = d->ht[table].table[idx];
while(he) {
if (key==he->key || dictCompareKeys(d, key, he->key))
return he;
he = he->next;
}
if (!dictIsRehashing(d)) return NULL;
}
return NULL;
}(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) 压缩列表
(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
(3.5) 哈希对象 OBJ_HASH
(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，为什么不好用了