listpack

listpack 编码为单个线性内存块。它有一个固定长度的六字节头部（而不是 ziplist 的十个字节，因为我们不再需要指向最后一个元素开始的指针）。头部后面跟着 listpack 元素。理论上，数据结构不需要任何终止符，然而出于某些考虑，提供了一个特殊的条目来标记 listpack 的结束，形式为一个值 FF（255）的单字节。终止符的主要优点是可以在不保留（并在每次迭代中比较）listpack 结束地址的情况下扫描 listpack，并且可以轻松地识别 listpack 是否良好形成或截断。这些优点在作者看来是值得在表示中额外使用的字节的。

<tot-bytes> <num-elements> <element-1> ... <element-N> <listpack-end-byte>

由 tot-bytes 和 num-elements 字段组成的六个字节头部按以下方式编码

• tot-bytes: 32 位无符号整数，表示 listpack 的总字节数。包括头部本身和终止符。这基本上是存储 listpack 所需的总分配大小，允许在需要时跳到末尾，以便从最后一个元素到第一个元素反向扫描 listpack。
• num-elements: 16 位无符号整数，表示 listpack 包含的总元素数。然而，如果此字段设置为 65535，这是 16 位中可以表示的最大无符号整数，这意味着 listpack 元素的数目是未知的，因此需要完全扫描 listpack 才能进行 LIST-LENGTH 操作。当 listpack 在某个时刻具有等于或大于 65535 个元素时，会发生这种情况。当 LIST-LENGTH 操作首次检测到可表示范围内的元素计数时，num-elements 字段将再次设置为较低的数量。

除非另有说明，listpack 中的所有整数都以小端格式存储（某些特殊编码以大端格式存储，因为以这种方式表示它们对于将规范映射到 C 代码来说更自然）。

为了查看 Redis 的另一个数据结构瑰宝，请查看用于替换 B-树和 HashMap 的 Radix Tree "Rax"。

Redis 中使用的 Radix Tree "Rax" 带到 Rust

用法

extern crate libc;
extern crate listpack;

use libc;
use listpack;
use listpack::{Listpack, Value};

fn main() {
    // Optionally use different memory allocator
    // Internally defaults to malloc in libc.
    patch_allocator();
    
    let mut lp = Listpack::new();
    
    {
        // Internally it's either Int or Str.

        lp.append_int(100);         // Compressed Int
        lp.append_str("hello");     // Str
        lp.append_str(100);         // Binary integer representation
        
        // Use the Raw Value type
        lp.append(Value::Int(1)); // Int
        let my_str = "hello";
        lp.append(Value::Str(my_str.as_ptr(), mystr.len())); // Str - Raw Pointer
        
        // Work with the primitive helpers.
        // get_xx ->            i8, u8, i16, u16, i32, u32, i64, u64, i128, u128, f32, f64, isize, usize
        // append_xx ->         i8, u8, i16, u16, i32, u32, i64, u64, i128, u128, f32, f64, isize, usize
        // append_xx_fixed ->   i8, u8, i16, u16, i32, u32, i64, u64, i128, u128, f32, f64, isize, usize
        
        // Example with u64...
        lp.append_u64(10);          // Represented as compressed Int type
                                    // This will only be 2 bytes total in the listpack
        lp.append_u64_fixed(10);    // Represented as 8byte binary type
        
        // Automatically converts regardless whether it was
        // encoded in compressed format or in it's full
        // binary representation.
        let my_u64 = lp.get_u64(element);
    }
    
    {
        // Seek element by index.
        let index = 1;
        let element = lp.seek(index);
        
        // Get the value
        let value = lp.get(element);
        let value_int = lp.get_int(element);
        let value_str = lp.get_str(element);
        let value_int_u64 = lp.get_u64(element);
        // get_xx -> i8, u8, i16, u16, i32, u32, i64, u64, i128, u128, f32, f64, isize, usize
        
        // Replace values
        lp.replace(element, Value::Int(2));
        // Delete element
        lp.delete(element);
    }
    
    

    println!("Iterate forward...");
    let mut ele = lp.start();
    while let Some(v) = lp.first_or_next(ele) {
        ele = v;
        let val = lp.get(ele);
        match val {
            Value::Int(v) => {
                println!("Int     -> {}", v);
            }
            Value::Str(_v, _len) => {
                println!("String  -> {}", val.as_str());
            }
        }
    }

    println!();
    println!("Iterate backward...");
    let mut ele = lp.start();
    while let Some(v) = lp.last_or_prev(ele) {
        ele = v;
        let val = lp.get(ele);
        match val {
            Value::Int(v) => {
                println!("Int     -> {}", v);
            }
            Value::Str(_v, _len) => {
                println!("String  -> {}", val.as_str());
            }
        }
    }
    
    println!();
    println!("Bytes:            {}", lp.size());
    println!("Length:           {}", lp.len());
    println!("Bytes / Element:  {}", (lp.size() - 6) as f32 / lp.len() as f32); // 6byte listpack header
}

