3 ms·
I came across a similar solution[1] while creating a packet analyzer. At speeds like 50Kpps, and needing 10 or so indexes per packet, you end up needing to do 5
by MichaelGG 14y ago
I came across a similar solution[1] while creating a packet analyzer. At speeds like 50Kpps, and needing 10 or so indexes per packet, you end up needing to do 500K index writes per second. If you plan on making it work on a single small server and disk, you need to get creative. I used the original PageRank paper as inspiration, but it turns out to be a rather old and straightforward problem.
Isn't the key insight just using a couple layers of ISAM? Create ISAM index, save. Repeat for as many levels as you find useful. Top-level pages are almost always in RAM, so almost all index lookups require only a single seek. Toss in a nice compression library and you've got a fairly tight system.
Not to say it isn't nice to have a standard format and library to implement such things. It just seems that everything's just a variation on things developed in the 70s.
1: I made each index contain a pair of 64-bit ints, allowing me to reasonably index a wide variety of values and point to the likely chunk file. As the keys and values are ordered, I could get by with easy-to-implement delta compression only. The indexes only point to a chunk, so many packets shared a single entry. In production, it came out to about 2.8bits/packet (down from a few 8-byte hash values).
Here's my admittedly poor KV implementation:
https://github.com/MichaelGG/cidb/tree/master/CiDB https://github.com/MichaelGG/cidb/tree/master/CiDB
- faltet 14y agoBlaze is intended to be a much more general solution than a pure key-value store (although it will be able to tackle this use case too). But yes, the idea under BLZ is close to your projects, namely, leveraging the available resources in your computer in the most useful way. But sorry, I strongly disagree in that everything is a variation on things from 70's: during these good old years, the memory hierarchy was far simpler than nowadays, and having to deal with that introduces a great amount of complexity in libraries that are designed to get most out of modern computers.
- MichaelGG 14y agoThe memory hierarchy can be pretty complicated, but the general design, the part that's making the rest possible, seems to me that it's stacking ISAM. It might not be a simple stacking, you need to tune the parameters to deal with various cache levels. But it's the same principle, isn't it? I agree the hardware is quite different, vastly more complex.