在 Redis 核心数据结构（三） 中，重点介绍了一下 Redis 7+ 使用的底层的数据结构 listpack。本文重点看一下，Redis 是如何基于 listpack 以及其他数据结构类型来构建对外暴露的五个核心数据结构的。
quicklist 关于 quicklist 更详细的介绍，请看 Redis 核心数据结构（一：quicklist。
与上述内容不一样的地方是，现在的 quicklist 底层是使用 listpack 来构建的，而不是上述内容介绍的 ziplist。
list 关于 list-max-listpack-size 的解释，在源码中找到了详细介绍：
redis.conf # Lists are also encoded in a special way to save a lot of space. # The number of entries allowed per internal list node can be specified # as a fixed maximum size or a maximum number of elements. # For a fixed maximum size, use -5 through -1, meaning: # -5: max size: 64 Kb <-- not recommended for normal workloads # -4: max size: 32 Kb <-- not recommended # -3: max size: 16 Kb <-- probably not recommended # -2: max size: 8 Kb <-- good # -1: max size: 4 Kb <-- good # Positive numbers mean store up to _exactly_ that number of elements # per list node. # The highest performing option is usually -2 (8 Kb size) or -1 (4 Kb size), # but if your use case is unique, adjust the settings as necessary. list-max-listpack-size -2
在五年前，D瓜哥写了 Redis 核心数据结构（一） 和 Redis 核心数据结构（二） 两篇文章，来对 Redis 内部的数据结构做了深入分析。随着时间的推移，Redis 的实现也在不断进化，现在这些内容已经跟不上最新发展了，推陈出新，现在重写文章，来介绍 Redis 的最新发展。
listpack 从 Redis 7.0 开始，使用 listpack 替换原来的 ziplist。至于替换原因，在 [NEW] listpack migration - replace all usage of ziplist with listpack 做了解释说明：
The reason for using listpack instead of ziplist is that ziplist may cause cascading updates when insert and delete in middle, which is the biggest problem.
— sundb 翻译过来：当在中间进行插入和删除时，ziplist 也许会产生级联更新，这是一个大问题。
编码规范 图 1. listpack 编码格式 相比 ziplist，listpack 更偏向空间换时间。淡化极致的内存使用率，向更快的方向发力。
对整数编码
在上一篇文章中，通过阅读 《In Search of an Understandable Consensus Algorithm》 前三节的内容，对论文的大致内容做了简介，简单说明了一下 Replicated state machines 的用途以及 Paxos 本身存在的问题。
4. Designing for understandability several goals in designing Raft:
it must providea complete and practical foundation for system building;
it must be safe under all conditions and available under typical operating conditions;
it must be efficient for common operations.
Our most important goal — and most difficult challenge — was understandability.
从这里可以看出，Raft 设计的初衷就是为了易于理解和便于构建。
There were numerous points in the design of Raft where we had to choose among alternative approaches. In these situations we evaluated the alternatives based on understandability.
前一段时间，在一次开组会的时候，给小组成员简单介绍了一下 Raft 协议。大概四年前读过 Raft 的论文，这次分享的时候，好多好多细节都忘了。所以，再次把 《In Search of an Understandable Consensus Algorithm》 这篇论文找出来，重读一遍，做个笔记和摘要，方便后续学习和复习。
Abstract Raft is a consensus algorithm for managing a replicated log. 开篇摘要就点出了 Raft 的特点： Raft 是一种管理复制日志的共识算法。
In order to enhance understandability, Raft separates the key elements of consensus, such as leader election, log replication, and safety, and it enforcesa stronger degree of coherency to reduce the number of states that must be considered. 为了增强可理解性，Raft 将共识分解成几个关键元素，例如 Leader 选举，日志复制，以及安全性等；同时，为了降低需要考虑的状态的数量，还强制实施了更强的一致性。
1. Introduction Consensus algorithms allow a collection of machines to work as a coherent group that can survive the failures of some of its members.
本文内容对于 Redis 7+ 来说已经过时，最新实现请看下面两篇文章：
Redis 核心数据结构（3）
Redis 核心数据结构（4）
Redis 目前是使用最广泛的缓存中间件。其突出特点就是支持多种常见的数据结构。对比 JDK 集合类的实现，Redis 的实现表现出很多独到之处，很多地方设计得别具匠心。下面就来简要介绍一下。
linkedlist Redis 底层也有很多地方使用到 linkedlist，并且也是双向链表。
adlist.h typedef struct listNode { struct listNode *prev; struct listNode *next; void *value; } listNode; typedef struct listIter { listNode *next; int direction; } listIter; typedef struct list { listNode *head; listNode *tail; void *(*dup)(void *ptr); void (*free)(void *ptr); int (*match)(void *ptr, void *key); unsigned long len; } list; Redis 的 linkedlist 实现特点是：
双向：节点带有前后指针；
无环：首尾没有相连，所以没有构成环状；
链表保存了首尾指针；
多态：可以保存不同类型的值，这里成为泛型也许更符合 Java 中的语义。
Redis 在 2014 年实现了 quicklist，并使用 quicklist 代替了 linkedlist。所以，现在 linkedlist 几乎已经是废弃状态。
ziplist Redis 官方在 ziplist.c 文件的注释中对 ziplist 进行了定义：
The ziplist is a specially encoded dually linked list that is designed to be very memory efficient. It stores both strings and integer values, where integers are encoded as actual integers instead of a series of characters. It allows push and pop operations on either side of the list in O(1) time. However, because every operation requires a reallocation of the memory used by the ziplist, the actual complexity is related to the amount of memory used by the ziplist.
