C++ in-memory Key-Value stores

Question

I'm looking for suggestions regarding in-memory key-value store engines or libraries, that have C++ interfaces or that are written in C++.

I'm looking for solutions that can scale without any problems to about 100mill key-value pairs and that are compatible/compilable on linux and win32/64

Broadside

do you have any duplicate keys/values or all unique? – Exclaim

The requirements "needs to scale to about 100 million key-value pairs" and "in memory" are going to be at odds with each other. It is possible to satisfy both, but the first question to ask is whether you need to satisfy both. Do the keys/values really have to be in memory? – Buckie

@Chris: It can have duplicate keys, so it would sort of be like std::multimap or std::multiset – Broadside

First of all, can the keys all be determined in advance, or do you need to be able to constantly insert/erase keys? If it's just a static table that you load in and only need to look up at runtime, storing it contiguously in a vector as sorted data and using binary_search might be sufficient. – Disaffection

Answer 1

How about std::map?
http://cplusplus.com/reference/stl/map/

Immaculate

Answer 2

If you really need to store such amount of pairs in memory consider this Sparse Hash. It has special implementation which is optimized for low memory consumption.

Flashy

Answer 3

std::map is fine given that size of key and value is small and the available memory is large ( for about 100million pairs). If its not the case, and you want to run a program over the key-value pairs, consider using a standard MapReduce API. Map Reduce is specifically meant to be used on distributed systems and process large data specially key-value pairs. Also there are nice C++ APIs for Map Reduce. http://en.wikipedia.org/wiki/MapReduce

Houppelande

Answer 4

Try Tokyo Cabinet, it supports hashtables and B+trees:

http://1978th.net/tokyocabinet/

Wilie

Link is broken! – Baggs

Answer 5

Try FastDB, though you may get more than you ask for. Tokyo cabinet also seems to support in-memory databases. (Or, backed by file mapped by mmap. With modern operating systems, there's no much difference between "in-ram" database and something mmap'd as the OS caching makes also the latter very efficient).

Monaghan

Answer 6

A hash map (also called unordered map) is the best bet for that many pairs. You can find an implementation in Boost and TR1.

Edit: Some people have questioned the size- if he's got, say, a 64bit server, there's plenty of space for 100million kv pairs.

Bifarious

I'd like some persistance mechanisms, possible to disk or the network. – Broadside

Then you need to get a database. – Bifarious

this might end up with memory fragmentation problems when adding or deleting. – Ammons

Answer 7

Oracle Berkeley_db is what you need.

Voluntary