邦纳娜娜

redis里面有个map数据量太大了，怎么分割？

现在有一个大map，里面的key有2w多个 怎么把里面的key每5000个一组，拆成多个map呢？ 有具体的命令吗？还是说之只能写代码，先读出来，再分开保存？ 想知道该运维的

明道

业务指标的采集与同步如何设计呢？

最近在做小说网站，需要统计小说作品的点击次数这个业务指标，需要实时记录并提供历史查询功能。 目前的方案是： 后端程序启动时，查询 mysql 数据，把各个作品的点击数据批量同步到 redis，这是初始化； 用户点击作品时，更改 redis 中的作品的点击数据，记录下待同步的作品 id； 启动定时执行任务，每 10 分钟执行一次，如果有待同步的作品 id，就把它们的 redis 中的点击数据批量同步到 mysql； 遇到的问题： 同步点击数据到 mysql 时，从 redis 里取的的可能是 0 值，作品的点击数据就被重置为 0 了；或者 redis 服务意外停了，导致指标数据异常。 这是简化后的描述，实际上是把 redis 的数据同步到 mysql 与 clickhouse。 后端使用的是golang

编程界菜niao

redis-py 默认有连接池吗？

redis-py 在和后端框架做集成的时候，我好奇 redis-py 和 redis server 之间的连接管理机制 比如, 假设后端框架是多线程模型，每来一个 http 请求，都会新开一个线程去处理改 HTTP 请求，视图函数内，要访问 redis server 根据 key 取 value 并且返回给 http client 假设 redis_client 作为全局变量 redis_client = redis.StrictRedis(host='localhost', port=6379, db=0) 视图函数里面调用 redis_client value = redis_client.get('my_key') 那么此时此刻，redis-py 会为每个线程都创建一个独立隔离的 TCP 连接并且在线程结束之后就销毁 redis 连接吗？ 还是说 redis-py 内部维护了一套复用和 redis server 通讯的 redis 连接？

无事小神仙

linux搭建redis集群

手动安装安装ruby因为创建Redis集群的工具是ruby文件。在我的linux上默认安装的版本是2.2.0 的。无法构建redis集群。这个时候我们需要安装高版本yum install ruby ruby -v 查看安装的ruby是否成功 下载ruby-2.3.1,通过xftp上传到服务器上。 tar -xvzf ruby-2.3.1 cd ruby-2.3.1 ./configure make sudo make install 然后通过ruby -v查看下载rubygems-2.7.3同上面一样的解压。执行ruby setup.rb安装zlib安装的linux系统比较干净，有的linux系统里就没有zlib模块需要我们安装C语言环境安装(zlib)：http://www.dataguru.cn/thread-50201-1-1.html如果没有openssl还需要安装openssl:http://blog.csdn.net/thanklife/article/details/55097429（这篇文章没有亲自试）安装了rubygems 后国内的朋友需要换请求地址gem -r source https://rubygems.org/ gem -a source http(s)://gems.ruby-china.org/ 之后就可以通过gem install redis安装redis.gem了 安装rediswget http://download.redis.io/releases/redis-4.0.6.tar.gz 下载4.0.6版本的Redis然后cd redis-4.0.6make : 和windows上安装一样注意点 - bind需要注释，不绑定就是任何网络都可以访问，这个时候需要将peotected-mode改为no。安全模式取消 - linux中防火墙需放开redis集群需要的端口。我用的是阿里云需要在安全组加入redis集群中需要的端口这样才可以对方公开。注意的是redis的端口是7000~7005 ，但是对应的总线成接口还有17000~17005端口也需要放开。这样用构造集群工具才可以构造集群。 - 如果node没有设置或者设置的是相对执行命令的相对位置，那么我们最好在redis.conf同级下执行。这样避免了集群中node。conf的冲突。 脚本安装(一键安装)源码下载找到start.sh直接执行start.sh执行完start.sh之后会见到如下选项选项解释如下：序号列表说明1懒人一键安装安装redis集群2安装必要环境安装所需环境组件3安装gitgit4卸载卸载5redis服务启动启动6集群启动集群配置启动7终极一键包含上面所有步骤

无事小神仙

【redis正传】redis淘汰+过期双向保证高可用 | 单线程如何做到快速响应

