4

We have a ratings system in our website that allows users to provide feedback to 3 different questions about a user.
We currently calculate the rating using averages using the following query on our RDBMS:

SELECT AVG(question_1), AVG(question_2), AVG(question_3)
FROM ratings
WHERE user_id = 1

This query does not scale even when the result is cached (and it is) since some of our users have millions of ratings.
Using a functional index is not an option because our RDBMS does not support them and using one would slow down writes significantly.

The solution I came up with is to create an append-only log of the averages in a given time frame and periodically merge them using a weighted average.
So we'd end up with the following data structure per user:

| question1_avg | question2_avg | question3_avg | ratings_count | timestamp  |

| 3.4           | 4.5           | 4.9           | 10000         | 1480429792 |

| 5             | 5             | 5             | 30            | 1480429848 |

So the merge process would look like:

(3.4 * 10000 + 5 * 30) / 10030

The previous records would be tombstoned and the new average will be appended to the log.
Is this design correct? Will it work at scale?
Where will you store that kind of data? A document store (such as MongoDB), a key-value store (such as Redis) or an RDBMS?

Since this concept is very similar to CRDT Counters I tried to find a Convergent Replicated Data Type that allows you to calculate averages but I could not find one. Is there a data structure I missed?
Is there another algorithm or data type I should look into?

  • 1
    What do you mean by "correct?" Are you asking if it will provide the correct answer? It will, with some degree of error. What does "will it work at scale" mean? You have to read the data to get an average, regardless of the math you use. "Where will you store it?" Wherever you store your other data? There isn't anything remarkable about this data. – Robert Harvey Nov 29 '16 at 14:55
  • Correct means that the calculation is correct and will provide the approximately same answer as the SQL query. As for the scale, will it allow us to query the data more frequently. Regarding the data store, this is again a question of scale and read/write throughput. – the_drow Nov 29 '16 at 15:12
  • 1
    Why not just keep the total and count for each user? – JimmyJames Nov 29 '16 at 15:34
  • @JimmyJames That can work quite well actually with two CRDT counters. – the_drow Nov 29 '16 at 15:50
  • 1
    You can also do something like total and counts per day, count by rating etc. If you keep the counts per rating as amon suggests you can calculate other more interesting statistics like percentiles. – JimmyJames Nov 29 '16 at 17:44
4

What you can do to optimize this depends on how precisely the rating system works, and what kinds of analysis you want to do with the data. But if the ratings are discrete (like a 1–5 star rating), we can calculate them efficiently by storing the accumulated votes in a histogram. That is, we count how often each rating was chosen:

| Question | r1  | r2  | r3  | r4  | r5  | (avg) |
+----------+-----+-----+-----+-----+-----+-------+
|        1 |  12 |  89 | 127 | 698 |  74 |   3.7 |
|        2 |  39 |  72 | 487 | 278 | 124 |   3.4 |
|        3 |  90 |   9 | 776 |  25 | 100 |   3.0 |

where the average is calculated as (1*r1 + 2*r2 + 3*r3 + 4*r4 + 5*r5) / (r1 + r2 + r3 + r4 + r5), which looks tedious but is a constant-time operation.

This is similar to your weighted average approach, but will not accumulate errors over time.

You should probably still store the individual ratings as well, as that allows additional analysis (e.g. is there a correlation between question 1 and 3? Are there trends over time?). By aggregating the data into a histogram, we lose that information.

It is perfectly reasonable to store both the individual ratings and the histogram in the same relational database. In particular, this will allow us to keep the vote counts in sync by using triggers and/or stored procedures. Upon insert, the appropriate count is simply incremented. If we were to use a separate database for the aggregated ratings, the applications writing to the database would have to do additional work.

This strategy will not work if the possible ratings are not discrete, or when the rating calculation is more complicated than a simple average, e.g. if ratings decay over time.

  • 1
    I glossed over this at first but this is a good idea. I would normalize it though to have a count and a rating column instead of a column per rating. – JimmyJames Nov 29 '16 at 17:46
  • It depends on your business requirements. – the_drow Nov 29 '16 at 18:38

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.