2

I'm researching strategies for storing what could potentially be a large amount of data and I want to find the best storage technologies. I'm open to any suggestions MySQL, NoSQL, flat files, anything.

What I'm doing:

  • I will distribute all 4-byte integer numbers amongst a set of users.
  • Numbers will be 0 through 4,294,967,295, unsigned 4-byte integer range.
  • Users can have many thousands of these numbers.
  • Expecting thousands of users but small possibility of millions.
  • Numbers will be distributed over a period of time, not all at once
  • Using AWS, a few servers and EBS volumes

My main concern is storage space. I need to do this on the cheap and large volumes cost a bit of money on AWS.

I've done a little research on representing the number allocation mathematically but I found too many issues with that.

Requirements

  • Somewhat efficient retrieval for analytics and realtime data display. Doesn't have to be lightning fast but reasonable.
  • I'll need to do lookups in both directions user id -> number and number -> user id
  • As little storage space as possible.
  • Reasonable (less than 8 GB) memory usage.
  • Must be accurate, lost numbers and mis-assigned numbers are not an option.

Here's what I've found so far:

The lower bound for storing all 4-byte numbers associated with 2-byte user IDs is ((4+2) * 2^32 / 1024 / 1024 / 1024) = 24 GB.

Cassandra is a key/value pair database. Based on this http://www.datastax.com/docs/0.8/cluster_architecture/cluster_planning I calculate that if I used every 4-byte number as keys and 2-byte user IDs as values the I'd need approx 260GB of storage (without replication).

Redis is in-memory. I think this would eliminate it as a possibility since that much memory would be crazy expensive on AWS.

I'm currently looking for similar info on MySQL and Mongo.

Here's my question. Is there any references I could use for determining the best solution or are there alternate solutions to this that I'm not thinking of.

Thanks all.

UPDATE - I added an additional requirement, I need to lookup numbers based on user id and user id based on number. Also, Redis is in-memory so a direct implementation would make Redis more expensive than a disk based solution.

8
  • 1
    If you store as a flat array, the lower bound is simply 2 * 2^32 / 1024 / 1024 / 1024 = 8 GB. No need to store the number itself, you can use that as the array index. Of course, that's not particularly tractable for an RDBMS-like solution... Commented Jan 13, 2013 at 19:55
  • @Oli does that pass "Somewhat efficient retrieval"? :-) Commented Jan 13, 2013 at 20:01
  • @JanDvorak: Who knows? ;) I guess it depends what is meant by "analytics"; an array is a pretty efficient way to index and represent a dense allocation. Of course, if the OP wants to do reverse-lookups (e.g. find all numbers assigned to a particular user), then it would be terrible. But that's the trade-off. Commented Jan 13, 2013 at 20:03
  • Reverse lookups (user id to number) is needed. I'll add this to the requirements list
    – crempp
    Commented Jan 13, 2013 at 20:07
  • When doing course assignments, it's best to make your own attempt. You'll learn a lot more.
    – Bohemian
    Commented Jan 13, 2013 at 20:31

2 Answers 2

2

Actually, you only need to store the numbers that have a user; if you're looking for a number that is not stored, you'll get an empty result so you know the number is not assigned.

For MySQL:

CREATE TABLE mashup
(
   id       bigint primary key,
   user_id  int,

   index (user_id);
);

The primary key will make sure 'id' has an index; also, bigint has more room so you don't run into nasty issues like integer overflow. Then, for each user, insert a record like so:

INSERT into mashup VALUES (181870388, 90128);

Want to know if a number has a user?

SELECT user_id FROM mashup where id=xxxxx;

Or

SELECT COUNT(*) FROM mashup where id=xxxxx;

Want to know what numbers a user has?

SELECT id FROM mashup WHERE user_id=yyyyy;

The beauty is that you don't waste space storing all 4 billion numbers, only the number of user entries.

2
  • Thanks for the answer. This is a beautiful solution, however I will need to assign every number eventually which means at some point I will hit the worst case for this database storage solution.
    – crempp
    Commented Jan 14, 2013 at 2:15
  • In that case, unfortunately yes. The only optimization I can think of is storing ranges of numbers, if you know there will be a reasonable amount of adjacent numbers assigned to the same user.
    – JvO
    Commented Jan 14, 2013 at 17:19
0

Maybe our example can help. We are using couchdb to store the whole set of ported telephone numbers for a big country in Europe. Indexing this for the first time takes quite a bit but then map-reduce makes it very quick.

Our disk usage is as follows:

Usage: 8.2 GB
Numbers of documents: 22109793
Average characters per document: 272

Hope this helps in your choice.

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.