Redis深入底层数据结构（万字详细）

标签：万字 缓存 数据库 Redis Sentinel 服务器 数据结构 节点

Redis

Redis 基本数据类型

Redis支持5种数据类型：

1. string（字符串）
2. hash（哈希）
3. list（列表）
4. set（集合）
5. zset(sorted set：有序集合)

String

1. string：一个key对应一个value。
2. string类型是二进制安全的,可以存储任何类型的数据
3. 常用命令:get,set,incr,decr,mget等

hash

1. hash：一个string类型的field和value的映射表
2. hash特别适合用于存储对象
3. 常用命令是hget，hset，hgetall。

list

1. list：简单的字符串列表，底层实现为双向链表。
2. 可以作为消息队列系统和取最新N个数据的操作。

set

1. set:string类型的无序集合，通过hashtable实现。集合内不能出现重复数据。
2. 可以交集，并集，差集等。
3. 实现方式:set 的内部实现是一个 value永远为null的HashMap，实际就是通过计算hash的方式来快速排重的，这也是set能提供判断一个成员是否在集合内的原因。
4. SADD key member1：添加一个或多个成员。SISMEMBER key:返回给定的集合的所有成员。

zset

1. string类型的集合,且不允许重复的成员
2. 常用命令zadd，zrange，zrem，zcard。
3. 而sorted set可以通过用户额外提供一个优先级(score)的参数来为成员排序，并且是插入有序的，即自动排序。
4. 实现方式：Redis sorted set的内部使用HashMap和跳跃表(SkipList)来保证数据的存储和有序，HashMap<value,score>里放的是成员到score的映射，而跳跃表里存放的是所有的成员。

Redis高级类型

HyperLongLong

用来近似计算集合的基数(通过前导0的个数反推基数)，用于计算访问量。

BitMap

bit通过一个bit位来表示某个元素对应的值或者状态，其中的key就是对应元素本身会极大的节省存储空间可以此实现BloomFilter。

GeoHash

1. 地理位置距离排序算法：将二维的经纬度数据映射到一维的整数，这样所有的元素都将挂载到一条线上，距离靠近的二维坐标映射到一维后的点之间距离会很接近。
2. Redis中经纬度使用52位的整数进行编码，放进zset中，zset的value元素是key，score是GeoHash的52位整数值。在使用Redis进行Geo查询时，其内部对应的操作其实只是zset(skiplist)的操作。通过zset的score进行排序就可以得到坐标附近的其它元素，通过将score还原成坐标值就可以得到元素的原始坐标。

布隆过滤器:

1. 是一个bit数组。在要映射一个值到布隆过滤器中,我们需要使用多个不同的哈希函数来生成多个哈希值并对每一个生成的哈希值指向的置为1。
2. 特点：
   1. 高效地插入和查询，能够告诉用户"某个东西一定不存在或可能存在"
   2. 不支持删除操作。
3. 计数删除：将bit位改为数值。每存在一个值对应的位就加1，删除时减1。
   

Redis底层结构

简单动态字符串SDS

Sds：简单动态字符串，实现字符串对象。在redis程序内部用作char*的替代品，当创建一个动态字符串时,free属性为0。

struct sdshdr {
    len;
    free;
    byte[] buf ;
}

1. 常数复杂度获取字符串长度。
2. SDS的API缩短SDS的字符串时，不会立即使用内存分配回收多出来的字节，而是记录在free属性中并等待将来使用。
3. 如果新字符串总长度小于SDS_MAX_PREALLOC那么为字符串分配2倍与所需长度的空间,否则就分配所需长度加上SDS_MAX_REPEALLOC的空间。

Redis双端链表:

应用

• 事务模块使用双端链表来按顺序保存输入的命令。
• 服务器模块使用双端链表来保存多个客户端。
• 订阅/发送模块使用双端链表来保存订阅模式的多个客户端。
• 事件模块使用双端链表来保存时间事件(time event)。

实现

1. 双端链表的表头标尾进行插入的复杂度都为o(1)，是高效实现LPUSH RPOP等命令的关键。
2. 双端链表带有len属性，所以链表的长度计算为o(1)。
3. redis链表是无环的。
4. 链表节点使用void *指针保存节点值,可以用于保存各种类型的值

