Storage system for large quantities of unique key value pairs optimized for insert

Question

Background

I'm in the process of attempting to improve part of our data storage and analysis architecture. Without getting into a lot of details, at a certain part of our data analysis process we have a need to store large quantities (~100s of millions) of small pieces of unique data. The data looks like this:

ID, 20 bytes (immutable)
Hits, unsigned 64bit int (mutable)
Value1, arbitrary length byte array (immutable)
Value2, arbitrary length byte array (immutable)

I currently have this data stored in two parts, a B+Tree index which maps the keys to unsigned 64bit integer values. Those values are file offsets in a data file which contains a structure like:

[Hits] UInt64
[LengthOfValue1] UInt32
[Value1DataBlob] N-bytes
[LengthOfValue2] UInt32
[Value2DataBlob] N-bytes

As new values are posted to this data store, the code performs a lookup in the B+Tree. If the tree contains the value, the hit count is incremented in the data file. If the value is not there, a new entry is appended to the end of the data file, it's start offset the inserted into the B+Tree.

Later, after this process is complete, we will enumerate the data performing more processing on it. What is important here though is that, if the key is already in our system, we are incrementing the hits on that key. This is essentially a cache, which is tracking hits on each piece of data as it's encountered.

What we are finding is that as the B+Tree grows larger, insert times become VERY slow. Lookup remains very fast (as you might expect).

Question

So -- Does anyone know of another way to do this, where unique checks are lightening fast, and so are inserts? We really don't care about later search performance, because once we go through the initial build of this dataset, all we will use it for is to enumerate the results. We're not going to be doing random searches against the dataset, in a long term manner.

Please do not suggest any kind of off-the-shelve database system. We've tried a lot of them, and this custom solution is faster than any of them, with a smaller data storage footprint.

We're just trying to improve our custom solution, and have hit a wall with our collective CS knowledge. Maybe this is the fastest way to do this, or maybe a different structure would perform better than the B+Tree for inserts at this scale?

Answer 1

B-trees and their various modified versions are the standard way to index arbitrary data while keeping insert times within a reasonable frame. Insertion happens in O(logn) time, which I believe cannot be improved, unless your key range is limited enough to make a bitmap usable.

That said, there a few things that can make B-trees and their variations faster:

• Watch your keys. Non-random keys can cause pathological situations. You are using a hash, so key-dependent pathological situations are rather improbable.

• Benchmark the application. Find out if the B-tree implementation achieves that O(logn) time for large datasets. Note: for large datasets. Only compare datasets for which the B-tree size significantly exceeds the size of your physical memory. Smaller datasets will have minimal disk seeks due to the OS cache and will seem lightning-fast. E.g. if you have 4GB of RAM, try comparing an 8GB, a 16GB, a 32GB and a 64GB index. If you do not see an O(logn) time curve, you may have a problem in your specific implementation.

• Profile the application. Find out where the bottleneck is. Is it the CPU (not very probable)? Disk seeks (here's my money)? What part of the code produces the bottleneck?

• Measure your B-tree index alone without the backing file. Does the application speed-up significantly without the backing file seeks? Would it make sense to store some data (e.g. the hit count) in the B-tree nodes themselves, to avoid the extra seeks? Storing some common data in the B-tree nodes should provide a major performance increase.

• Use a shorter and faster intermediate hash. It does not have to be cryptography-level, just sufficiently random. I have used MurmurHash3 with pretty good results. Use that hash as the key in the B-tree, and an external mechanism (e.g. linked lists) to handle collisions. Using shorter keys will speed up your B-tree significantly, because each node can fit more ranges.

• Optimise for less I/O and fewer disk seeks. In your case it's quite probable that the performance killer lies in your disk. Try using larger B-tree nodes.

Answer 2

The mutable state is the set of active IDs and the number of hits for each. I bet you can fit those in RAM.

• Create an in-memory hashtable mapping IDs to hit-counts.
• Create an on-disk journal file of records, similar to your current data file.

To insert an item, query the hashtable. If the key is found, increment the hit-counter. Otherwise, insert the key with count 0 into the hashtable, and append a record to the end of the journal file. After all the items are inserted, walk through the file and update each hit-counter to reflect what's in the hashtable.

The increment case involves only a hashtable lookup and increment operation, and never touches disk, so it should be fast. The append case involves only a hashtable lookup and a single disk write. You'll build the journal in sequential order which will make good use of cache and avoid seeks.

Answer 3

This was migrated here from stackoverflow, and I'm not sure that this is the best place for it. The TCS Stack Exchange is really for theoretical questions, so details about how many bytes are in the key are often not seen here.

That being said, I will try to answer a question similar to yours that is framed in a somewhat more theoretical way:

How can I optimize insert time on a disk?

On a disk, you're more concerned about I/O than computation. I know of a few ways to reduce the number of I/Os needed on insert.

1. Just dump your data to disk. If you can really put off lookups until "Later, after this process is complete, we will enumerate the data performing more processing on it", you can just append your data to the end of a file. I/O performance of insert: $O(1/B)$; of queries: $O(n/B)$.

2. Just use a hash table, rather than a B-tree. A B-tree has insert and lookup I/O performance of $O(\log_B(n))$. Hash tables reduce this to a constant.

3. If #1 puts our lookups off too far into the future, you might try log-structured merge trees. They go under many names, and are implemented in many places: leveldb, riak, rethinkdb, Acunu's castle, COLAs (now sold by Tokutek), Cassandra, and others. The I/O cost of insert is roughly $O((\lg n)/B)$, and of update $O(\lg^2 n)$ (and $O(\lg n)$ for some implementations). One choice you can make when implementing these is to allow at most $O(n)$ total duplicate records while still maintaining $O((\lg n)/B)$ insert performance. For spinning disks, This is actually $o(1)$, and may be faster than a hash table in practice.

4. The results from "Using Hashing to Solve the Dictionary Problem (In External Memory)" by Iacono and Pătraşcu. Unlike your B+-tree solution, your keys will no longer be in lexicographical order. I/O performance of insert: $O(\lambda/B)$, where $\lambda \geq \max(\log \log n, \log_{M/B}(n/B))$; of queries: $O(\lg_{\lambda} n)$, for the same $\lambda$. This data structure is pretty complicated.

There are a few more that you might be interested in, including buffer trees and Brodal et. al's tunable update/query tradeoff trees.