前言【redis前传】持续更新！各种穿插更新！嘿嘿嘿redis和数据相比除了他们的结构型颠覆以外！还有他们存储位置也是不相同。传统数据库将数据存储在硬盘上每次数据操作都需要IO而Redis是将数据存储在内存上的。这里稍微解释下IO是啥意思。IO就是输入流输出流方式将数据在硬盘和内存之间进行交互！而redis直接在内存上就剩下了IO操作。这也是redis快的原因之一吧内存相对于硬盘来说很宝贵。我们平时的电脑也是硬盘是内存的几百倍。既然内存很宝贵而redis又将数据存储在内存上那么redis肯定不能肆无忌惮的进行存储 。这就需要redis和开发者们作出相应的优化首先redis在配置文件(redis.conf)中通过maxmemory参数指定redis 设置整个对内存的支配大小！其次就是要求我们开发者在想redis中填值的时候根据自己的需求设置相应的key过期时间。这样不必要的数据就会被redis过期驱逐策略清楚。从而节省内存供别人使用本文凌驾于redis基础之上，这里笔者默认大家都已经安装了redis . 并实际使用过redis内存分配maxmemory  指定大小。在redis.conf配置文件中可以直接指定。他的单位时byte。上图中注释部分是给大家的解释，实际中#配置需要换行哈！！！友情提示另外我们可以连接上redis通过config命令来设置两种方式都可以设置，前者是全局设置重启之后仍然有效！后者是临时设置重启之后就会重新加载redis.conf中的配置。键过期上面我们从redis本身角度出发设置了内存限制，这样不用担心他们吞噬系统内存！下面就需要我们开发者设计角度约束自己了。设置过期时间expire key time 设置过期时间默认单位时S 。然后通过ttl 命令可以查看剩余过期时间经过多次执行ttl能够观察到剩余时间在不断的减少！当减少到0的时候就被给驱逐策略驱逐！注意这里说的是驱逐策略驱逐并不是意味着立马被删除更新过期时间del key 直接将key删除了那么该key对应的过期自然也就不存在了！这种情况笔者也算作是更新过期时间set getset等命令重新设置key、value方式会覆盖过期时间 ， 直接被覆盖成-1set 、 getset包括del严格意义是覆盖过期时间。真正做到更新过期时间的还是expire  .在expire是已最新为准的！上面其实都修改了key才会应发原本的过期时间失效的！因为此key非彼key 。 但是append、incr 等命令是改变值这种命令是不会影响到原来的过期设置的淘汰策略根据上面配置我们可以将我们的redis最大内存设置为1MB , 设置大小随便最好能小点。然后我们通过Java小程序不断向redis中填充。最终当内存不够使用时就会报错报错就是因为内存满了，新增的key被redis拒绝了！不仅仅是新增的被拒绝，就算此时我们想改变已经在redis中的key的值也是不可用的public static void main(String[] args) { Jedis jedis = new Jedis("39.102.60.114", 6379); jedis.auth("Qq025025"); Integer index = 1; while (true) { String uuid = UUID.randomUUID().toString(); jedis.set(index.toString(), uuid); System.out.println(index++); } } 不管是append 还是set 都是报OOM command not allowed when used memory > maxmemory 。代码中打印和redis键个数一致；说明我们默认的淘汰策略是直接拒绝总结下来就是：当redis内存被使用满了后，任何的写操作都会被拒绝！当没有足够内存时难道就这么直接拒绝吗？上面也提到了需要我们程序员自己根据需求设置键过期已释放内存供其他有需要的key使用！那么设置了过期key之后这些key又是怎么被清除的呢？ 这就牵扯出我们的淘汰策略volatile-lru【最近很少使用】当内存告警时redis会将近期很少使用且设置了过期时间的key剔除出去，即使该key还没有到过期时间。如果没有符合的key也就是执行之后内存仍然不足时将会和默认淘汰策略noeviction抛出一样的错误OOM command not allowed when used memory > maxmemory首先我们在redis.conf中配置我们最近很少使用策略.  maxmemory-policy volatile-lru   。 然后重启我们的redis服务 。重启之后flushall清空所有数据，我们在通过上面的Java程序重新生成下数据！Java程序中我们设置前100个key添加过期时间public static void main(String[] args) { Jedis jedis = new Jedis("39.102.60.114", 6379); jedis.auth("Qq025025"); Integer index = 1; while (true) { String uuid = UUID.randomUUID().toString(); if (index < 100) { jedis.setex(index.toString(),360, uuid); } else { jedis.set(index.toString(), uuid); } System.out.println(index++); } } 简单分析下为什么程序计数器大于redis库中的key数量！就是因为我们为前100设置了过期时间。当内存不足时redis就会将当前设置了过期时间的key中最近最少使用的key进行剔除！所以我们计数器会大于键数量。因为有部分键被清除了！我们获取前100的key都是null ， 说明被删除了！ 那么为什么本次计数器不是比上次多100 。 那是因为我们每次存储进来的是uuid， 所占长度都不是固定的。还有本身淘汰策略也是占用内存的策略总结上面演示了最近最少使用的淘汰策略！除此之外还有其他的策略noeviction：拒绝写请求，正常提供读请求，这样可以保证已有数据不会丢失（默认策略）； 2. volatile-lru：尝试淘汰设置了过期时间的key，虽少使用的key被淘汰，没有设置过期时间的key不会淘汰； 3. volatile-ttl：跟volatile-lru几乎一样，但是他是使用的key的ttl值进行比较，最先淘汰ttl最小的key； 4. volatile-random：其他同上，唯一就是他通过很随意的方式随机选择淘汰key集合中的key； 5. allkeys-lru：区别于volatile-lru的地方就是淘汰目标是全部key，没设置过期时间的key也不能幸免； 6. allkeys-random：这种方式同上，随机的淘汰所有的key。 使用哪种淘汰策略需要我们结合自己的项目场景来配合使用！！！过期删除上面我们从【键过期】、【淘汰策略】两个角度分析了redis 。 仅仅这两方面还没有完全高效使用内存！淘汰策略是濒临内存不足时触发。那么当设置了过期时间的键真正到了过期时间而此时内存尚够使用？这种场景是不是需要将过期键删除呢？因为redis是单线程，那么在键过期的时候如何不影响对外服务的同时清除过期键呢？答案是【不行】。严格意义是无法解决的因为单线程同时只能做一件事！既然无法解决那么我们可以达到一种协调状态！如果同一时刻出现一个过期键那么清除键很快这时候阻塞外部服务的时间很短可能毫秒级设置纳秒级！但是如何同一时间发生上万键过期，如果想要删除上万键那肯定需要花费一定时间这时候就会阻塞对外服务！这肯定是不能接受的，阻塞时间过长会导致客户端连接超时报错的。这在并发场景下更是无法接受的！所以redis如何应对同一时间过多数据过期的场景，他的删除过期键的方法略有不同！定时清除针对每个过期键设置一个定时器，在过期时就会进行清理该键！该做法能够做到数据实时被清理从而保证内存不会被长期占用！提高了内存的使用率！但是问题也随之而来，每一个key需要设置一个定时器进行跟踪。redis这里笔者猜测应该是启用另外线程来进行定时跟踪！这里有清除的还请帮忙解答下？当同一时间过期key很多的时候！我们的CPU就需要不断的执行这些定时器从而导致CPU资源紧张。最终会影响到redis服务的性能定期清除定期删除就是上面我们图示效果，redis会每隔100ms执行一次定时器，定时器的任务就是随机抽取20个设置过期的key 。 判断是否进行清除。上面图示中说明中写错了不是10S ， 而是每隔100ms  。请原谅我的粗心!!!定期删除和定时删除作用是相反的！定期删除是将key集中进行处理同时为了保证服务的高可用在处理时加入的时间限制。每次执行总时长不能超过25ms 。 也就是说对于客户端来说服务端的延迟不会超过25ms 。他的优点就是不需要CPU频繁的进行操作key清除！因为他是定期进行清除所以就会导致一部分数据没有来得及清除从而导致内存使用上会被一直占用！惰性清除关于惰性删除我们在平时开发中也经常使用这种方式！当数据过期时redis并不急着去清除这些数据，而是等到该key被再次请求时进行删除！这样在最终效果上是没有问题的。优点和定期清除一样他保证了CPU不必频繁的进行切换！但是缺点也很明显会导致很多已经过期的key任然在redis中。惰性清除+定期清除我们开头说过了既要高可用又要实时清理过期key 这是无法做到的！既然无法做到我们就需要在CPU和内存中间做一个权衡！redis内部是使用惰性清除和定期清除两种方式结合使用，最终保重CPU和内存之间的一种平衡！总结相信大家对上面三个概念有点模糊了。【键过期】、【淘汰策略】、【过期清除】首先【键过期】是redis给我们开发者提供的功能。我们可以根据自己的业务需求合理的设置键的过期时间，从而保证内存的高可用其次【过期清除】在我们之前设置的过期的key如何进行合理的清除，并不能一股脑一下子进行清除因为数据过大会导致服务的卡顿。这个时候我们需要通过定期清除减缓清除key代码的卡顿。在redis.conf中我们可以设置 hz 10 代表1S中平均执行几次这也是我们上面所说的100MS的由来。但是仅仅定期删除会产生遗漏数据所以我们还需要加上惰性清除，最终保证对客户端来说数据是准确实时清除的。那么关于【淘汰策略】又是啥呢？在上面过期清除是如果用户一直不请求过期的key ，并且随着业务产生越来越多的过期key . 这时候redis服务中还会堆积很多过期的无效key 。这个时候如果内存不够用了的话那又该怎么办呢？这时候我们需要设置淘汰策略比如果volatile-lru  . 就会将最近最少使用的设置过期key进行清除从而保证尽可能的接收更多的有效数据！这就是为什么会设计三者的原因！好好理解上面三个主题我们再去想想为什么会发生【缓存雪崩】、【缓存奔溃】、【缓存击穿】就好理解一点了呢？关于上述的redis常见的灾难场景，我们下章节继续分析如何产生的、并且如何进行修复进行展开讨论。