typedef struct list{
    listNode* head;
    listNode* tail;
    unsigned long len;
    viod *(*dup)(void *ptr)//节点值复制函数
    void *(*dup)(void *ptr)//节点值释放函数
    int  *(*match)(void *ptr,void *key);//节点值对比函数
}

字典

1. 实现数据库键空间

   • SET：设置一个字符串键到键空间
   • GET：从键空间取出该字符串的值
   • FLUSHDB：可以清空建空间上的现有的键值对

2. Redis使用链地址法来解决键冲突

3. Redis字典使用哈希表作为底层实现，一个哈希表有多个哈希表节点，每个哈希表节点保存了字典中的一个键值对。

typedef struct dictht{
    dictEntry ** table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
}

typedef struct dict{
    dictType *type;//保存了一组用于操作特定类型键值对的函数,
    void *privadata//需要传给类型特定函数的可选参数
    dictht ht[2];//每一项都是哈希表,一般只使用ht[0],ht[1]哈希表只会在对ht[0]进行rehash时使用
    int rehashidx;//rehash索引,当rehash不在进行时,为-1   
}

rehash

1. 该过程不是一次性的，而是分多次，渐进式完成的以防止量大的时rehash对服务器对性能造成影响。分而治之,以降低算量。(该过程中,旧数据会在两个表里查询,新增会全部落入新的hash表)
   1. 为ht[1]分配空间。
   2. 将rehashidx设置为0，表示rehash正式开始。
   3. 在rehahs进行期间，每次对字典执行更新操作时候。会顺带将ht[0]上的rehash到ht[1]同时将rehashidx增一。
   4. 全部完成后rehashidx置为-1，表示rehash过程完成。将ht[1]和ht[0]交换地址。

跳跃表：有序数据结构

跳表的性质

跳表具有如下性质：

1. 由很多层结构组成
2. 每一层都是一个有序的链表
3. 最底层(Level 1)的链表包含所有元素
4. 如果一个元素出现在 Level i 的链表中，则它在 Level i 之下的链表也都会出现。
5. 每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素。
6. Redist两处使用了跳跃表 1.实现有序集合建，集群节点内部。
7. 插入：程序根据幂次定律(越大的数出现的概率越小，（1/2^n）)随机生成一个介于1和32之间的值作为level数组的大小(高度)。
8. 每一层都有一个前进指针，节点的后退指针用于从表尾向表头访问节点。
9. 各个节点保存的对象必须唯一，但分值可以相同,相同的对象使用字典排序。

整数集合

1. 当一个集合只包含整数，且元素数量不多时，Redist就使用整数集合（intset）作为集合键的底层实现。

2. 当新添加的元素类型比现有的所有元素都长时，整数集合需先升级才能添加。升级需要对底层数组的所有元素进行类型转换，所以添加新元素的时间复杂度为o（N）。

3. 升级的好处

   1. 提升灵活性：可以随意将不同的类型整数添加到集合，不需要担心类型错误。
   2. 节约内存：既能让集合同时保存三种不同类型的值，又能确保升级只会在需要的时候进行。

4. 整数集合不支持降级操作。

typedef struct intset｛
    uint32_t encoding;//数组每一项的类型
    uint32_t length;//记录了包含的元素数，
    int8_t contents[];
}

压缩列表

1. 当列表键只包含少量列表项，并且每一个列表项要么是小整数，要么是长度比较短的字符串，redis使用压缩列表来实现。
2. 当哈希键只包含少量键值对，并且每一个项键和值要么是小整数，要么是长度比较短的字符串，redis使用压缩列表来实现。
3. 压缩列表格式如下

[zlbytes][zltail][zllen][entryx][zlend]

* zlbytes：整个压缩链表的内存字节数
* zltail：用于确认尾节点，记录压缩列表尾节点距离压缩列表的起始地址有多少字节
* zllen：记录了压缩列表包含的节点数量
* zlend：特殊值0xff，标记压缩列表的末端

