首页 文章

Redis使用的基础数据结构是什么？

提问于
浏览 次
288

我想在一个明确的清单中回答两个问题：

  • Redis使用的基础数据结构是什么？

  • 每种类型的主要优点/缺点/用例有哪些？

所以，我've read the Redis lists are actually implemented with linked lists. But for other types, I'm无法挖掘任何信息 . 此外，如果有人偶然发现了这个问题并且没有对修改或访问不同数据结构的优缺点进行高级概述，那么他们也会有一个完整的参考列表 when to best use specific types .

具体来说，我想概述所有类型：字符串，列表，集，zset和哈希 .

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

algorithm data-structures redis

3 回答

  • 76

    我首先会看到一些可能看起来很奇怪的东西：如果你对Redis内部不感兴趣，那么 should not care 关于数据类型如何在内部实现 . 这是一个简单的原因：对于每个Redis操作，您都会在文档中找到时间复杂度，如果您有一组操作和时间复杂度，您需要的唯一其他内容是关于内存使用的一些线索（并且因为我们做了许多可能因数据而异的优化，获得后面这些数字的最佳方法是进行一些简单的实际测试 .

    但是既然你问过，这里是每个Redis数据类型的底层实现 .

    • Strings 是使用C动态字符串库实现的，这样我们就不会为追加操作中的分配付费（渐态） . 这样我们就可以添加O（N），而不是具有二次行为 .

    • Lists 使用链接列表实现 .

    • Sets 和 Hashes 使用哈希表实现 .

    • Sorted sets 用skip lists（一种特殊类型的 balancer 树）实现 .

    但是，当列表，集合和有序集合的项目数量和最大值的大小较小时，使用不同的，更紧凑的编码 . 这种编码因不同类型而异，但其特点是它是一个紧凑的数据块，通常会对每个操作强制执行O（N）扫描 . 由于我们仅将此格式用于小型对象，因此这不是问题;扫描一个小的O（N）blob是缓存不经意，所以实际上它非常快，当有太多元素时，编码会自动切换到本机编码（链表，哈希等） .

    但你的问题并不仅仅是关于内部，你的观点是用什么类型来完成什么？

    字符串

    这是所有类型的基本类型 . 它是四种类型中的一种，但也是复杂类型的基本类型，因为List是字符串列表，Set是一组字符串，依此类推 .

    在您想要存储HTML页面的所有明显场景中，Redis字符串都是一个好主意，但是当您想要避免转换已编码的数据时也是如此 . 因此，例如，如果您有JSON或MessagePack，则可以将对象存储为字符串 . 在Redis 2.6中，您甚至可以使用Lua脚本操作此类对象服务器端 .

    字符串的另一个有趣用法是位图，并且通常是字节的随机访问数组，因为Redis导出命令以访问字节的随机范围，甚至是单个位 . 例如，检查this good blog post: Fast Easy real time metrics using Redis .

    列表

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

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

    集

    集合是一个无序的数据集合，因此每次有一组项目时它们都很好，并且以非常快的方式检查集合的存在或大小非常重要 . 关于集合的另一个很酷的事情是支持窥视或弹出随机元素（SRANDMEMBER和SPOP命令） .

    集合也可以很好地表示关系，例如“什么是用户X的朋友？”等等 . 但是，正如我们所看到的，这类东西的其他优秀数据结构都是有序集合 .

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

    小集以非常有效的方式编码 .

    哈希

    哈希是表示由字段和值组成的对象的完美数据结构 . 哈希字段也可以使用HINCRBY以原子方式递增 . 当您拥有诸如用户，博客帖子或其他类型项目之类的对象时，如果您不想使用自己的编码（如JSON或类似代码），则可能需要使用哈希 .

    但是，请记住，Redis会非常有效地编码小哈希，并且您可以要求Redis以非常快速的方式原子地获取，设置或增加单个字段 .

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

    排序集

    除了列表之外，排序集是唯一的其他数据结构，用于维护有序元素 . 你可以用排序集做很多很酷的东西 . 例如，您可以在Web应用程序中包含各种 Top Something 列表 . 按分数排名最高的用户，按浏览量排名靠前的帖子，顶部用户，但单个Redis实例每秒将支持大量的插入和get-top-elements操作 .

    排序集（如常规集）可用于描述关系，但它们还允许您对项列表进行分页并记住排序 . 例如，如果我记得用户X的朋友有一个排序的集合，我可以很容易地按照接受的友谊记住它们 .

    排序集适用于优先级队列 .

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

    结论

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

    对不起语法拼写错误，这是午夜，太累了，无法查看帖子;）

    回复于
  • 579

    大多数情况下，您不需要了解Redis使用的基础数据结构 . 但是一些知识可以帮助你进行CPU v / s内存折衷 . 它还可以帮助您以有效的方式建模数据 .

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

    • 字符串

    • 字典

    • 双重链表

    • 跳过清单

    • 邮编列表

    • Int集

    • Zip Maps（自Redis 2.6以来，不赞成使用zip列表）

    要查找特定键使用的编码，请使用命令 object encoding <key> .

    1.字符串

    在Redis中，字符串被称为Simple Dynamic Strings, or SDS . 它是 char * 的一个小包装器，它允许您将字符串的长度和空闲字节数存储为前缀 .

    由于存储了字符串的长度，strlen是O（1）操作 . 此外，因为长度是已知的，Redis字符串是二进制安全的 . 包含null character的字符串是完全合法的 .

    字符串是Redis中最通用的数据结构 . String是以下所有内容：

    • 可以存储文本的字符串 . 请参见SET和GET命令 .

    • 可以存储二进制数据的字节数组 .

    • A long 可以存储数字 . 请参见INCR，DECR，INCRBY和DECRBY命令 .

    • 的阵列（的 chars ， ints ， longs 或任何其他数据类型），其可允许有效的随机存取 . 请参阅SETRANGE和GETRANGE命令 .

    • A bit array允许您设置或获取单个位 . 请参阅SETBIT和GETBIT命令 .

    • 可用于构建其他数据结构的内存块 . 这在内部用于构建ziplists和intsets，它们是用于少量元素的紧凑，内存有效的数据结构 . 更多关于此的信息 .

    2.字典

    Redis使用Dictionary进行以下操作：

    • 将键映射到其关联值，其中value可以是字符串，散列，集，排序集或列表 .

    • 将密钥映射到其到期时间戳 .

    • 实现散列，设置和排序集数据类型 .

    • 将Redis命令映射到处理这些命令的函数 .

    • 将Redis密钥映射到该密钥上阻止的客户端列表 . 见BLPOP .

    Redis词典使用Hash Tables实现 . 我将解释Redis的具体内容，而不是解释实现事情：

    • 字典使用名为 dictType 的结构来扩展哈希表的行为 . 此结构具有函数指针，因此以下操作是可扩展的：a）散列函数，b）密钥比较，c）密钥析构函数，以及d）值析构函数 .

    • 字典使用murmurhash2 . （之前他们使用djb2 hash function，种子= 5381，但是哈希函数was switched to murmur2 . 请参阅this question for an explanation of the djb2 hash algorithm . ）

    • Redis使用Incremental Hashing，也称为Incremental Resizing . 该字典有两个哈希表 . 每次触摸字典时，一个存储桶从第一个（较小的）哈希表迁移到第二个 . 这样，Redis可以防止昂贵的调整大小操作 .

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

    3.双重链接列表

    list 数据类型使用Doubly Linked Lists实现 . Redis的实现是直接来自算法的教科书 . 唯一的变化是Redis将长度存储在列表数据结构中 . 这可确保LLEN具有O（1）复杂度 .

    4.跳过列表

    Redis使用Skip Lists作为排序集的基础数据结构 . 维基百科有一个很好的介绍 . William Pugh的论文Skip Lists: A Probabilistic Alternative to Balanced Trees有更多细节 .

    排序集使用“跳过列表”和“词典” . 字典存储每个元素的分数 .

    Redis的Skip List实现在以下方面与标准实现不同：

    • Redis允许重复分数 . 如果两个节点具有相同的分数，则它们按lexicographical order排序 .

    • 每个节点都有一个0级的后向指针 . 这允许您以与分数相反的顺序遍历元素 .

    5.邮编列表

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

    双向链表中的每个节点具有3个指针 - 一个前向指针，一个后向指针和一个指向存储在该节点处的数据的指针 . 指针需要内存（64位系统上为8个字节），因此对于小型列表，双向链表效率非常低 .

    Zip列表按顺序在Redis字符串中存储元素 . 每个元素都有一个小 Headers ，用于存储元素的长度和数据类型，到下一个元素的偏移量以及到前一个元素的偏移量 . 这些偏移取代了前向和后向指针 . 由于数据是内联存储的，因此我们不需要数据指针 .

    Zip列表用于存储小列表，有序集和散列 . 排序集被展平为 [element1, score1, element2, score2, element3, score3] 之类的列表并存储在Zip列表中 . 哈希被夷为平地，如 [key1, value1, key2, value2] 等 .

    使用Zip Lists，您可以在CPU和内存之间进行权衡 . Zip列表具有内存效率，但它们使用的CPU比链表（或哈希表/跳过列表）多 . 在zip列表中查找元素是O（n） . 插入新元素需要重新分配内存 . 因此，Redis仅将此编码用于小型列表，哈希和有序集 . 您可以通过在redis.conf中更改 <datatype>-max-ziplist-entries 和 <datatype>-max-ziplist-value> 的值来调整此行为 . 有关更多信息，请参见Redis Memory Optimization, section "Special encoding of small aggregate data types" .

    comments on ziplist.c非常好，您可以完全理解这种数据结构，而无需阅读代码 .

    6. Int集

    Int Sets是“Sorted Integer Arrays”的奇特名称 .

    在Redis中，集合通常使用哈希表来实现 . 对于小集合，散列表是低效的内存 . 当集合仅由整数组成时，数组通常更有效 .

    Int Set是整数的排序数组 . 要查找元素，请使用binary search algorithm . 这具有O（log N）的复杂性 . 向此数组添加新整数可能需要重新分配内存，这对于大型整数数组而言可能会变得昂贵 .

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

    Int集是CPU和内存之间的权衡 . Int集合具有极高的内存效率，对于小集合，它们比散列表更快 . 但经过一定数量的元素后，O（log N）检索时间和重新分配内存的成本变得太多了 . 根据实验，切换到常规哈希表的最佳阈值为512.但是，您可以增加此阈值（减少它不需要 . 请参阅redis.conf中的 set-max-intset-entries .

    7. Zip Map

    Zip Map 是平面化的词典并存储在列表中 . 它们与Zip Lists非常相似 .

    自Redis 2.6以来，Zip Map 已弃用，小哈希存储在Zip列表中 . 要了解有关此编码的更多信息，请参阅comments in zipmap.c .

    回复于
  • 2

    Redis存储指向值的键 . 密钥可以是任何二进制值，直到合理的大小（出于可读性和调试目的，建议使用短ASCII字符串） . 值是五种本机Redis数据类型之一 .

    1.strings - 一系列二进制安全字节，最大512 MB 2.hashes - 键值对的集合3.lists - 字符串的插入顺序集合4.sets - 没有排序的唯一字符串的集合5.sorted sets - 由用户定义的评分排序的唯一字符串的集合

    Strings

    Redis字符串是一个字节序列 .

    Redis中的字符串是二进制安全的（意味着它们的已知长度不是由任何特殊的终止字符决定的），因此您可以在一个字符串中存储最多512兆字节的内容 .

    字符串是典型的“关键 Value 商店”概念 . 您有一个指向值的键，其中键和值都是文本或二进制字符串 .

    有关字符串的所有可能操作，请参阅http://redis.io/commands/#string

    Hashes

    Redis哈希是键值对的集合 .

    Redis散列包含许多键值对，其中每个键和值都是一个字符串 . Redis哈希不直接支持复杂值（意思是，您不能让哈希字段具有列表或集合的值或其他哈希值），但您可以使用哈希字段指向其他顶级复杂值 . 您可以对哈希字段值执行的唯一特殊操作是数字内容的原子递增/递减 .

    您可以通过两种方式考虑Redis哈希：作为直接对象表示和紧凑地存储许多小值的方法 .

    直接对象表示很容易理解 . 对象具有名称（哈希的键）和具有值的内部键的集合 . 以下是示例，请参阅下面的示例 .

    使用散列存储许多小值是一种聪明的Redis海量数据存储技术 . 当散列具有少量字段（~100）时，Redis优化整个散列的存储和访问效率 . Redis的小型哈希存储优化提出了一个有趣的行为：拥有100个哈希值，每个哈希值有100个内部键和值，而不是让10,000个顶级键指向字符串值，效率更高 . 使用Redis哈希来优化数据存储这种方式确实需要额外的编程开销来跟踪数据最终的位置，但如果您的数据存储主要基于字符串，则可以使用这一个奇怪的技巧节省大量内存开销 .

    有关哈希的所有可能操作，请参阅hash docs

    Lists

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

    您可以从列表的头部或尾部插入，删除和遍历列表 .

    需要按照插入顺序维护值时使用列表 . （如果需要，Redis会为您提供插入任意列表位置的选项，但如果插入远离起始位置，插入性能会降低 . ）

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

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

    您还可以通过在每次插入后将列表修剪为特定大小来维护固定长度列表（上限集合） .

    对于列表上的所有可能操作，请参阅lists docs

    Sets

    Redis集合就是集合 .

    Redis集包含唯一的无序Redis字符串，其中每个字符串每集仅存在一次 . 如果将相同的元素添加十次到一个集合，它将只显示一次 . 套装非常适合懒洋洋地确保某些东西存在至少一次，而不必担心重复元素的累积和浪费空间 . 你可以加你想要多次使用相同的字符串，而无需检查它是否已经存在 .

    对于集合中成员的成员资格检查，插入和删除，集合很快 .

    正如您所料，集合具有高效的集合操作 . 您可以同时获取多个集合的并集，交集和差异 . 结果可以返回给调用者，也可以将结果存储在新的集合中供以后使用 .

    集合具有常量时间访问以进行成员资格检查（与列表不同），并且Redis甚至可以方便地随机删除成员并返回（“从集合中弹出随机元素”）或随机成员返回而无需替换（“给我30个随机成员唯一用户“）或替换（”给我7张卡片，但在每次选择后，将卡片放回原位，以便可能再次取样“） .

    有关集合上的所有可能操作，请参阅sets docs .

    Sorted Sets

    Redis排序集是具有用户定义排序的集合 .

    为简单起见，您可以将有序集视为具有唯一元素的二叉树 . （Redis排序集实际上是skip lists . ）元素的排序顺序由每个元素的分数定义 .

    排序集仍然是集 . 元素只能在一组中出现一次 . 出于唯一性目的，元素由其字符串内容定义 . 插入具有排序分数3的元素“apple”，然后插入具有排序分数500的元素“apple”导致在您的分类集合中具有分类分数500的一个元素“apple” . 集合仅基于数据是唯一的，而不是基于（分数，数据）对 .

    确保您的数据模型依赖于字符串内容而不是元素的唯一性分数 . 允许分数重复（甚至为零），但最后一次，每个有序集合只能存在一次 . 例如，如果您尝试将每个用户登录的历史记录存储为有序集，方法是将分数设置为登录的时期和用户ID的值，则最终将仅为所有用户存储上次登录时期 . 您的设置将增长到您的用户群的大小，而不是您想要的userbase *登录大小 .

    元素将添加到您的集合中 . 您可以随时更新任何元素的分数，只需使用新分数再次添加元素即可 . 分数由浮点双精度表示，因此您可以根据需要指定高精度时间戳的粒度 . 多个元素可能具有相同的分数 .

    您可以通过几种不同的方式检索元素 . 由于所有内容都已排序，因此您可以要求从最低分数开始的元素 . 你可以要求从最高分开始的元素（“反向”） . 您可以按自然顺序或反向顺序询问元素的排序分数 .

    有关已排序集的所有可能操作，请参阅sorted sets docs.

    回复于

相关问题