Comment by simonw | Hacker News Reader

Comment by simonw | Hacker News Reader

Parent Full thread

There's a flaw in this bit, which leads to the 530 million account estimate:

"The highest Twitter user id when I started the experiment was around 637M (found by trial and error). I figured there would be gaps in user ids mostly because of massive deletions of spammer accounts, and a quick sample estimated the gaps to be on the order of 20%. So I generated 1.25M unique user ids in the range 0-637M, and tried to fetch the profile details for them.

[...]

After fetching the 12,500 batches I was left with 1,039,556 Twitter profiles. This means that there must exist approximately 530 million Twitter accounts: 83% of 637M."

The problem is that Twitter account IDs used to be sequential - every integer would correspond to an account, unless that account had been deleted. Then in 2011 Twitter introduced the Snowflake update https://dev.twitter.com/docs/twitter-ids-json-and-snowflake which changed the way IDs were generated (for scaling reasons - it's much better to have separate machines able to deal out IDs rather than rely on a single point of failure).

This means that if you were to create a pool of random IDs between 1 and 637,000,000 you'll find that the IDs below a certain number (the highest ID at the time snowflake kicked in) almost all correspond to an account, whereas the IDs above that number have a much higher number of misses.

Good catch. I just checked the data. The effect of Snowflake is not too high, the error in the estimate because of this is perhaps 10M to 20M accounts. It's almost in the noise considering Twitter's daily signup rate. Also, it may even offset the fact that Twitter wouldn't return accounts created in the past ten days through the API.

Can you explain what it means to "check the data"? The point here is that, for the last year, Twitter has NOT been generating sequential IDs. Just look at the source code[1]. They save a few low bits for the worker ID, data center, and worker-specific sequence. The highest bits are the timestamp bits.

Maybe you can correct me if my assumptions based on the code are wrong, but my guess is you'll magically find that Twitter's highest ID grows linearly with time. Then you're just randomly sampling within this maximum timestamp. At this point you're assuming that Twitter sees a constant rate of signups wrt time, which I highly doubt.

[1] https://github.com/twitter/snowflake/blob/master/src/main/sc...

What I did was to measure the difference in yield between uniformly generated ids that would correspond to the time after Snowflake (when ids were at 380M) and the ones before. It's true that the yield is less. It went down from about 86% to 82%.

A separate problem is that my estimate of the highest id at the time of the experiment likely fell short. Since then I've encountered higher ids that are pretty sparse, but I don't know how many there are.

Do you have any ideas as to how to generate a better sequence of random ids that tracks Twitter ids after Snowflake? I'd like to redo this experiment in a while.

As far as I know, Snowflake is used to generate tweet IDs. Do you have any reason to believe that it's being used to generate user IDs?

As evidence against this, note that the ID density currently being produced for tweets is very, very low: when I collect from the sprinkler, I rarely get a tweet ID where the sequence number portion is much higher than 2 or 3. That is, almost all of the 12 bits of sequence number are 0, almost all the time. So the ID density for tweets is well under 1%. (And the sampling method Twitter is using to produce the sprinkler doesn't have an effect here, as far as I can work out.)

If Snowflake were being used to generate user IDs, I'd expect even lower ID densities. This doesn't jibe at all with 86% (or 82%) or anywhere close to it.

Reply on news.ycombinator.com