每一个压缩列表的节点：
[previous_entry_length][encoding][content]
* previous_entry_length：记录了前一个节点的长度，压缩列表从表尾到表头的遍历实现
* encoding：content属性所保存数据的类型和长度

连锁更新：在极端情况（多个连续的，长度介于250字节到253字节之间）下产生的连续多长空间扩展，新增/删除节点都会引起连锁更新

redis 对象

1. redis每创建一个键值对时,redis会分别创建两个对象,键对象,值对象.

typedef struct redisObject{
    unsigned type;//类型 字符串对象 列表对象 哈希对象 集合对象 有序集合对象
    unsigned encoding;//编码 底层使用的数据结构
    void *ptr//数据结构指针
}

2. Object ENCODING 可以查看底层使用的结构,redist可以根据不同的场景来为一个对象设置不同的编码。

embstr编码

1. embstr编码用于保存短字符串的一种优化编码方式，通过一次内存分配函数分配一块连续的空间，释放时也只需一次内存释放函数。
2. embstr保存数据的连续性能够更好的利用缓存带来的优势。
3. embstr由redisObject和sdshdr组成:
   

int编码

1. 对于int编码的字符串对象，若某个命令使得对象保持不是整数而是字符串值,则字符串对象编码将从int变为raw。
2. embstr编码的字符串对象在执行修改命令后，会变成一个raw编码的字符串对象。
   

raw编码

raw对象格式:需要两次内存申请

Redis数据类型的底层实现

String

底层使用SDS简单动态字符串实现。

hash

哈希对象的编码使用ziplist或hashtable

1. ziplist 保存了键的压缩列表节点推入压缩列表的表尾，再将保存了值的压缩列表节点推入压缩列表的表尾，保证了同一键值对总是紧挨着的。
2. 若
   1. 哈希对象保存的所有键值对的键和值的字符串长度都小于64字节(限值可以修改)
   2. 哈希对象保存的所有键值对数量小于512个(限值可以修改)

则使用ziplist
否使用hashtable

3. 对于ziplist编码所需两个条件任意一个不被满足时,编码会被转移并保存到字典(hashtable)里

list

列表对象的编码是ziplist(压缩列表)或者linkedlist
若：

• 列表对象保存的所有字符串元素的长度都小于64(限值可以修改)
• 列表对象保存的元素数据量小于512个(限值可以修改)

则使用ziplist。
否使用linkedlist。

set

集合对象的编码可以是intset或hashtable

1. 若集合对象使用字典作为底层实现。
2. 每一个键都是字符串对象，值对象都是NULL。
3. 若:
   • 集合保存的所有元素都是整数值
   • 集合对象保存的元素数量不超过512个(限值可以修改)

则使用intset
否使用hashtable

4. 对于intset编码所需两个条件任意一个不被满足时，编码会被转移并保存到字典(hashtable)里。

zset

1. 有序集合对象的编码可以是ziplist或skiplist
2. ziplist实现：
   1. 每一个集合元素使用两个紧挨在一起的压缩列表节点保存。
   2. 第一个保存元素成员，第二个保存元素分值。
   3. 分值较小的元素被放置在靠近表头的方向,分值较大的放置在表尾巴方向。
3. skiplist实现:使用zset结构作为底层实现。

typedef struct zset{
    zskiplist *zsl;//按照分值从小到大保存所有的集合元素(score/value)
    dict * dict;//为有序集合创建了一个从成员到分值的映射(value->score)
}

4. 有序集合的每一个元素的成员都是一个字符串对象,每一个元素的分值都是一个double类型的浮点数。
5. zsl和dict使用指针共享相同元素的成员和分值避免内存浪费。
6. 若:
   1. 有序集合的元素数量少于128个(限值可以修改)
      2.有序集合保存的所有元素成员的长度都小于64(限值可以修改)
      则使用ziplist
      否使用skiplist
      对于ziplist编码所需两个条件任意一个不被满足时,编码会被转移并保存到skiplist结构里

Redis单机操作

Redis命令分类：

Redis命令分为两种类型

