Fastest way to retrieve/store millions of small binary objects

Question

Hi everyone,

I am looking for a fast (as in huge performance, not quick fix) solution for persisting and retrieving tens of millions of small (around 1k) binary objects. Each object should have a unique ID for retrieval (preferably, a GUID or SHA). Additional requirements is that it should be usable from .NET and it shouldn't require additional software installation.

Currently, I am using an SQLite database with a single table for this job, but I want to get rid of the overhead of processing simple SQL instructions like SELECT data FROM store WHERE id = id.

I've also tested direct filesystem persistency under NTFS, but the performance degrades very fast as soon as it reaches half a millions objects.

Give me your best, hackers of stackoverflow :D

P.S. By the way, objects never need to be deleted, and the insertion rate is very, very low. In fact, every time an object changes a new version is stored and the previous version remains. This is actually a requirement to support time-traveling.

Just adding some additional information to this thread:

To BLOB or Not To BLOB: Large Object Storage in a Database or a Filesystem http://arxiv.org/abs/cs.DB/0701168

Answer 1

I think the database query is your best bet.

The whole structure of a database is tuned to just this kind of case, and parsing and optimizing the simple query is farily insignificant.

You might be able to cook up a scheme where you store all the objects in a big blob directly to the filesystem, and then open a memory mapped file view on it, and index the object IDs with an offset into the blob, but I doubt you'd see much more perf than the DB, since this is essentially what it does.

Answer 2

Store a separate index (another file) of [Guid -> file number + offset in file]. Use a binary search for retrieval, and move to file n+1 whenever file n reaches a certain size. Each row in the index file is only 24 bytes (fixed size: guid + file number + offset, split files at 4GB), and sorting it is fast (insertion sort at a low rate.)

Edit: You have very simple requirements that are straightforward to optimize. This carefully constructed system should outperform the database, especially if you are careful about block reads of the data and asynchronous IO. The database queries will always have the overhead of parsing.

Edit 2: If you need it safe as well (always a good idea), take a look here for a description of how the concept of file system transactions can help you bullet-proof things.

Answer 3

You may be able to lessen the performance problems of NTFS by breaking the object's GUID identifier up into pieces and using them as directory names. That way, each directory only contains a limited number of subdirectories or files.

e.g. if the identifier is aaaa-bb-cc-ddddeeee, the path to the item would be c:\store\aaaa\bbcc\dddd\eeee.dat, limiting each directory to no more than 64k subitems.

Answer 4

You need call a prepare function only once per statement, with parameter denoted e.g. by ? (so SELECT data FROM store WHERE id=? is the statement you'd prepare); then what you do "millions of times" is just to bind the parameter into the prepared statement and call sqlite_step -- these are fast operations. Worth benchmarking if blob open might not be even faster. IOW, I recommend sticking with SQLite and digging into its low-level interface (from managed C++ if you must) for maximum performance -- it's really an amazing little engine, and it has often surprised me favorably with its performance!

Answer 5

Did you considered to try object database, like db4o? It can persist any CLR objekt, and access them quickly with query language (supports LINQ!). I didn't have millions of objects, but with few thousands access was fairly quick, no major difference than similar SQL query with indexed id field.

Answer 6

How about a binary file with fixed size blocks of around 2k, having the first 4 bytes be the length of the object...

location of object i is at i*2048 bytes, then read 2048 bytes for the object, getting the length of the actual object from the first 4 bytes (unsigned).

Answer 7

I like Earwicker's solution. The way I've dealt with this is very similar.

What I did was this:

Let's say your guid is 3F2504E0-4F89-11D3-9A0C-0305E82C3301.

Hash the guid down to a three letter hash. aaa-zzz.

Suppose, for the sake of argument, that your guid hashes down to "xap".

Your info will be found in the file c:\store\x\xa\xap\3F2504E04F8911D39A0C0305E82C3301.dat

Naturally, there are many variants of this strategy. For instance, xap could be a file with all the binary objects appended together, with a header or an external file that has the guids and offsets into the file.

Answer 8

You can check if HDF5 structures are suitable for your tasks

• .Net interface

Answer 9

I tend to agree w/ Alex, if you write your own solution you are reinventing stuff that's already likely in SQLite, but if you must...

You can likely make a BTree work here. It is the workhorse of any database and your problem space isn't all that bad. 10s of millions of 1k objects is still only 10's of billions of bytes so the file is manageable by the OS and there are a lot of BTree examples out there to try.

Compared with using the file system directory structure to essentially create a BTree analogue using a real BTree is going to be far faster.

Another solution that might be of interest is Mogilfs which is a distributed redundant file system.

Answer 10

I don't know if SQLite support indexes or not, but if it does then you can speed up things by creating an Index over the ID field.

If it doesn't, then your best option is B+ trees. Thanks