Redis使用的底层数据结构是什么？

我试图在一个确定的列表中回答两个问题：

1. Redis使用的底层数据结构是什么？
2. 每种types的主要优点/缺点/用例是什么？

所以，我读过Redis列表实际上是用链表实现的。 但对于其他types，我无法挖掘任何信息。 另外，如果有人偶然发现了这个问题，而且没有对修改或访问不同数据结构的优缺点进行高层次的总结，那么他们也会有一个完整的清单， 以便最好地使用特定的types来引用。

具体来说，我正在寻找概述所有types：string，列表，集，zset和哈希。

哦，到目前为止，我已经看过这些文章：

• http://redis.io/topics/data-types
• http://redis.io/topics/data-types-intro
• http://redis.io/topics/faq

Answer 1

我会尽量回答你的问题，但是我会先从一些看起来很奇怪的事情开始：如果你对Redis内部没有兴趣，你不应该关心数据types是如何在内部实现的。 这是一个简单的原因：对于每一个Redis操作，你会发现文档中的时间复杂度，如果你有一套操作和时间复杂度，你唯一需要的就是关于内存使用的一些线索（因为我们做了很多优化，这可能会根据数据而有所不同，获得这些数字的最好方法是做一些简单的现实世界testing）。

但是，既然你问了，这是每个Redis数据types的底层实现。

• string是使用Cdynamicstring库实现的，所以我们不会为了附加操作中的分配而支付（渐近地说）。 这样，我们有O（N）追加，而不是二次行为。
• 列表是用链表实现的。
• 集合和散列是用散列表实现的。
• sorting集是用跳过列表 （一种特殊types的平衡树）实现的。

但是，当列表，集合和sorting集的项目数量和最大值的大小都很小时，就会使用不同的更紧凑的编码。 这种编码对于不同的types有所不同，但是具有这样一个特点：它是一个紧凑的数据块，经常强制每个操作进行O（N）扫描。 由于我们只将这种格式用于小对象，这不是问题; 扫描一个小的O（N）blob是不知道caching的，所以实际上它非常快，而当元素太多时，编码自动切换到本地编码（链表，散列等等）。

但是你的问题并不仅仅是内部的问题，你的观点是用什么types来完成什么？ 。

string

这是所有types的基本types。 它是四种types之一，但也是复杂types的基本types，因为List是一个string列表，一个Set是一组string，依此类推。

在所有想要存储HTML页面的显而易见的场景中，Redisstring都是一个好主意，但是也可以避免转换已经编码过的数据。 所以举个例子，如果你有JSON或者MessagePack，你可以把对象存储为string。 在Redis 2.6中，您甚至可以使用Lua脚本来操作这种对象服务器端。

string的另一个有趣用法是位图，通常是字节的随机访问数组，因为Redis会导出命令来访问随机范围的字节，甚至是单个位。 例如检查这个好博客文章：使用Redis快速简单的实时指标 。

清单

当你可能只触及列表的极端时，列表是好的：靠近尾巴或靠近头部。 列表不是很好分页的东西，因为随机访问很慢，O（N）。 如此好的列表使用是普通队列和堆栈，或者使用具有相同源和目的地的RPOPLPUSH来循环处理项目，以“旋转”项目环。

当我们只想创buildN个项目的上限集合时，列表也是好的， 通常我们只能访问顶部或底部的项目，或者当N很小时。

集

集合是一个无序的数据集合，所以每当你有一个项目的集合，它们是很好的，检查集合的存在或大小是非常重要的，以非常快的方式。 另一个很酷的事情是支持窥视或popup随机元素（SRANDMEMBER和SPOP命令）。

集合也很好地代表关系，例如，“用户X的朋友是什么？” 等等。 但是我们将会看到，这种东西的其他好数据结构是有序集合。

集支持复杂的操作，如交叉点，联合等，所以这是一个很好的数据结构，以“计算”的方式使用Redis，当你有数据，你想对这些数据进行转换来获得一些输出。

小集合以非常有效的方式进行编码。

哈希

哈希是表示由字段和值组成的对象的完美数据结构。 哈希的字段也可以使用HINCRBY以primefaces方式递增。 当你拥有诸如用户，博客文章或其他types的项目的对象时 ，如果你不想使用自己的编码（比如JSON或类似的），哈希可能就是要走的路。

但是请记住，Redis非常有效地编码小哈希值，并且可以让Redis以非常快速的方式自动获取，设置或增加单个字段。

哈希也可以用来表示链接的数据结构，使用引用。 例如检查lamernews.com的评论实施。