无事小神仙

【redis前传】自己手写一个LRU策略 | 抓住时间的尾巴

一、题目描述运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制 。 实现 LRUCache 类： LRUCache(int capacity) 以正整数作为容量 capacity 初始化LRU缓存 int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。 void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。 进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？二、思路分析第一想法刚看到本题时没有多想就觉得会用到队列，因为队列FIFO可以做到淘汰末尾数据，但是仔细一想本题是需要淘汰最近最少使用数据，如果仅仅是最近的数据那么队列很容易实现。加上使用频率就涉及到数据的频繁挪动。很明显队列是无法完成的。那么有没有一种顺序添加的数据，每次在获取之后就会将数据前移至一端呢？答案是有的！LinkedHashMapLinkedHashMap 不熟悉的朋友们可以简单的将它理解成HashMap 。 下图展示了HashMap的存储结构上述的元素我这里做了个动画演示全过程！！！而LinkedHashMap只是多了一条链表串起里面的元素这也是为什么LinkedHashMap是按照顺序存储的。但是LinkedHahsMap也无法做到按照使用频率进行排序啊？大家都知道他是按照添加顺序排序的！！！*LinkedHashMap*改造原生的LinkedHashMap的确无法满足情况，但是我们稍微看下源码能够发现在put之后都会执行下afterNodeInsertion 这个方法。这也是HashMap留给LinkedHashMap做的扩展！removeNode 就是将最前面的数据。想要进入这个方法就需要removeEldestEntry判断。LinkedHashMap默认是false . 所以我们只需要重写他就行了。但是还是在get值的时候如何保值在最后面呢？我们仔细看下源码就能够发现在get中有这个一个方法afterNodeAccess 。他的作用就是将get的元素移位值后面。正好符合我们LRU的策略特征综上！我们借助LinkedHashMap就非常容易的实现了LRU策略！自己实现但是本题的意思是想考察我们自己是如何实现的，而不是巧妙对现有的工具改造的！不过上面对LinkedHashMap的确改造的很巧这是不可否认的！下面我们就尝试自己来实现下这种方式！首先我们需要确定需要用到Hash结合链表来实现。Hash我们自然使用HashMap来存储数据为的就是方便定位数据。定位到数据就需要操作链表将数据实时移位值链表尾部，每次淘汰是将链表首位移除既可。为了方便我们操作链表这里的链表肯定是双链表的！链表单元首先我们定义一个内部类！用于链表的基本单元。里面存储了key,value方便根据Hash中存储的内容找到节点！preNode，nextNode分别指向前后节点在构建器中初始化容量和链表大小，并初始化边界节点方便我们操作节点中移位和删除。在获取数据时没有添加就返回-1 ， 已经添加的数据则将该数据对应的node节点移动到链表的尾部。在put中当第一次添加我们需要维护链表大小并进行检测是否需要进行淘汰数据，如果不是第一次添加我们只需奥更新值和对应node在链表中的位置即可方法名作用addToTail将节点添加值链表尾部moveToTail将已经存在于链表中的节点移动到链表的尾部removeHeadNode删除链表中第一个节点，注意是边界节点后第一个节点四、总结虽然执行时间和内存消耗有点高！但是我就是不优化。本题主要就是在链表的移动上面会复杂点。我们需要按照添加顺序和使用频率两个维度进行维护他们之间的顺序。只要这个顺序维护好，就没啥问题了！