1. 一种可以对任何类型的键执行:DEL EXPIRE RENAME TYPE OBJECT
2. 一种只能对特定类型的键执行:
   • SET GET APPEND STRLEN 只能对字符串键执行
   • HDEL HSET HGET HLEN 只能对哈性键执行
   • RPUSH LPOP LINSERT LLEN 只能对列表键执行
   • SADD SPOP SINTER SCARD 只能对集键执行
   • ZADD ZCARD ZRANK ZSCORE 只能对有序集合键执行
3. 类型特定命令所进行的类型检查是通过RedistObject的type属性来完成的

redis:设置过期时间

1. EXPIRE 将键key的生存时间设置为ttl秒
2. PEXPIRE 将键key的生存时间设置为毫秒
3. EXPIREAT 将键key的生存时间设置为timestamp所指定时间(秒)
4. PEXPIREAT 将键key的生存时间设置为timestamp所指定时间(毫秒)(所有命令的基础实现)
5. PERSIST 移除一个键的过期时间

redisDB的expires字典保存了数据库中所有键的过期时间：

1. 过期字典的键是一个指针，指向键空间的某个键对象。
2. 过期字典的值是一个long long类型的整数,用于保存过期时间。

过期删除策略

定时删除

创建一个定时器,在过期时间来临时,立即删除(对cpu不好,服务器应该优先处理客户端的请求)

惰性删除

每次从键空间获取键的时候删除(对内存不友好)

定期删除

每隔一段时间,程序就对象数据库进行一次检查:每隔一段时间执行一次删除过期键操作,并限制操作执行的频率和时间来减少对cpu的影响,随机挑选100个设置了过期时间的key,若删除超过25个,则在合适时期再进行一波删除

Redis采用的过期策略

惰性删除+定期删除。

内存回收

Redis使用引用计数技术实现内存回收，每一个对象的计数信息由redisObject的refcount记录。

内存淘汰算法

redis的内存占用过多的时候，需要使用某种淘汰算法来决定清理掉哪些数据。常用的淘汰算法有下面几种：

• FIFO:先进先出。判断被存储的时间，离目前最远的数据优先被淘汰。
• LRU:最近最少使用。判断最近被使用的时间，目前最远的数据优先被淘汰。
• LFU:最不经常使用。在一段时间内，数据被使用次数最少的，优先被淘汰。

对象的空转时长

1. redisObject结构包含的lru用于记录对象最后一次被命令程序访问的时间。
2. OBJECT IDLETIME 命令可以打印出给定键的空转时长,该命令访问对象时不会修改LRU属性。

Redis事务

redis通过MULTI，EXEC，WATCH等命令来实现事务功能。

• MULTI：事务的开始，所有的命令都会进入事务队列。
• EXEC：服务器遍历执行队列中保存的所有命令。
• WATCH：乐观锁，在EXEC命令执行之前用来监视任意数量的数据库键，并在执行EXEC命令执行时,检查被监视的键是否至少一个已经被执行过了。若是,服务器拒绝执行事务(每一个Redis数据库都保存着一个watched_keys字典)。

Redis 发布和订阅

1. 发布和订阅命令：PUBLISH SUBSCRIBE PSUBSCRIBE
2. 发布者和订阅者都是Redis客户端,
3. Redis将所有频道的订阅关系都保在服务器状态的pubsub_channels字典。
4. Redis将所有模式的订阅关系保存在服务器状态的pubsub_patterns属性。
5. 消息发送时，根据pubsub_channels和pubsub_patterns的信息来发送。

其他

1. 对象的生命周期：创建对象,操作对象,释放对象
2. Redis在初始化服务器时，创建一万个字符串对象。包含了0到9999的所有整数值,当服务器需要时就直接使用。
3. Redis不共享包含字符串的对象只共享包含整数值的字符串对象
4. 初始化服务器时，程序会根据服务器的dbnum属性来决定创建数据库的数量。Redist默认数据库为0号，通过SELECT来切换目标数据库。

Redis集群

Redis持久化

RDB持久化

1. SAVE：阻塞Redis服务器，直到RDB文件创建完毕。在阻塞期间服务器不能处理任何命令。
2. BGSAVE：后台子进程负责创建RDB文件。
3. RDB的载入：是服务器启动时自动执行的,只要redis服务检测到RDB文件的存在就会自动载入RDB。

