redis源码
2021-11-21 19:37:22 0 举报AI智能生成
redis渐进式hash，string.ziplist,list,set,zset,geohash
作者其他创作
大纲/内容
redis整体是一个大的hashmap,使用拉链法解决hash冲突
介绍
特性
非关系型键值对数据库，O(1)时间复杂度根据key读取和写入value
数据存储在内存中
键只能是字符串,且键是唯一的，value可以是string,list,hash,set,zset
Redis内置了主从复制，磁盘持久化，LUA脚本，事务，SSL，ACLS，客户端缓存，客户端代理
可以通过哨兵、集群来保证高可用
应用场景
分布式id生成
分布式队列\阻塞队列
分布式锁
热点数据存储，如评论
set可以实现社交类需求，共同好友等
渐进式rehash
由于Redis是单线程的，为了不阻塞其他命令的执行，Redis每次只迁移一个桶，分多次、渐进式的将ht[0]迁移到ht[1]，查询，插入和删除都会触发一次rehash
使用2张hash表，每次执行查询、插入、删除时，除了执行命令，还会迁移一个桶到ht[1]，使用rehashidx记录下一次要迁移的桶的索引
rehash时查询需要查2张hash表，插入时都插到ht[1]
分而治之的思想，将整张hash表rehash的计算量分摊到每次命令的操作上，提高系统响应速度
string
sds(simple dynamic string，简单动态字符串)来保存字符串
sds在字符数组的基础上，增加了长度和容量，解决了C语言字符串以\0为结束符，不能存储二进制数据的问题
仍用字符数组保存，可以复用部分C已有的字符串函数库
SDS的5种类型
redis3.2之后对长度和容量做了优化，对不同长度的字符串使用不同类型的无符号整型值存储它的长度和容量
sdshdr5,sdshdr8，sdshdr16，sdshdr32，sdshdr64
string存储
int
长度小于20，且能转化为整数的字符串
embstr
长度小于等于44，redisObject和sds分配在同一内存块中，只需要一次内存io，并且该内存块能刚好放下一个64B缓存行
raw
内存块长度超过一个缓存行时，转为raw，redisObject和sds分配在不同内存块
扩容机制
小于1m时，扩容为2倍，超过1m时，每次扩容1m,最大512m
ziplist
类似于数组，是一块连续的存储空间，但它的每个entry节点大小可以不同
链表的缺点：指针占用额外空间，元素较少时空间利用率低，会加剧内存碎片化，影响内存管理效率
时间换空间
保存了最后一个entry的偏移量和entry个数，以便倒序遍历，末尾有一个结束符0xff
每个entry节点保存了上一个节点长度以便倒序遍历
每个节点大小不同，如何找到下一个节点：节点中存储了encoding信息，里面标识了数据类型，整形值隐含了它的数据长度，字符串encoding中存储了长度
list
当元素较少，或者占用空间较小时，使用ziplist作为底层实现,元素多的时候会用双向指针将ziplist链成quicklist
list-max-ziplist-size :当取正值时，是ziplist最大元素个数；当取负值时，是ziplist最大字节数
list-compress-depth：压缩深度，首位第几个不压缩，list一般两端元素访问较多，因此可以对中间元素进行压缩
hash
当元素较少时，并且单个元素较小时，使用ziplist实现，否则转为hashtable
hash-max-ziplist-entries 512 :元素个数超过该值时，ziplist转hashtable
hash-max-ziplist-value 64:单个value大小超过该字节时，ziplist转hashtable
用来存储对象时比string mset ,mget更省内存
set
当元素较少，并且都是64位范围内的整数时，用intset实现，否则转为值为null的hashtable
set-max-intset-entries 512：元素个数超过该值时，intset转hashtable
intset是有序的，便于判断重复时采用二分查找
zset
当元素个数较少，并且单个元素大小较小时，用ziplist实现，否则用skiplist+hashtable
zset-max-ziplist-entries 128：元素个数阈值
zset-max-ziplist-value 64：元素大小阈值
ziplist实现：每个entry由2部分组成，值和score，并且按照score有小到大排序
hashtable实现：key是member，值是score，o(1)时间复杂度获取值的score
hashtable实现了根据成员获取分数（zscore），跳表实现了根据分数范围查找成员（zrangebyscore,zrevrangebyscore,），根据排名范围查找成员（zrange,zrevrange）,根据成员获取排名（zrank,zrevrank）
skiplist
插入、删除、查找时间复杂度为O(logn)
是在有序链表的基础上发展出多层，产生若干稀疏的链表，每层跳过一些节点，越高层跳过的节点越多，加快了查找速度，类似于二分查找
为了方便插入和删除，不严格要求每层节点数，而是采用随机的方法生成每个节点的层数，每加一层概率为低一层的1/4，层数最大为32（6.2版本）
是如何存储每层的后置指针的：每个节点中有一个变长数组，其中有每层的后置指针，该数组长度是运行期通过随机算法确定的，每加一层的概率为1/4时，平均每个节点的指针数为1.33
变长数组中还保存了每一层的跨度span，表示当前层跨过多少节点，不包含当前节点，包含尾结点，可以通过累加span的方式来计算排名（zrank，zrange），
跳跃表、平衡树和哈希表的比较
跳跃表和平衡树是有序的支持范围查找，哈希表不支持
查找单个key，跳跃表和平衡树的查找时间复杂度是Ologn，哈希表是O1
范围查找，平衡树查找到边界后，需要中序遍历，跳跃表不需要，找到最小值后直接通过第一层的指针遍历即可，实现较简单
平衡树的插入和删除需要重平衡调整，跳跃表只需要修改相邻节点的指针，操作简单快速
内存占用，平衡树每个节点占用2个指针，redis跳表平均1.33个指针
算法实现难度，相比于平衡树，跳表更为简单
geohash
使用
geoadd key long lat member ...
将一个或多个经纬度和名字添加到指定key中，实际上是将经纬度通过geohash编码成52位整数，再加进sorted set
删除geo用zrem
geodist key mem1 mem2 [m|km|ft|mi]
指定key的2点间的距离
geohash key mem1 mem2 ...
获取指定key的成员的geohash值，11位字符串类型，前缀相同的在同一区块
geopos key mem1 mem2 ...
获取指定key的成员的经纬度，有误差
算法思想：
将二维的坐标系映射到一维的有序的整数，坐标越靠近的点整数值越接近
将地球坐标系这个二维平面划分成一系列正方形方格，每个方格对应一个经纬度坐标，方格越小越精确，然后对方格进行编码，使得越靠近的点的编码越接近
具体实现
经纬度转编码
将地球经纬度不断二分为左右两个区间，给定经纬度落在左区间时取0，落在右区间时取1，得到2个二进制串
经度二进制串放偶数位，维度二进制串放奇数位，将2个二进制串组合起来形成一个52位整数，存到zset的score中
每5位转成10进制，再base32编码成字符串
突变问题
redis采用了Peano空间填充曲线（z型曲线）进行编码，缺点是具有突变型，有的距离很远的坐标编码却很近，会导致求附近的点时出现一个很远的点，可以筛选后再根据实际距离计算
临界问题
当坐标点落在边界处，距离较远的点处于同一方块，较近的点处于不同方块，从而导致求附近点时近的点没出来，远的点反而出来了
解决方法：除了当前区域的点，其他8个区域的点的编码也选进来进行匹配
适合点数据，不是绝对精确的场景，位数越多精度越高
0 条评论
下一页
