Help me design this use case

Question

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?

Answer 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.

Answer 2

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.

Answer 3

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.