AOF持久化:

1. 通过保存Redis服务器所执行的写命令来记录数据库的状态。
2. 被写入AOF文件的命令都是纯文本格式。
3. AOF实现分为命令追加、文件写入、文件同步三个步骤。
   1. 命令追加：服务器执行完一个命令后，以协议的方式追加到服务器状态的aof_buf缓冲区。
   2. 文件写入与同步：服务器每次结束一个事件循环之前会考虑是否将aof_buf内容写入。
4. Redis读取AOF文件并还原数据库的状态步骤:
   1. 创建一个不带网络连接的伪客户端(Redis只能在客户端上下文中执行)
   2. 从AOF文件中分析并读取一条写命令,使用伪客户端执行
   3. 一直重复步骤2和步骤3
5. AOF重写：为了解决AOF文件体积膨胀问题，Redis会直接读取服务器当前的数据库状态来创建一个新的AOF文件去替换老的AOF文件。在重写过程中，新的写命令会被保存到缓冲区。

Redis主从模式

主从同步步骤

1. 从服务器向主服务器发送SYNC命令。
2. 收到SYNC命令后,主服务器执行BGSAVE生成一个RDB文件。
3. 主服务器将RDB文件传送给从服务器,从服务器接收并载入这个RDB文件。
4. 主服务器将记录到缓冲区的所有命令发给从服务器。

同步后的数据一致

1. 传播：主服务器将写命令发送给从服务器执行。从服务器默认每秒一次的频率向主服务器发送自己的复制偏移量(心跳检测)。
2. 完整重同步：主服务器创建并发送RDB文件。
3. 部分重同步：用于处理断线后复制,主服务将断开期间的写命令发送到从服务器。
   1. 主从服务器分别维护一个复制偏移量，如果处于一致状态,主从的偏移量相同。
   2. 复制积压缓冲区：主服务器维护的一个固定长度的FIFO队列保存一部分最近传播的写命令。

Sentinel(哨兵)模式

1. Sentinel(哨兵)：可以检测任意多个主服务器和主服务器下的从服务器。被监控的主服务器进入下线状态时自动将下线的主服务器下的某个从服务器升级为新的主服务器。
2. Sentinel模式是运行在一个特殊模式下的Redis服务器。它默认每10秒向主服务器发送INFO命令来获取服务器的当前信息。
3. 一个Sentinel可以通过分析接收到的频道信息来获取其他Sentinel的存在，监视同一个服务器的多个Sentinel可以自动发现对方,各个Sentinel形成网络连接。

故障判定

1. Sentinel以每秒一次的频率向所有与它创建了命令链接的实例(主服务器、从服务器、Sentinel)发送ping命令，检测其是否在线。如不在线则判定位主观下线。
2. 当一个主服务器被判断为主观下线后，Sentinel会询问其他Sentinel看它们是否也认为主服务器已经进入了下线状态。收到足够多的已下线判断后，Sentinel就将服务器判定为客观下线然后执行故障转移。
3. 当一个主服务器被判为客观下线后，监视这个下线服务器的各个Sentinel会进行协商选举一个领头Sentinel。并由领头Sentinel对下线服务器进行故障转移。

领头Sentinel选举

概述

1. 发现主服务器下线的哨兵具有被选举权，要求其他哨兵为自己投票。
2. 每个哨兵都只有一票。
3. 当某个哨兵拥有半票以上，这哨兵将成为领头哨兵并进行故障迁移。

规则

1. 所有在线Sentinel都有被选举的资格
2. 每次进行选举后不论是否成功，所有的Sentinel配置纪元都会自增一。
3. 每一个纪元内的所有Sentinel都有一次机会成为局部领头Sentinel
4. 若给定时限内没有一个Sentinel被选举为Sentinel，那么各个Sentinel将在一段时间之后再次进行选举。

过程