无事小神仙

【redis前传】redis字典快速映射+hash釜底抽薪 | 单线程不影响后台工作之渐进式reha

前言相信你一定使用过新华字典吧！小时候不会读的字都是通过字典去查找的。在Redis中也存在相同功能叫做字典又称为符号表！是一种保存键值对的抽象数据结构本篇仍然定位在【redis前传】系列中，因为本篇仍然是在解析redis数据结构！当你尝试去了解redis时才能明白其中原理！才能明白为什么redis被大家吹捧速度快，而不是被告知redis很快！应用场景在Redis中有很多场景都是用了字典作为底层数据结构！我们使用最多的应该是redis的库的设置和五种基本数据类型的Hash结构数据！在上一篇【redis前传】中我们学习了list数据结构。今天我们继续学习主流数据结构Hash。在redis内部有字典结构、hash结构但是这里的hash和我们平时熟知的redis基础数据的hash并不是一个意思！我们简单的将字典结构、hash结构理解成redis更加底层的一种抽象结构。平时我们使用的hash基础数据结构理解成hash工具而今天我们的主角就是五种数据结构的Hash分析。他的底层使用了字典这个结构。字典结构内部使用的是底层的hash结构。有点绕！好好理解你行的哈希表上面这张图诠释了作为redis底层结构的Hash。在内部redis称之为dictht  。 后面我们为什么和之前的hash结构冲突我们都已类名为准叫做dictht类。在hictht类中有四个属性分别是table 、 size 、 sizemask 、 used  ; 其中table就是一个数组；数组中元素是另外一个类叫做dictEntry类。dictEntry就是真正存储数据的。内部是key、value存储结构。一个简单的哈希表就如图所示。数据最终会存储在table中的dictEntry对象中。至于为什么sizemask = size -1 ; 这个是为了在计算hash索引时需要用到的。那为什么不直接使用size-1而是通过一个变量来承接呢？这个吧！！！我也不知道。容我去百度百度。数组节点上面的哈希表是不是很熟悉，这不和我们Java中的Map数据结构如出一辙吗。可以说是也可以说不是，两者很相似但也有区别的。在上面中我们提到数据最终是存储在哈希表里table数组里的元素。该元素叫dictEntry 。 下面我们看看dictEntry结构如何吧！通过左侧对dictEntry的定义我们可以看出。dictEntry存储的值可以是指针、正数、浮点数各种数据类型！类似于Java中的Object属性。  对于上述的key没有啥真意的就是一个键。既然是数组那么索引就是固定长度的，那么在有限的长度中肯定会出现经典问题就是【hash冲突】。在Java中我们是通过链表和红黑树来解决冲突的问题！在redis中是通过链表解决的。在dictEntry中通过next指针将冲突元素连接。这里我们就可以和Java中的Map结构进行理解。他们内部很是相似!!!这里需要注意下在hash冲突时redis的确是通过链表进行存储的，但是由于哈希表(dictht)中没有记录每个索引未中链表的尾部节点只有头结点信息所以。而且我们也知道链表在查询上效率不佳，所以当发生哈希冲突时redis是将新加入的节点加入在链表的头部！字典多态字典字典是本文开头提出的结构！也是redis中大量使用的一种底层数据结构。在redis中名叫做dict类。通过图示我们明确的看出内部是包含哈希表的。其实从名字上我们也可以看出哈希表为什么叫dictht 。 笔者这里认为是dicthashcodetable 。 意思就是字典表内部的一个hash相关的数组(仅个人理解)之前也提到过redis内部很多地方会使用到字典！就好比我们上学是用到【新华字典】、【成语词典】、【歇后语词典】等等。虽然名字叫法不一样但是内部结构都是一部字典供我们快速定位。而redis中dict内部就是通过type字段进行区分每个字典的。而privdata是每部字典需要的特定参数。通过type和privdata就可以轻松实现各种功能不同的字典，他有个专有名词叫~~多态字典~~rehash除了type 、 privdata以外剩下的就是ht 、 rehashidx了。其中ht是一个长度为2的数组。数组里元素就是我们之前提到了哈希表(dictht) 。 ht为什么长度为2 这就需要我们了解下redis的rehash过程了。而rehashidx就是记录rehash的进度！在没有发生rehash的时候rehashidx=-1;在实际使用过程中在字典中我们所有的数据都会存储在ht[0]对应的哈希表中。ht[1]永远都是一个空数组。这些都是为什么rehash做准备，在正式开始之前我们先来了解下redis为什么需要rehash这个动作首先我们在哈希表中是一个定长数组发生冲突时内部是通过链表解决的。理论上一个哈希表可以存储足够的数据，这里的足够就是指空间允许的范围有多少存多少。但是我们知道链表的特点就是新增、删除很快但是查询很慢，尤其是当链表很长的时候就会出现查询效率低下的问题！为了避免链表过长redis就会在一定条件下对哈希表中数组长度的扩展从而解决局部链表过长的问题！每次数组发生长度变化时，那么之前的hash值就需要重新经历一遍hash然后寻址index的过程。这个过程就叫做rehash 。关于rehash和Java中Map的resize是一样的功能！Java中resize是直接new 出一片内存进行复制的而且他是每次进行2倍扩展。而redis的rehash稍微不同基本上我们也可以理解成2倍扩展！关于两块内存复制有点类似于JVM中垃圾回收有点类似。有时间我们可以一起研究下JVM章节。那么啥时候需要进行rehash呢？这里和Java的负载因子一样；但是除了负载因子这个空间考核以外redis还考虑一个性能的问题。因为在单线程的前提下我们还要考虑客户端使用的感知性！单线程的意思就是执行命令是顺序执行的。总不能在我们rehash的过程中全部阻塞客户端的使用这对于操作体验上稳定性来说是不友好的。涉及到上述两个命令的我们称之为后台命令结合负载因子产生如下条件渐进式rehash一直强调redis是单线程。那么什么叫单线程模型？就是对于redis服务来说执行命令是线性操作！但是每个客户端的命令是无序的，先到的就先进入队列redis服务从队列一次取出命令进行执行。除了客户端的命令还有一些系统生成的命令比如说我们上面提到的rehash操作！①、首先为了避免阻塞客户端或者说尽量控制阻塞的时间在客户端感知范围内，redis内部的rehash并不是一次性操作而是一个循序渐进的过程。一次仅复制一部分②、还记得之前我们提到dict中rehashidx这个属性吗，他是记录rehash的进度。因为哈希表内部是一个数组而rehashidx就是记录这个数组的索引。从而我们也可以知道每次rehash复制的时候是已一个索引完整链表为单元进行复制的。③、除了新增以外的其他操作都会同时影响到ht[0]、ht[1] 因为在rehash过程中两个数组都是在使用状态的④、新增值的时候就只需要新增到ht[1]中。因为最终的目的就是将所有值同步到ht[1]中。而ht[0]的值会慢慢的变少；没必要新增到ht[0]⑤、在rehash过程中查找元素时会查找两个数组中的并集元素。这也就也是了为什么再rehash过程新增元素只需要新增到ht[1]的原因总结①、字典表在redis被广泛使用，基于字典表优秀的设计解决redis单线程问题②、字典里包含哈希表，哈希表内部使用节点负责存储key、value③、字典type实现多态字典用于多场景！④、渐进式rehash解决服务卡顿问题

