Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

View Counting at Reddit

redditblog.com

Post reply on HN
Print view View original

81–90 of 121 posts

Re: View Counting at Reddit

#81

Post by twotwotwo »

haburka wrote: post #9

I 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? Tha…

For outliers by random chance, lucasschm's reply explains.

The usual trick for preventing folks _maliciously_ sending in outliers is to use a hash with a secret key such as SipHash so that folks on the outside can't trivially figure out what inputs will lead to hashes with a lot of leading zeroes.

Re: View Counting at Reddit

#82

Post by sverhagen »

kondor6c wrote: post #5
tsukaisute wrote: post #3

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. Again, you get 3. Seems like a replication issue?

I believe they are using cassandra to store the upvotes

Just 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?

Re: View Counting at Reddit

#83

Post by stevenh »

nyar wrote: post #65

"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.

Suppose there's a comment with 12 upvotes and 207 downvotes. Now suppose you're reddit and you want to make this comment seem more popular than it actually is.

You could slowly remove the downvotes, but attentive people refreshing the page will see the number shrinking and become suspicious, because real users never suddenly do a mass retraction of their votes.

You could slowly add a bunch of upvotes, but then people will wonder why this comment with a consistent 12/207 popularity ratio for the past hour suddenly overcame it and became the most popular comment in the thread. People will suspect a coordinated raid took place.

Both approaches raise too much suspicion. The safest approach is to turn off the ability to view the separate upvote/downvote values altogether and use a simple easing function to artificially increase the comment's total score over time. When no one can see the upvote/downvote ratio or the volume of vote activity over time, they lose the ability to judge whether manipulation is taking place.

You need an excuse for the change, so don't forget to also come up with a spurious narrative about how it was supposedly done to fight bots.

Re: View Counting at Reddit

#84

Post by tudorconstantin »

gniv wrote: post #73
tudorconstantin wrote: post #14

Wouldn'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

That might work, but the cookie would be huge for people who read a lot of reddit threads, no?

That depends on their definition of 'short lived'.

How many posts can a user visit in, lets say, an hour?

They said they want to avoid increasing the views when a user refreshes the page in a short interval

Re: View Counting at Reddit

#85

Post by jimmaswell »

eropple wrote: post #68
jimmaswell wrote: post #64

Earlier quoted context omitted.

Why 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.

Have you stopped to think how many users that is and how many posts? Viewing a single thread could require five hundred associations.

And it already requires reading five hundred comments.

Re: View Counting at Reddit

#86

Post by andreareina »

Lukassus wrote: post #16
haburka wrote: post #9

I 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? Tha…

The 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-again...

The 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.

Re: View Counting at Reddit

#87

Post by andreareina »

noamhacker wrote: post #28

How do you test a system like this for accuracy? Is this done by simulating millions of unique requests?

The 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

Re: View Counting at Reddit

#88

Post by tudorconstantin »

frenchie14 wrote: post #51
tudorconstantin wrote: post #14

Wouldn'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

A browser cookie that can be trivially deleted by the client? What's the purpose of the cookie?

Indeed it can easily be deleted, that's why I said to put the spam detection before the counter.

I assume most of the visits are from normal users, not spammers, so if a normal user has the cookie for the post set then it means it's a page refresh, so don't increase the counter.

Identifying sophisticated spammers accurately is more complicated though. You can't rely on any client side info (user agent, cookies, browser history, screen resolution, OS, etc) because they can all be modified. You can't rely on IP address either, because there are public hotspots used by genuine users also. I think their spam detector is more complicated than this and they have to use it for HLL also.

So, for the genuine users, a counter increased based on the cookie mechanism would've worked just fine.

Re: View Counting at Reddit

#89

Post by ketralnis »

sverhagen wrote: post #82
kondor6c wrote: post #5

Earlier quoted context omitted.

I believe they are using cassandra to store the upvotes

Just 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?

Cassandra 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

Re: View Counting at Reddit

#90

Post by [deleted] »

nowarninglabel wrote: post #80
jliptzin wrote: post #78

Earlier quoted context omitted.

Can't you just delay updating the count by some random number of minutes/hours?

That 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]
Post reply on HN