4 ms·

>A list of votes per user per page would also work. 90% of the time that list would be empty, if it's not your likely going to eventually need to know which spe

by zardeh 10y ago

>A list of votes per user per page would also work. 90% of the time that list would be empty, if it's not your likely going to eventually need to know which specific items where voted on so might as well just load them all. How? This means you're now duplicating data, instead of organizing as page has comments have comments have ... have votes you now have page has comments have comments have ... have votes page has list of special comments where you don't know where they are or what their parental hierarchy is and still need to look up in the list anyway. you're duplicating the "has been voted on" field.

Retric 10y ago
> How? Page has a list of people who have voted, and that list points to a list of their votes. Each comment has a a number for vote counts, but not a list of scores. User opens page, they get a list of comments with scores. And a possibly empty list of votes. 99.9% is probably less than 20 votes from that user so 160 bytes or less. Worst case is what 8 byte comment ID * 1,000 up-votes = 8k. On user vote, server looks at past votes on page and adds it if missing then updates comment score. Ok, you need every vote from each user and caching comment scores is really likely a no brainier, but I guess you could recalculate it. PS: Not all comments are going to be loaded, but again if your sending <200 bytes for the full list 99.9% of the time then doing something else has limited value.
- zardeh 10y ago
  But that requires like entirely rearchitecting the reddit backend to be less efficient. A page has comments a comment has comments a comment has votes a vote has a user That is to say that a vote is a many to many join from user-comment. To do what you want, you'd also have to give the page the concept of "people who have voted on a comment that belongs to be or one of my children" >User opens page, they get a list of comments with scores. And a possibly empty list of votes. 99.9% is probably less than 20 votes from that user so 160 bytes or less. Worst case is what 8 byte comment ID * 1,000 up-votes = 8k. The problem isn't sending additional data over the wire, its that, say I've voted on 500 things on a page, then we're at 250,000 operations (for each comment check if its in my list of voted on comments), whereas a bloom implementation is O(n). And also the whole making your database structure repetative and icky.
  - Retric 10y ago
    In your approach comments have votes the server must check the bloom filter for each comment then do a fetch for each match in the case of 500 votes that's 500 fetches which are at least votes * (log comments votes) because you can't trust the filter. My approach that's client side most of the time. Further it's O (n) to compare matches between two sorted lists so just sort them in O (n log n). Further log 500 is faster than most hashes. And of course for the most common case of no votes it's a single lookup and done. PS: As to changing the back end, yes if the initial implementation is bad then you might have a point. But, again fixing the problem also works and produces far less code to maintain.

by zardeh 10y ago

Retric 10y ago

> How? Page has a list of people who have voted, and that list points to a list of their votes. Each comment has a a number for vote counts, but not a list of scores. User opens page, they get a list of comments with scores. And a possibly empty list of votes. 99.9% is probably less than 20 votes from that user so 160 bytes or less. Worst case is what 8 byte comment ID * 1,000 up-votes = 8k. On user vote, server looks at past votes on page and adds it if missing then updates comment score. Ok, you need every vote from each user and caching comment scores is really likely a no brainier, but I guess you could recalculate it. PS: Not all comments are going to be loaded, but again if your sending <200 bytes for the full list 99.9% of the time then doing something else has limited value.

zardeh 10y ago
But that requires like entirely rearchitecting the reddit backend to be less efficient. A page has comments a comment has comments a comment has votes a vote has a user That is to say that a vote is a many to many join from user-comment. To do what you want, you'd also have to give the page the concept of "people who have voted on a comment that belongs to be or one of my children" >User opens page, they get a list of comments with scores. And a possibly empty list of votes. 99.9% is probably less than 20 votes from that user so 160 bytes or less. Worst case is what 8 byte comment ID * 1,000 up-votes = 8k. The problem isn't sending additional data over the wire, its that, say I've voted on 500 things on a page, then we're at 250,000 operations (for each comment check if its in my list of voted on comments), whereas a bloom implementation is O(n). And also the whole making your database structure repetative and icky.
- Retric 10y ago
  In your approach comments have votes the server must check the bloom filter for each comment then do a fetch for each match in the case of 500 votes that's 500 fetches which are at least votes * (log comments votes) because you can't trust the filter. My approach that's client side most of the time. Further it's O (n) to compare matches between two sorted lists so just sort them in O (n log n). Further log 500 is faster than most hashes. And of course for the most common case of no votes it's a single lookup and done. PS: As to changing the back end, yes if the initial implementation is bad then you might have a point. But, again fixing the problem also works and produces far less code to maintain.