再谈redis

底层实现：主要是从Redis的源码中提炼的问题，包括但不限于底层数据结构、服务模型、算法设计等。
基础架构：可用概况为Redis整体对外的功能点和表现，包括但不限于单机版主从架构实现、主从数据同步、哨兵机制、集群实现、分布式一致性、故障迁移等。
实际应用：实战中Redis可用帮你做什么，包括但不限于单机缓存、分布式缓存、分布式锁、一些应用。

Q1: Redis常用五种数据类型是如何实现的？
Redis支持的常用5种数据类型指的是value类型，分别为：字符串String、列表List、哈希Hash、集合Set、有序集合Zset，但是Redis后续又丰富了几种数据类型分别是Bitmaps、HyperLogLogs、GEO。

Redis底层的数据结构包括：简单动态数组SDS、链表、字典、跳跃链表、整数集合、压缩列表、对象。

Q2: Redis的SDS和C中字符串相比有什么优势？
在C语言中使用N+1长度的字符数组来表示字符串，尾部使用’\0’作为结尾标志，对于此种实现无法满足Redis对于安全性、效率、丰富的功能的要求，因此Redis单独封装了SDS简单动态字符串结构。
从图中可以知道sds本质分为三部分：header、buf、null结尾符，其中header可以认为是整个sds的指引部分，给定了使用的空间大小、最大分配大小等信息。
好处：O(1)获取长度
防止缓冲区溢出bufferoverflow

Q3:Redis的字典是如何实现的？简述渐进式rehash的过程。

dictEntry是哈希表节点，也就是我们存储数据地方，其保护的成员有：key,v,next指针。key保存着键值对中的键，v保存着键值对中的值，值可以是一个指针或者是uint64_t或者是int64_t。next是指向另一个哈希表节点的指针，这个指针可以将多个哈希值相同的键值对连接在一次，以此来解决哈希冲突的问题。
如图为两个冲突的哈希节点的连接关系：
关于dictht
从源码看哈希表包括的成员有table、size、used、sizemask。table是一个数组，数组中的每个元素都是一个指向dictEntry结构的指针， 每个dictEntry结构保存着一个键值对；size 属性记录了哈希表table的大小，而used属性则记录了哈希表目前已有节点的数量。sizemask等于size-1和哈希值计算一个键在table数组的索引，也就是计算index时用到的。
如上图展示了一个大小为4的table中的哈希节点情况，其中k1和k0在index=2发生了哈希冲突，进行开链表存在，本质上是先存储的k0，k1放置是发生冲突为了保证效率直接放在冲突链表的最前面，因为该链表没有尾指针。

关于dict
从源码中看到dict结构体就是字典的定义，包含的成员有type，privdata、ht、rehashidx。其中dictType指针类型的type指向了操作字典的api，理解为函数指针即可，ht是包含2个dictht的数组，也就是字典包含了2个哈希表，rehashidx进行rehash时使用的变量，privdata配合dictType指向的函数作为参数使用，这样就对字典的几个成员有了初步的认识。

.Redis的单线程模式
本质上Redis并不是单纯的单线程服务模型，一些辅助工作比如持久化刷盘、惰性删除等任务是由BIO线程来完成的，这里说的单线程主要是说与客户端交互完成命令请求和回复的工作线程。
CPU并非瓶颈
Redis的所有操作都是基于内存的，处理事件极快，因此使用多线程来切换线程提高CPU利用率的需求并不强烈；
内存才是瓶颈
单个Redis实例对单核的利用已经很好了，但是Redis的瓶颈在于内存，设想64核的机器假如内存只有16GB，那么多线程Redis有什么用武之地？
常用的Hash、Zset、List等结构在value很大时，CURD的操作会很复杂，如果采用多线程模式在进行相同key操作时就需要加锁来进行同步，这样就可能造成死锁问题。

基于redis实现的分布式锁

分布式锁需要具备的条件：
互斥性
在任意时刻，只有一个客户端能持有锁 其他尝试获取锁的客户端都将失败而返回或阻塞等待。
健壮性
一个客户端持有锁的期间崩溃而没有主动释放锁，也需要保证后续其他客户端能够加锁成功。
唯一性
加锁和解锁必须是同一个客户端，客户端自己不能把别人加的锁给释放了，自己持有的锁也不能被其他客户端释放
高可用
不必依赖于全部Redis节点正常工作，只要大部分的Redis节点正常运行，客户端就可以进行加锁和解锁操作。
最初分布式锁借助于setnx和expire命令，但是这两个命令不是原子操作，如果执行setnx之后获取锁但是此时客户端挂掉，这样无法执行expire设置过期时间就导致锁一直无法被释放，因此在2.8版本中Antirez为setnx增加了参数扩展，使得setnx和expire具备原子操作性。
在单Matster-Slave的Redis系统中，正常情况下Client向Master获取锁之后同步给Slave，如果Client获取锁成功之后Master节点挂掉，并且未将该锁同步到Slave，之后在Sentinel的帮助下Slave升级为Master但是并没有之前未同步的锁的信息，此时如果有新的Client要在新Master获取锁，那么将可能出现两个Client持有同一把锁的问题。
为了解决这个问题，Redlock算法：
现在假设有5个Redis主节点(大于3的奇数个)，这样基本保证他们不会同时都宕掉，获取锁和释放锁的过程中，客户端会执行以下操作:
1.获取当前Unix时间，以毫秒为单位
2.依次尝试从5个实例，使用相同的key和具有唯一性的value获取锁
当向Redis请求获取锁时，客户端应该设置一个网络连接和响应超时时间，这个超时时间应该小于锁的失效时间，这样可以避免客户端死等
3.客户端使用当前时间减去开始获取锁时间就得到获取锁使用的时间。当且仅当从半数以上的Redis节点取到锁，并且使用的时间小于锁失效时间时，锁才算获取成功
4.如果取到了锁，key的真正有效时间等于有效时间减去获取锁所使用的时间，这个很重要
5.如果因为某些原因，获取锁失败（没有在半数以上实例取到锁或者取锁时间已经超过了有效时间），客户端应该在所有的Redis实例上进行解锁，无论Redis实例是否加锁成功，因为可能服务端响应消息丢失了但是实际成功了，毕竟多释放一次也不会有问题