search

spotify / sparkey

Simple constant key/value storage library, for read-heavy systems with infrequent large bulk inserts.
Apache License 2.0
1.18k stars 81 forks source link

Problem creating hash indices larger than available RAM #31

Open spkrka opened 9 years ago

spkrka commented 9 years ago

Currently the hash writing requires malloc of the entire index size. If this is larger than available memory, the operation fails.

We have a use case requiring more than 1.65 billion entries, which results in a 32 GB+ hash index. This is larger than the available memory on the machine that builds it.

We could replace the malloc with mmap:ing of the file itself but that would lead to a lot of random reads and writes from disk which would be horribly slow.

I have an idea to reduce this limitation, but no time to do it at the moment.

  1. Write all hash entries to some sort of log file (64 bit hash value, 64 bit data offset).
  2. Calculate hash capacity (num_entries * factor)
  3. Sort the entries in the file by hash value % capacity. (This can be done efficiently without having everything in RAM)
  4. Mmap the large index file
  5. Iterate over the sorted hash entries and write them to the mmapped index. This should be efficient since the mmapped writes will happen with good locality and in sequential order. Except for the last values which may wrap around to the beginning of the file, but that's a small part of the data.

For sorting the large set of entries, split it into reasonably small chunks and sort those in memory. Then run a tree of sequential file merges.

nresare commented 9 years ago

Sounds like a good strategy, unfortunately I don't have any leftover time either. Perhaps we should offer this up as something fun for algorithmically inclined people to have a go at? We could give access to a machine and a test dataset.

spkrka commented 9 years ago

Yes, if anyone is randomly reading the issues here, feel free to implement this and submit a pull-request :)

spkrka commented 9 years ago

I don't think a test dataset or machine is necessary, you can just generate a fake dataset and make max-memory configurable.

vinniefalco commented 8 years ago

Did this ever get resolved?

spkrka commented 8 years ago

No, this has not been implemented yet.

omidraha commented 6 years ago

Please note this on Read-Me file that hash index needs to be lower than available memory.

spkrka commented 6 years ago

Done!