Redis [NEW] Find the corresponding slot for a key without adding it to the cluster

The problem/use-case that the feature addresses

Sometimes I would like to see which slot a key should belong to without actually adding it. So I think such a feature would be helpful.

I am sorry if there is already a convenient solution for this.

Description of the feature

For example, we can introduce a command HASHSLOT <key name>, and it returns the slot the key should go to. Here is a demo of my own implementation:

The implementation should be technically easy: we can let the process take place completely on the client side (without consulting the server or the cluster) by using the crc16 hash function we already have for client: https://github.com/redis/redis/blob/unstable/src/redis-cli.c#L3790

Alternatives you've considered

Maybe add a variation to the CLUSTER KEYSLOT command to achieve this.

Additional information

None

Comment From: itamarhaber

Hello @yuanwang2011

without actually adding it

Just to make sure I understand the feature, "it" means the cluster in this case, right? You want to be able to call the equivalent of CLUSTER KEYSLOT against a single-instance server, correct?

If that is indeed the case, AFAIK, this is indeed missing in the project, and I can see why it would be helpful to have it for non-production use.

However, as an alternative, one can take any cluster-aware Redis client and modify it slightly to provide that functionality. Here's a Lua script you can run against Redis that should do the trick (not thoroughly tested though):

--/*
-- Examples:
-- $ redis-cli --eval hashslot.lua , key
-- (integer) 12539
-- $ redis-cli --eval hashslot.lua , key2
-- (integer) 4998
-- $ redis-cli --eval hashslot.lua , key3
-- (integer) 935
-- $ redis-cli --eval hashslot.lua , "id:{key}"
-- (integer) 12539
--
-- Derived from: https://github.com/cloudwu/skynet/blob/master/lualib/skynet/db/redis/crc16.lua
-- This is the CRC16 algorithm used by Redis Cluster to hash keys.
-- Implementation according to CCITT standards.
--
-- This is actually the XMODEM CRC 16 algorithm, using the
-- following parameters:
--
-- Name                       : "XMODEM", also known as "ZMODEM", "CRC-16/ACORN"
-- Width                      : 16 bit
-- Poly                       : 1021 (That is actually x^16 + x^12 + x^5 + 1)
-- Initialization             : 0000
-- Reflect Input byte         : False
-- Reflect Output CRC         : False
-- Xor constant to output CRC : 0000
-- Output for "123456789"     : 31C3
--*/

local XMODEMCRC16Lookup = {
    0x0000,0x1021,0x2042,0x3063,0x4084,0x50a5,0x60c6,0x70e7,
    0x8108,0x9129,0xa14a,0xb16b,0xc18c,0xd1ad,0xe1ce,0xf1ef,
    0x1231,0x0210,0x3273,0x2252,0x52b5,0x4294,0x72f7,0x62d6,
    0x9339,0x8318,0xb37b,0xa35a,0xd3bd,0xc39c,0xf3ff,0xe3de,
    0x2462,0x3443,0x0420,0x1401,0x64e6,0x74c7,0x44a4,0x5485,
    0xa56a,0xb54b,0x8528,0x9509,0xe5ee,0xf5cf,0xc5ac,0xd58d,
    0x3653,0x2672,0x1611,0x0630,0x76d7,0x66f6,0x5695,0x46b4,
    0xb75b,0xa77a,0x9719,0x8738,0xf7df,0xe7fe,0xd79d,0xc7bc,
    0x48c4,0x58e5,0x6886,0x78a7,0x0840,0x1861,0x2802,0x3823,
    0xc9cc,0xd9ed,0xe98e,0xf9af,0x8948,0x9969,0xa90a,0xb92b,
    0x5af5,0x4ad4,0x7ab7,0x6a96,0x1a71,0x0a50,0x3a33,0x2a12,
    0xdbfd,0xcbdc,0xfbbf,0xeb9e,0x9b79,0x8b58,0xbb3b,0xab1a,
    0x6ca6,0x7c87,0x4ce4,0x5cc5,0x2c22,0x3c03,0x0c60,0x1c41,
    0xedae,0xfd8f,0xcdec,0xddcd,0xad2a,0xbd0b,0x8d68,0x9d49,
    0x7e97,0x6eb6,0x5ed5,0x4ef4,0x3e13,0x2e32,0x1e51,0x0e70,
    0xff9f,0xefbe,0xdfdd,0xcffc,0xbf1b,0xaf3a,0x9f59,0x8f78,
    0x9188,0x81a9,0xb1ca,0xa1eb,0xd10c,0xc12d,0xf14e,0xe16f,
    0x1080,0x00a1,0x30c2,0x20e3,0x5004,0x4025,0x7046,0x6067,
    0x83b9,0x9398,0xa3fb,0xb3da,0xc33d,0xd31c,0xe37f,0xf35e,
    0x02b1,0x1290,0x22f3,0x32d2,0x4235,0x5214,0x6277,0x7256,
    0xb5ea,0xa5cb,0x95a8,0x8589,0xf56e,0xe54f,0xd52c,0xc50d,
    0x34e2,0x24c3,0x14a0,0x0481,0x7466,0x6447,0x5424,0x4405,
    0xa7db,0xb7fa,0x8799,0x97b8,0xe75f,0xf77e,0xc71d,0xd73c,
    0x26d3,0x36f2,0x0691,0x16b0,0x6657,0x7676,0x4615,0x5634,
    0xd94c,0xc96d,0xf90e,0xe92f,0x99c8,0x89e9,0xb98a,0xa9ab,
    0x5844,0x4865,0x7806,0x6827,0x18c0,0x08e1,0x3882,0x28a3,
    0xcb7d,0xdb5c,0xeb3f,0xfb1e,0x8bf9,0x9bd8,0xabbb,0xbb9a,
    0x4a75,0x5a54,0x6a37,0x7a16,0x0af1,0x1ad0,0x2ab3,0x3a92,
    0xfd2e,0xed0f,0xdd6c,0xcd4d,0xbdaa,0xad8b,0x9de8,0x8dc9,
    0x7c26,0x6c07,0x5c64,0x4c45,0x3ca2,0x2c83,0x1ce0,0x0cc1,
    0xef1f,0xff3e,0xcf5d,0xdf7c,0xaf9b,0xbfba,0x8fd9,0x9ff8,
    0x6e17,0x7e36,0x4e55,0x5e74,0x2e93,0x3eb2,0x0ed1,0x1ef0
}