1. 每一个发现主服务器进入客观下线的Sentinel都会要求其他Seninel将自己设置为局部领头Sentinel。
2. 最先向目标Sentinel发送设置要求的源将成为目标Sentinel的局部领头Sentinel之后的所有接收的设置要求都会被拒绝。
3. 如果某个Sentinel被半数以上Sentinel设置成为了局部领头Sentinel，那么这个Sentinel将成为领头Sentinel。

故障转移

1. 领头Sentinel会将已下线的主服务器的所有从服务器保存到一个列表里,然后按照以下规则,一项一项的过滤
   1. 删除列表中处于下线或者断线状态的从服务器
   2. 删除列表中最近5秒没有回复领头Sentinel的INFO命令的从服务器
   3. 删除所有与已下线主服务器连接断开超过一定时间的从服务器
2. 从剩余的从服务器中按照优先级进行排序，然后选出其中偏移量最大的从服务器，再按照运行ID选择运行ID最小的从服务器成为新的主服务器。

Redis集群模式

1. 集群的整个数据库被分为16384个槽。
2. 每个节点可以处理0个或最多16384个槽
3. 若16384个槽都有节点处理时集群处于上线状态，否则处于下线状态。
4. 一个节点就是一个运行在集群模式下的Redis服务器
5. Redis集群的节点分为主节点和从节点。主节点用于处理槽，从节点用于复制主节点。
6. 集群中的各个节点会互相发送消息的方式来交换各个节点的状态消息，在线、疑似下线、已经下线。若半个节点都认为某个节点疑似下线，那么这个节点就被标记为已下线。
7. 节点使用 CRC16(key) % 16386 指定槽。若发现键所在的槽并非自己负责处理时，节点就会向客户端返回一个MOVED错误指引客户端转向至正在负责槽的节点。
8. 节点和单机服务器在数据库方面的一个区别是：节点只使用0号数据库而Redis服务器没有这一规则。

集群实现

1. 每一个节点会使用一个ClusterNode结构记录自己的状态，然后为其他的节点都创建一个相应的clusterNode。每个节点都和其它节点通过互ping保持连接，每个节点保存整个集群的状态信息，可以通过连接任意节点读取或者写入数据。
2. ClusterNode结构保存了一个节点的当前状态、节点的创建时间、节点的名字、节点当前的配置纪元、节点的IP地址和端口号。
3. ClusterNode的link属性是一个clusterLink结构。该结构保存了连接节点所需的有关消息：套接字描述,输入缓冲区,输出缓冲区。
4. clusterState结构记录了当前视角下集群所处的状态、集群上线下线状态、集群包含的节点数。

新节点加入集群

CLUSTER MEET 让节点A将另外一个节点B添加到A当前所在的节点集群中。

过程

1. A为B创建一个clusterNode结构,并添加到自己的clusterState.nodes里。
2. A向B发送一条MEET消息
3. B接收到A的MEET消息后，B为A创建一个clusterNode结构,并添加到自己的clusterState.nodes字典里。
4. B向A返回一条PONG消息。
5. A收到PONG消息，得知B已经收到了自己的MEET消息。
6. A向B发送一条PING消息。
7. B收到PING消息,得知A已经收到了自己的PING消息。
8. 之后，A将节点B的消息通过Gossip协议传播给集群中的其他节点。

Redis性能

redis是单线程数据为何那么快

1. 纯内存操作
2. 单线程机制,避免了上下文切换,同时避免了锁操作
3. 采用了非阻塞I/O多路复用机制

redis为啥是单线程操作

1. 多线程的存在基本是因为程序中存在等待，处理器资源使用不充分。redis纯内存操作，cpu不是限制。Redis主要受限于内存和网络。
2. Redis单线程避免了不必要的上下文切换和竞争条件且实现简单。
3. Redis利用队列技术,将并发访问变成串行访问。
4. redis提供的每一个API都是原子操作，单线程保证了事务的原子性。

除了主线程外，它也有后台线程在处理一些较为缓慢的操作，例如清理脏数据、无用连接的释放、大 key 的删除等等。所以严格来讲Redis不是单线程的。

Redis 6.0 多线程的Redis

多线程的Redis线程模型

