数据结构

redis能在微秒级别通过key快速查询到数据，除了它是内存型数据库外，还得益于它的数据存储结构。

全局哈希表

上图是 redis 数据类型和底层数据结构的关系，在此之前，我们首先了解一个重要的知识，全局哈希表。redis 中所有的数据，也即键值对都存储在一个哈希表中，哈希表的本质是数组，每个节点为一个哈希桶，桶中存储的就是 <key，value> 结构的键值对，value 存储的是真实数据内存地址，而不是真实数据本身。结构如图所示：

当发生哈希冲突时，会在同一个通中退化成链式结构，这点和HashMap一样。

为了避免哈希冲突，通常会在合适的时候进行扩容，扩容的逻辑如下：

1. 申请一个更大的哈希表
2. 之后每来一个请求，就把原来哈希表的元素复制一个到新的哈希表中，从第一个开始复制
3. 将一次性大量复制的开销分摊到每次请求上，避免了耗时操作。

压缩列表

压缩列表实际上类似数组，在数组的头部有3个特殊元素节点，分别存储列表长度、列表尾部偏移量、列表中实际数据的元素个数。数组尾部有一个特殊的结束标识节点。

这样设计的目的的查询列表头尾的速度是O(1)，其他元素是O(n)。

对于List类型的数据，如果元素个数很少，就用压缩列表的结构存储，否则就用双向链表存储。期间可能发生数据结构变更的操作。实际上在 Redis3.2 之后，用了一种新的数据结构 quickList，他的原理就是把元素划分为多个分段，每个分段中的元素个数不多，他们的结构是压缩表，分段与分段之间用的双向链表。这样就同时拥有了2个结构的优点，还不会发生结构转变。

• 内存优化案例

  需求是存储大量 10000123 - 33423923851 这种数字的映射关系。

  如果直接选择String类型存储。将会产生大量的dictEntry，其中的指针和元数据相较于数据本 身，占用了大量的内存。

  将 10000123 拆分成 10000 和 123 两部分，前面的 10000 当作 key ，后面的 123 和 33423923851 作为 hash 类型存储。这样一个 key 下面是一个 hash 列表，其中最多有 1000 个元素。当这些元素用压缩列表结构存储时，就能节省大量内存了。

BigMap

数据结构如下：value是一连串的二进制，每一个bit位表示一种二值状态。

• 示例

  # 8对应的ASCII码为：0011 1000
  127.0.0.1:6379> set mykey "8"
  OK
  
  # 8对应的ASCII码为：0011 1000
  127.0.0.1:6379> getbit mykey 0
  (integer) 0
  127.0.0.1:6379> getbit mykey 1
  (integer) 0
  127.0.0.1:6379> getbit mykey 2
  (integer) 1
  127.0.0.1:6379> getbit mykey 3
  (integer) 1
  127.0.0.1:6379> getbit mykey 4
  (integer) 1
  127.0.0.1:6379> getbit mykey 5
  (integer) 0
  127.0.0.1:6379> getbit mykey 6
  (integer) 0
  127.0.0.1:6379> getbit mykey 7
  (integer) 0
  
  命令格式  SETBIT key offset value ，表示针对key存储的数据在 offset这个位置的值设置为value（ 只能是 0 或 1 ）
  
  # 将第8位（索引为7）的位设置为1
  127.0.0.1:6379> setbit mykey 7 1
  (integer) 0
  127.0.0.1:6379> getbit mykey 7
  (integer) 1

• 场景

  比如我们有一个App，需要统计2021年每个用户登录的情况，针对这个需求，我们以用户id+2021作为key，将用户上线那天对应的offset设置为1，这样就可以统计每个用户在本年度登录的情况，使用 BITCOUNT 命令就可以统计登录天数。

  举个例子，今天是2021年第100天，而user_id:10001在今天阅览过网站，那么执行命令 SETBIT 2021:user_id:10001 100 1 ；如果明天该用户（10001）也登录的App，那么执行命令 SETBIT 2021:user_id:10001 101 1 ，以此类推。

  最后使用 BITCOUNT 2021:user_id:10001，就可以统计该用户本年度登录App的次数了

  通过上例我们可以看出，使用Bitmap来统计二值数据非常节省内存，一个用户一年只需要占用 365个比特，10年也只需要 365*10/8=456个字节。

HyperLogLog

HyperLogLog 是用来做基数统计的算法，所谓基数就是统计集合的总个数，每个HyperLogLog 只要12kb 的内存就能 2^64 个不同元素的基数，这是因为其只会在加入元素的时候计算基数，而不会存储元素本身，另外基数统计只适用于大基数的统计，并且结果会有一定的误差，是可以接受的误差范围。

• 示例

  # 命令格式：PFADD key element [element …]  
  # 返回的结果是基数是否变化
  # 如果给定的键不存在，那么命令会创建一个空的 HyperLogLog，并向客户端返回 1
  127.0.0.1:6379> PFADD ip_20190301 "192.168.0.1" "192.168.0.2" "192.168.0.3"
  (integer) 1
  # 元素估计数量没有变化，返回 0（因为192.168.0.1 已经存在）
  127.0.0.1:6379> PFADD ip_20190301 "192.168.0.1"
  (integer) 0
  # 添加一个不存在的元素，返回 1。注意，此时 HyperLogLog 内部存储会被更新，因为要记录新元素
  127.0.0.1:6379> PFADD ip_20190301 "192.168.0.4"
  (integer) 1
  
  # 返回 ip_20190301 包含的唯一元素的近似数量
  127.0.0.1:6379> PFCOUNT ip_20190301
  (integer) 4
  127.0.0.1:6379> PFADD ip_20190301 "192.168.0.5"
  (integer) 1
  127.0.0.1:6379> PFCOUNT ip_20190301
  (integer) 5
  127.0.0.1:6379> PFADD ip_20190302 "192.168.0.1" "192.168.0.6" "192.168.0.7"
  (integer) 1
  # 返回 ip_20190301 和 ip_20190302 包含的唯一元素的近似数量
  127.0.0.1:6379> PFCOUNT ip_20190301 ip_20190302
  (integer) 7

• 场景

  比如统计页面的用户数，每日访问ip数，在线用户数，月活。

  用户1001 访问的时候执行命令 PFADD page:index 1001 ，用户1002 访问的时候执行命令 PFADD page:index 1002 。以此类推，最后使用命令 PFCOUNT page:index 就能统计出index页面访问的用户数了。

GEO

用来存储地理位置信息，原理是把经纬度进行若干次的二分，每次的结果进行编码后得到一个值，用该值作为权重。

• 场景

  有一年汽车id是33，他的位置经纬度是（ 116.034579 , 39.030452），
  执行命令 GEOADD cars:locations 116.034579 39.030452 33 就能建立位置和汽车的映射。
  执行命令 GEORADIUS cars:locations 116.054579 39.030452 5 km ASC COUNT 10 就能求出 小明所处位置（116.054579 ， 39.030452）周边 5km 范围内距离最近的10辆汽车id。

后记

当然 redis 还有其他数据结构，比如流等，但是一般不会用 redis 来处理，有更适合的方案。本文列举的都是常用的、好用的。实际上最关键的还是全局哈希表，能徒手画出那张图就算融会贯通了。