fn patch_allocator() {
    // Can hook memory allocator to control the internal heap allocations.
    // All memory is reclaimed when listpack leaves scope automatically
    // through the Drop trait.
    unsafe {
        listpack::set_allocator(
            lp_malloc_hook,
            lp_realloc_hook,
            lp_free_hook,
        );
    }
}

extern "C" fn lp_malloc_hook(size: libc::size_t) -> *mut u8 {
    unsafe {
        println!("malloc");
        libc::malloc(size) as *mut u8
    }
}

extern "C" fn lp_realloc_hook(ptr: *mut libc::c_void, size: libc::size_t) -> *mut u8 {
    unsafe {
        println!("realloc");
        libc::realloc(ptr, size) as *mut u8
    }
}

extern "C" fn lp_free_hook(ptr: *mut libc::c_void) {
    unsafe {
        println!("free");
        libc::free(ptr)
    }
}

Listpack 规范

Version 1.0, 1 Feb 2017: Intial specification.

Version 1.1, 2 Feb 2017: Integer encoding simplified. Appendix A added.

Version 1.2, 3 Feb 2017: Better specify the meaning of the num-elements
                         field with value of 65535. The two 12 bits
                         positive/negative integers encodings were
                         replaced by a single 13 bit signed integer.
                         Crash resistance better specified.
                         (Thanks to Oran Agra for all the hints).

Salvatore Sanfilippo
Yuval Inbar
Oran Agra

自Redis开发初期，优化内存使用一直是重要考虑。可扩展的数据结构通常由节点（堆分配的内存块）组成，节点包含指向其他节点的引用（指针）。这种表示方式虽然可以很好地随着数据结构中元素数量的增加而扩展，但非常浪费：如果平均元素大小较小，元数据很容易占据内存空间的50%。然而，当数据结构用于存储非常少量的元素时，可以切换到不同的、更紧凑的表示方式。由于交替表示使用的元素数量是固定的且较小，数据结构的时间复杂度相同。此外，即使需要完整扫描元素以访问或修改数据结构，处理少量元素这种紧凑表示的常数时间也很好地被顺序访问字节线性数组时的缓存局部性所补偿。这允许节省内存，同时一旦达到给定最大尺寸，就可以透明地切换到链式表示。

传统上，Redis为了压缩少量元素的哈希表、列表和有序集合，使用了一种名为ziplist的数据结构。ziplist基本上是一个包含字符串元素列表的单个堆分配内存块。它可以用来表示通过交替键和值表示的映射，或有序元素列表。多年来，ziplist数据结构为我们提供了很好的服务，然而最近一位用户报告在访问ziplist时发生崩溃。这个错误发生在最新一代纠错内存模块中，而RDB文件由CRC64校验和保护。因此，我们开始调查，以发现ziplist.c文件中的错误。

经过几周的工作，我（Salvatore）分析发现了一个与用户崩溃无关的错误。Oran Agra和Yuval Inbar，也是本规范的贡献者，加入了代码审计的努力。Salvatore还编写了几个模糊测试工具，以模拟用户数据的布局。即使使用的模糊测试技术可以轻易地找到分析发现的非常复杂的难以复制的错误，但在使用Hash数据类型时，即用户报告的崩溃期间使用的数据类型，从未看到崩溃。

