Re: question on string hashing and interning in Lua

[Javier Guerra Giraldez <javier@...>]

On Thu, 14 May 2020 at 01:41, Philippe Verdy <verdyp@gmail.com> wrote:
>
> That's surprizing: such fast hash is too much easy to create collisions in very common cases, like indexing keys that have many common prefixes and suffixes.

First of all, i want to stress that this is a LuaJIT issue, not Lua.
Lua uses a more conventional hash strategy.

Second, some forks of LuaJIT add extra safety things.  in particular,
OpenResty uses a random-sample CRC for longer strings, which (IIRC)
covers strings up to 72 bytes.

But after that, yes; bad hashes are a thing you have to be mindful of
if you handle lots of external data on mainline LuaJIT.

surprisingly, the most commonly mentioned danger (malicious HTTP
headers) isn't a real problem.  This came up when I was at Cloudflare,
and did a few experiments to be sure.  with the highest density of
distinct colliding strings on every single request, at the highest
rate handled by a server, i could easily make the string interning
step take 10,000 times more... but that increased total latency by
less than 5%.  so, it wasn't that scary in the end.  the saving point
was a limit in the request size; if it was an unbounded input, the
outcome would be much worse.

but there was other place where it _did_ bite us: when exporting
status messages written in capn'proto.  since this is a static
structure, lots of messages were the same except by an id number,
which was between the midpoint and the end, safely between the few
bytes sampled by the hash.

the packets were produced on C and FFI buffers, so there weren't
considered "strings" until the last step, where the OpenResty output
function only received a Lua string.  it was this last part that took
over 40% of the total time.  the simple fix was to add an output
function that received the FFI buffer directly.  the moral was: "don't
handle static structs as strings".



-- 
Javier
_______________________________________________
lua-l mailing list -- lua-l@lists.lua.org
To unsubscribe send an email to lua-l-leave@lists.lua.org