Redis的List（列表）数据类型是一个双向链表，允许从两端高效地插入和删除元素。为了提高性能和内存利用率，Redis对List进行了多种优化。特别是在Redis 3.2版本中引入的quicklist结构，和Redis 6.2版本中引入Listpack结构（替代之前的ziplist压缩列表），逐步提升List的性能。
简单概括如下：
- 早期版本（3.2之前）：基于双向链表（linkedList）或压缩列表（ziplist）实现。Redis会根据List数据的特点选择二者之一去存储数据。
- Redis 3.2版本：基于quicklist实现，即：通过linkedList+ ziplist结合实现。
- Redis 6.2版本：引入Listpack替代ziplist，即：通过linkedList+ Listpack结合实现。
1、LinkedList或zipList
这是Redis早起版本（3.2之前）对List的存储模式。
（1）、双向链表（linked list）
Redis最初使用的是标准的双向链表（linked list）实现的，每个节点包含指向前一个节点和后一个节点的指针，以及存储实际数据的字段，允许从两端高效地插入和删除元素。
（2）、压缩列表（ziplist）
对于短列表，Redis使用压缩列表来存储数据。压缩列表是一种紧凑的内存表示形式，减少了内存碎片并提高了性能。当列表中的元素较少时，Redis会优先使用压缩列表存储数据，而不是使用LinkedList，进而可以节省内存。
（3）、具体规则
当一个列表只有少量数据的时候，且每个列表项要么是小整数值，要么就是长度比较短的字符串，那么我就会使用ziplist来做List的底层实现。
规则默认是：
- List的元素数量小于 512 个。
- List的每个元素的占用的字节小于 64 字节。
（4）、ziplist原理
ziplist虽然是存储列表数据的，但实际上分配的是一块连续的内存，所有的元素紧挨着一起存储的。ziplist中可以包含多个entry数据节点，每个entry节点可以存放整数，浮点数或者字符串。与 linkedlist 相比，少了prev、next指针。所有的操作都是通过指针与解码出来的偏移量进行的。
示意图如下：
ziplist结构说明：
- zlbytes：整个压缩列表ziplist占字节数。
- zltail：尾结点相对于首地址偏移量。
- zllen：结点数量。
- entry：数据节点，内部类似SDS（结点长度+编码+内容），兼容（字符串，整数，浮点数）。
- zlend：代表结束。
（5）、3.2版本前简单总结下：
ziplist是使用连续的存储空间，替换传统列表的散列空间，所以在遍历查询会比较快。
因为Redis仅会在数据量较少时才使用ziplist，由于数据量较少，所以数组插入或删除慢的特性也不会被表现出来。
数据节点内保存类似SDS结构（例如，存储时记录了列表长度，占用空间大小等），进一步提升了性能。
2、quicklist
（1）、概述
在Redis 3.2版本开始，List的底层实现被替换为quicklist，这是一种更高效的混合结构（LinkedList+ziplist）。quicklist的设计目标是结合压缩列表和双向链表的优点，同时避免它们的缺点。
（2）、quicklist结构
quicklist主体上是一个双向链表，每个quicklistNode内通过使用压缩列表（ziplist）可以存储多个元素。
具体结构：
- quicklistNode：quicklist链表的一个节点，内部包含一个压缩列表（ziplist）。每个节点可以存储多个元素，而不是像传统的双向链表那样每个节点只存储一个元素。
- 压缩列表（ziplist）：每个quicklistNode中的压缩列表用于存储多个连续的元素。压缩列表是一种紧凑的内存表示形式，适用于存储小规模数据。通过将多个元素打包到一个压缩列表中，quicklist减少了内存碎片，并且降低了指针开销。
- 双向链表：quicklist本身仍然是一个双向链表，允许从两端高效地插入和删除节点。每个 quicklistNode都有一个指向前一个节点和后一个节点的指针。
简单说明：
1、主结构还是一个双向链表。
2、链表的每一个节点存储的是一个压缩列表。这样极大缩短了主结构双向链表的长度。同时通过压缩列表优化了存储，减少了指针开销。
简单理解示例如：
要存储的List中包含100个元素。
Redis会创建一个长度为10的双向链表，链表的每一个节点都是一个长度为10的数组。Redis相当于采用这样的结构存储了这个100个元素的List。
（3）、quicklist工作原理
- 分段存储：quicklist将List分成多个quicklistNode，每个节点内部使用压缩列表来存储多个元素。这样做的好处是可以减少指针开销，同时保持高效的插入和删除操作。
- 动态调整：quicklist会根据列表的大小动态调整每个quicklistNode中元素的数量。默认情况下，每个quicklistNode中最多可以存储8KB的数据（可以通过配置参数调整）。当某个 quicklistNode中的元素超过这个限制时，Redis会自动创建一个新的quicklistNode，并将新元素添加到新的节点中。
- 两端操作优化：由于quicklist是一个双向链表，因此可以从两端高效地插入和删除元素。每次插入或删除操作只会影响最靠近两端的quicklistNode，而不会影响整个链表的其他部分。这使得quicklist在处理频繁的两端操作时具有很高的性能。
（4）、quicklist的优势
- 内存效率高：通过将多个元素打包到一个压缩列表中，quicklist减少了指针开销，降低了内存碎片，从而提高了内存利用率。
- 性能优越：quicklist结合了压缩列表和双向链表的优点，既保持了高效的插入和删除操作，又减少了内存开销。特别是对于频繁的两端操作，quicklist表现尤为出色。
- 灵活性强：quicklist可以根据列表的大小动态调整每个quicklistNode中的元素数量，适应不同的应用场景。
（5）、quicklist的配置参数
1、list-max-ziplist-size：控制每个quicklistNode中的最大元素数量或字节数。默认值为 -2，表示每个quicklistNode最多可以存储8KB的数据。你可以根据需要调整这个值，以优化内存使用和性能。
- -2（负2）：每个 quicklistNode 最多存储 8KB 的数据。
- -1（负1）：每个 quicklistNode 最多存储 64KB 的数据。
- 0：每个 quicklistNode 只存储一个元素（相当于传统的双向链表）。
- 正整数：指定每个 quicklistNode 中最多可以存储的元素数量。
2、list-compress-depth：控制quicklist中哪些quicklistNode会被压缩。默认值为0，表示不压缩任何节点。你可以设置为1或2，表示只压缩距离链表两端1或2个节点之外的quicklistNode。压缩可以进一步减少内存占用，但会影响性能，通常用默认即可。
（6）、quicklist的应用场景
- 频繁的两端操作：quicklist在处理频繁的两端插入和删除操作时表现出色，因为它只需要操作最靠近两端的quicklistNode，而不会影响整个链表的其他部分。
- 中等规模的列表：对于中等规模的列表（例如几千个元素），quicklist可以提供良好的性能和内存利用率。它既能节省内存，又能保持高效的插入和删除操作。
（7）、与传统双向链表的对比
（8）、quicklist总结
quicklist是Redis 3.2版本引入的一种优化后的List实现（主体上是一个双向链表，节点上使用压缩列表），它结合了压缩列表和双向链表的优点，提供了更高的内存利用率和更好的性能。通过将多个元素打包到一个压缩列表中，quicklist减少了指针开销，降低了内存碎片，同时保持了高效的插入和删除操作。特别是对于频繁的两端操作，quicklist 表现尤为出色。
3、Listpack
（1）、概述
Listpack是Redis 6.2版本中引入的一种新的数据结构，用于替代之前的ziplist（压缩列表）。Listpack是对ziplist的进一步优化，旨在提供更好的内存利用率和性能，特别是在处理小规模数据时。它是Redis内部多种数据类型（如 List、Hash、Set和Sorted Set）的底层存储结构之一。
背景：
在Redis 5及之前版本中，ziplist是一种紧凑的内存表示形式，用于存储小规模数据。它通过将多个键值对或元素打包到一个连续的内存块中，减少了指针开销和内存碎片。然而，ziplist在某些场景下也表现出了局限性。
ziplist局限性：
- 内存对齐问题：ziplist中的元素需要进行内存对齐，这会导致额外的内存开销。
- 复杂性增加：ziplist的实现较为复杂，维护和优化难度较大。
- 性能瓶颈：在某些情况下，ziplist的性能不如预期，特别是在处理大量小元素时。
为了克服这些局限性，Redis 6.2引入了listpack，作为ziplist的替代品。listpack在设计上更加简洁高效，提供了更好的内存利用率和性能。
扩展：理解下内存对齐？
内存对齐（Memory Alignment），是指在计算机系统中，数据在内存中的存储位置必须满足某些特定的对齐要求。具体来说，不同的数据类型在内存中的起始地址必须是某个固定值的倍数。例如，32位整数通常要求其起始地址是4字节的倍数，64位整数则要求是8字节的倍数。这种对齐要求是由硬件架构和编译器共同决定的，目的是为了提高内存访问的速度和效率。
内存对齐的原因：
1、硬件性能优化：现代CPU在访问内存时，通常是按字（word）或双字（double word）进行读取的。如果数据没有正确对齐，CPU可能需要进行多次读取操作，或者使用更复杂的指令来处理未对齐的数据，这会导致性能下降。因此，操作系统和编译器通常会强制数据按照一定的对齐方式进行存储。
2、简化硬件设计：某些硬件（如DMA控制器、网络接口卡等）也要求数据在内存中的位置是对齐的。如果不满足对齐要求，可能会导致硬件无法正确处理数据，甚至引发系统崩溃。
3、跨平台兼容性：不同平台（如 x86、ARM等）可能有不同的对齐要求。为了确保代码在不同平台上都能正常运行，编译器通常会根据目标平台的要求进行内存对齐。
内存对齐的影响：
- 内存浪费：为了满足对齐要求，编译器可能会在数据结构中插入额外的填充字节（padding），以确保每个字段的起始地址符合对齐要求。这些填充字节虽然不存储实际数据，但占用了宝贵的内存空间，导致内存利用率降低。
- 性能提升：尽管内存对齐可能会增加一些内存开销，但它可以显著提高内存访问的速度。特别是对于大规模数据结构，正确的内存对齐可以避免频繁的缓存未命中，从而提升整体性能。
示例说明：
假设我们有一个包含int和char的结构体：
struct Example {char a; // 1 字节int b; // 4 字节char c; // 1 字节
};
在32位系统上，int类型要求4字节对齐，因此编译器会在a和b之间插入3个填充字节，以确保b的起始地址是4字节的倍数。最终的内存布局如下：
这个结构体的实际大小是12字节，而不是理论上的6字节。这就是内存对齐造成的内存浪费。 padding是为了实现内存对齐，编译器自动填充的字节，不影响数据本身但会额外占用内存。
（2）、Listpack的结构
Listpack是一种紧凑的、变长编码（长度可变的）的数据结构，能够高效地存储不同类型的数据（如整数、浮点数、字符串等）。
主要特点如下：
- 变长编码：listpack使用变长编码来存储数据，即：每个元素的存储空间可以根据其实际大小动态调整。例如：小整数可以使用较少的字节来表示，而大整数则使用更多的字节。这种设计减少了不必要的内存浪费。
- 无内存对齐：与ziplist不同，listpack不需要进行内存对齐，因此可以更高效地利用内存。每个元素直接按照其实际大小存储，避免了额外的填充字节。
- 支持多种数据类型：listpack支持多种数据类型，包括整数、浮点数、字符串等。它可以根据数据的类型选择最合适的编码方式，以减少存储空间。
- 高效的插入和删除操作：listpack优化了插入和删除操作，特别是在处理小规模数据时表现尤为出色。它可以通过局部重排（local rearrangement）来保持数据的紧凑性，避免频繁的内存分配和释放。
- 兼容性：listpack与ziplist具有良好的兼容性，现有的Redis数据结构可以无缝迁移到listpack，而不会影响现有功能。
扩展：理解下局部重排？
局部重排（Local Rearrangement）是Redis中listpack数据结构的一项优化技术，用于在插入或删除元素时保持数据的紧凑性，减少内存碎片，并提高性能。与传统的链表或数组相比，listpack通过局部重排可以在插入或删除元素时避免频繁的内存分配和释放。
局部重排的工作原理：
1、插入操作：
- 当向listpack中插入新元素时，Redis会首先检查当前节点是否有足够的空间来容纳新元素。如果有，直接将新元素插入到合适的位置；如果没有，Redis会尝试将相邻的元素向后移动，为新元素腾出空间。
- 如果相邻的元素也无法移动（例如，它们已经占据了最大允许的空间），Redis会创建一个新的节点，并将新元素插入到该节点中。然后，它会将部分旧节点中的元素迁移到新节点中，以保持数据的紧凑性。
2、删除操作： - 当从listpack中删除元素时，Redis会将该元素占用的空间标记为可用，并将后续的元素向前移动，填补空缺。这样可以避免留下大量的小块空闲空间，减少内存碎片。
- 如果删除操作导致某个节点中的元素数量过少，Redis会将该节点中的剩余元素迁移到相邻的节点中，甚至可能完全移除该节点，以保持数据的紧凑性。
局部重排的优势：
- 减少内存碎片：通过局部重排，listpack可以在插入或删除元素时保持数据的紧凑性，避免留下大量的小块空闲空间。这有助于减少内存碎片，提高内存利用率。
- 提高性能：局部重排减少了频繁的内存分配和释放操作，特别是在处理大量小元素时，性能优于传统的链表或数组。每次插入或删除操作只需要调整局部的数据结构，而不会影响整个listpack的其他部分。
- 简化实现：局部重排的实现相对简单，不需要复杂的算法或数据结构。它通过简单的移动和迁移操作，就能有效地保持数据的紧凑性，降低了代码复杂度。
示例说明：
假设我们有一个 listpack，其中包含以下元素：
[1, 2, 3, 4, 5]
现在我们要插入一个新元素2.5，位于2和3之间。
listpack 会执行以下步骤：
1、检查当前节点是否有足够的空间来容纳新元素2.5。如果有，直接将2.5插入到合适的位置。
2、如果当前节点没有足够的空间，listpack会将3和4向后移动，为2.5 腾出空间。
3、最终的 listpack 变为：
[1, 2, 2.5, 3, 4, 5]
再假设我们要删除元素3。listpack 会执行以下步骤：
1、将3占用的空间标记为可用，并将后续的元素4和5向前移动，填补空缺。
2、最终的listpack变为：
[1, 2, 2.5, 4, 5]
（3）、Listpack工作原理
listpack的核心思想是通过变长编码来存储数据，并且尽量减少内存开销。以下是 listpack 的一些关键技术细节：
- 变长整数编码：listpack使用变长整数编码（如LEB128编码）来存储整数。LEB128是一种高效的编码方式，能够根据整数的大小动态调整所需的字节数。例如，小整数（如0到127）只需要1个字节，而较大的整数则需要更多字节。这种编码方式大大减少了整数的存储空间。
- 浮点数编码：对于浮点数，listpack使用IEEE 754标准的二进制表示法来存储。它可以根据浮点数的精度选择合适的编码方式，以减少存储空间。
- 字符串编码：对于字符串，listpack使用前缀压缩技术来减少重复字符串的存储空间。如果两个相邻的字符串有相同的前缀，listpack只会存储一次前缀，并在后续的字符串中引用该前缀。这种技术特别适用于存储大量相似的字符串。
- 局部重排：当插入或删除元素时，listpack会尽量保持数据的紧凑性，避免频繁的内存分配和释放。它通过局部重排（即将新元素插入到合适的位置，并调整相邻元素的存储位置）来减少内存碎片。
（4）、Listpack优化内存对齐
因为Redis是基于内存的，所以内存大小对Redis来说是最宝贵的。Listpack通过变长编码，大大节省了内存对齐造成的额外开销，但同时也会对操作系统的读取造成一定的性能问题。那么Redis又是怎么优化操作系统读取元素的呢？
1、Listpack存储虽然没有内存对齐，但数据是紧凑的，大大节省了内存空间。同时，紧凑的数据能够充分利用 CPU 缓存，减少CPU指针偏移的消耗，减少内存访问延迟。
2、每个字段都有一个长度前缀，表示该字段的实际长度。通过预读长度前缀，Redis 可以快速跳过未对齐的数据项，而不需要逐个字节地解析。
还是该示例：
struct Example {
char a; // 1 字节
int b; // 4 字节
char c; // 1 字节
};
ListPack的内存模型如下：每个空间内的第一个元素实际都是该字段的长度（如下红色圈出的部分）
简单理解下：
如果需要读取整数int b，int是4个字节，Redis仅读取长度就会发现只有第二个空间的内存是4的倍数，就不会读取a和c的变量了。
（5）、Listpack优势
- 更高的内存利用率：listpack 通过变长编码和无内存对齐的设计，显著减少了内存开销，尤其是在处理小规模数据时表现尤为明显。
- 更好的性能：listpack 优化了插入和删除操作，特别是在处理大量小元素时，性能优于 ziplist。它通过局部重排减少了内存分配和释放的频率，提高了操作效率。
- 简化实现：listpack 的设计更加简洁，减少了代码复杂度，使得维护和优化变得更加容易。
- 兼容性：listpack 与 ziplist 具有良好的兼容性，现有的 Redis 数据结构可以无缝迁移到 listpack，而不会影响现有功能。
（6）、Listpack应用场景
- 小规模数据存储：listpack在处理小规模数据时表现出色，能够显著减少内存占用并提高性能。它特别适用于List、Hash、Set和Sorted Set等数据类型的内部存储。
- 频繁的插入和删除操作：listpack优化了插入和删除操作，特别是在处理大量小元素时，性能优于ziplist。它通过局部重排减少了内存分配和释放的频率，提高了操作效率。
（7）、Listpack与Ziplist的对比
（8）、Listpack总结
Listpack是Redis 6.2 版本引入的一种新的数据结构，旨在替代ziplist，提供更好的内存利用率和性能。它通过变长编码、无内存对齐、局部重排等技术，显著减少了内存开销，并优化了插入和删除操作的性能。listpack特别适合处理小规模数据和频繁的插入删除操作，能够在内存敏感的应用场景中表现出色。
学海无涯苦作舟！！！