即使从表面上看ziplist.c似乎不包含错误，或者至少我们无法找到它们，也没有经常有关代码这部分潜在错误的崩溃报告，但在审查过程中，所有涉及的程序员都同意，ziplist代码非常复杂，并且具有非平凡的副作用，因此切换到其他东西是一个明智的想法。之所以难以审计，是因为ziplist具有以下布局

<header> <entry> <entry> ... <entry> <end-of-ziplist>

然而，对于Redis来说，重要的是能够向后访问ziplist，从最后一个元素到第一个元素，以便以避免扫描整个ziplist仅获取尾部几个元素的方式模拟LRANGE等命令。因此，每个条目实际上由以下两部分组成

<previous-entry-length> <entry-data>

前一个条目长度可以从1到5字节变化，以便使用少量的空间来编码小的前一个条目长度。然而，在中间插入或删除元素时，使用这种特定的编码可能会产生级联效应，前一个长度甚至前一个长度编码的字节数可能会改变，并且可能会级联到下一个元素。这是ziplist复杂性的主要来源。然而，其他替代实现可以防止这个问题，并且只为每个条目使用局部信息。

listpack借鉴了ziplist的优良思想，并重新实现以创建一个更紧凑、更易于解析的实现，它直接映射到易于审计和理解的代码。此外，listpack中的单个条目表示被重新设计，以更好地利用Redis用户通常存储在列表和哈希中的数据类型。本文档描述了新格式。

总体结构

listpack 编码为单个线性内存块。它有一个固定长度的六字节头部（而不是 ziplist 的十个字节，因为我们不再需要指向最后一个元素开始的指针）。头部后面跟着 listpack 元素。理论上，数据结构不需要任何终止符，然而出于某些考虑，提供了一个特殊的条目来标记 listpack 的结束，形式为一个值 FF（255）的单字节。终止符的主要优点是可以在不保留（并在每次迭代中比较）listpack 结束地址的情况下扫描 listpack，并且可以轻松地识别 listpack 是否良好形成或截断。这些优点在作者看来是值得在表示中额外使用的字节的。

<tot-bytes> <num-elements> <element-1> ... <element-N> <listpack-end-byte>

由 tot-bytes 和 num-elements 字段组成的六个字节头部按以下方式编码

• tot-bytes: 32 位无符号整数，表示 listpack 的总字节数。包括头部本身和终止符。这基本上是存储 listpack 所需的总分配大小，允许在需要时跳到末尾，以便从最后一个元素到第一个元素反向扫描 listpack。
• num-elements: 16 位无符号整数，表示 listpack 包含的总元素数。然而，如果此字段设置为 65535，这是 16 位中可以表示的最大无符号整数，这意味着 listpack 元素的数目是未知的，因此需要完全扫描 listpack 才能进行 LIST-LENGTH 操作。当 listpack 在某个时刻具有等于或大于 65535 个元素时，会发生这种情况。当 LIST-LENGTH 操作首次检测到可表示范围内的元素计数时，num-elements 字段将再次设置为较低的数量。

除非另有说明，listpack 中的所有整数都以小端格式存储（某些特殊编码以大端格式存储，因为以这种方式表示它们对于将规范映射到 C 代码来说更自然）。

元素表示

列表包中的每个元素都具有以下结构

<encoding-type><element-data><element-tot-len>
|                                            |
+--------------------------------------------+
            (This is an element)

元素类型和元素总长度始终存在。元素数据有时可能缺失，因为某些小型元素直接表示在编码类型的预留位中。

编码类型基本上用于理解随后跟随的数据类型，因为字符串可以编码为小端整数，并且字符串可以包含多个字符串长度字段位以减少空间使用。元素数据是实际数据本身，如整数或表示字符串的字节序列。最后，元素总长度用于从列表包的末尾向头部遍历列表，并且由于否则无法以唯一的方式从右到左解析条目，因此需要能够跳转到指定字节数的左侧。

