8 ms·
View Counting at Reddit
- fiatjaf 9y agoAt https://trackingco.de/ https://trackingco.de/ we store events on Redis and compile them daily into a reduced string format, storing these on CouchDB.
- tsukaisute 9y agoWeird thing I have been seeing on Reddit is comment upvotes being off-by-one periodically on page refreshes. Reload, you get 3. Reload again, you get 4. Again, you get 3. Seems like a replication issue?
- kondor6c 9y agoI believe they are using cassandra to store the upvotes
- ketralnis 9y agoThat one is in postgres
- sverhagen 9y agoJust curious if this is a stab at Cassandra, or whether use of Cassandra would automatically imply eventual consistency or something else that would appear in this way?
- ketralnis 9y agoCassandra as it's often used can imply eventual consistency (e.g. counter incrs with CL.ONE) but "eventual" in this case would be in the range of 10's of ms That said, reddit's upvote counters in particular are stored in Postgres, not Cassandra
- kelnage 9y ago> Weird thing I have been seeing on Reddit is comment upvotes being off-by-one periodically on page refreshes. Reload, you get 3. Reload again, you get 4. Reload, you get 3. Seems like a replication issue? This is done on purpose [1], to prevent bots from calculating exact post/comment scores. 1. https://www.reddit.com/wiki/faq#wiki_how_is_a_comment.27s_score_determined.3F https://www.reddit.com/wiki/faq#wiki_how_is_a_comment.27s_sc...
- Xeoncross 9y agoI still don't understand what purpose this feature has - can you explain more?
- Gaelan 9y agoA votebot suspects that it is being detected and filtered out of the final scores. Because the scores fluctuate, it is harder to determine if your vote had an impact.
- wordupmaking 9y agoBut that doesn't "prevent spambots etc.", that merely prevents people from easily and instantly figuring out whether their bots are detected yet. It doesn't stop them from spamming votes, or from making their bots more elaborate regardless of whether they have been detected yet. I don't know all the motivations for spam bots or how people who make them tick, but I'd figure for a significant number the crucial bit is having an impact, not measuring it. Most spam is fire and forget, after all.
- sanswork 9y agoThe point isn't to prevent them which is near on impossible but to get them to waste enough resources on non-visible actions regularly enough that it isn't economically viable to continue trying to spam the site.
- 9y ago
- samtho 9y agoThat's vote fuzzing you're seeing. It's to prevent people (read: bots) from being able to tell if they are shadowbanned.
- hellbanner 9y agoSlightly OT; but I wish reddit would use traditional forum style replies to push threads up, instead of the positive feedback loop of votes with opinions that agree with majority getting upvotes giving views which give proportionally more upvotes
- rjaco31 9y agoIt might be conceivable on smaller subreddits, but on the big ones it would basically just drown everything into a sea of low-quality threads. I got the feeling that the vast majority of threads never ever make it to the "front page" of their subreddit.
- hellbanner 9y agoHm good points..
- sotojuan 9y ago> but on the big ones it would basically just drown everything into a sea of low-quality threads The big subreddits' comment sections is largely low quality anyway. Traditional forums have their downsides (anyone remember super nested quote trains?), but I still find them superior to upvote + nested replies. The best forum UI for me, though, are imageboards. Too bad they are associated with a less than popular community.
- johnfn 9y agoTraditional forum style sorting just sorts for controversiality. Posts that generate heated discussion will continue to push their way to the top. This is okay but it means that non controversial stories will not make it to the top, which is honestly one of the largest benefits of news aggregator sites.
- wordupmaking 9y agoHow about, here and on reddit, being able to mark threads you're interested in, and having a page where you can see those sorted by last reply. On HN, make that page refresh every 15 or 60 minutes or whatever. Heck, once every 24 hours would be enough... sometimes I just want to talk about the things that interest me, with the people that are interested in them. I would love to be able to think on something for a few days, or to familiarize myself with a subject before mouthing off. As they are now, reddit and HN are require you to be there when something is "current", and that's ultimately not that much better than TV. Yeah, sometimes you can get something out of it, but it's nowhere near as useful or deep. Even worse, there is a tendency to get semi- or unrelated stuff one out when something slightly similar is discussed, instead of putting things exactly where they "belong", where they add to a useful corpus. [which is exactly what I'm doing right now, and am doing too often.. but I honestly would prefer the alternative which doesn't exist yet] Just think about it, we have practically infinite storage, there's certainly plenty of expertise in reach of HN -- yet discussions get constantly restrained because our attention is limited. But it's limited because all we get are these flat lists, X items per page, next to no means to curate or organize anything. Imagine how much worse it would be without people who sometimes link to old but very relevant and insightful stories or individual comments. I'm very grateful to them, but to take them for granted, to rely on them for "structure" is totally stone age to me. Give us tools, give us transparency, let us figure out things even if they might be hard - stop trying to hand hold people you might underestimate! We don't need you as much as you need us.
- haburka 9y agoI love the article on hyperloglog! It is really quite good to read even if you're not interested in algorithms. I always liked number theory and I think that it's very interesting that you can guess how many uniques there are by counting how long your longest run of zeroes in a hash is. I suppose this could be broken by injecting in a unique visitor id that would hash to something with an absurd amount of zeroes? That's assuming that the user has control over their user id and that I'm understanding the algorithm correctly.
- Lukassus 9y agoThe HyperLogLog was a very nice article, but I wanted to ask, is this related to the estimation of Naci tanks during WW2 by Allies? https://www.wired.com/2010/10/how-the-allies-used-math-against-german-tanks/ https://www.wired.com/2010/10/how-the-allies-used-math-again...
- andreareina 9y agoThe German Tank Problem guesses the size of a set, given a limited sample and successive serial numbers. If they had randomized the serial numbers it wouldn't have worked. HyperLogLog is different because you have the entire population (not just a sample), and it's a multiset (the same element can appear more than once). Getting the size of a (non-multi) set is easy, you just keep a counter and increment it for each element; it only takes enough memory to maintain the counter. Counting the distinct members of a multiset takes a lot more memory because you have to remember whether you've already seen a particular element or not. The tl;dr is that the German Tank Problem is about making an estimate of size when you have imperfect information, and HyperLogLog gives you an estimate when you have perfect information, but it's too expensive to make an exact calculation.
- lucasschm 9y agoYou are correct, but HyperLogLog has many buckets counting the longest run of zeros in order to avoid the problem of outliers. I recently studied these probabilistic algorithms and did a notebook with code and plots to show their performance: https://github.com/lucasschmidtc/Probabilistic-Algorithms/blob/master/Probabilistic%20Algorithms.ipynb https://github.com/lucasschmidtc/Probabilistic-Algorithms/bl...
- qrbLPHiKpiux 9y agoNot applied to /r/the_donald however.
- hellbanner 9y agoI didn't see this in the article
- hexane360 9y agoAre you talking about the "impressions"/subscribers incident? Because that was a mislabeled field that affected almost every other sub more than T_d. https://www.reddit.com/r/help/comments/62naj4/can_someone_explain_why_there_is_such_a/dfnvegl/ https://www.reddit.com/r/help/comments/62naj4/can_someone_ex... https://www.reddit.com/r/SubredditDrama/comments/62nw33/rthe_donald_thinks_it_has_discovered_evidence/dfo220k/ https://www.reddit.com/r/SubredditDrama/comments/62nw33/rthe...
- superioritycplx 9y agoThere are simply too many incidents to name. They keep changing the algorithm to suppress the subreddit, sometimes failing in an epic fashion, like that time when r/all was showing only T_D posts for an hour.
- tudorconstantin 9y agoWouldn't it had been easier to simply increment a counter for each visit and then set a short lived cookie in the browser for that post? And put the spam detection system before the counter increment
- deleted 9y ago[deleted]
- bognition 9y agoHow do you concurrently update a counter?
- BillinghamJ 9y agoRedis writes are atomic - you just use the increment function
- bognition 9y agoWrites are atomic in redis because redis is single threaded. So you are bounded by how fast redis can write. If you try to write any faster then redis can handle you'll get queueing or errors.
- btmorex 9y agoRun enough redis servers to handle the load. Choose a server by hashing a user id. Total = sum of counts from all servers.
- deleted 9y ago[deleted]
- antirez 9y agoThe wonderful thing about HyperLogLogs is that you can split the counter in N servers and "merge" the registers later, in case you want an architecture that shards the same counter in multiple servers. But sharding directly by resource looks simpler actually...
- stoicking 9y agoGiven how much simpler it is to count total views than unique user views, why is it more valuable to count unique user views?
- danso 9y agoBecause it's more valuable of a data point to those who care about overall audience and reach. Someone visiting repeatedly might be evidence of an engaged user, but things like ads would have diminishing returns.
- Namrog84 9y agoPossibly to combat bots or artificially inflated view statistics?
- jonathanbull 9y agoFrom a Reddit engineer: "This was a product decision. Currently view counts are purely cosmetic, but we did not want to rule out the possibility of them being used in ranking in the future. As such, building in some degree of abuse protection made sense (e.g. someone can't just sit on a page refreshing to make the view number go up). I am fully expecting us to tweak this time window (and the duplication heuristics in general) in future, especially as the way that users interact with content will change as Reddit evolves." https://www.reddit.com/r/programming/comments/6da6n9/comment/di12fd2?st=J37U6ZXI&sh=1b5c2a56 https://www.reddit.com/r/programming/comments/6da6n9/comment...
- Splendor 9y agoBecause it's a metric advertisers care about.
- noamhacker 9y agoHow do you test a system like this for accuracy? Is this done by simulating millions of unique requests?
- icelancer 9y agoCan't you just use Apache Benchmark and some proxies?
- GhostVII 9y agoReddit probably has enough analytics to be able to show mathematically that it will be accurate without simulating any requests.
- andreareina 9y agoThe algorithm's accuracy is known. From the wiki[1]: The HyperLogLog algorithm is able to estimate cardinalities of > 10^9 with a typical error rate of 2% [1] https://en.wikipedia.org/wiki/HyperLogLog https://en.wikipedia.org/wiki/HyperLogLog
- federicoponzi 9y agoBut what about the implementation accuracy? :)
- zeroxfe 9y agoTests against both historical and synthetic datasets.
- ugh123 9y agoForgive my ignorance, but isn't this what Google Analytics is for?
- 659087 9y agoGoogle Analytics is for giving Google the ability to track your users.
- ckarmann 9y agoThat would not help to prevent illegitimate views like those generated by spambots.
- PetahNZ 9y agoGoogle Analytics is not accurate (its sampled), or realtime (48 hour turn around).
- raquo 9y ago^ For big sites like reddit, which is why you don't typically run into this when using GA on your personal blog
- hashhar 9y agoIt uses sampling to generate reports AFAIK.
- alzaeem 9y agoSo how do they determine whether a user has viewed a post already? I would think that unique counting is accomplished using the hyperloglog counter, but the article says that this decision is made by the Nazar system, which doesn't use the hyperloglog counter in Redis.
- hrshtr 9y agoThats true, I am thinking that Nazar is more like spam filter and monitors the user behavior.
- kchandra 9y agoPretty much, yeah.
- lucasschm 9y agoBloom Filters? It has false positives but no false negatives
- jimmaswell 9y agoWhy can't they just associate a list of viewed posts with each user, or list of users that viewed a post with each post, and check that? I don't get why this needs any consideration.
- eropple 9y agoHave you stopped to think how many users that is and how many posts? Viewing a single thread could require five hundred associations.
- jimmaswell 9y agoAnd it already requires reading five hundred comments.
- sethammons 9y agoThey addressed your second point in the article. On a popular post, you would be storing several megabytes of data to capture/relate each unique user that visited. That gets expensive at scale. HLL takes then down to a few kilobytes, less than 1% of the original size. For your first suggestion, you would have to do a very expensive look up. You couldn't cache it effectively due to the requirement of near real time stats. You could improve look up time using columnar storage, but the performance and memory usage will be nowhere near as nice as with HLL. Problems are harder at scale.
- alzaeem 9y agoSo how do they determine whether a user has viewed a post already? I would think that unique counting is accomplished using the hyperloglog counter, but the article says that this decision is made by the Nazar system, which doesn't use the hyperloglog counter in Redis.
- nyar 9y ago"We want to better communicate the scale of Reddit to our users." If that's true why did they hide vote numbers on comments and posts? It used to say "xxx upvotes xxx downvotes" now it just gives a number and hides that.
- jonknee 9y agoIt's to deter bots. The numbers weren't previously accurate, they were fuzzed (also to deter bots). https://www.reddit.com/wiki/faq#wiki_how_is_a_submission.27s_score_determined.3F https://www.reddit.com/wiki/faq#wiki_how_is_a_submission.27s...
- ma2rten 9y agoI don't quite see the connection. How exactly does this deter bots?
- Klathmon 9y agoIt's difficult to see if their votes are counting, allowing Reddit to silently-ignore their votes without them knowing.
- jliptzin 9y agoCan't you just delay updating the count by some random number of minutes/hours?
- nowarninglabel 9y agoThat be easy to test though if you were bot was effective or not, just post to unpopular subreddits, make bot votes on those submissions, then check back the next day. If votes not counted, then your bot is being ignored and you'd move on to changing your IP address or building your next bot or such.
- deleted 9y ago
- federicoponzi 9y agoProbably noob question, but: >> Nazar will then alter the event, adding a Boolean flag indicating whether or not it should be counted, before sending the event back to Kafka. Why don't they just discard it instead of reputting the event back to Kafka?
- bashtoni 9y agoI suspect they archive events into S3 or similar for later analysis/training.
- golergka 9y agoA beautiful example of how a feature that seems so easy to an end user can be complex at scale.
- TempleOS 9y agoTher CIA is at war with God. Every rtime I see the CIA attack God, I run to the battle. I stand with pedophiles. It is actually atheist attacking God. When I am king we will execute the entire CIA. they started a war on God and will all die. God says... pathogenic aphelia necklace's Randolph's philosophy Khoikhoi chairmen bonitoes hamburger postscript's bathrobe's warmonger's theorem slows louver shellac meander's guinea vertices choreographed demarcate disrepair's topsails sandwich's updated choose pianos inextricable Numbers's minestrone lecher's Mujib's
- theomega 9y agoVery interesting article, thanks for publishing. I have two related questions: 1. I assume the process which reads from Cassandra and puts it back to Redis is parallized if not even distributed. How do you ensure correctness? Implementing 2PC seems extreme overhead. Or do you lock in Redis? 2. What database is used to actually store the view counts? Cassandras Counters are afaik not very reliable...
- kchandra 9y ago1. Redis is atomic, so we use the SETNX operation to ensure that only one write succeeds. 2. We have HLLs in Redis, so we just issue a PFCOUNT and store the result of that in Cassandra as an integer value. We don't use counters in Cassandra.
- ronalbarbaren 9y agoThanks Reddit guys. I hope engineer of Youtube will post similar article. Still curious how Youtube count.
- mxmxm 9y agoCounting views/impressions in combination with Apache Kafka sounds like the ideal use case for a stream processor like Apache Flink. It supports very large state which can be managed off-hand. This should enable you to count the exact number of unique views in real time with exactly once semantics. Here is a blog post on large scale counting with more details. It also includes a comparison with other streaming technologies like Sanza and Spark: https://data-artisans.com/blog/counting-in-streams-a-hierarchy-of-needs https://data-artisans.com/blog/counting-in-streams-a-hierarc... Also check out this blog post by a Twitter engineer on counting ad impressions: https://data-artisans.com/blog/extending-the-yahoo-streaming-benchmark https://data-artisans.com/blog/extending-the-yahoo-streaming...