无事小神仙

【redis前传】 redis五大天王值list基本数据如何成长 | 由内之外深入学习

前言在【数据结构】学习中，绕不过的就是链表和数组的学习了！数组应该更容易理解点！因为他和我们平时的逻辑一样。但是链表在刚入门的同学中应该算是比较抽象的了！尤其是指针交换位置更是容一部分同学望而却步！今天我们来学习下Redis中的常用的链表数据结构list在Redis低版本(3.2之前)中list数据结构底层就是使用链表来进行串联数据的！上图就是Redis中在操作List数据结构时的结构图！在redis中并不是仅仅使用这一种双向的链表结构.关于ziplist等其他结构我们这里暂时不讨论。而针对一整条链条redis有将它 抽象化一个list对象node是链条中重要的组成部分，而list我们可以理解成对整个链条的描述。list中包含头结点、尾结点、链条中节点个数、节点的复制释放比对等功能！typedef struct listNode { struct listNode *prev; struct listNode *next; void *value; } listNode; typedef struct listIter { listNode *next; int direction; } listIter; typedef struct list { listNode *head; listNode *tail; void *(*dup)(void *ptr); void (*free)(void *ptr); int (*match)(void *ptr, void *key); unsigned long len; } list; 函数作用dup复制链表节点值free释放链表节点值match比对链表节点值与指定值是否想的相等小结很明显在redis中链表是一种双指针链表，可以通过当前节点轻松定位前后节点！list中可以轻松获取链表头尾节点！这也就解释redis中的lpush  、 rpush命令最终的实现了。就是通过改变头、尾指针就可以了。操作那是非常迅速的list中len表示链表长度。就是一个节点计数器。对应着llen 命令了解数据结构后基本上就可以理解redis对应的操作命令在内存中的结构了list其他数据结构上面我们提到在3.2之前的版本中redis采用链表结构进行存储list数据。在3.2之后开始出现一种ziplist结构的数据结构！首先我们思考下listnode用的好好的为什么要改用ziplist结构。因为list结构中存储了头尾节点方便了我们寻址但是牺牲了内存说白了就是空间换时间ziplist就是针对内存浪费的问题进行了优化。我們看下ziplist的存储内存分布图(以下图片来源于网络)位置作用zlbytesziplist字节长度；长度最长为（2^32）-1zltail整个ziplist偏移量；四个字节zllenziplist中存储的元素个数；两个字节entryXziplist中元素zlend结束位  。固定值0xFF=255typedef struct zlentry { unsigned int prevrawlensize, prevrawlen; unsigned int lensize, len; unsigned int headersize; unsigned char encoding; unsigned char *p; } zlentry; 小结ziplist又称为压缩列表本质上就是一个数组。除了list以外还有hash也都使用了ziplist. 压缩列表虽然节省了内存的开销但是随之而来的问题就是连锁更新。关于什么是连锁更新我们以后在分析！本文是一篇入门级的文章。到这里就结束啦

