Scalable way to track who's viewed a post? I'm building an app that needs to check who, out of millions of users, has not received a post. If a post hasn't been seen by many people, this task will be easy. But if a post has been seen by nearly everyone, it will be difficult to find the needle (the user who hasn't seen it) in the haystack (users who have seen it)

Are there any known strategies to resolving this problem?
I think the complexity of performing this task is small and does not change with size. The same SQL that will find a missing recipient from 100 users will also find a single missing recipient from 100M users.  The time to do so, however, is likely to be linear in the number of posts and the number of users.

I can see two ways to organize the data. One is a "positive" list, the other a "negative". For the positive route the system actively stores what has happened. As a post is dispatched a list is kept of the recipients. For one million users this will be one million separate data items. Each item is marked as "unread". As a user sees a post the corresponding data item is marked "read". This will result in two million writes per post. It is likely most reading would happen within a short interval of the post being sent and tail off rapidly thereafter, so there will be spikes in write activity. The system will have to account for new users joining after the post was sent and users leaving before or after seeing the post.

In the "negative" route you store only read events - as a user sees a post the corresponding event is stored. When you need to check who has read the post the system compares this "read" list to the master list of users and returns the intersection or complement as appropriate. Should a new user join after the post was sent they will show as "not read" even if that post was never sent to them. (This assumes a push model, like email, rather than a pull model, like browsing a website.)

How to store this? In a relational model you would have one row per user/post. For 1M users and 100k posts, and integer IDs for each, this works out at 150GB, probably about 500GB once indexes and overhead are considered. This is not big by modern standards. Data compression or a columnstore would help here, but IIRC PostgreSQL does not provide either out of the box.

It would be possible to reduce the amount of storage at the cost of additional writes. Rather than store the individual user/ post receipts store a post/ userid range i.e.

Post A has been read by users 1 through 10
Post A has been read by users 11 through 11
Post A has been read by users 45 through 78


As new receipts arrive existing ranges can be extended, merged or inserted. Assuming receipts arrive in random order, the number of rows will increase (to at worst COUNT(users)/2 before reducing toward 1 as rows merge). I have a nasty feeling that this would be polynomial in IO, however, something like O(Nx).

If UserIDs are allocated without gaps the checks are easier. In the real world there are likely to be gaps and there will be a lot of look-ups on the user table to see if two receipt ranges can be merged.

The above is symmetrical for "user has read post x through y" and also read vs unread.



Having thought it through some more, I think the algoritm is actually O(log N). For each message receipt the algorithm will have to read where that message lies in the current log and UPDATE, INSERT or DELETE as appropriate. Assuming a BTree index exists these are O(log N) operations (even though there may be several operations per read receipt).

In the best case scenario read receipts would arrive in exactly primary key sequence (massively unlikely). Then the logging table would only ever have one row. In worst case read receipts would arrive in alternate sequece e.g. all the odd numbered keys followed by all the even numbered keys. This will cause the log table to grow to 50% of the number of posts sent.

A rough prototype with read recipts arriving in random sequence saw the logging table grow to a maximum of 25% of the number or posts. So for a sample of one million posts the log table would start with a single row; this would grow to about 250,000 rows; and then shrink to zero rows when the last read receipt was processed. This was consistent across several orders of magnitude.  Some day I'll sit and work out the maths of why this should be so, but not today.