6

I have around 200 million new objects coming in, and a 90 day retention policy, so that leaves me with 18 billion records to be stored in the form of key-value pairs.

Key and value both will be a string. It is basically a mapping between a unique identifier for the object in the application to the unique identifier for the object in the actual object storage.

There is an application which loads objects into a Web OS. For each object it loads, it creates a 16 character string key, say DataID. The Web OS itself creates a 40 character string key, say ObjectID. So what I'm trying to do is create a mapping between DataID -> ObjectID for 18 billion objects. I'm don't know the mechanism being used to create the IDs.

I will have to deal with:

write(key,value)
read(key)
delete(key,value)

I am looking for ideas for an optimal way to implement this. It should be optimized for reads & writes. Space optimization is secondary.

I know Hadoop/NoSQL is one way to go, and probably another solution would be distributed Hash tables, but a few more options would help me decide which is the best solution. A relational database is not an option as we don't have an existing RDBMS in the current environment.

Chaos
  • 187
  • 1
  • 1
  • 7
  • 3
    20 million times 90 is 1.8 billion. Not that it matters much for the question, but is there a factor of ten somewhere you left out? – Karl Bielefeldt Jun 05 '13 at 18:21
  • Sorry, missed a 0, it should be 200 million, edited it – Chaos Jun 05 '13 at 18:24
  • 8
    Well, even if it is just 1.8B and not 18B you still likely won't be able to hold that all in memory, which means you'd need to be storing it in flat files, probably broken up into chucks. Doing that efficiently is...very hard. With that much data I'd *highly* suggest getting a database, trying to manage all of that from scratch would be...a lot. – Servy Jun 05 '13 at 18:25
  • ok, so do I rule out using datastructures like tries etc..? – Chaos Jun 05 '13 at 18:26
  • 1
    What do you mean by "optimal" or "best?" – Robert Harvey Jun 05 '13 at 18:27
  • 2
    i mean, it should perform reads and writes quickly – Chaos Jun 05 '13 at 18:29
  • 1
    When you say NoSQL, are you considering CouchDB? – Matthew Flynn Jun 05 '13 at 18:38
  • I'm not sure which of the noSQL database would be best for my requirement, but yes CouchDB is an option. I am also considering using HBase – Chaos Jun 05 '13 at 18:40
  • So you just want to know which one is the fastest? – Robert Harvey Jun 05 '13 at 18:52
  • I am exploring different options to see which option would be fastest, yes. NoSQL is one such option – Chaos Jun 05 '13 at 18:56
  • 2
    I'm sorry, but I just don't see a question here. There are plenty of resources already out there to help you make your decision, and I don't see how we can add any new value here. A cursory [Google Search](https://www.google.com/search?q=fastest+nosql) turns up this: http://www.datastax.com/resources/whitepapers/benchmarking-top-nosql-databases and this: http://www.networkworld.com/news/tech/2012/102212-nosql-263595.html – Robert Harvey Jun 05 '13 at 19:00
  • 4
    If a relational database is not an option because you don't have a RDBMS in your environment, NoSQL isn't because you don't have that in your environment, either. This wheel has been invented many times; don't reinvent your own. – Blrfl Jun 05 '13 at 19:04
  • These are comparisons between NoSQL databases themselves. But as I said earlier, NoSQL would be one option. I am also exploring option in another directions like Distributed Hash Tables, RDBMS, or probably some options involving not using any sort of database. – Chaos Jun 05 '13 at 19:05
  • @Blrfl, ok, so are there any options outside of databases? – Chaos Jun 05 '13 at 19:06
  • @shailesh: Sure, but are they options you really want to explore? Will coming up with a home-grown scheme to write this stuff out to a bunch of flat files and go find it later really be worth your time? – Blrfl Jun 05 '13 at 19:19
  • @Blrfl , it's not ideal i agree, but i have to pitch a proposal to higher management, and I'm not sure what they will approve, so I need to explore an option outside of database too – Chaos Jun 05 '13 at 19:23
  • 2
    You could do it in-memory if you're willing to spring for a blade with 1.5TB RAM. For example: http://www.cisco.com/en/US/products/ps12527/index.html – Matthew Flynn Jun 05 '13 at 21:15
  • This question is very ill-specified. What's the rate of reads and writes? Is there a single reader/writer or many? If many, how consistent do you need the results to be? – Dan Halbert Jun 05 '13 at 21:51
  • There will be a single reader/writer. Read will be of type read(key), returns a key-value pair. Write will be write(key,value) – Chaos Jun 05 '13 at 21:54
  • What is the max string length of the key and value? That would help you calculate the size of the data you need to store. – zuallauz Jun 05 '13 at 21:59
  • 1
    @zuallauz around 100 bytes per key value pair, comes upto 1.6 terabytes for 18 billion key value pairs – Chaos Jun 05 '13 at 22:08
  • If you want 'optimal' and really fast you could store it all in RAM with some kind of database for persistence as well. You might need a [System z (Mainframe)](http://www-03.ibm.com/systems/z/hardware/zenterprise/) which can hold up to 3TB RAM or perhaps cluster a few of those Cisco blades mentioned earlier. – zuallauz Jun 05 '13 at 22:24
  • You are going to have to do something dramatic to partition that key space and reduce your search times. That requires knowing something about how the the keys are assigned and how they are statistically distributed. – John R. Strohm Jun 06 '13 at 12:38
  • There is an application which loads objects into a Web OS. For each object it loads, it creates a 16 character string key, say DataID. The Web OS itself creates a 40 character string key, say ObjectID. So what I'm trying to do is create a mapping between DataID -> ObjectID for 18 billion objects. I'm don't know the mechanism being used to create the IDs – Chaos Jun 06 '13 at 16:22

2 Answers2

6

Try redis. Its all in memory and dumps data so it can be hot on reset. However you might need to be careful and change the settings if you need to not lose data as it normally waits a second or two before dumping (or did i remember the default settings wrong?).

Use a hash where GUID/6 or 7 bits is the key and the remaining is a field http://redis.io/commands/hmset. Note having more field names make it slower so stick to <=128 as my personal rule of thumb. I recommend having 64 or 32bit but test with the keylength.

The reason I say use a hash is to decrease memory usage. More fields = less pointers (and an increase in CPU time)

Seki
  • 241
  • 1
  • 13
5

Look at these key-value stores: Berkeley DB Java Edition, or JDBM (JDBM3 is the latest), or MapDB (JDBM successor). Tokyo Cabinet is not native Java but has a Java wrapper.

For an overview see http://en.wikipedia.org/wiki/Dbm.

Dan Halbert
  • 151
  • 4