5
$\begingroup$

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?

$\endgroup$
7
  • $\begingroup$ Are the keys random? What is the key data type? Do you adhere fully to the B-tree balancing requirements? $\endgroup$
    – thkala
    Apr 28, 2011 at 21:49
  • $\begingroup$ The keys are SHA1 hash digests of some other data. They are 20 arbitrary bytes. This is a B+Tree and yes, fully balanced. I was thinking that a less rigidly balanced structure would help, but I'm not aware of anything that's been proven to be significantly better for this use case. $\endgroup$
    – Troy Howard
    Apr 28, 2011 at 22:01
  • $\begingroup$ I'd so be throwing this into redis... just saying... $\endgroup$ Jan 20, 2012 at 6:05
  • 2
    $\begingroup$ How much data do you actually have? For example, if you had 500 million 20-byte identifiers + 64-bit offsets, it would be less than 16 GB in total, and nowadays getting a server with >> 16 GB of RAM shouldn't be any problem. Hence it sounds like it might be possible to store your entire index in RAM (as a hash table perhaps?). $\endgroup$ Jan 21, 2012 at 22:47
  • 1
    $\begingroup$ I don't think I understand the exact requirements of your data structure. It's not clear what you mean by "the key" and "the value". Is the ID the key? Is it ever possible to generate two "values" with the same ID but different blobs? If so, is it important to keep the first blobs generated? Do you ever need to look up hit counts before the "this process is complete"? I think you might be able to get what you want in $O((\lg n)/B)$ I/Os per insert, but I'm hesitant to conclude that with the information given. Could you perhaps make a short list of the required operations and their invariants? $\endgroup$
    – jbapple
    Jan 22, 2012 at 20:30

3 Answers 3

1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.