2

I have following entities:

Data:

  1. User_id
  2. Categories: Interests, Disinterests, Categories A, B C...
  3. Each categories have sub categories: Interests=Gaming, Physics, Programming etc..
  4. Now each user could belong to multiple sub categories.
  5. So there is M:N relation ship between categories and users.

Scale:

  1. 1 Billion Users
  2. 100 Categories each could have subcategories ranging form 100 - 10,000

Operations Needed

  1. Batch Read and Write: Selection and Projection given user_id. E.g. Get all the Interests of user A.

  2. Real Time Read and Write: I need to get all the users for a given field like Interest:Games.

Current Design

I used separate files for each sub categories containing list of users. Redis server has keys-value pairs like

<userId_InterestId:games,programming>

However this design has many limitations, like slow access times due to disk operations to get all users for a given category. Huge number of keys in Redis i.e. number of (users * number of sub_categories).

I need a change of design

Current plan is to use MongoDb to maintain hierarchical data for user <-> categories mapping.

<User_id, Interests, A, B, C>.

Each categories will have children fields. Since MongoDB is in-memory DB access using user_id should be faster right? But how about reverse query where I specify Interest::Programming as key? Is there any better way I could design it?

  • 4
    1 Billion Users - seriously? – Philipp Jul 23 '15 at 11:43
  • One of the reason I haven't implemented such system yet. Current file base implementation has locks on the number of users per list. – Mangat Rai Modi Jul 23 '15 at 12:33
  • @Philipp these are not actual human users, but we expect 250k unique human users. Plus this data is for life time of the service. Hence the huge number. – Mangat Rai Modi Jul 24 '15 at 7:19
1

Here's what I would do: make no distinction between categories and subcategories. Each category would have parent category associated with it, which may be null (category and not subcategory).

If I understand correctly, categories are not children of users, so if a user gets deleted, it won't delete its categories. In that case, you will need a child table of user called UserCategories that associate a user id with a particular category.

So now, if you want to find all categories of a user, you have a child table which gives you this information. Inversely if you have a category, you can find all users associated with its id given UserCategories. By eliminating the need for subcategories to pass through a category, you've directly linked Users with subcategories and thus it becomes much easier to manage.

Obviously in your program, you may handle a category with a parent as a "subcategory" and treat it differently, but in the database, it only means a category with a parent category.

  • Neil, Thanks for the answer, However which db are you talking about? Is there any DB which will support child table and store that in memory for fast execution? – Mangat Rai Modi Jul 24 '15 at 11:36
  • @MangatRaiModi All and none. All in the sense that virtually all databases support caching of some type, but none in the sense that save for trivial databases run entirely in memory, you wouldn't want to keep an entire table in memory more than likely so databases don't generally do that. However, that doesn't stop you from keeping a LIFO cache for category lookups, holding the most common categories for fast lookup. – Neil Jul 27 '15 at 6:26
0

There are essentially 3 basic aspects of the model:

  1. A List of users (identified and indexable using user-id)
  2. A Tree structure for the Categories and Subcategories
  3. The M x N relationship between users and categories/subcategories.

Had there been a simpler structures of categories as linear list there would hardly be a question of how to do it. All you needed was to have a map of user-id:cat-id.

Now, since the category listing is a tree and not a linear map, it isn't all that bad! what you should do ideally is to create a hash-map which can linearize the completely hierarchical representation for till each leaf node

for a simple example -

  • HASH_VAL1 := GAMING
  • HASH_VAL2 := PROGRAMMING
  • HASH_VAL3 := PROGRAMMING->C++

Now it is easy to see that MxN relationship can be set up as user_id - HASH_VALX list.

There are several simple advantages this system has:

  1. The look up from Interest to User is just as fast as the other way. The reverse maping doesn't require any special indexing.

  2. You can edit and manipulate the interest categories or have other information around it which evolve without having to modify user-interest_hash_value relationship.

  3. You can convert the leaf into node and all still works. For example, another HASH_VALUE_X can start representing PROGRAMMING->C++->Borland-C++ that wouldn't affect the existing relationship which are at USER:PROGRAMMING->C++ level.

  4. You can interestingly add indirect relation ship for example, if USER_X:HASH_VALUE_3=PROGRAMMING->C++ implies USER_X:HASH-PROGRAMMING you can maintain that by just having another USER_X:HASH_VALUE_2 without affecting other data relations.

  5. Last but not least, adding data - filtering records can be pretty linear and hence can be optimized in multiple different ways (Caching, indexing etc.) depending on how system works.

-1

MongoDB would allow you to create an index on Interests. When you create an index for a field which includes arrays, each array entry gets a separate index entry. So when your documents look like this:

{
    _id:<<Objectid>>
    interests: [
        "Programming",
        "Knitting",
        "Paragliding"
    ]
}

a query like db.collection.find({interests:"Programming"}) would give you all documents where the interests array has an entry "Programming" and would benefit from an index on interests.

  • How will MongoDB perform if I have index on all the columns(100) in the table? As I need reverse query for each of them. Same index will work on sub categories also? @Negative Voter, I am not familiar with MongoDB could you please point out the problem with this answer? – Mangat Rai Modi Jul 24 '15 at 11:43
  • @MangatRaiModi What's a "column" and a "table"? Such things do not exist in MongoDB. Or do you mean field and collection? Like with every database system, each additional index reduces performance for inserts and for any updates which affect the indexed fields. Also, indexes require additional storage space. You might consider to turn those 100 fields into an array of objects where the field-name is the value of a key. Or not - it depends on how you query your data and how many datasets you expect per document. – Philipp Jul 24 '15 at 11:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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