无事小神仙

【redis前传】为什么set底层hashtable+intset两种数据结构 | 超出长度升级解决

前言整数集合相信有的同学没有听说过，因为redis对外提供的只有封装的五大对象！而我们本系列主旨是学习redis内部结构。内部结构是redis五大结构重要支撑！前面我们分别从redis内部结构分析了redis的List、Hash、Zset三种数据结构了。今天我们再来分析set数据结构内部是如何存储的基本结构在src/t_set.c中我们发现这样一段代码由此我们可知在set中是由两种数据结构构成的： hashtable+intset 。关于redis内部其他的结构我专门在【redis专栏中有介绍】。hashtable不是我们今天的主角，我们今天先分析intset俗称整数集合。从上图中我们可以看出，我构造了两个set集合分别为【commonset】、【cs】。两个集合前者存储字符串、后者专门存储数字。我们在通过object encoding key 来查看下两个集合的底层数据结构，发现一个是hashtable 一个是intset 。这也验证了我们上面对set基本结构的描述。在redis中对外提供五大类型实际上都是redis的一个抽象对象叫做redisobject。在内部映射了我们redis内部的数据结构针对commonset和cs两个集合在内部数据结构大概可以这么理解何时使用intset你可以单纯的认为只要是数字就会使用intset结构来存储，我恐怕要给你当头一棒了。实际上并不是这样需要同时满足以下两个条件：intset图中表示的很清楚了，在intset中的encoding有三种取值分别代表contents保存数据类型。这里有人可能会有疑问了contents的类型不就是int8_t吗？为什么还需要encoding呢？这里通过源码跟踪内部的确跟int8_t没啥关系。而且数据的默认类型就是int16_t 。关于length这里无需太多解释，记住一点表示contents元素的个数并非表示contents数组的长度！了解intset的同学都知道在encoding三种取值范围中涉及了升级的操作！在讲升级之前我们先来了解下C、C++中int的取值范围是如何定义的int8_t的取值范围是【-128,127】 。 类似于java中byte占1个字节也就是8位。他的取值范围是添加元素sadd juejin -123 sadd juejin -6 sadd juejin 12 sadd juejin 56 sadd juejin 321 juejin这个key内部就是intset 。上面我们添加了5个元素且这五个元素的长度都在16之内！所以当前的intset的encoding=INTSET_ENC_INT16。-123在contents中占前16位。所以当前五个元素占contents的长度是16*5=80 ；注意set在存储int类型数据时，内部是按照从小到大的顺序存储的。类型变动上面的问题不知道你有没有考虑过，或者说有没有遇到过！intset默认是int16位，正如我们上面添加的五个元素。加入此时我们添加第6个元素是65535(32位)。那么此时16位的长度就不够存储了这个时候intset会怎么做！另外当我们添加第6个元素后又将65535删除了之后，结构和添加之前是否一样！下面我们带着这两个问题来一探究竟！！！升级首先我们针对第一问题来看看。原来五个元素都是16位就可以满足了，这个时候添加的65535是32位长度的。那么是不是可以直接追加32位分配给65535呢？答案是肯定不行，首先直接追加无法保证数组元素的大小顺序！其次如果前五个分别是16位，第6个是32位那么在intset结构中没有多余的字段来进行标记。也就是说在解析的时候就无法判断应该解析16位还是32位了.redis为了方便解析所以在有高长度加入时会将整个contents进行升级。意思就是将整个contents先进行扩容，然后在重新填充数据加入65535首先根据length可以确定扩容后元素个数为6 ， 每个占位32，所以contents长度为32*6=192 。 此时前80位内容保持不变旧数据移位开辟了足够的空间后，我们就可以对旧数据进行移位了这里我们从原数组的末尾开始移动，在移动之前需要明确在新数组中的排序位置。此时我们首先将321进行比对确定在新数组中他的排名是第五名，那么他将占用新contents中128~159区间。最终前5 个元素就会被移动好 。最后将新加入的元素填充进去。当发生升级时肯定是因为新元素的长度大于原有长度了。那么他的值一定会是在新数组的两端。负数在最左侧，正数在最右侧降级接下来就是第二个问题当新加入的65535又被删除了redis该怎么办，这个时候元素长度实际16位就可以满足了，但是此时encoding却是32位的。按照我的看法应该在实现降级！但是遗憾的是redis并没有，那么请思考为什么没有？如果让你实现你将如何实现为什么不实现降级当加入元素超过当前长度我们很容易就知道此时需要进行升级操作，但是当我们删除一个数据时我们如何判断是否需要降级却很困难，我们需要重新遍历一遍剩下的元素是否小于当前长度，实现复杂度O(N) 。这就是为什么不进行降级原因之一你可能会说重新遍历一遍很快的反正在内存中，那么你有没有想过如果降级之后又遇到升级情况，这样来回的升级降级就降低了我们程序的性能了。我们知道升级是必须的所以这里降级redis采取的是忽略的策略小结

