Hom*_*er6 298 algorithm redis data-structures
我想在一个明确的清单中回答两个问题:
所以,我读过Redis列表实际上是用链表实现的.但对于其他类型,我无法挖掘任何信息.此外,如果有人偶然发现了这个问题并且没有对修改或访问不同数据结构的优缺点进行高级概述,那么他们就会有一个完整的列表,列出何时最好地使用特定类型来引用.
具体来说,我想概述所有类型:字符串,列表,集,zset和哈希.
哦,到目前为止,我已经看过这些文章,其中包括:
ant*_*rez 596
我会尝试回答你的问题,但我会先从一些看起来很奇怪的东西开始:如果你对Redis内部不感兴趣,你不应该关心内部如何实现数据类型.这是一个简单的原因:对于每个Redis操作,您都会在文档中找到时间复杂度,如果您有一组操作和时间复杂度,您需要的唯一其他内容是关于内存使用的一些线索(并且因为我们做了许多可能因数据而异的优化,获得后面这些数字的最佳方法是进行一些简单的实际测试.
但是既然你问过,这里是每个Redis数据类型的底层实现.
但是,当列表,集合和有序集合的项目数量和最大值的大小较小时,使用不同的,更紧凑的编码.这种编码因不同类型而异,但其特点是它是一个紧凑的数据块,通常会对每个操作强制执行O(N)扫描.由于我们仅将此格式用于小型对象,因此这不是问题; 扫描一个小的O(N)blob是缓存不经意,所以实际上它非常快,当有太多元素时,编码会自动切换到本机编码(链表,哈希等).
但你的问题并不仅仅是关于内部问题,你的观点是用什么类型来完成什么？.
这是所有类型的基本类型.它是四种类型中的一种,但也是复杂类型的基本类型,因为List是字符串列表,Set是一组字符串,依此类推.
在您想要存储HTML页面的所有明显场景中,Redis字符串都是一个好主意,但是当您想要避免转换已编码的数据时也是如此.因此,例如,如果您有JSON或MessagePack,则可以将对象存储为字符串.在Redis 2.6中,您甚至可以使用Lua脚本操作此类对象服务器端.
字符串的另一个有趣用法是位图,并且通常是字节的随机访问数组,因为Redis导出命令以访问字节的随机范围,甚至是单个位.例如,查看这篇好文章:使用Redis进行Fast Easy实时指标.
当您可能只接触列表的极端时,列表很好:靠近尾部或靠近头部.列表不是很好的分页东西,因为随机访问很慢,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中使用,并且有许多关于如何使用来解决给定任务的线索.
对不起语法拼写错误,这是午夜,太累了,无法查看帖子;)
Sri*_*nan 77
大多数情况下,您不需要了解Redis使用的基础数据结构.但是一些知识可以帮助你进行CPU v/s内存折衷.它还可以帮助您以有效的方式建模数据.
在内部,Redis使用以下数据结构:
要查找特定键使用的编码,请使用该命令object encoding <key>.
在Redis中,字符串称为简单动态字符串或简称SDS.它是一个小的包装器,char *它允许您存储字符串的长度和空闲字节数作为前缀.
因为存储了字符串的长度,所以strlen是O(1)操作.此外,因为长度是已知的,Redis字符串是二进制安全的.字符串包含空字符是完全合法的.
字符串是Redis中最通用的数据结构.String是以下所有内容:
long可以存储数字的.请参阅INCR,DECR,INCRBY和DECRBY命令.chars,ints,longs其能够允许高效的随机存取或任何其他数据类型).请参阅SETRANGE和GETRANGE命令.Redis使用字典进行以下操作:
Redis Dictionaries使用哈希表实现.我将解释Redis的具体内容,而不是解释实现:
dictType扩展哈希表行为的结构.此结构具有函数指针,因此以下操作是可扩展的:a)散列函数,b)密钥比较,c)密钥析构函数,以及d)值析构函数.该Set数据结构使用字典,以保证没有重复.在Sorted Set使用字典的元素映射到它的分数,这是为什么ZSCORE是O(1)的操作.
的list数据类型是使用实现的双向链表.Redis的实现是直接来自算法的教科书.唯一的变化是Redis将长度存储在列表数据结构中.这确保了LLEN具有O(1)复杂度.
Redis使用" 跳过列表"作为"排序集"的基础数据结构.维基百科有一个很好的介绍.William Pugh的论文Skip Lists:平衡树的概率替代方案有更多细节.
排序集使用"跳过列表"和"词典".字典存储每个元素的分数.
Redis的Skip List实现在以下方面与标准实现不同:
Zip列表就像一个双向链表,除了它不使用指针并将数据内联存储.
双向链表中的每个节点具有3个指针 - 一个前向指针,一个后向指针和一个指向存储在该节点处的数据的指针.指针需要内存(64位系统上为8个字节),因此对于小型列表,双向链表效率非常低.
Zip列表按顺序在Redis字符串中存储元素.每个元素都有一个小标题,用于存储元素的长度和数据类型,到下一个元素的偏移量以及到前一个元素的偏移量.这些偏移取代了前向和后向指针.由于数据是内联存储的,因此我们不需要数据指针.
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内存优化,"小型聚合数据类型的特殊编码"部分.
对ziplist.c的评论非常好,您可以完全理解这种数据结构,而无需阅读代码.
Int Sets是"Sorted Integer Arrays"的奇特名称.
在Redis中,集合通常使用哈希表来实现.对于小集合,散列表是低效的内存.当集合仅由整数组成时,数组通常更有效.
Int Set是整数的排序数组.为了找到元素,使用二进制搜索算法.这具有O(log N)的复杂性.向此数组添加新整数可能需要重新分配内存,这对于大型整数数组而言可能会变得昂贵.
作为进一步的存储器优化,Int Sets有3种不同整数的变体:16位,32位和64位.Redis足够聪明,可以根据元素的大小使用正确的变体.添加新元素并且它超过当前大小时,Redis会自动将其迁移到下一个大小.如果添加了字符串,Redis会自动将Int Set转换为基于常规哈希表的集合.
Int集是CPU和内存之间的权衡.Int集合具有极高的内存效率,对于小集合,它们比散列表更快.但是经过一定数量的元素后,O(log N)检索时间和重新分配内存的成本变得过高.根据实验,切换到常规哈希表的最佳阈值为512.但是,您可以根据应用程序的需要增加此阈值(减少它没有意义).请参阅set-max-intset-entriesredis.conf.
Zip地图是平面化的词典并存储在列表中.它们与Zip Lists非常相似.
自Redis 2.6以来,Zip地图已弃用,小哈希存储在Zip列表中.要了解有关此编码的更多信息,请参阅zipmap.c中的注释.