每个元素都可以从左到右解析。第一个字节的第一个两位选择编码。总共有3种可能性。前两种编码表示小字符串。第三种编码用于指定其他子编码。

小数

可以表示为小数字符串的字符串（如"65"或"1"）非常常见，因此它们有特殊的编码，允许将表示从0到127的数字的字符串指定为单字节。

0|xxxxxxx

其中xxxxxxx是一个7位无符号整数。我们可以通过检查条目第一个字节的最高位是否为零来测试这种编码。

一些示例

"\x03" -- The string "3"
"\x12" -- The string "18"

微型字符串

小字符串也是Redis集合中对象内部非常常见的元素，因此指定它们的长度只需一个字节的开销。

10|xxxxxx <string-data>

此编码表示长度最多为63个字符的字符串，因为xxxxxx是一个6位无符号整数。字符串数据是逐字节字符串本身，在空字符串的特殊情况下可能缺失。

一些示例

"\x40" -- The empty string
"\x45hello" -- The string "hello"

多字节编码

如果第一个字节的最高两位都设置为1，则剩余位选择以下子编码之一。

当第一个两位都是"11"但后续位永远不会是"11"时发生前三种子编码。

110|xxxxx yyyyyyyy -- 13 bit signed integer
1110|xxxx yyyyyyyy -- string with length up to 4095

在此编码中，xxxx|yyyyyyyy表示一个无符号整数，其中xxxx是最重要的位，而yyyyyyyy是最不重要的位。

最后，当第一个四位都设置为1时，定义了由剩余四位表示的以下子编码

1111|0000 <4 bytes len> <large string>
1111|0001 <16 bits signed integer>
1111|0010 <24 bits signed integer>
1111|0011 <32 bits signed integer>
1111|0100 <64 bits signed integer>
1111|0101 to 1111|1110 are currently not used.
1111|1111 End of listpack

元素总长度字段

如前所述，条目的最后一部分是其自身大小的表示，因此列表包可以从右向左遍历。此字段具有可变长度，因此如果字段长度较小，则仅使用一个字节，对于更大的条目则逐渐使用更多的字节。总长度字段设计为从右到左解析，因为我们就是这样使用它的，不能从左到右解析。然而，当我们从左到右解析条目时，在需要解析总长度字段时我们已知道其长度，因此我们可以计算使用可变编码表示其总长度字段所需的字节数。这允许我们只需跳过这么多字节而无需尝试解析它。我们将在此节的后面通过示例使它更加清晰。

变量长度是从右到左存储的，每个字节的最高位用来指示是否有更多的字节。这意味着我们每个字节只使用7位。小于128的条目长度可以直接编码为8位无符号整数，表示条目值。

"\x20" -- 32 bytes entry length

然而，如果我想编码一个值为，例如，500的条目长度，则需要两个字节。500的二进制表示如下

111110100

我们可以将表示分为两个7位的半部分

0000011 1110100

注意，由于我们是自右向左解析条目长度，条目是以大端方式存储的（但这并不是标准的大端，因为只使用了7位，而第8位用来指示是否有更多字节的条件）。

然而，我们还需要添加一个位来指示是否有更多字节，因此最终的表示将是

[0]0000011          [1]1110100
 |                   |
 `- no more bytes    `- more bytes to the left!

实际的编码将是

"\xf4\x03" -- 500 bytes entry length

让我们以一个非常简单的条目编码字符串"hello"为例

"\x45hello" -- The string "hello"

原始条目是6个字节：编码字节后跟原始数据。为了使条目完整，我们需要在末尾添加条目长度字段，在这个例子中只是字节"06"。因此，最终的完整条目将是

"\x45hello\x06" -- A complete entry representing "hello"

请注意，我们可以很容易地从右到左解析条目，通过读取长度6，然后在左边跳过6个字节以到达条目的开始，但也可以从左到右解析条目，因为在我们解析了6个字节的条目数据之后，我们知道用来编码其长度的字节数，可以使用以下表格