无事小神仙

【redis前传】zset如何解决内部链表查找效率低下|跳表构建

前言紧接前文我们学习了Redis中Hash结构。在里面我们梳理了字典这个重要的内部结构并分析了hash结构rehash的流程从而解释了为什么redis单线程还是那么快本章节我们将视角下推，继续学习Redis五大天王中的zset数据结构 ; zset是有序不重复集合其内部元素唯一且是有序的，他的排序标准是根据其内部score维度进行排序的。zset结构基本单元关于zset结构很简单，一个是我们之前学习的字典结构(简单理解成Hash结构)，另外一个是跳跃表结构 ；  关于字典我们上一章节已经详细解说了其内部的构造及其如何进行数据扩容等操作！剩下的且符合今天我们学习主旨的自然就是这个熟悉又陌生的zskiplist。我们根据上面zset的结构图也能够看出来，zskiplist实际上就是一个链表。zskiplist我们查看源码不难看出其内部结构是对zset中链表的一个抽象描述。zskiplist首先会对这个链表记录其头结点、尾结点方便通过zskiplist进行遍历操作。剩下的length自然就是对内部的这个链表数量的统计。比较抽象的是这个level的理解。在上面我们也看到了zskiplist那个链表实际上会有分层的概念。笔者这里通过不同的颜色进行表述不同层级的概念。笔者这里针对上述描述的跳跃表内部的zskiplist绘画了一张内部数据图在对zskiplist结构描述和数据描述中我将他们拆开理解，觉得这样更容易理解结构关系。下面是整个图示细心的读者应该能够发现，我好想漏掉了链表重要组成部分zskiplistNode这个重要的节点说明。实际上他就是我们右侧那个链表中节点。换句话说链表中每个点就是zskiplistNode 。level跳跃表的重要特性类型与树结构可以避免逐个遍历的苦恼。那么他是如何实现这种跳跃性质的访问的呢？还有一点为什么redis会这么设计。首先我们先回答下为什么这么设计。在链表中插入、删除等操作是很快速的只需要改变指针指向就可以完成。但是对于查询来说他需要遍历整个链表才能完成操作。针对链表的这个弊端redis设计了跳表的数据结构。下面就是针对如何实现来简单梳理下。上述zskiplistNode节点对象结构中我们也可以看到有个level属性。redis就是通过这个属性来实现跳跃的特性。在每个节点生成的时候回随机生成这个level值。他就表示这个节点所在层的范围。关于这个level为什么说是随机。这有牵涉到其内部的幂等性算法。这个算法保证数字越大生成的概览越小。在redis内部level最大值32.比如说level随机生成5 。  表示当前节点node在level1~level5这五层中。上面的图示中所示的三个节点生成的level值分别是level3、level2、level7。注意在实际存储中level索引时从0开始。forward在level中还有两个属性分别是前进指针、跨越长度。根据字面意思我们能够理解前进指针是想链表后端方向推进的指针。其跨度就是表示当前节点距离前进指针处节点的距离。这个距离的是参考最底层的距离的。双链表在zskiplist中每一层都是一个单向链表。在level中通过forwar指针指向我们表尾。那么为什么我说是双链表呢？这里的双链表不是严格意义的双链表。但是我们可以借助这些层级的单链表实现我们双向自由路由。随机层上面我们已经解释过level的定义了。那么为什么这里还有再提一遍呢？因为上面我们简单提到了幂等性算法。这里我们就详细解释下什么是幂等性。首先根据level的定义我们可以总结如下几点关于level的特性。①、一个节点如果在level[i]中，那么他一定在level[i]以下的层中②、越高层元素跨度越大，这个跨度是不定的。取决于生成节点时的随机算法③、每一层都是一个链表这是redis中源码部分。关于这个随机level的算法其实不是很难理解。笔者这里将上述代码进行流程化梳理就是一个不断重试的机制。其中p和maxLevel都是代码中的固定值。在这个算法机制下我们就可以尽可能的保证在数据量小的情况下保证level不会特别的高。换句话说我们的level就不会显得特别的突兀。如果是纯粹的随机生成的话就有可能有的节点level很低，有的level很高。这样会造成资源不必要的浪费。查找好了，同学们到了这里我们已经学习了关于zset的基本结构。 简单回顾下内部就是字典+跳表的结合。下面我们针对这两种数据结构来简单梳理下关于zset的常用的一些操作！首先就是我们的查找。上面说了那么多内部结构。纸上谈兵终觉浅，我们还需要实战操作一下。分数定位上述的命令基本都是通过分数定位然后在做自己的业务处理。图示中已经说明了我们过程。首先是在最高层中寻找因为高层最稀疏。当高层没有发现时我们就会下推层级。此时我们来到level中的节点1.然后在通过forwar指针进行前移。最终定位节点5。还有一点补充说明：节点中通过obj指针指向实际内容，score存储分支；笔者这里为什么演示方便直接在节点中标注了分数。其他部分并未进行标注！！！成员定位笔者在整理相关逻辑的时候也是经过百度、视频、书籍等方式翻阅后作出的结论。原谅我的能力无法直接阅读源码！但是在查阅资料的过程中。发现很少有说明是如何进行成员定位的。因为zset中除了分数的相关命令以外还有不少是基于成员定位的。上述命令部分是基于成员进行定位的。在zset结构中实际节点是有基于score进行排序的。在obj中没有顺序可言。我们无法按照我们上述通过分数进行逐层定位元素！这就牵扯到我们另外一个重要的角色【字典(hash)】了。上图是我们上一章节的关于字典的说明。在通过成员定位的时候我们就是多了一步先从字典中定位到分数，然后在重复上面的步骤进行定位！了解结构自然就能很容易理解相关的操作。站在巨人的肩膀我们虽然不需要在重复的造轮子了。但是我们得知道当初前辈们造轮子的过程！吃水不忘挖井人！命令内部理解了解结构就能快速掌握命令，否则就算死记硬背命令过一阵子又会忘记了。但是牢记结构后我们就会知道有命令可以实现我们的需求然后根据手册就可以得心应手。下面我们看看一下四个命令是如何实现的吧。zcard通过zskiplist中length属性zcount通过分数定位边界，然后遍历底层链表最终得到统计数量zlecount通过字典定位分数，在执行zcount操作zrank返回有序集合中指定成员的索引 ， 先定位成员，定位过程中通过span可以确定排名总结zset是一种有序链表。为了解决链表查询低下从而redis构建了跳表的数据结构。大大提高了效率！关于zset的数据结构我们实际好多案例可以通过它来实现；延时队列、内部LRU、热点数据等等