1. I/O多路复用程序复制监听多个套接字，I/O多路复用程序总是将所有产生事件的套接字放到一个队列里
2. 主线程阻塞，等待IO线程读套接字并解析请求，多个IO线程并行解析。
3. 主线程根据解析后的命令进行执行，单线程的执行命令
4. 主线程阻塞，等待IO线程将执行结果回写入套接字

Redis的多线程部分只是用来处理网络数据的读写和协议解析，执行命令仍然是单线程顺序执行

优点

1. 可以充分利用服务器 CPU 资源，目前主线程只能利用一个核。
2. 多线程任务可以分摊 Redis 同步 IO 读写负荷。

Redis应用

缓存相关

1. 缓存雪崩在某一个时间段里缓存集中过期失效。
   解决方式：不同的对象设置不同的过期时间,或者过期时间加一个随机因子,尽量分散时间。

2. 缓存穿透：查询一个数据库一定不存在的数据，则请求必然会打到数据库。
   解决方式：

   1. 使用布隆过滤器,将所有可能存在的数据哈希到一个足够大的bitmap中,一定不存在与数据库的数据会被这个bitmap拦截掉。
   2. 数据库不存在的值，统一返回一个特定值缓存到redis中,代表数据不存在。

3. 缓存击穿：缓存中没有数据但数据库中有。由于并发用户特别多同时，没有读取到数据，都同时去数据库取数据。造成数据库压力瞬间增大。
   解决方式：

   1. 热点数据永不过期
   2. 加分布式锁
   3. 设置一个watcher进行锁续期

缓存更新的设计模式：

1. 先删缓存后更新数据库：考虑两个并发请求，一个是要更新操作，另一个是查询操作。更新操作会致使当前缓存失效，删除缓存后。这时查询操作没有命中缓存，就会将数据库中的数据读出来放到缓存中。然后更新操作更新了数据库，此时缓存中数据并不是更新操作的新值，而是原来的数据库中的值。所以说这种更新策略是错误的。
* 优化方案：删除缓存、修改数据库、读取缓存等的操作积压到队列里边，实现串行化。

2. 先更新数据库后删除缓存：如果更新数据库的时候，正好有读请求到达，此时读到的数据将是脏数据，但是当更新完数据库，会删除旧的缓存，等下次读请求到达时，没有命中缓存，会从数据库重新load到内存中，保证只出现因此脏数据，之后都是正确的数据。

   • 优化方案：考虑删除缓存失败的情况，可以不断重试删除操作，直到成功。

3. 读写穿透模式

   • 读操作中更新缓存：让缓存服务自己加载，对程序调用来说是透明的。当读操作没有命中缓存时将触发读穿透
   • 写操作中更新缓存：当数据进行更新时，如果没有命中缓存，直接更新数据库，然后返回。如果命中了缓存，则更新缓存，然后再由缓存自己更新数据库

4. Write Behind Caching Pattern：在更新数据的时候，只更新缓存，不更新数据库。而我们的缓存会异步地批量更新数据库可能会出现数据不一致的情况：当系统掉电，缓存中数据还没有来得及写到数据库，则会造成一定的数据丢失。

redis为什么采用跳表而不是红黑树?

在做范围查找的时候，平衡树比skiplist操作要复杂。而在skiplist上进行范围查找就非常简单，只需要在找到小值之后，对第1层链表进行若干步的遍历就可以实现。(实现复杂)

平衡树的插入和删除操作可能引发子树的调整，逻辑复杂，而skiplist的插入和删除只需要修改相邻节点的指针，操作简单又快速。对于高并发的场景下skiplist可以减少锁竞争,获取更高的并发(平衡树插入删除会引发子树调整)

从内存占用上来说，skiplist比平衡树更灵活一些。一般来说，平衡树每个节点包含2个指针（分别指向左右子树），而skiplist每个节点包含的指针数目平均为1/(1-p)，具体取决于参数p的大小。如果像Redis里的实现一样，取p=1/4，那么平均每个节点包含1.33个指针，比平衡树更有优势。(内存占用少)

标签：万字,缓存,数据库,Redis,Sentinel,服务器,数据结构,节点
From： https://blog.csdn.net/JJTX00/article/details/143778643