不用碰撞：读懂一段 Lua，O(1) 造出落在指定 Slot 的 Redis Key

大纲

先打个比方。Redis Cluster 就像一个有 16384 个抽屉的大柜子，每条数据都要放进其中一个抽屉。放哪个抽屉，不是你随便挑的——你给数据起个名字（叫 Key），柜子有一套固定的算法，拿这个名字算出一个 0 到 16383 的编号，这个编号就叫 Slot（槽），数据就进那个抽屉。

平时大家都是顺着用：给名字，柜子告诉你进几号抽屉。但有时候我们想反着来：我偏要让数据进 5461 号抽屉，那我该给它起个什么名字？换句话说——给定抽屉号，倒推一个能落进去的名字。

这需求不是闲得慌。大促前想把热点数据均匀铺到各个分片上、多机房想把某批数据钉在就近的节点上、压测想精确控制负载打到哪台机器——这些时候，你手里攥的是“目标抽屉号”，缺的正是“能落进去的名字”。

大多数人第一反应是瞎试（专业点叫“碰撞”）：随便起个名字，算一下落哪个抽屉，不对就再换一个，直到蒙对为止。能用，但很笨——想蒙中某个指定抽屉，平均得试一万多次；而且快慢全看运气，偶尔卡你一下。要是你一秒钟要造几百万个名字，这点开销就受不了了。

这篇不讲瞎试，讲一段真实的 Lua 代码怎么一步到位、直接算出答案。 给它一个抽屉号，它立刻吐出一个保证落进去的名字，不循环、不试错。我把这段代码对全部 16384 个抽屉逐一验证过，个个对得上。更重要的是——它背后的道理一点都不玄，没学过高数、刚入门编程的人也能看懂。往下我一段一段拆给你看。

先认识这段代码的两个出口

整段 Lua 对外只开两个函数，先记住它俩，别的都是为它俩服务的：

_M.slot(key)       -- 正向：给 Key,算它落哪个槽
_M.for_slot(slot)  -- 反向:给槽号,造一个命中它的 Key

slot() 是 Redis 本来就在做的事，我们用它来验证；for_slot() 才是这篇的主角。先看 slot()，因为理解它是理解一切的前提。

slot()：Redis 怎么把 Key 变成槽号

