如何用Java和Redis设计一个高效的先入先出的队列

分析：

redis的list底层是多个ziplist结构组成的“双向”链表。中间部分还压缩了一下。

最外层是由两个哈希表构成的dict。

哈希表的get(key)时间复杂度为O(1),而且这个O(1)理论上不会因为所占内存的大小和元素数目所改变。list的出队列和入队 *** 作也都是O(1)。

Java的队列时间复杂度也应为O(1)。

可不可以直接用redis的list做先进先出？

情况1，数据数量不多，可以用

情况2，数据量多，但存的数据是激活码这样简单值一类，可以用。

情况3，list存的是要获取数据的索引，大量数据的值已经存在redis的KV结构中。

这时候，如果数据每次获取下一个数据都要执行redis的hash查找（O(1)）然后redis的list从头或者末尾出一个。经过网络IO返回，Java程序在用出来的key去请求redis去get(key) （O(1)）。这里是两次网络IO或者进程间的IO。

这时候，可以不用redis的list存索引而只是用redis大的KV哈希结构存键值。用①Java的队列先进先出获取下一个key或者②使用预先规定好的键生成的规则，让键是有规则有顺序的，比如自增ID，然后每次获取都是ID++，而直接从redis.get(ID.next())来获取值。

最后一种就是最高效的办法，为了特殊场景的高效出队列而设计。但是如果只是一般的数据量，使用redis的list也未尝不可。

ziplist 编码的哈希对象使用压缩列表作为底层实现， 每当有新的键值对要加入到哈希对象时， 程序会先将保存了键的压缩列表节点推入到压缩列表表尾， 然后再将保存了值的压缩列表节点推入到压缩列表表尾， 因此：

保存了同一键值对的两个节点总是紧挨在一起， 保存键的节点在前， 保存值的节点在后；

先添加到哈希对象中的键值对会被放在压缩列表的表头方向， 而后来添加到哈希对象中的键值对会被放在压缩列表的表尾方向。

举个例子， 如果我们执行以下 HSET 命令， 那么服务器将创建一个列表对象作为 profile 键的值：

另一方面， hashtable 编码的哈希对象使用字典作为底层实现， 哈希对象中的每个键值对都使用一个字典键值对来保存：

Redis 的字典使用哈希表作为底层实现， 一个哈希表里面可以有多个哈希表节点， 而每个哈希表节点就保存了字典中的一个键值对。

Redis 字典所使用的哈希表由 dict.h/dictht 结构定义：

table 属性是一个数组， 数组中的每个元素都是一个指向 dict.h/dictEntry 结构的指针， 每个 dictEntry 结构保存着一个键值对。

size 属性记录了哈希表的大小， 也即是 table 数组的大小， 而 used 属性则记录了哈希表目前已有节点（键值对）的数量。

sizemask 属性的值总是等于 size - 1 ， 这个属性和哈希值一起决定一个键应该被放到 table 数组的哪个索引上面。

图 4-1 展示了一个大小为 4 的空哈希表 （没有包含任何键值对）。

哈希表节点使用 dictEntry 结构表示， 每个 dictEntry 结构都保存着一个键值对：

key 属性保存着键值对中的键， 而 v 属性则保存着键值对中的值， 其中键值对的值可以是一个指针， 或者是一个 uint64_t 整数， 又或者是一个 int64_t 整数。

next 属性是指向另一个哈希表节点的指针， 这个指针可以将多个哈希值相同的键值对连接在一次， 以此来解决键冲突（collision）的问题。

举个例子， 图 4-2 就展示了如何通过 next 指针， 将两个索引值相同的键 k1 和 k0 连接在一起。

Redis 中的字典由 dict.h/dict 结构表示：

type 属性和 privdata 属性是针对不同类型的键值对， 为创建多态字典而设置的：

ht 属性是一个包含两个项的数组， 数组中的每个项都是一个 dictht 哈希表， 一般情况下， 字典只使用 ht[0] 哈希表， ht[1] 哈希表只会在对 ht[0] 哈希表进行 rehash 时使用。

除了 ht[1] 之外， 另一个和 rehash 有关的属性就是 rehashidx ： 它记录了 rehash 目前的进度， 如果目前没有在进行 rehash ， 那么它的值为 -1 。

图 4-3 展示了一个普通状态下（没有进行 rehash）的字典：

在Redis中，由于它对实时性要求更高，因此使用了渐进式rehash

当有新键值对添加到Redis字典时，有可能会触发rehash。Redis中处理哈希碰撞的方法与Java一样，都是采用链表法，整个哈希表的性能则依赖于它的大小size和它已经保存节点数量used的比率。

比率在1:1时，哈希表的性能最好，如果节点数量比哈希表大小大很多的话，则整个哈希表就退化成多个链表，其性能优势全无。

上图的哈希表，平均每次失败查找需要访问5个节点。为了保持高效性能，在不修改键值对情况下，

需要进行rehash，目标是将ratio比率维持在1:1左右。

Ratio ＝ Used / Size

rehash触发条件：

rehash执行过程：

Redis哈希为了避免整个rehash过程中服务被阻塞，采用了渐进式的rehash，即rehash程序激活后，并不是

马上执行直到完成，而是分多次，渐进式（incremental）的完成。同时，为了保证并发安全，在执行rehash

中间执行添加时，新的节点会直接添加到ht[1]而不是ht[0], 这样保证了数据的完整性与安全性。

另一方面，哈希的Rehash在还提供了创新的（相对于Java HashMap）收缩（shrink）字典，当可用节点远远

大于已用节点的时候，rehash会自动进行收缩，具体过程与上面类似以保证比率始终高效使用。

