存储小技巧 ｜ 大端序在存储领域 — 有序 Key 的构造

背景描述

奇伢需要把一对键值数据存储到一个 kv （ rocksdb ）引擎里，key 从用户视角是有序的，key 的构造是一个组合信息，里面是关键元素是一个单调递增的整形。当然，设置进去的时候 key 和 value 要都是通用的字节序列，也就是 []byte 类型。所以这里就涉及到一个关键问题怎么去序列化 key ？

先来看下 key 的原始结构体构造，由 namespace 和 id 组成：

type KeyStruct struct {
    Namespace string
    Idx       uint16
}

最常见的 Key 的构造方法就是字符串拼起来，如下：

// key => {namespace}/{id}
key := []byte(fmt.Sprintf("%s/%v", k.Namespace, k.Idx))

namespace 其实就是用来划分子空间的字符串，id 则是一个 8 字节的整数型，标识的是该命名空间内的唯一值。

构造字符串然后转成 []byte 构造 key ，这个思路很简单。也是最符合人的第一思考。举个例子来简单看下效果。假设 namespace 是 "apple" ，id 从 1 开始递增，那么对应的 key 字符串表现就是：

"apple/1"
"apple/2"
"apple/3"
"apple/10"
"apple/11"
"apple/12"
...

当我把上述一系列的 key 存入 rocksdb 里之后，但当逐条遍历取出来的时候，遇到了问题。因为取出的顺序是：

"apple/1"
"apple/10"
"apple/11"
"apple/12"
"apple/2"
"apple/3"
...

小知识：rocksdb 的 key 存入的时候是排序的。默认按照“字典序”排序。

What ？这不是我想要的顺序！ 我想要的是这样：

"apple/1"
"apple/2"
"apple/3"
"apple/10"
"apple/11"
"apple/12"
...

这才是符合我们人类的认知习惯，从小到大。

如何做到呢？

什么是字典序？

Go 里面 string 是可以用运算符号直接比较的，默认用的“字典序”。前面提了一嘴 rocksdb 排列 key 的时候也是用字典序，那什么是字典序呢？

定义可以网上冲浪查。简单讲就是类似查字典时候用的顺序，基于字母顺序排列的单词按字母顺序排列的方法。这里不纠结定义，举几个例子来理解下。

key 1 => 0x1, 0x1, 0x2
key 2 => 0x1, 0x2, 0x3
key 3 => 0x1, 0x2, 0x4
key 4 => 0x2, 0x1
key 5 => 0x3

上面就是字典序排列的结果。说白了就是逐个字节比较。从第一个字节开始比较，大的放后面，小的放前面。相等就看下一个字节，直到排列结束。

好，回头看上面的构造字符串的在内存的值如下：

apple, 1   => 97 'a'  112 'p' 112 'p' 108 'l' 101 'e' 47 '/'  49 '1'
apple, 10  => 97 'a'  112 'p' 112 'p' 108 'l' 101 'e' 47 '/'  49 '1'  48 '0'
apple, 11  => 97 'a'  112 'p' 112 'p' 108 'l' 101 'e' 47 '/'  49 '1'  49 '1'
apple, 12  => 97 'a'  112 'p' 112 'p' 108 'l' 101 'e' 47 '/'  49 '1'  50 '2'
apple, 2   => 97 'a'  112 'p' 112 'p' 108 'l' 101 'e' 47 '/'  50 '2'
apple, 3   => 97 'a'  112 'p' 112 'p' 108 'l' 101 'e' 47 '/'  51 '3'

ASCII 码一共 128 个字符。对照 ASCII 码 ，字母 'a' 的编码值是 97 ，字符 '1' 对应的编码值是 49 。

所以，如果按照字典序来排序，字符串 '2' 的编码是 50 ，字符串 '10' 的编码是 49, 48 ，49 < 50 ，所以自然放前面。上面的结果自然就不符合我们的预期。

究竟要怎么做呢？

有个办法倒是，自己写一个序列化，核心的地方用大端序。

const (
    // 假设第一个字段 5 个字节
    namespanceLen = 5
)

func generateKey(k *KeyStruct) []byte {
    var offset int

    key := make([]byte, namespanceLen+2)
    copy(key[offset:], []byte(k.Namespace)[:namespanceLen])

    offset += len(k.Namespace)
    binary.BigEndian.PutUint16(key[offset:], k.Idx)

    return key
}

这个序列化之后:

apple, 1   => 97 'a'  112 'p' 112 'p' 108 'l' 101 'e'  0 '\000'  1 '\001'
apple, 2   => 97 'a'  112 'p' 112 'p' 108 'l' 101 'e'  0 '\000'  2 '\002'
apple, 3   => 97 'a'  112 'p' 112 'p' 108 'l' 101 'e'  0 '\000'  3 '\003'
apple, 10  => 97 'a'  112 'p' 112 'p' 108 'l' 101 'e'  0 '\000'  10 '\n'
apple, 11  => 97 'a'  112 'p' 112 'p' 108 'l' 101 'e'  0 '\000'  11 '\v'
apple, 12  => 97 'a'  112 'p' 112 'p' 108 'l' 101 'e'  0 '\000'  12 '\f'

根据字典序排列之后，这才是我们想要的样子。

不过这里有个小问题就是自定义的字节数组已经不能直接转化成字符串，否则你可能看到的是乱码。要自己写反序列化的代码。举个例子：

func parseKey(key []byte) (ks *KeyStruct) {
    ks = &KeyStruct{}

    ks.Namespace = string(key[:namespanceLen])
    ks.Idx = binary.BigEndian.Uint16(key[namespanceLen:])

    return ks
}

注意：上面的例子简单化处理，正式的版本关于空间的分配要仔细斟酌一下。序列化的长度定长还是不定长？这个看个人需求。

所以按照这样方法构造的 key 存入 rocksdb 之后，就是按照我们认知的顺序取出来了。

总结

1. 当既想要拼接复合信息，又想要按照直观的顺序，那么可能不能直接构造字符串，而是要自定义序列化规则；
2. 字符串拼接也只是一种序列化的方式而已，注意这个顺序的细节，因为可能不是你想要的顺序；
3. 这是一个非常典型的大端序在存储领域的小应用，排序更符合人的认知（并且某些场景也依赖这种排序的结果）。这种方式要注意的是直接取出转化为字符串的话可能会乱码，所以这种场景要配合专门的反序列化哦；

本文由哈喽比特于1年以前收录，如有侵权请联系我们。
文章来源：https://mp.weixin.qq.com/s/WyIP6M4-z9onI_WHqQs5RQ