local function crc16(bytes)
    local crc = 0
    for i=1,#bytes do
        local b = string.byte(bytes,i,i)
        crc = bit.bxor(bit.band(bit.lshift(crc,8),0xffff),XMODEMCRC16Lookup[bit.band(bit.bxor(bit.rshift(crc,8),b) , 0xff) + 1])
    end
    crc = bit.band(crc,0x3fff)
    return tonumber(crc)
end

local function hashtag(bytes)
    local _, _, _, tag = string.find(bytes, "([{])(.-)}")
    if tag then
        return tag
    end
    return bytes
end

return crc16(hashtag(ARGV[1]))

Comment From: madolson

I'm still not quite clear why CLUSTER KEYSLOT is insufficient to solve your use case.

Comment From: ghost

I'm still not quite clear why CLUSTER KEYSLOT is insufficient to solve your use case.

It seems that CLUSTER KEYSLOT has to work in the cluster mode, and has to go through the server. But since it is just applying the crc16 hash function, it can be run purely on the client side (without consulting the server, hence no need for the cluster mode). So I am just thinking that it may be better to implement it in this way (purely on the client side).

I was originally thinking that we need the key to be present in the cluster in order to run this command, but it seems that is not the case. Sorry for the mistake.

Comment From: ghost

Hello @yuanwang2011

without actually adding it

Just to make sure I understand the feature, "it" means the cluster in this case, right? You want to be able to call the equivalent of CLUSTER KEYSLOT against a single-instance server, correct?

If that is indeed the case, AFAIK, this is indeed missing in the project, and I can see why it would be helpful to have it for non-production use.

However, as an alternative, one can take any cluster-aware Redis client and modify it slightly to provide that functionality. Here's a Lua script you can run against Redis that should do the trick (not thoroughly tested though):

