Hello, i have a problem with performance, i have database with 200k hashes, where 100k of them begins with "TEMP_" rest of key is exactly the same, here is sample: (in total there is 100k pairs in db)
ASIC_STATE:SAI_OBJECT_TYPE_ROUTE_ENTRY:{"dest":"1.0.147.132/32","switch_id":"oid:0x21000000000000","vr":"oid:0x3000000000022"}
TEMP_ASIC_STATE:SAI_OBJECT_TYPE_ROUTE_ENTRY:{"dest":"1.0.147.132/32","switch_id":"oid:0x21000000000000","vr":"oid:0x3000000000022"}
on average length of the key without TEMP_ prefix is 126 bytes, but with TEMP_ prefix, on average key length is 131 bytes.
and with that said i'm getting huge time differences when dumping keys: when using lua script
$ time redis-cli -n 1 "keys" "ASIC_STATE:*" >/dev/null
real 0m0,137s
user 0m0,046s
sys 0m0,026s
$ time redis-cli -n 1 "keys" "TEMP_ASIC_STATE:*" >/dev/null
real 0m0,124s
user 0m0,030s
sys 0m0,029s
and with lua:
sonic@centaur ~/sonic-sairedis/tests $ time redis-cli -n 1 eval 'redis.call("keys", KEYS[1].."*")' 1 ASIC_STATE
(nil)
real 0m5,554s
user 0m0,000s
sys 0m0,002s
sonic@centaur ~/sonic-sairedis/tests $ time redis-cli -n 1 eval 'redis.call("keys", KEYS[1].."*")' 1 TEMP_ASIC_STATE
(nil)
real 0m36,393s
user 0m0,002s
sys 0m0,001s
with lua with ASIC_STATE its 5.5 seconds and with TEMP_ASIC_STATE its 36 seconds !
my question here, is there some internal redis/lua buffer mechanism, that treats string < 128 differently than longer than 128 bytes, and this impacts performance here? (my suspect here is some extra memory allocation for longer strings)
I looked to redis code, and there are plenty of 128 number used values, but nothing that is obvious to me right away. I would appreciate it if i could get explanation why this phenomena happens, and whether this value could be increased from 128 to some bigger one (by config or at compile time). Thank You!
ps. this is tested on version: Redis server v=4.0.9 sha=00000000:0 malloc=jemalloc-4.0.3 bits=64 build=d17ee921f2be9d48
Comment From: yossigo
@kcudnik First thing that comes to mind having such a large difference is the fact that results are sorted, in order to ensure consistency with Lua script replication. Check out redis.replicate_commands() and see if using this mode in your script makes a difference (note that since 6.0 this has become the default).
If not, please consider sharing an rdb file so it's easier to reproduce this.
Comment From: kcudnik
Hey @yossigo, thanks for response, i don't do any sorting, and i prepared a bash test script to confirm this scenario, those are the only commands that i execute, issue is definitely related to "keys" command and key length
$ cat key.sh
#!/bin/bash
redis-cli FLUSHALL
PAD="#############################################################################################################:"
# populate redis
redis-cli -n 1 eval 'for i=1,100000 do redis.call("hset", string.format("ASIC_STATE:" .. KEYS[1] .. "%05d",i), "a", "b"); end' 1 $PAD
redis-cli -n 1 eval 'for i=1,100000 do redis.call("hset", string.format("TEMP_ASIC_STATE:" .. KEYS[1] .. "%05d",i), "a", "b"); end' 1 $PAD
# confirm keys are there
redis-cli -n 1 SCAN 0 MATCH "ASIC_STATE:*" | grep ASIC | head -n 1
redis-cli -n 1 SCAN 0 MATCH "TEMP_ASIC_STATE:*" | grep ASIC | head -n 1
# test time performance
echo -n "asic keys: "
redis-cli -n 1 "keys" "ASIC_STATE:*" | wc -l
time redis-cli -n 1 eval 'redis.call("keys", KEYS[1].."*")' 1 ASIC_STATE
echo -n "temp asic keys: "
redis-cli -n 1 "keys" "TEMP_ASIC_STATE:*" | wc -l
time redis-cli -n 1 eval 'redis.call("keys", KEYS[1].."*")' 1 TEMP_ASIC_STATE
and here are the results:
$ ./key.sh
OK
(nil)
(nil)
ASIC_STATE:#############################################################################################################:63915
TEMP_ASIC_STATE:#############################################################################################################:06038
asic keys: 100000
(nil)
real 0m6,698s
user 0m0,000s
sys 0m0,001s
temp asic keys: 100000
(nil)
real 0m34,694s
user 0m0,000s
sys 0m0,001s
notice time difference 6.6 sec vs 34.6 sec !!, and if i replace "TEMP_" with "T" (actual chars don't matter here), entire key length drops below 128 chars, and time becomes 0m6,656s for ASIC and 0m6,738s for TASIC
Comment From: yossigo
Looking like you're hitting a hash table conflict due to the way Lua hashes strings in its internal string table. See here:
TString *luaS_newlstr (lua_State *L, const char *str, size_t l) {
GCObject *o;
unsigned int h = cast(unsigned int, l); /* seed */
size_t step = (l>>6)+1; /* if string is too long, don't hash all its chars */
size_t l1;
for (l1=l; l1>=step; l1-=step) /* compute hash */
h = h ^ ((h<<5)+(h>>2)+cast(unsigned char, str[l1-1]));
Comment From: kcudnik
Hey @yossigo, you are correct about this one, i cloned master (on master is that line is >>5) and i recompiled this with different values and here are results: (i stripped noise)
~/redis/src $ ./key.sh # >>5
asic keys: 100000
real 0m3,318s
temp asic keys: 100000
real 0m28,979s
~/redis/src $ ./key.sh # >>6
asic keys: 100000
real 0m0,494s
temp asic keys: 100000
real 0m3,609s
~/redis/src $ ./key.sh # >>7
asic keys: 100000
real 0m0,143s
temp asic keys: 100000
real 0m0,547s
Thank you for your help and pointing out right piece of code. The time difference with running those examples is dramatic, don't know why on the last one there is difference 0.1sec vs 0.5sec but still better than initial 3.3sec and 28.9sec.
Of course this is only this particular test, this change may have impact on some other lua scripts when processing long strings internally, but at my case it helps to make things faster.
I will just need to make my own redis package with applied patch to make this running.
Comment From: jianxinluo
@kcudnik Modifying the offset affects the step size, which in turn affects the sampling of the string. If the data repeatability is high and the sampling interval is large, the hash calculation result will be affected and the data will be recorded in the same conflict chain. If you change the offset to 8(l>>8), the two test results will be closer; however, the test time may increase.Because hashing all the bytes increases the calculation time
for (l1=l; l1>=step; l1-=step) / compute hash / h = h ^ ((h<<5)+(h>>2)+cast(unsigned char, str[l1-1]));
Comment From: kcudnik
Hey @jianxinluo, yes, after brief code analyze that @yossigo pointed out, i figure out what's happening in that piece. From my case i probably would be leaning to make lua code modification, since i know my data, and i will not have strings longer than ~200 chars in db, but i will have a lot of them > 200k, and from tests that i performed it seems like hash collision is way more expensive than calculating hash using all characters of string.
I wish that could be runtime option to select from redis config, then i would not need to compile my own redis and have git submodulre for that, i would just take of the shelf package from debian server.
From my point of view such config solution could be done in 2 ways: * (l>>5), the "5" could be config option, but this would seems way intrusive to the code itself, and it would require extra field to keep shift variable. (and some extra penalty since ">>5" is like 1 asm instruction, so read field and shift, those are at least 2, but probably negligible in comparison with hash loop * have 2 different luaS_newlstr functions, (one with just step == 1) and use pointer as function selector, and function could be selected via config (hash string with steps vs hash all string)
but those seems to be very specific cases and i doubt that this will be considered for adding into redis config, current hash solution is good enough for most generic cases, but when we start talking about specific data, then more specific scenarios will have better performance
Thank you for your explanation.
Comment From: kcudnik
Does it make sense to create PR for such redis config option for lua allowing hashing step to be set to 1? Would you consider merging that into main branch? If yes, any proposal of which 2 mentioned options would be preferred?
Comment From: yossigo
@kcudnik Thanks for offering a solution, but as you indicated yourself I also have doubts about introducing this as a Lua patch and an extra config parameter. I'd much rather see Redis picking up speed on upgrading to Lua 5.4 which seems to have made some progress around this as well.
Comment From: kcudnik
Hey @yossigo, I already seen PR for 5.4 https://github.com/redis/redis/pull/8078, code around this string hash is improved, but in sense that hash shift value is extracted to a define:
// from 5.4
/*
** Lua will use at most ~(2^LUAI_HASHLIMIT) bytes from a long string to
** compute its hash
*/
#if !defined(LUAI_HASHLIMIT)
#define LUAI_HASHLIMIT 5
#endif
...
unsigned int luaS_hashlongstr (TString *ts) {
lua_assert(ts->tt == LUA_VLNGSTR);
if (ts->extra == 0) { /* no hash? */
size_t len = ts->u.lnglen;
size_t step = (len >> LUAI_HASHLIMIT) + 1;
ts->hash = luaS_hash(getstr(ts), len, ts->hash, step);
ts->extra = 1; /* now it has its hash */
}
return ts->hash;
}
It's a step better, since after merging that to main branch, and including in my project as submodule, i can pass "-DLUAI_HASHLIMIt=8" parameter to CFLAGS to set it up. But i still need to have submodule and i still need to compile redis-server and create own deb redis-server package. This improvenemnt is removing necessary a patch file for lstring.c file. My preffered way would be to have this as as a redis.conf option, then i could take of the shelf redis-server package from ubuntu and just change redis.conf 1 line and would be good to go (which i already have my custom redis.conf anyway). Also we already established that making this change improves lua string hash collisions when having a lot of keys, and improves speed, which could be potentially desired for other users as well. Only downside is that it would require some ingerention redis/deps/lua source code.
Comment From: yossigo
@kcudnik My concern also involves exposing Lua internals in a way which may have undesired side effects on the Lua VM, or may introduce compatibility issues in the future. I would rather spend some time learning how much of a problem this is for the Lua community (it should be) and how Lua itself deals / going to deal with that.
Comment From: yossigo
So it seems like Lua is indeed moving in this direction: https://github.com/lua/lua/commit/9a89fb1c9dfeda4640780111f9e9437f08cfad88#diff-502e2af53d91e94730b9452015d8c8a2b3b435dbca1e73393bbf6e36db3048e7
Comment From: kcudnik
Thanks @yossigo for pointing this commit out, this seems like a good direction. This commit will be included in lua 5.4.2 version, and then it will be just question of time to move this to redis-server. Unfortunately it will probably not happen any time soon. I would like this solution the best, but for now i will need to stick to custom server build. Thanks for your help.
Comment From: kcudnik
After merge https://github.com/redis/redis/pull/8180 this problem will be solved.
Comment From: oranagra
solved by #9449