sorting集

sorting集是唯一的其他数据结构，除了列表以外，维护有序的元素 。 你可以用有序集合做很多很酷的事情。 例如，您可以在Web应用程序中包含各种Top Something列表。 顶级用户评分，顶级页面浏览，顶级用户，而单个Redis实例将支持每秒大量的插入和get-top-elements操作。

与常规集合一样，sorting集合可用于描述关系，但它们也允许您对项目列表进行分页并记住sorting。 例如，如果我记住用户X的朋友与一个有序的集合，我可以很容易地记住他们接受友谊的顺序。

sorting集适合优先级队列。

sorting集就像更强大的列表，其中从列表中间插入，删除或获取范围总是很快。 但是他们使用更多的内存，并且是O（log（N））数据结构。

结论

我希望我在这篇文章中提供了一些信息，但是从http://github.com/antirez/lamernews下载lamernews的源代码并理解它是如何工作的会好得多。; 来自Redis的许多数据结构都在Lamer News中使用，并且有许多关于如何使用来解决特定任务的线索。

对不起语法错别字，现在是午夜，太累了查看post;）

Answer 2

大多数情况下，您不需要了解Redis使用的基础数据结构。 但是有一点知识可以帮助您使CPU v / s内存权衡。 它还可以帮助您以有效的方式build模您的数据。

在内部，Redis使用以下数据结构：

1. 串
2. 字典
3. 双链表
4. 跳过列表
5. 邮编列表
6. Int集
7. Zip地图（自Redis 2.6开始弃用Zip列表）

要查找特定密钥使用的object encoding <key> ，请使用命令object encoding <key> 。

1.string

在Redis中，string被称为简单dynamicstring，或SDS 。 这是一个小小的char *封装，允许您将string的长度和空闲字节的数量作为前缀存储。

由于string的长度是存储的， strlen是一个O（1）操作。 另外，由于长度已知，Redisstring是二进制安全的。 包含空字符的string是完全合法的。

string是Redis中最通用的数据结构。 string是以下所有内容：

1. 可以存储文本的string。 请参阅SET和GET命令。
2. 一个可以存储二进制数据的字节数组。
3. long可以存储数字。 请参阅INCR ， DECR ， INCRBY和DECRBY命令。
4. 可以允许高效的随机访问的数组（ chars ， ints ， longs ints或任何其他数据types）。 请参阅SETRANGE和GETRANGE命令。
5. 一个位数组 ，允许您设置或获取单个位。 请参阅SETBIT和GETBIT命令。
6. 一块可用于构build其他数据结构的内存块。 这在内部用于构buildziplists和intset，它们是用于less量元素的紧凑，高效的内存数据结构。 更多关于这个下面。

2.字典

Redis使用以下字典 ：

1. 将键映射到其关联的值，其中值可以是string，散列，集合，sorting集合或列表。
2. 将密钥映射到其到期时间戳。
3. 实现哈希，设置和sorting设置数据types。
4. 将Redis命令映射到处理这些命令的函数。
5. 将Redis键映射到在该键上被阻止的客户端列表。 参见BLPOP 。

Redis字典是使用哈希表实现的。 我不会解释实现，而只是解释Redis具体的事情：

1. 字典使用称为dictType的结构来扩展哈希表的行为。 这个结构有函数指针，所以下面的操作是可扩展的：a）哈希函数，b）键比较，c）键析构函数，和d）值析构函数。
2. 字典使用murmurhash2 。 （以前他们使用djb2散列函数 ，其中seed = 5381，但是散列函数被转换为murmur2 。查看这个问题以获得对djb2散列algorithm的解释 。）
3. Redis使用增量哈希，也称为增量调整 。 字典有两个哈希表。 每次触摸字典时，一个桶将从第一个（较小的）哈希表迁移到第二个。 这样，Redis可以防止昂贵的resize操作。

Set数据结构使用Dictionary来保证没有重复。 Sorted Set使用字典将元素映射到其分数，这就是为什么ZSCORE是O（1）操作的原因。

3.双向链接列表

list数据types是使用双重链接列表实现的 。 Redis的实现是直接从algorithm教科书。 唯一的变化是Redis将这个长度存储在列表数据结构中。 这确保了LLEN具有O（1）的复杂性。

4.跳过列表

Redis使用跳过列表作为sorting集合的基础数据结构。 维基百科有一个很好的介绍。 William Pugh的论文Skip Lists：平衡树的概率替代方法有更多的细节。