From 0 to 127: 1 byte
From 128 to 16383): 2 bytes
From 16383 to 2097151: 3 bytes
From 2097151 to 268435455: 4 bytes
From 268435455 to 34359738367: 5 bytes

没有条目可以超过34359738367字节。

实现要求

关于实现的需求，按重要性递减的顺序如下

1. 抵抗错误编码的崩溃。这在ziplist实现中并不是这样。
2. 易于理解和审计。有良好注释的代码。
3. 快速。避免不必要的复制。例如，当添加到头部时，检测realloc()是否为非OP（当有高级malloc功能可用时），然后使用malloc()并直接在正确偏移处复制数据以避免复制数据。
4. 提供更新元素操作，以便如果元素以相同大小更新（与哈希一起使用时非常常见，例如HINCRBY），则不涉及内存复制。

关于可理解性的说明

请注意，没有设计简单性，就无法获得可理解性。然而，本文件中概述的设计被认为可以简单且稳健地转换为实现。

关于崩溃抵抗的说明

值得注意的是，崩溃抵抗有限：例如，损坏的listpack头可能使程序跳转到无效地址。在此上下文中，对于崩溃抵抗，我们指的是，只要损坏不会迫使程序跳转到非法地址，就可以在可能的情况下检测到错误编码（即，当损坏不意外地映射到有效条目时）。例如，每当listpack中剩余的字节数与宣布的字符串长度不兼容时，就会检测到错误的字符串长度。API应始终能够报告此类错误，而不是使程序崩溃。

致谢

本规范由Salvatore Sanfilippo编写。Oran Agra和Yuval Inbar，以及本规范的作者一起分析了ziplist实现，以寻找错误并了解规范如何得到改进。

Yuval提出了使用仅限于条目本身的信息（条目长度在条目末尾）来允许向后遍历，而不是使用全局信息（如前一个条目的长度，如ziplist中所做的那样）的想法。

Yuval还建议使用渐进长度整数作为向后长度的表示。

Oran提供了关于实现优化的想法。

附录A：未利用的潜在优化

为了增强数据结构的简洁性，我们在这份规范中省略了一些改进。

正整数和负整数的不同编码。

理论上，我们可以更好地利用额外的编码类型位，以区分正整数和负整数，并且总是以无符号形式表示它们。这样，我们可以改善用给定字节数表示的整数范围。这份规范的前一个版本使用了以下编码

1111|0001 <16 bits unsigned integer>
1111|0010 <16 bits negative integer>
1111|0011 <24 bits unsigned integer>
1111|0100 <24 bits negative integer>
1111|0101 <32 bits unsigned integer>
1111|0110 <32 bits negative integer>
1111|0111 <64 bits unsigned integer>
1111|1000 <64 bits negative integer>

然而，经过进一步思考，这被认为会使实现更加复杂且可能更慢，因此选择了稍微低效的存储有符号整数的表示方式。

紧凑字符

列表包中的许多元素将使用范围 A-z 中的字符子集。例如，诸如 name、surname 等字符串。

使用每个字符六个位，可以表示所有大小写字母、从0到9的数字以及一些额外的字符，如 -、_、.。因此，可以通过每个字符六个位的额外编码来表示字符串，从而大大提高字符串的空间效率。

这主要不是出于性能考虑，因为增加的复杂性被认为是可管理的，并且不太可能是潜在错误的来源。

跳过索引

访问长列表包中的远端元素是O(N)，因此添加一些方法以加快此类查找似乎是自然而然的。虽然这对于很少更改的打包数据表示通常是个好主意，但列表包将在数据经常在中间更改的情况下使用（Redis Hash和List数据类型都强调了这种使用模式）。

更新跳过索引可能会出错，甚至代价高昂，并且使用默认设置，Redis只使用相对较小的列表包，其中访问局部性很好地补偿了扫描的需求。

当需要内存节省的表示，并且能够扩展到许多元素时，作者认为使用列表包作为节点链接的数据结构是首选方法：它改善了两种表示之间的关注点分离，并且可能更容易管理。在这方面，列表包非常友好，因为它们可以通过线性复制轻松分割和合并，无需调整偏移量。