Suggestions for a scalable architecture solution to large data problem

Question

Hi folks,

I am in the process of building/architecting a business social network web application that has a component that I think will lead to major scalability issues and I'd like to get some feedback/thoughts on the best way forward.

The application has a User object. The idea is, that every time a new user joins the system he ranks everyone else's "usefulness" to him based on a set of factors. Similarly, every other user on the system ranks him/her.

However, I'm worried about the scalability implications of this approach. For example, if 10,000 users join the system we are talking about 10,000^2 calculations to be stored to the database. That is 100 million records so that clearly becomes problematic both in terms of time taken to calculate these rankings but also in terms of storing this in a database.

Thus, I'm looking for help/inspiration :)

My background is in java and I've been looking at hadoop/map-reduce as a possible way to implement the calculations in a parallel manner, however I really am not sure whether this problem is applicable to Map Reduce or as to what is the best approach in general.

So, I suppose there are two specific parts to my query..

1) To do the actual calculations, should I do these in a parallel manner, ie..is Map Reduce a good approach for this problem

2) To store the rankings, what should I be using...is a standard relational database a bad idea, ie...this won't be a good fit for MySQL...should I look at something like Cassandra, HBase or some other NoSQL solution?

Any help/ideas is greatly appreciated.

cheers, Brian

Answer 1

I'd suggest only storing "real" values (those entered by a user). That way, users rank the other users that have value to them, and all the rest are assumed to be "useless" ;). Therefore, you'll store maybe a couple hundred values for each user. I'm assuming you're not really going to make each new user go through the entire list of other users and rank them individually, right?

You could also cut your space requirements down by making bidirectional associations that store both users' evaluations (one record links user A with user F and notes that A ranks F as a 5, and F ranks A as a 3). Cuts your space requirements in half, roughly, but it's still a lot of records. Plus you'll want indexes on both user keys, since you'll have to search both to find all records for a single user.

Answer 2

While 100m rows is surely big, it may not be as big as you think. I deal with a MySQL db that has a table with more than 10m rows that joins to other tables with more than 100k rows without too many problems. The important point is to get your indexes right and make your queries efficient. Perhaps before spending too much time thinking about a super-architecture, fill a play table with the rows you think might be in it and also write some queries you think you'll be writing and see if its manageable.

Answer 3

Before throwing the brute force of MapReduce to the problem, I'd try to reduce the search space. If it's a social network of even 10K users, that means to a particular user most other users are not known, thus not useful.

I would therefore try to limit the space of users to evaluate based on criteria that fit your social network. For instance, perhaps limiting the search to local users might be applicable (or limit it to them initially and do a more exhaustive search later). What "local" means in practice depends on your user, the idea is to use some optimizations based on the real world.