sorting集使用跳过列表和词典。 字典存储每个元素的分数。

Redis的Skip List实现与标准实现有以下不同之处：

1. Redis允许重复的分数。 如果两个节点具有相同的分数， 则按字典顺序sorting 。
2. 每个节点都有一个位于级别0的后退指针。这允许您按照相反的顺序遍历元素。

5.邮编列表

一个Zip列表就像是一个双向链表，除了它不使用指针并将数据存储在内部。

双向链表中的每个节点都有3个指针 – 一个前向指针，一个后向指针和一个指向存储在该节点的数据的指针。 指针需要内存（64位系统上的8个字节），所以对于小列表来说，双向链表是非常低效的。

Zip List按顺序将元素存储在Redisstring中。 每个元素都有一个小标题，用来存储元素的长度和数据types，下一个元素的偏移量和前一个元素的偏移量。 这些偏移取代了前进和后退指针。 由于数据是以内联方式存储的，所以我们不需要数据指针。

Zip列表用于存储小列表，sorting集合和散列。 sorting的集合被[element1, score1, element2, score2, element3, score3]的列表并存储在Zip List中。 哈希被平化为一个列表，如[key1, value1, key2, value2]等

通过Zip列表，您可以在CPU和内存之间进行权衡。 Zip列表是内存有效的，但是它们比链表（或哈希表/跳过列表）使用更多的CPU。 在zip列表中查找元素是O（n）。 插入新元素需要重新分配内存。 正因为如此，Redis仅使用这种编码方式来处理小列表，哈希和有序集合。 您可以通过在<datatype>-max-ziplist-entries更改<datatype>-max-ziplist-entries和<datatype>-max-ziplist-value>的值来调整此行为。 有关更多信息，请参阅Redis内存优化，“小型聚合数据types的特殊编码”部分 。

对ziplist.c的评论非常好，你可以完全理解这个数据结构，而不必阅读代码。

6. Int集

Int集合是“Sorted Integer Arrays”的奇特名称。

在Redis中，集合通常使用散列表来实现。 对于小集合，散列表是低效率的记忆智慧。 当该集合仅由整数组成时，数组通常更高效。

一个Int Set是一个整数sorting的数组。 为了find使用二分searchalgorithm的元素。 这具有O（logN）的复杂度。 向这个数组添加新的整数可能需要一个内存重新分配，这对于大整数数组可能会变得很昂贵。

作为进一步的内存优化，Int集具有不同整数大小的3个变体：16位，32位和64位。 Redis足够聪明，可以根据元素的大小使用正确的变体。 当添加一个新元素并超过当前大小时，Redis会自动将其迁移到下一个大小。 如果添加了一个string，Redis会自动将Int集合转换为基于常规哈希表的集合。

Int集是CPU和内存之间的折中。 Int集具有极高的内存效率，对于小集，它们比散列表快。 但是在一定数量的元素之后，O（log N）的检索时间和重新分配内存的代价变得太大了。 基于实验，发现切换到常规哈希表的最佳阈值为512.但是，根据您的应用程序的需要，您可以增加此阈值（降低它没有意义）。 请参阅set-max-intset-entries 。

7.邮编地图

Zip地图是字典压平并存储在一个列表中。 它们与Zip列表非常相似。

从Redis 2.6开始，Zip Maps已经被弃用了，而且小的哈希值被存储在Zip列表中。 要了解更多关于此编码的信息，请参阅zipmap.c中的注释 。

Answer 3

Redis存储指向值的键。 密钥可以是任何二进制值，达到合理的大小（为便于阅读和debugging，build议使用短的ASCIIstring）。 值是五种本地Redis数据types之一。

1.strings – 一个高达512 MB的二进制安全字节序列

2.哈希 – 一组键值对

3.列表 – 一个插入顺序的string集合

4.sets – 一个没有sorting的唯一string的集合

5.sorted sets – 由用户定义的评分sorting的唯一string集合

string

Redisstring是一个字节序列。

Redis中的string是二进制安全的（意味着它们的长度不是由任何特殊的终止字符决定的），所以你可以在一个string中存储512兆字节的内容。

string是cannonical“键值存储”的概念。 您有一个指向值的键，其中键和值都是文本或二进制string。

对于所有可能的string操作，请参阅http://redis.io/commands/#string

哈希

Redis哈希是键值对的集合。

