Creating a Key-Value Store on Disc with Concurrency in Java

Question

I need to read a set of files and break it in to key-value pairs, and save these as a (key,list of values) for that key on disc, much like the map-reduce paradigm. Everything is on one computer though. I could for example write the different lists on different files and name the files with the key. That seems like a very poor way of doing things. To begin with if you have a billion keys, you will end up with a billion files. So obviously that is not going to work, and I will need some sort of memory mapping. I will also have to have different threads doing the map job, so if they were to write to this same buffer there is going to have to be some sort of synchronization between them. If I have a key-value buffer mapping, and synch over the buffers, then the threads shouldn't be stepping on each others toes, so I think that part should work. The question is how do I do the mapping of the values to disc. How do I write buffers that correspond to different keys in the same file? If someone could point me in the right direction, it would be much appreciated. My knowledge of this area is quite pathetic. Thanks again.

Answer 1

From a practical standpoint, it would be easy to do this with BerkeleyDB, as Lirik suggested.

If you are more interested in theory than practice, I'd suggest that you approach this as an "external sort" operation. That is, read as much input as you can into memory, then sort by key. Write the sorted chunk out as a single file. The sorted files can then be easily merged into a single file.

Among other applications, this is the approach used by Lucene to build "inverted indexes" for searching text. The "keys" are words in documents, and the "values" are a list of documents in which the word appears. Lucene reads documents, and for each word, creates a term-to-document entry in memory. When memory is full, it writes the index segment to disk. When there are a lot of index segments on disk, they are merged into a single segment. In fact, you could also adapt Lucene's index writer to your task.

The work can be partitioned into multiple threads. However, you have to be sensitive to disk contention. Skipping around to read and write many files concurrently will slow a conventional drive down a lot. There may be opportunities to schedule some activities concurrently. You could probably read in new data from one file while you are writing the previous sorted chunk to disk, especially if the machine has two disk drives. Of course, using an SSD for temporary storage of some of the sorted segments would help immensely.