36.Redis核心设计原理
本文针对前面的讲解做一次总结
1.Redis基本特性
1.非关系型的键值对数据库，可以根据键以O(1)的时间复杂度取出或插入关联值
2.Redis的数据是存在内存中的
3.键值对中键的类型可以是字符串，整型，浮点型等，且键是唯一的
4.键值对中的值类型可以是字符串，哈希，列表，集合，排序集合等
5.Redis内置了复制，磁盘持久化，LUA脚本，事务，SSL,ACL，客户端缓存，客户端代理等功能
6.通过Redis哨兵和Redis集群模式提供高可用性
2.Redis应用场景
2.1 缓存
可以作为缓存使用，数据存在内存中，数据存取效率非常高
2.2 计数器
实现计数器功能。Redis 这种内存型数据库的读写性能非常高可以对 String 进行自增自减运算,很适合存储频繁读写的计数量。
2.3 分布式ID生成
利用自增特性一次请求一个大一点的步长如 incr 2000,缓存在本地使用，用完再请求。
2.4 海量数据统计
位图_(bitmap):存储是否参过某次活动，是否已读谋篇文章，用户是否为会员，日活统计
2.5 会话缓存
可以使用 Redis 来统一存储多台应用服务器的会话信息。当应用服务器不再存储用户的会话信息，也就不再具有状态，一个用户可以请求任意一个应用服务器，从而更容易实现高可用性以及可伸缩性。
2.6 分布式队列/阻塞队列
List 是一个双向链表，可以通过 lpush/rpush 和 rpop/lpop 写入和读取消息。可以通过使用brpop/blpop 来实现阻塞队列。
2.7 分布式锁实现
在分布式场景下，无法使用基于进程的锁来对多个节点上的进程进行同步。可以使用 Redis 自带的SETNX 命令实现分布式锁。
2.8 热点数据存储
最新评论，最新文章列表，使用list 存储,ltrim取出热点数据，删除老数据。
2.9 社交类需求
Set 可以实现交集，从而实现共同好友等功能，Set通过求差集，可以进行好友推荐，文章推荐。
2.10 排行榜
sorted set可以实现有序性操作，从而实现排行榜等功能。
2.11 延迟队列
使用sorted set(zset)，使用 【当前时间戳 +需要延迟的时长】做score,消息内容作为元素,调用zadd来生产消息，消费者使用zrangbyscore获取当前时间之前的数据做轮询处理。消费完再删除任务 rem keymember
3.Redis键(Key)存储
所有的键都是String类型，都存储在buf里面，参考下面DB存储结构
4.Redis(Value)DB存储
redis的数据结构更偏向于map,在redis更具象化叫做dict，通过key找到value,存储海量数据；存储结构包括
1.数组：O(1)
2.链表： O(N)
4.1 String
Redis 3.2以前
C语言中使用字符串数组存储 char buf[] = "xiehao\0"；但是C语言有个问题，在read键时，可能会漏读String键的长度，所以redis重新定义了一个SDS存储方式:
如下以键“xiehao”的键的存储位案例分析；
在 C语言中存储 C：char data[] = "xiehao\0",默认结尾会带一个“\0”;
SDS:
free:0
len:6
char buf [] = "xiehao"
当扩容free长度不够时，
将键"xiehao"变成"xiehao123",数组长度会自动计算多一些（ 6+3）*2 =18
SDS:
free: 9
len ：9
char buf[]="xiehao123"
当扩容free长度够用时，
如果再次扩容变成"xiehao123456",则增加了3个长度，判断free剩余长度可以容纳，则直接使用free,不需要扩容
SDS:
free: 6
len ：12
char buf[]="xiehao123456"
当扩容到1024 *1024(也就是内存为1M时)则不会在继续扩容；
Redis 3.2后
len：长度
buf: 数据
alloc:buf分配的长度
flags：1字节 类型和业务数据长度,根据类型指向定义不同长度的内存；
类型有： sdshrd5 、 sdshrd8、 sdshrd16 、 sdshrd32 、 sdshrd64
使用SDS优点：
1.二进制安全的数据结构；
2.提供了内存预分配机制，避免了频繁的内存分配
3.兼容C语言的函数库
4.2 Hash
Hash数据结构根据Hash(key)进行随机散列，并且将hash值变成自然数，这样可以将自然数作为索引来定位数据，大大提高效率；若发生hash碰撞，则进行链表关联；
例如：
创建一个大的数组:
arr[4]
hash( key)->自然数[大]%4=「0，arr.size]
1.任意相同的输入，一定能得到相同的输出
2.不同的输入，有可能得到相同的输出
定义3个键值对 (k1,v1)(k2,v2),(k3,v3)
hash(k1)%4=0
hash(k2)%4=1
hash(k3)%4=1
arr[0]->(k1,v1,next->null)
arr[1]->(k3,v3,next ->k2 )(k2,v2,next ->null)
链表 ：redis：头插入方式
Redis 有16个DB
typedef struct redisDb{
dict *dict; (k-v)
dict *expires; (过期时间)
dict *blocking keys; （阻塞队列）
dict *ready keys; （客户端）
dict *watched_keys; （事务处理）
int id; （SELECT * 命令 - 数据库索引）
long long avg_ttl; （数据统计、遍历等）
unsigned long expires_cursor;
list *defrag _later;
}redisDb;
typedef struct dict{
dictType *type; （类型）
void *privdata;
dictht ht[2]; （扩容）
long rehashidx; (渐进式rehash)
unsigned long iterators;
}dict;
typedef struct dictht{
dictEntry **table;
unsigned long size;
unsigned long sizemask;
unsigned long used;
}dictht;
typedef struct dictEntry{
void *key;
union{
void *val;
uint64t u64;
int64t s64;
double d;
}V;
struct dictEntry *next;
}dictEntry;
typedef struct redisObject{
unsigned type:4; （约束类型）
unsigned encoding:4; （数据类型）
unsigned Iru:LRU BITS;
int refcount;
void *ptr; （数据存储位置）
}robj;
4.3 List
List存储结构采用quickList(双端链表) 和 zipList存储；数据结构K-V(array)
zipList
zibytes: 4字节 存多少数据
zltail：尾节点的索引
zllen：有多少元素
zlend：1字节 数据结尾标识
prerawlen: 前一个数据的信息
len: 当前数据的类型
data:当前的数据
quickList:
head:
tail
count:
length:
quickListNode:节点数据
zl：ziplist的数据
单个ziplist节点最大能存储 8kb ,超过则进行分裂,将数据存储在新的ziplist节点中
hash
4.4 Set
Set为无序的，自动去重的集合数据类型，Set 数据结构底层实现为一个value为x`的字典（dict），当数据可以用整形表示时，Set集合将被编码为intset数据结构。两个条件任意满足时Set将用hashtable存储数据。K - V（array）
1：元素个数大于set-max-intset-entries；
2：元素无法用整形表示；
typedef struct intset{
uint32t encoding;
uint32t length;
int8t contents[];
}intset;
encoding：编码类型
length：元素个数
contents[]：元素存储
整数集合是一个有序的，存储整型数据的结构。整型集合在Redis中可以保存int16t，int32 t，int64t类型的整型数据，并且可以保证集合中不会出现重复数据。
4.5 Zset
ZSet 为有序的，自动去重的集合数据类型，ZSet 数据结构底层实现为字典（dict）+跳表（skiplist），当数据比较少时，用ziplist编码结构存储。K-V(array)
zipList
zset-max-ziplist-entries 128/元素个数超过128，将用skiplist编码
zset-max-ziplist-value64//单个元素大小超过64 byte，将用skiplist编码
skipList
typedef struct zskiplist{
struct zskiplistNode *header,（头节点，做索引，不存数据）
*t ail; （尾节点，会
存数据）
unsigned long length;（元素个数）
int level; （层高）
}zskiplist;
跳表算法：
数据项:N
index1 : N/2
index2 : N/2^2
index3: N/2^3
indexk: N/2^k
N/2^K = 2
2^K = N/2
k = log2 N/2
k = logN
ZSet 为有序的，自动去重的集合数据类型，ZSet 数据结构底层实现为 字典(dict) + 跳表(skiplist) ,当数据比较少时，用ziplist编码结构存储。