redis的key 底层都是String

C语言标识字符串：
char data[] = “Strig\0” : \0结尾标识

sds：simple dynamic String

redis定义的字符串类型

len:6
char buf[] = “string\0jaa”
依据len长度取值，
1：二进制安全的数据结构
2：提供内存预分配机制，避免频繁内存分配
3：兼容C语言函数库
后面会加上\0
free： buff还有多少可用空间

key扩容
成倍的扩容
（len + addlen ） 2
append命令
setbit命令涉及 key扩容
*长度=1024时，只会成倍扩容

String

数据结构

  1. // redis 3.2 以前
  2. struct sdshdr {
  3. int len;
  4. int free;
  5. char buf[];
  6. };

3.2提供了5种区分不同的长度，应对不同的场景

  1. typedef char *sds;
  3. struct __attribute__ ((__packed__)) sdshdr5 {
  4.     unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
  5.     char buf[];
  6. };
  7. struct __attribute__ ((__packed__)) sdshdr8 {
  8.     uint8_t len; /* used */
  9.     uint8_t alloc; /* excluding the header and null terminator */
  10.     unsigned char flags; /* 3 lsb of type, 5 unused bits */
  11.     char buf[];
  12. };
  13. struct __attribute__ ((__packed__)) sdshdr16 {
  14.     uint16_t len; /* used */
  15.     uint16_t alloc; /* excluding the header and null terminator */
  16.     unsigned char flags; /* 3 lsb of type, 5 unused bits */
  17.     char buf[];
  18. };
  19. struct __attribute__ ((__packed__)) sdshdr32 {
  20.     uint32_t len; /* used */
  21.     uint32_t alloc; /* excluding the header and null terminator */
  22.     unsigned char flags; /* 3 lsb of type, 5 unused bits */
  23.     char buf[];
  24. };
  25. struct __attribute__ ((__packed__)) sdshdr64 {
  26.     ........
  30. #define SDS_TYPE_5  0
  31. #define SDS_TYPE_8  1
  32. #define SDS_TYPE_16 2
  33. #define SDS_TYPE_32 3
  34. #define SDS_TYPE_64 4
  35. static inline char sdsReqType(size_t string_size) {
  36.     if (string_size < 32)  
  37.         return SDS_TYPE_5;
  38.     if (string_size < 0xff) //2^8 -1  
  39.         return SDS_TYPE_8;
  40.     if (string_size < 0xffff) // 2^16 -1  
  41.         return SDS_TYPE_16;
  42.     if (string_size < 0xffffffff)  // 2^32 -1 
  43.         return SDS_TYPE_32;
  44.     return SDS_TYPE_64;
  45. }

image.png

key

: String

value:

: String ,hash set ,sorted set list

map —> dict
数据库：海量数据的存储
redis 使用了下面两种数据结构
1：数组： O(1)
2：链表：O(n）
hash(key) -> 自然数 %4 获取 arr的坐标值
1：任意仙童的输入，一定得到相同的输出
2：不同的输入可能会有相同的输出
hash碰撞
解决方案：链表法 类型hashmap，开放地址法（用的少）

redisDb

  1. typedef struct redisDb {
  2.     dict *dict;     //   key -value          
  3.     dict *expires;     //过期时间     
  4.     dict *blocking_keys;          
  5.     dict *ready_keys;           
  6.     dict *watched_keys;         
  7.     int id;                      
  8.     long long avg_ttl;           
  9.     unsigned long expires_cursor;  
  10.     list *defrag_later;          
  11. } redisDb;
  1. typedef struct dictEntry {
  2.     void *key; // 指针，sds对象
  3.     union {      // 值，只会用到下面的一个
  4.         void *val;    //执行一个value 对象 执行不同的类型，执行任意对象，redisObject
  5.         uint64_t u64;
  6.         int64_t s64;
  7.         double d;
  8.     } v;
  9.     struct dictEntry *next;  //链表，hash冲突时
  10. } dictEntry;
  1. typedef struct dict {
  2.     dictType *type;
  3.     void *privdata;
  4.     dictht ht[2];
  5.     long rehashidx; 
  6.     unsigned long iterators;  
  7.     } dict;
  1. typedef struct redisObject {
  2.     unsigned type:4;  //标识value对象类型，string，hash，约束value类型
  3.     unsigned encoding:4; //底层编码：命令： > Object  
  4.     unsigned lru:LRU_BITS;  
  5.     int refcount;        //:  对象引用，回收用的
  6.     void *ptr;            //value的真实内存指向
  7. } robj;

image.png

  1. typedef struct dictht {
  2.     dictEntry **table;
  3.     unsigned long size; //hashTabl容量
  4.     unsigned long sizemask;   = size-1 求模用
  5.     unsigned long used;  
  6. } dictht;

扩容不是一次全部都转移，而是分批次的

String结构
embstr嵌入式string 45一下
raw类型 45以上

bitmap

一亿级日活统计，
key: 日期
value : offset

setbit key offset 0/1 setbit a-bit-map 0 1 对key a-bit-map 的第0 位设为1

bitcount a-bit-map 统计bit=1的个数 bitcount a-bit-map 0 12 统计0-12范围的位等于1的个数

bitcount and login-11-5-6 login-11-

bitop and newkey login11-5-6 login11-5-7 把后面的key 位与运算存在new key中 然后在 bitcount newkey 得到位1的总算 bitop or newkey key1 key2 然后在 bitcount newkey 统计

RedisDB主体数据结构.png