当哈希对象可以同时满足以下两个条件时， 哈希对象使用 ziplist 编码：

第一：Redis 是什么？

Redis是基于内存、可持久化的日志型、Key-Value数据库 高性能存储系统，并提供多种语言的API.

第二：出现背景

数据结构(Data Structure)需求越来越多, 但memcache中没有, 影响开发效率

性能需求, 随着读 *** 作的量的上升需要解决，经历的过程有: 

数据库读写分离(M/S)–>数据库使用多个Slave–>增加Cache (memcache)–>转到Redis

解决写的问题： 

水平拆分，对表的拆分，将有的用户放在这个表，有的用户放在另外一个表；

可靠性需求 

Cache的"雪崩"问题让人纠结 

Cache面临着快速恢复的挑战

开发成本需求 

Cache和DB的一致性维护成本越来越高(先清理DB, 再清理缓存, 不行啊, 太慢了!) 

开发需要跟上不断涌入的产品需求 

硬件成本最贵的就是数据库层面的机器，基本上比前端的机器要贵几倍，主要是IO密集型，很耗硬件；

维护性复杂 

一致性维护成本越来越高； 

BerkeleyDB使用B树，会一直写新的，内部不会有文件重新组织；这样会导致文件越来越大；大的时候需要进行文件归档，归档的 *** 作要定期做； 

这样，就需要有一定的down time；

基于以上考虑， 选择了Redis

第三：Redis 在新浪微博中的应用

Redis简介

1. 支持5种数据结构

支持strings, hashes, lists, sets, sorted sets 

string是很好的存储方式，用来做计数存储。sets用于建立索引库非常棒；

2. K-V 存储 vs K-V 缓存

新浪微博目前使用的98%都是持久化的应用，2%的是缓存，用到了600+服务器 

Redis中持久化的应用和非持久化的方式不会差别很大： 

非持久化的为8-9万tps，那么持久化在7-8万tps左右； 

当使用持久化时，需要考虑到持久化和写性能的配比，也就是要考虑redis使用的内存大小和硬盘写的速率的比例计算；

3. 社区活跃

Redis目前有3万多行代码, 代码写的精简，有很多巧妙的实现，作者有技术洁癖 

Redis的社区活跃度很高，这是衡量开源软件质量的重要指标，开源软件的初期一般都没有商业技术服务支持，如果没有活跃社区做支撑，一旦发生问题都无处求救；

Redis基本原理

redis持久化(aof) append online file： 

写log(aof), 到一定程度再和内存合并. 追加再追加, 顺序写磁盘, 对性能影响非常小

1. 单实例单进程

Redis使用的是单进程，所以在配置时，一个实例只会用到一个CPU； 

在配置时，如果需要让CPU使用率最大化，可以配置Redis实例数对应CPU数, Redis实例数对应端口数(8核Cpu, 8个实例, 8个端口), 以提高并发: 

单机测试时, 单条数据在200字节, 测试的结果为8~9万tps；

2. Replication

过程: 数据写到master–>master存储到slave的rdb中–>slave加载rdb到内存。 

存储点(save point): 当网络中断了, 连上之后, 继续传. 

Master-slave下第一次同步是全传，后面是增量同步；、

3. 数据一致性

长期运行后多个结点之间存在不一致的可能性； 

开发两个工具程序： 

1.对于数据量大的数据，会周期性的全量检查； 

2.实时的检查增量数据，是否具有一致性；

对于主库未及时同步从库导致的不一致，称之为延时问题； 

对于一致性要求不是那么严格的场景，我们只需要要保证最终一致性即可； 

对于延时问题，需要根据业务场景特点分析，从应用层面增加策略来解决这个问题； 

例如： 

1.新注册的用户，必须先查询主库； 

2.注册成功之后，需要等待3s之后跳转，后台此时就是在做数据同步。

第四：分布式缓存的架构设计

1.架构设计

由于redis是单点，项目中需要使用，必须自己实现分布式。基本架构图如下所示：

2.分布式实现

通过key做一致性哈希，实现key对应redis结点的分布。

一致性哈希的实现：

l        hash值计算：通过支持MD5与MurmurHash两种计算方式，默认是采用MurmurHash，高效的hash计算.

l        一致性的实现：通过java的TreeMap来模拟环状结构，实现均匀分布

3.client的选择

对于jedis修改的主要是分区模块的修改，使其支持了跟据BufferKey进行分区，跟据不同的redis结点信息，可以初始化不同的 ShardInfo，同时也修改了JedisPool的底层实现，使其连接pool池支持跟据key,value的构造方法，跟据不同 ShardInfos，创建不同的jedis连接客户端，达到分区的效果，供应用层调用

4.模块的说明

l        脏数据处理模块，处理失败执行的缓存 *** 作。

l        屏蔽监控模块，对于jedis *** 作的异常监控，当某结点出现异常可控制redis结点的切除等 *** 作。

整个分布式模块通过hornetq，来切除异常redis结点。对于新结点的增加，也可以通过reload方法实现增加。（此模块对于新增结点也可以很方便实现）

对于以上分布式架构的实现满足了项目的需求。另外使用中对于一些比较重要用途的缓存数据可以单独设置一些redis结点，设定特定的优先级。另外对 于缓存接口的设计，也可以跟据需求，实现基本接口与一些特殊逻辑接口。对于cas相关 *** 作，以及一些事物 *** 作可以通过其watch机制来实现。

声明：所有博客服务于分布式框架，作为框架的技术支持及说明，框架面向企业，是大型互联网分布式企业架构，后期会介绍linux上部署高可用集群项目。

---