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

  在做系统稳定性-下游用户接口的兜底时,当时有2种方案:
  第一种是只校验用户uid(18位数字 long类型 8字节)是否合法,这种方案实现简单,但有安全风险;
  另一种方案是缓存一份用户信息(uid、城市、运营单元、收货地址id、身份 等) 数据,用户接口异常时用缓存数据校验,这种方案实现稍微复杂点,但是没有安全风险。

 当时有2亿多用户,别的组的同学缓存过全量(20多个字段)用户数据,用了200G内存。 由于占用内存太多,收益不高,他们很快就放弃缓存用户数据了。

 由于我们并不需要缓存用户的20多个字段,只需要缓存6个字段,想自己计算一下+实验下看需要多大内存,如果占用内存少可以使用方案二。

(1) redis整体存储结构

 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,为什么不好用了