Redis哈希包含许多键值对，其中每个键和值都是一个string。 Redis哈希不直接支持复杂值（也就是说，不能有一个哈希字段有一个列表或集合或另一个哈希的值），但是您可以使用哈希字段来指向其他顶级复杂值。 您可以对散列字段值执行唯一的特殊操作是数字内容的primefaces增量/减量。

您可以通过两种方式来思考Redis哈希：作为一种直接的对象表示forms，以及一种紧凑地存储许多小值的方式。

直接对象表示很容易理解。 对象有一个名字（哈希键）和一个带有值的内部键集合。 看下面的例子，以及一个例子。

使用哈希存储很多小值是聪明的Redis海量数据存储技术。 当散列具有less量字段（〜100）时，Redis会优化整个散列的存储和访问效率。 Redis的小散列存储优化引发了一个有趣的行为：有100个散列，每个散列有100个内部键和值，而不是有10000个顶级键指向string值，这样更有效率。 使用Redis哈希来优化你的数据存储这种方式确实需要额外的编程开销来跟踪数据的结束位置，但是如果你的数据存储主要是基于string的，那么使用这个奇怪的技巧可以节省大量的内存开销。

对于散列上的所有可能的操作，请参阅散列文档

清单

Redis列表就像链接列表一样。

您可以插入，从列表的头部或尾部遍历列表，并从列表中删除列表。

当您需要按照插入顺序维护值时使用列表。 （如果需要，Redis会给你select插入到任意列表中的位置，但是如果插入远离你的开始位置，插入性能会降低。）

Redis列表通常用作生产者/消费者队列。 将项目插入列表中，然后从列表中popup项目。 如果消费者尝试从没有元素的列表中popup，会发生什么？ 您可以要求Redis等待元素出现，并在添加元素后立即将其返回给您。 这将Redis转变为实时消息队列/事件/作业/任务/通知系统。

您可以自动从列表的任一端删除元素，使任何列表都被视为堆栈或队列。

您也可以在每次插入后将列表修剪为特定大小，以维护固定长度列表（封顶的集合）。

对于列表中所有可能的操作，请参阅列表文档

集

Redis集合就是集合。

Redis集包含唯一的无序Redisstring，其中每个string仅在每个集合中存在一次。 如果将相同的元素添加到集合中，则只会显示一次。 集合非常适合懒惰地确保至less存在一次，而不用担心重复的元素累积和浪费空间。 您可以根据需要多次添加相同的string，而无需检查它是否已经存在。

集合中的成员检查，插入和删除的速度非常快。

如您所期望的那样，集合具有有效的集合操作。 您可以一次取多个组合，交集，差异。 可以将结果返回给调用者，也可以将结果存储在新的集合中供以后使用。

集合有恒定的时间访问成员资格检查（不像列表），而且Redis甚至有方便的随机成员移除和返回（“从集合中popup一个随机元素”）或随机成员返回没有replace（“给我30随机ish唯一用户“）或更换（”给我7张卡，但每次select后，把卡放回来，因此可能会再次采样“）。

对于所有可能的操作集，请参阅集文档 。

sorting集

Redissorting集是用户定义的sorting集。

为了简单起见，您可以将sorting后的集合看作具有独特元素的二叉树。 （Redissorting集实际上是跳过列表 。）元素的sorting顺序由每个元素的分数定义。

sorting集仍然是集合。 元素只能在一个集合中出现一次。 为了唯一性目的，元素由其string内容定义。 将sorting分数为3的元素“苹果”插入，然后将sorting分数为500的元素“苹果”插入，得到sorting集合中sorting分数为500的一个元素“苹果”。 集合仅基于数据而不是基于（分数，数据）对。

确保您的数据模型依赖于string内容而不是元素的唯一性分数。 得分可以重复（甚至为零），但最后一次，set元素只能在每个有序集合中存在一次。 例如，如果您尝试将每个用户login的历史logging存储为已sorting的集合，则将login的分数设为login的时间，并将值设为用户标识，则最终只会为所有用户保存上次login时间。 你的设置将会增加到你的用户基的大小，而不是你想要的用户基数*login的大小。

元素添加到您的设置与分数。 您可以随时更新任何元素的分数，只需再添加一个新分数的元素。 分数由浮点双精度表示，因此您可以根据需要指定高精度时间戳的粒度。 多个元素可能具有相同的分数。

您可以通过几种不同的方式检索元素。 由于所有东西都是sorting的，你可以要求从最低分开始的元素。 你可以要求从最高分数开始的元素（“反向”）。 您可以按自然顺序或相反顺序通过sorting得分来请求元素。

对于有序集合上的所有可能的操作，请参阅sorting集文档。