技术史上的画蛇添足: Redis HGETALL 排序问题

一个系列

在技术史上,有很多彼时的 bug 历经岁月锤炼最后化身 feature 的事儿发生。
在阅读一些热门开源框架代码时,经常能发现狗血的、难以置信的、童真的、幽默的、这也能写的,代码。
以上这些,都值得吐槽。吐槽是为了解构“权威”,此处的权威是应用广泛,少有人提出异议的框架工具、架构设计、代码组织等。通过解构,进一步了解软件工程的本质。
今天要说的,是 Redis …… 里面一个很小的特性。
如果时间允许的话,我想写成一个系列。

一个例子

我们利用 Redis Hash 实现一个简单的需求——
存储一些 tweets,然后读取出来,顺序地展示在页面上。
技术选型我们采用 Redis 和 Python。

第一步,顺序存储 tweets

import redis

tweets = [{
  "id": 250075927172759552,
  "geo": null,
  "retweeted": false,
  "in_reply_to_user_id": null,
  "place": null,
    ...
  },
  ...
]
rc = redis.Redis(host='localhost', port='6379', db=0)
for tweet in tweets:
    rc.hsetnx('tweets', tweet['id'], tweet)

登入 redis,查看:

127.0.0.1:6379> HGETALL 'tweets'
1) "250075927172759552"
2) "{...}"
3) "250075927172759553"
4) "{...}"
5) "250075927172759554"
6) "{...}"
7) "250075927172759555"
8) "{...}"

看上去是顺序输出,有点谱,继续下边的逻辑实现。

第二步,顺序展示 tweets

import redis
rc = redis.Redis(host='localhost', port='6379', db=0)
tweets = rc.hgetall('tweets')
...

这时候我们会发现,tweets 变成了这样:

tweets = {
    '250075927172759552': {...},
    '250075927172759555': {...},
    ...
}

一个无序的 dict
显然,这完成不了我们的顺序输出的需求。
难道,是 redis-py 这个框架实现错了吗?

Redis HGETALL 和它的 Python 实现

redis-py 的 hgetall

首先来解决第一个问题,是否 redis-py 实现错了——
redis-py 和此处有关的源码是:
https://github.com/andymccurdy/redis-py/blob/master/redis/client.py#L406

'HGETALL': lambda r: r and pairs_to_dict(r) or {},

https://github.com/andymccurdy/redis-py/blob/master/redis/client.py#L184

def pairs_to_dict(response):
    "Create a dict given a list of key/value pairs"
    it = iter(response)
    return dict(izip(it, it))

一个明显的字典转换。

HGETALL 的文档描述及源码

再来看 HGETALL 的文档——

Returns all fields and values of the hash stored at key. In the returned value, every field name is followed by its value, so the length of the reply is twice the size of the hash.

没有提到任何和排序有关的描述,也即,不保证返回结果的排序。
那,上边看到的顺序输出是什么意思?Redis 官方客户端画蛇添足了?再者说,一个严肃的 Hash,key 怎么可能是顺序存储的?
我们看下 HGETALL 的源码:
https://github.com/antirez/redis/blob/4.0/src/t_hash.c#L37

/* Check the length of a number of objects to see if we need to convert a
 * ziplist to a real hash. Note that we only check string encoded objects
 * as their string length can be queried in constant time. */
void hashTypeTryConversion(robj *o, robj **argv, int start, int end) {
    int i;
    if (o->encoding != OBJ_ENCODING_ZIPLIST) return;
...

从源码可以看到,默认情况下,Redis 的 Hash 是使用 ziplist 进行存储的,当超出一定限制后,再改为一个正统的 hash 进行存储。ziplist 是一个双向链表,所以是顺序的,这就是上边我们看到的。下面我们看看在什么情况下会进行转换。

redis Hash 的 ziplist 和 hash 的转换条件

# 哈希对象只包含一个键和值都不超过 64 个字节的键值对
127.0.0.1:6379> HSET test_hash test_key "value's length less than 64 bytes"
(integer) 1
127.0.0.1:6379> OBJECT ENCODING test_hash
"ziplist"
# 向哈希对象添加一个新的键值对,键的长度为 66 字节
127.0.0.1:6379> HSET test_hash long_long_long_long_long_long_long_long_long_long_long_description "content"
(integer) 1
# 编码改变
127.0.0.1:6379> OBJECT ENCODING test_hash
"hashtable"

# 创建一个包含 512 个键值对的哈希对象
127.0.0.1:6379> EVAL "for i=1, 512 do redis.call('HSET', KEYS[1], i, i) end" 1 "numbers"
(nil)
127.0.0.1:6379> HLEN numbers
(integer) 512
127.0.0.1:6379> OBJECT ENCODING numbers
"ziplist"
# 再向哈希对象添加一个新的键值对,使得键值对的数量变成 513 个
127.0.0.1:6379> HMSET numbers "key" "value"
OK
127.0.0.1:6379> HLEN numbers
(integer) 513
# 编码改变
127.0.0.1:6379> OBJECT ENCODING numbers
"hashtable"

在两种情况下,Hash 会使用 ziplist 进行存储:

  1. 哈希对象保存的所有键值对的键和值的字符串长度都小于 64 字节;
  2. 哈希对象保存的键值对数量小于 512 个;

其中,64 字节和 512 分别可以通过配置文件中的 server.hash_max_ziplist_valueserver.hash_max_ziplist_entries 进行配置。

结语

通过阅读文档和源码,我们可以知道,乍看 Redis Hash 是顺序存储这个假象可以很好地被解释。redis 的文档写的也没什么毛病。Redis 默认使用 ziplist 来存储 Hash、List、ZSet 这些数据结构,目的只有一个:节约内存。
而在本例中,Redis 的这种做法引发了一个错觉,这是完全合理的,一个 Cache,当然要追求性能。
感谢 Redis 作者及开源贡献者!

References