```lua --/ -- Examples: -- $ redis-cli --eval hashslot.lua , key -- (integer) 12539 -- $ redis-cli --eval hashslot.lua , key2 -- (integer) 4998 -- $ redis-cli --eval hashslot.lua , key3 -- (integer) 935 -- $ redis-cli --eval hashslot.lua , "id:{key}" -- (integer) 12539 -- -- Derived from: https://github.com/cloudwu/skynet/blob/master/lualib/skynet/db/redis/crc16.lua -- This is the CRC16 algorithm used by Redis Cluster to hash keys. -- Implementation according to CCITT standards. -- -- This is actually the XMODEM CRC 16 algorithm, using the -- following parameters: -- -- Name : "XMODEM", also known as "ZMODEM", "CRC-16/ACORN" -- Width : 16 bit -- Poly : 1021 (That is actually x^16 + x^12 + x^5 + 1) -- Initialization : 0000 -- Reflect Input byte : False -- Reflect Output CRC : False -- Xor constant to output CRC : 0000 -- Output for "123456789" : 31C3 --/

local XMODEMCRC16Lookup = { 0x0000,0x1021,0x2042,0x3063,0x4084,0x50a5,0x60c6,0x70e7, 0x8108,0x9129,0xa14a,0xb16b,0xc18c,0xd1ad,0xe1ce,0xf1ef, 0x1231,0x0210,0x3273,0x2252,0x52b5,0x4294,0x72f7,0x62d6, 0x9339,0x8318,0xb37b,0xa35a,0xd3bd,0xc39c,0xf3ff,0xe3de, 0x2462,0x3443,0x0420,0x1401,0x64e6,0x74c7,0x44a4,0x5485, 0xa56a,0xb54b,0x8528,0x9509,0xe5ee,0xf5cf,0xc5ac,0xd58d, 0x3653,0x2672,0x1611,0x0630,0x76d7,0x66f6,0x5695,0x46b4, 0xb75b,0xa77a,0x9719,0x8738,0xf7df,0xe7fe,0xd79d,0xc7bc, 0x48c4,0x58e5,0x6886,0x78a7,0x0840,0x1861,0x2802,0x3823, 0xc9cc,0xd9ed,0xe98e,0xf9af,0x8948,0x9969,0xa90a,0xb92b, 0x5af5,0x4ad4,0x7ab7,0x6a96,0x1a71,0x0a50,0x3a33,0x2a12, 0xdbfd,0xcbdc,0xfbbf,0xeb9e,0x9b79,0x8b58,0xbb3b,0xab1a, 0x6ca6,0x7c87,0x4ce4,0x5cc5,0x2c22,0x3c03,0x0c60,0x1c41, 0xedae,0xfd8f,0xcdec,0xddcd,0xad2a,0xbd0b,0x8d68,0x9d49, 0x7e97,0x6eb6,0x5ed5,0x4ef4,0x3e13,0x2e32,0x1e51,0x0e70, 0xff9f,0xefbe,0xdfdd,0xcffc,0xbf1b,0xaf3a,0x9f59,0x8f78, 0x9188,0x81a9,0xb1ca,0xa1eb,0xd10c,0xc12d,0xf14e,0xe16f, 0x1080,0x00a1,0x30c2,0x20e3,0x5004,0x4025,0x7046,0x6067, 0x83b9,0x9398,0xa3fb,0xb3da,0xc33d,0xd31c,0xe37f,0xf35e, 0x02b1,0x1290,0x22f3,0x32d2,0x4235,0x5214,0x6277,0x7256, 0xb5ea,0xa5cb,0x95a8,0x8589,0xf56e,0xe54f,0xd52c,0xc50d, 0x34e2,0x24c3,0x14a0,0x0481,0x7466,0x6447,0x5424,0x4405, 0xa7db,0xb7fa,0x8799,0x97b8,0xe75f,0xf77e,0xc71d,0xd73c, 0x26d3,0x36f2,0x0691,0x16b0,0x6657,0x7676,0x4615,0x5634, 0xd94c,0xc96d,0xf90e,0xe92f,0x99c8,0x89e9,0xb98a,0xa9ab, 0x5844,0x4865,0x7806,0x6827,0x18c0,0x08e1,0x3882,0x28a3, 0xcb7d,0xdb5c,0xeb3f,0xfb1e,0x8bf9,0x9bd8,0xabbb,0xbb9a, 0x4a75,0x5a54,0x6a37,0x7a16,0x0af1,0x1ad0,0x2ab3,0x3a92, 0xfd2e,0xed0f,0xdd6c,0xcd4d,0xbdaa,0xad8b,0x9de8,0x8dc9, 0x7c26,0x6c07,0x5c64,0x4c45,0x3ca2,0x2c83,0x1ce0,0x0cc1, 0xef1f,0xff3e,0xcf5d,0xdf7c,0xaf9b,0xbfba,0x8fd9,0x9ff8, 0x6e17,0x7e36,0x4e55,0x5e74,0x2e93,0x3eb2,0x0ed1,0x1ef0 }

local function crc16(bytes) local crc = 0 for i=1,#bytes do local b = string.byte(bytes,i,i) crc = bit.bxor(bit.band(bit.lshift(crc,8),0xffff),XMODEMCRC16Lookup[bit.band(bit.bxor(bit.rshift(crc,8),b) , 0xff) + 1]) end crc = bit.band(crc,0x3fff) return tonumber(crc) end

local function hashtag(bytes) local , , _, tag = string.find(bytes, "([{])(.-)}") if tag then return tag end return bytes end

return crc16(hashtag(ARGV[1])) ```

Hi @itamarhaber , thanks for the detailed solution! Still, the lua script has to be run on the server side (with the EVAL command), right? I was wondering if it would be better to let the command (either CLUSTER KEYSLOT or a new one like HASHSLOT I was originally trying) run purely on the client side, using the hash function we already have there: https://github.com/redis/redis/blob/unstable/src/redis-cli.c#L3790

Comment From: ghost

Anyway, this is not an imperative feature, just an observation I had when working with Redis. So feel free to ask me to implememt it or close it as you like:)

Comment From: itamarhaber

Still, the lua script has to be run on the server side (with the EVAL command), right?

Right, but you can also do something similar pretty much anywhere else. For example, Python (and no Redis):

In [1]: import redis

In [2]: redis.cluster.key_slot(b'key')
Out[2]: 12539

In [3]: redis.cluster.key_slot(b'key2')
Out[3]: 4998

In [4]: redis.cluster.key_slot(b'key3')
Out[4]: 935

In [5]: redis.cluster.key_slot(b'id:{key}')
Out[5]: 12539

In any case, adding this functionality to the cli alone is less appealing IMO.

Comment From: madolson

I will also add that from a feature perspective, we want slots to not really be a "user" visible construct. The idea is that slots are just transparent behind the scenes.