function _M.slot(key)
    if type(key) ~= "string" then return nil end
    -- Redis 只认第一对非空花括号。空的第一对会退回整串计算,
    -- 哪怕后面还有非空的花括号。
    local first = key:find("{", 1, true)
    local last = first and key:find("}", first + 1, true)
    if last and last > first + 1 then
        key = key:sub(first + 1, last - 1)
    end
    return crc16(key, #key) % 16384
end

它干两件事：

第一，花括号规则（hash tag）。 如果名字里有一对花括号 {...}，Redis 只拿花括号里的内容去算抽屉号，花括号外面的全不管。所以 ms_health:{DLH@}:write 这个名字，真正参与计算的只有 DLH@ 这 4 个字符。这条规则就是我们的突破口——花括号外面随便写业务含义（让人看得懂），花括号里那 4 个字符专门拿来控制落哪个抽屉。

第二，crc16(...) % 16384。 把花括号里的内容交给 crc16 算出一个数，再对 16384 取余（% 就是取余数，比如 17 % 5 = 2），得到 0~16383 之间的抽屉号。crc16 到底在算什么，下一节讲。

这里先埋一个后面要用的小知识：

16384 正好是 2 乘 14 次（2¹⁴）。 任何数对 2 的整次方取余，效果就是“只留下末尾那几位二进制、把前面的砍掉”。对 16384 取余，就是只留下末尾 14 位二进制。现在看不懂没关系，记住“取余 = 砍掉前面、只留末尾 14 位”就行，后面会用到。

CRC16 其实只是在拨一排开关

很多人一看 crc16 就觉得是什么高深的加密，望而生畏。其实不用怕。要看懂这段代码，你只需要先认识两样东西：二进制，和一个叫异或的简单运算。

先认识二进制：数字就是一排开关

我们平时用的数字是“十进制”，逢十进一。计算机里用的是二进制，逢二进一，每一位只能是 0 或 1。你可以把一个二进制数想成一排灯的开关：亮（1）或灭（0）。每一个开关，专业叫法是一个比特（bit）。

比如十进制的 5，写成二进制是 101，就是“开—关—开”三盏灯。一个数有多少位，就是多少盏灯。本文里反复出现的“14 位”，意思就是“14 盏灯”。

（代码里还会见到 0x1021 这种写法，前缀 0x 表示这是十六进制，一种把二进制写得更紧凑的记法，一位顶 4 盏灯。看到它当成“一个数”就行，不用换算。）

异或：两个开关一比，相同灭、不同亮

异或（英文 XOR，记号 ⊕）是拿两盏灯一位一位地比：两边一样就灭（0），不一样就亮（1）。

就这么个规则。它有一个特别顺手的性质，后面全靠它：

一盏灯被异或两次，就变回原样。 因为“不同才亮”，你拿同一个东西异或它两次，等于先翻一下再翻回来。所以异或是可逆的——这正是我们能“反推”的根本原因。普通加法做不到这点（加了 3 不知道原来是几，可能溢出进位），异或能。

代码开头的 xor_nibble 和 xor16 两段，就是在手写这个异或运算（因为部署环境里不一定有现成的异或函数，作者干脆用除法和取余拼了一个）。你完全不用看懂它们的实现，只要知道：xor16(a, b) = “把 a 和 b 两个数按开关比一遍，输出结果”。

crc16：把异或重复很多遍

crc16 做的事，说穿了就是把异或这个动作，对着输入的每个字符翻来覆去做很多遍，最后得到一个数。它不做乘法、不做进位，从头到尾只有“挪位置 + 异或”。代码里的 crc_table 只是把中间步骤提前算好存起来加速，不影响理解。

你不需要搞懂它每一步，只要记住一个结论——这是全文的地基：

crc16 从头到尾只有挪位置和异或，所以它是“可以反推”的。 它不像 MD5、SHA 那种加密哈希（算出来就倒不回去），而是一个老老实实、能一步步逆着走回去的运算。

关键一招：每个开关，固定改变一个结果

到了整篇最关键的直觉。看懂这一节，后面全是水到渠成。

想象一个调音台，面前一排开关，每个开关控制一盏结果灯。因为 crc16 只做异或（可逆、规整），它有一个好得出奇的性质：

你拨动某一个开关，对最终结果造成的改变是固定的——而且跟别的开关在什么位置毫无关系。

举个具体的。@@@@ 这个名字算出来落在某个抽屉。现在我把最后一个字符从 @ 改成 A（相当于只拨了一个开关），抽屉号就变了。变了多少？把这个“变化量”记成 Δ（读作 delta，就是“差多少”）。最关键的事实是：这个 Δ 是个固定的数。 不管你前面三个字符是什么样，只要拨的是同一个开关，Δ 永远一样。

既然每个开关的影响都固定、又互不干扰，那同时拨好几个开关的总效果，就是把各自的 Δ 全异或起来（异或就是我们这里的“加”）：

最终抽屉号 = @@@@的抽屉号  ⊕  第1个开关的Δ  ⊕  第3个开关的Δ  ⊕  第7个开关的Δ  ⊕ ...

这一下，一个看着吓人的问题（倒推一个哈希）就变成了一道小学难度的凑数游戏：

我想让抽屉号变成目标值，该拨哪几个开关？ = 从一堆固定的 Δ 里，挑出几个，让它们异或起来正好等于“目标抽屉号和起点差多少”。

挑开关凑目标——这种“已知每个开关的效果、反推该开哪几个”的题，数学上有现成的套路可以一次解出来（专业叫高斯消元，你不用会，知道有这么个解法就行），根本不用一个个瞎试。

最后补一个之前埋的伏笔：slot() 里那个 % 16384（只留末尾 14 位）会不会把这个好性质搞坏？不会。“砍掉前面、只留末尾几位”这个动作本身也很规整，照样不破坏“每个开关影响固定、可叠加”。所以从“拨开关”到“最终抽屉号”，这条链一路都成立。

开关从哪来：4 个字符凑出 16 个开关

上一节说“拨开关”，开关到底是什么？就是我们那 4 个字符里能自由改动的部分。关键是要让这块“操作面板”干净可控，所以代码规定：4 个字符，每个只能从下面这 16 个里挑一个：

@ A B C D E F G H I J K L M N O

为什么偏偏锁死这 16 个？先说个背景：计算机里每个字符背后都对应一个编号（叫 ASCII 码），比如 @ 是 64、A 是 65……这 16 个字符的编号是连续的 64~79。写成二进制（8 盏灯），它们的前 4 盏灯完全一样，只有后 4 盏灯在 0000 到 1111 之间变。

换句话说：

• 每个字符后 4 盏灯能自由拨 → 每个字符给我们 4 个开关；
• 4 个字符 → 一共 16 个开关。

我们要凑的抽屉号是 0~16383，正好用 14 盏灯就能表示。16 个开关去控制 14 盏灯，开关比灯还多，所以每一个抽屉号都一定能凑出来——16384 个抽屉，一个都不会漏。

还有个省事的巧合：因为这 16 个字符编号连续，一个字符后 4 盏灯拼成的数，正好就是它在 @ABC…O 里排第几（@ 排第 0，A 排第 1，……O 排第 15）。这让最后“把算出来的开关状态变回字符”这一步几乎白送，等会儿你会在代码里看到。

顺带一提，这套字符集还避开了花括号 { } 和各种会把字符串搞乱的特殊符号，拼出来的名字形如 ms_health:{DLH@}:write，合法、能读、能直接上生产。

拆解 for_slot()：三步造出 Key

铺垫完了，来看主角。整个造 Key 的过程就三步，全是查表和异或，没有一个循环。

第一步：定个起点，算“差多少”

local base_slot = 13881 -- CRC16/XMODEM("@@@@") % 16384.
...
local delta = xor16(slot, base_slot)

先随便选一个名字当起点，代码选的是 @@@@。把它算一遍，落在 13881 号抽屉——这个 13881 就当我们的“零刻度”。接着算一下：目标抽屉离零刻度“差多少”？

delta = 目标抽屉号 ⊕ 13881

这里的“差”用异或算，不用减法——前面说了，异或就是我们这套系统里的“加减”。

第二步：查两张小抄

local mask = xor16(low[delta % 128], high[floor(delta / 128)])

这是最巧的一步。我们想知道：要凑出这个 delta，该拨哪些开关？最直白的办法是做一张大抄，列出全部 16384 个 delta 各自对应的开关组合，查一下就行。但 16384 条太占地方，查起来也慢。

巧在哪？利用“开关可以叠加”这一点，可以把 delta 劈成两半各查各的。delta 有 14 盏灯，前 7 盏做一张小抄 high，后 7 盏做一张小抄 low，各自只有 128 条（7 盏灯的全部组合就是 2 的 7 次 = 128）。两边查出来的开关一异或，就是完整答案：

开关组合 mask = low[后7盏灯] ⊕ high[前7盏灯]

两张小抄加起来才 256 条，小到可以一直待在 CPU 手边（专业叫“缓存命中”，意思就是取数据极快），所以每次查都飞快。那这两张小抄怎么造出来的？看上面这段：

local inverse = {
    0x88d4, 0x808a, 0x9007, 0x9efb, 0x19a2, 0x0c93, 0x1184,
    0x8eed, 0x1efb, 0x8022, 0x89c4, 0x82aa, 0x9447, 0x967b
}
local low, high = { [0] = 0 }, { [0] = 0 }
local step = 1
for bit = 1, 7 do
    for value = 0, step - 1 do
        low[value + step]  = xor16(low[value],  inverse[bit])
        high[value + step] = xor16(high[value], inverse[bit + 7])
    end
    step = step * 2
end

• inverse 这 14 个数是提前算好的基础答案，一盏灯一个：第 i 个数的意思是“想让结果里第 i 盏灯单独翻一下，该拨哪些开关”。这 14 个是用前面说的那个现成套路（高斯消元）一次性解出来的，你不用自己会，照抄即可。
• 下面那个双层循环，是拿这 14 个基础答案，把 128 种组合提前全排列好，分别存进 low 和 high 两张小抄。这招叫“空间换时间”——启动时多花一点点工夫把小抄备齐，换来之后每次查都是一瞬间。

第三步：把 mask 变回字符

local tag = string.char(64 + mask % 16,
                        64 + floor(mask / 16) % 16,
                        64 + floor(mask / 256) % 16,
                        64 + floor(mask / 4096) % 16)
return "ms_health:{" .. tag .. "}:write"

查出来的 mask 里装着全部 16 个开关的状态，每 4 个开关一组，正好对应 4 个字符。还记得前面那个巧合吗——4 个开关拼成的数，正好就是字符的排序号。所以只要把 16 个开关每 4 个切一段，每段加上 64（也就是 @ 的编号），就还原出一个字符：

• mask % 16 取出最后 4 个开关 → 64 + 它 → 第 1 个字符；
• floor(mask / 16) % 16 跳过已取的、再取 4 个 → 第 2 个字符；
• 后面 /256、/4096 同理，依次取出第 3、4 个字符。

（这里的除法和取余，作用就是“把一段开关从整串里切出来”。string.char 负责把编号变回字符。）4 个字符拼好，塞进花括号，一个保证落进目标抽屉的名字就造好了。

跑一遍，验证一下

光说不练假把式。验证的逻辑很简单——造出来的 Key 再算回去，槽号得对得上：slot(for_slot(s)) 必须等于 s。

在浏览器里就能跑：lua-playground

不想本地装 Lua？我写了个在线的 lua-playground：docker compose up -d 起一个 OpenResty 容器，打开 http://localhost:8080，把代码贴进编辑器点 Run，print() 的输出就出现在页面上。它在一个受限的 LuaJIT 沙箱里跑，正好适合验证这种纯算术的小算法。

有两点要照顾到这个沙箱：它没有 dofile/require（所以把上面整段模块代码连同下面的自测一起贴进去，别分文件），而且单次运行有 100 万条指令的上限。把全部 16384 个槽扫一遍会超这个上限，所以在 playground 里只抽查几个代表性的槽——首槽、末槽、中间几个，足够说明问题：

下面这段是可以整段复制、直接粘进 playground 点 Run 的完整代码：模块本体（去掉末尾的 return _M）加上自测，内联成一个文件，不需要 dofile。

local _M = {}
local floor = math.floor
local xor_nibble = {}
for a = 0, 15 do
    xor_nibble[a] = {}
    for b = 0, 15 do
        local x, y, value, place = a, b, 0, 1
        for _ = 1, 4 do
            if x % 2 ~= y % 2 then value = value + place end
            x, y, place = floor(x / 2), floor(y / 2), place * 2
        end
        xor_nibble[a][b] = value
    end
end
local function xor16(a, b)
    local value, place = 0, 1
    for _ = 1, 4 do
        value = value + xor_nibble[a % 16][b % 16] * place
        a, b, place = floor(a / 16), floor(b / 16), place * 16
    end
    return value
end
local crc_table = {}
for byte = 0, 255 do
    local crc = byte * 256
    for _ = 1, 8 do
        if crc >= 32768 then crc = xor16((crc * 2) % 65536, 0x1021)
        else crc = crc * 2 end
    end
    crc_table[byte] = crc
end
local function crc16(key, length)
    local crc = 0
    for i = 1, length do
        local index = xor16(floor(crc / 256), key:byte(i))
        crc = xor16((crc * 256) % 65536, crc_table[index])
    end
    return crc
end
function _M.slot(key)
    if type(key) ~= "string" then return nil end
    local first = key:find("{", 1, true)
    local last = first and key:find("}", first + 1, true)
    if last and last > first + 1 then key = key:sub(first + 1, last - 1) end
    return crc16(key, #key) % 16384
end
local inverse = {
    0x88d4, 0x808a, 0x9007, 0x9efb, 0x19a2, 0x0c93, 0x1184,
    0x8eed, 0x1efb, 0x8022, 0x89c4, 0x82aa, 0x9447, 0x967b
}
local base_slot = 13881
local low, high = { [0] = 0 }, { [0] = 0 }
local step = 1
for bit = 1, 7 do
    for value = 0, step - 1 do
        low[value + step] = xor16(low[value], inverse[bit])
        high[value + step] = xor16(high[value], inverse[bit + 7])
    end
    step = step * 2
end
function _M.for_slot(slot)
    if type(slot) ~= "number" or slot < 0 or slot > 16383 or slot ~= floor(slot) then return nil end
    local delta = xor16(slot, base_slot)
    local mask = xor16(low[delta % 128], high[floor(delta / 128)])
    local tag = string.char(64 + mask % 16, 64 + floor(mask / 16) % 16,
        64 + floor(mask / 256) % 16, 64 + floor(mask / 4096) % 16)
    return "ms_health:{" .. tag .. "}:write"
end

-- ===== 轻量自测:抽查几个槽的往返一致性 =====
local checks = {0, 1, 5461, 8192, 10922, 16383}
local ok = true
for _, s in ipairs(checks) do
    local key = _M.for_slot(s)   -- 反向:给槽号造 Key
    local got = _M.slot(key)     -- 正向:再算回槽号
    local flag = (got == s) and "OK" or "FAIL"
    if got ~= s then ok = false end
    print(string.format("slot %5d -> %-26s back=%5d  %s", s, key, got, flag))
end
print("base slot('@@@@') =", _M.slot("@@@@"), "(expect 13881)")
print(ok and "ALL SPOT CHECKS PASSED" or "SOME CHECKS FAILED")

实测输出：

slot     0 -> ms_health:{DLH@}:write     back=    0  OK
slot     1 -> ms_health:{@A@H}:write     back=    1  OK
slot  5461 -> ms_health:{IDKA}:write     back= 5461  OK
slot  8192 -> ms_health:{OKNI}:write     back= 8192  OK
slot 10922 -> ms_health:{HC@@}:write     back=10922  OK
slot 16383 -> ms_health:{EKCA}:write     back=16383  OK
base slot('@@@@') = 13881   (expect 13881)
ALL SPOT CHECKS PASSED

for_slot(0) 给出 DLH@，拼成 ms_health:{DLH@}:write，再用 slot() 按 hash tag 规则（只取 DLH@）算回去，正好 0 号槽。

本地跑全量：16384 个槽一个不落

抽查能说明算法对，但要证明全覆盖，得把 16384 个槽都扫一遍。这超出 playground 的指令上限，放到本地 Lua 跑（指令数不设限）。把模块存成 slot.lua：

local M = dofile("slot.lua")
assert(M.slot("@@@@") == 13881, "锚点对不上")
local bad = 0
for s = 0, 16383 do
    if M.slot(M.for_slot(s)) ~= s then bad = bad + 1 end
end
print("coverage failures:", bad, "/16384")

实测输出（Lua 5.4）：

coverage failures:  0   /16384

全部 16384 个槽，零遗漏——每个槽都能被精确命中。

几个要留神的边界

这套方法漂亮，但有明确的适用边界，别拿它去干它不干的事。

• 只保证命中槽，不保证 tag 有语义。 产出的 DLH@ 是没含义的串。要可读的业务 Key，靠花括号外的前后缀；括号里那 4 个字符是给路由用的，不是给人读的。
• 一个槽对应很多个合法 tag，这里只取一个。 16 个开关凑 14 位，多出 2 位自由度，意味着每个槽有不止一个 tag 能命中。代码取的是其中一个；想要分散，可以在那 2 位上做文章。
• 换了 CRC16 变体，全套常数要重算。 base_slot=13881、inverse 那 14 个数、两张表，全都绑定在“XMODEM、初值 0、无末异或”这个前提上。换个 CRC16 变体，它们全变。
• 这是路由技巧，不是安全机制。 能预测 Key 落哪个槽，在集群运维里是便利；但它只管算术，不管权限，别拿它当访问控制。

总结：难题的本质，是一道凑开关的游戏

把这事收一下：一个看着像“倒推哈希”的难题，一旦认清 crc16 从头到尾只是异或——每个开关的影响固定、还能叠加——它就塌成了一道小学难度的凑数游戏：挑几个开关，让它们异或起来正好等于目标。这种题有现成解法，不用猜、不用一个个试。

读这段 Lua，真正要带走的就一句话：固定一块 4 字符的操作面板，把“每个目标该拨哪些开关”提前做成两张小抄，用的时候查两下、异或一下，一步到位命中任意抽屉。

行动清单：

1. 确认你的 Redis 用的是 CRC16/XMODEM（初值 0、无末异或）——标准实现基本都是；
2. 固定 tag 长度 4，字符集锁 @ABC…O；
3. 用离线脚本解出 inverse 那 14 个常数，建好 low/high 两张表存成静态数据；
4. 运行时只调 for_slot(slot)，把结果直接当 Key 用；
5. 上线前跑一遍全 16384 槽的覆盖断言——别信我的话，信你自己的断言。

真正的性能优化，常常不是把慢的东西写得更快，而是认出它根本不必做。

全文思维导图

@startmindmap
<style>
mindmapDiagram {
  node {
    BackgroundColor #F8F9FA
    RoundCorner 10
    Padding 10
    FontSize 13
  }
  :depth(0) {
    BackgroundColor #1E3A5F
    FontColor white
    FontSize 18
    FontStyle bold
  }
  :depth(1) {
    FontSize 15
    FontStyle bold
  }
  :depth(2) {
    FontSize 13
  }
}
</style>

* 读懂一段 Lua：O(1) 造指定 Slot 的 Key
** 问题
*** 需求：按槽造 Key
*** 碰撞法：慢 + 延迟抖
** 两个出口
*** slot()：正向算槽（验证用）
*** for_slot()：反向造 Key（主角）
** crc16 只是异或
*** 二进制 = 一排灯开关
*** 异或：相同灭、不同亮
*** 异或两次变回原样 → 可反推
** 核心直觉
*** 拨一个开关，影响固定
*** 多个开关可异或叠加
*** 倒推 = 凑开关游戏，有现成解法
** tag 设计
*** 4 字符，字符集 @ABC…O
*** 高4位固定，低4位自由
*** 16 个开关覆盖 14 位槽号
** for_slot 三步
*** 锚点 @@@@ → 13881，算 delta
*** delta 劈两半，查两张128项表
*** mask 每4位 → 字符下标
** 验证
*** lua-playground 浏览器抽查
*** 本地跑全 16384 槽零遗漏
** 边界
*** 只保证命中槽
*** 一槽多 tag
*** 换变体要重算
*** 路由技巧,非安全机制
@endmindmap

本作品采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议进行许可。 欢迎在我的个人网站 https://www.fanyamin.com 访问原文并评论。