6 ms·

A long time ago we discovered Twitter used a round robin of three servers for assigning IDs to tweets. We inferred the round robin was done by doing mod 3 of a

by madrox 4y ago

A long time ago we discovered Twitter used a round robin of three servers for assigning IDs to tweets. We inferred the round robin was done by doing mod 3 of a signed int32, and because that space doesn't divide neatly by two it meant one of the three servers saw less load than the others and we could map ID assignment volume according to how often it overflowed and hence estimate total tweet volume for a given period. Some of the details escape me (this was a decade ago) but it was a fun combination of statistical inference and CS knowledge that I don't get to use often. Whenever integer overflow comes up in a systems engineering context I get a little tickled.

_3u10 4y ago
If they were incrementing and modding wouldn’t that server see an extra 1/2 billionth more traffic? I don’t get how mod 3 affects anything if you’re just incrementing…
vecter 4y ago
Wouldn't that unevenness only affect 2^31 - 2 and 2^31 - 1, so a negligible fraction of the integers? Was that tiny discrepancy enough to make your calculations? In other words, what do you mean that it was done by doing mod 3 of a signed int32? If it was a monotonically increasing or random int32, I don't see how that unevenness would manifest in a meaningful way.
- madrox 4y ago
  In another subthread, we realized my memory was wrong and we were measuring millisecond collisions. The serving ID imbalance was a side-effect. Also, it might've been an int16 I was thinking of but turns out the whole thing was shadows on cave walls.
pedrovhb 4y ago
That's really neat, I'd love to hear more about it. Was this something you were actively trying to find out, or was it poking around until something caught your eye?
- kypro 4y ago
  Not op, but at an ecommerce company I worked for we did similar things to track how well our competitors were doing relative to us so could be something like that. Also collecting data like this can be useful if you want to beat markets.
- madrox 4y ago
  A little of both. I was working in social media analytics, and we were collecting everything we could to understand how to communicate the value of this new medium to businesses who could use twitter for marketing. This was still in an era where privacy wasn't at the front of anyone's minds, so there were zero retention policies. Hard to believe that was only 10 years ago. Eventually, we learned to treat Twitter as a lead generation tool for off-platform activity and apply old school funnel mechanics to it. The next problem became how to build a follower count. Sadly, that problem is what I think led to extremism on the platform. Hence: https://madrox.substack.com/p/yet-another-quitting-twitter https://madrox.substack.com/p/yet-another-quitting-twitter
mashygpig 4y ago
Maybe a dumb question, but I don’t follow what you mean by “the space doesn’t divide neatly by two” and also how that connects with overflowing ints. Asking because I’m genuinely curious and would like to know more about this. Sounds really neat!
liquidgecka 4y ago
I am pretty sure that snowflake didn't use a mod of a signed int32. It used a service discovery pool as part of finagle (and prior to that dns iirc). The server used a very simple method internally to convert time into a integer (that was 52 bits because of javascript). In fact it was completely open source: https://blog.twitter.com/engineering/en_us/a/2010/announcing-snowflake https://blog.twitter.com/engineering/en_us/a/2010/announcing... The integer generation was pretty simple, there was a fixed id of each server, and unless I a mistaken we have 5 servers per datacenter. Each id was basically <time><offset><id> where time was a millisecond timer, offset was the number of ids generated in that same millisecond by the same server, and id was the machines unique identifier. When we first talked about this process I thought that offset was going to roll, every id would increment it by one. This was changed to resetting it every millisecond specifically so that it would obscure tweet volumes. At the time I remember reading a LOT of articles estimating tweet volume and most of them were way, way off. I don't know that we ever really put effort into correcting them though. =) * - Does not account for changes in the system post 2012.
- duskwuff 4y ago
  Twitter didn't always use Snowflake -- that was introduced in November 2010. There was another, much simpler algorithm used before that which generated much smaller IDs (e.g. under 3e10).
  - liquidgecka 4y ago
    Yea.. "auto increment" in mysql. it SUCKED in so many ways, primary of which was that it required a single mysql database to be the primary for all tweet writes. Every tweet just incremented a counter by 1. As we scaled up that server got overloaded rapidly and became a huge single point of failure. Snowflake was introduced to solve several problems at once. =)
- madrox 4y ago
  Awesome to hear from someone on the other side of the API with knowledge of this. This is ringing bells for me. Yeah, the id parameter was how we knew how many servers there were, and we saw more assignment in some servers than others that neatly mapped to a int32 max failing to divide by the number of IDs we saw. I thought I recall Twitter confirming that was how round robin happened but I could be totally misremembering. We never got a contact to talk to Twitter about it. FWIW, we did eventually see this fixed. I imagine it was pretty easy to spot one server seeing less load than others. The offset was actually how we calculated volume, because millisecond collisions become a variant of the german tank problem[1]. A few times when y'all made tweet volumes public it mapped pretty closely with our estimates. This was around 2011, so your knowledge should be relevant. 1: https://en.wikipedia.org/wiki/German_tank_problem https://en.wikipedia.org/wiki/German_tank_problem
manigandham 4y ago
If it’s round robin then it should be an even load, how does the modulo change that exactly? Also what number are they using to modulo and where is that happening? Because at that point don’t they already have an incrementing ID before generating another one?
- andreareina 4y ago
  Take a 3-bit counter: 0->A 1->B 2->C 3->A 4->B 5->C 6->A 7->B A and B get hit three times while C only twice, so it will see 66% utilization compared to A and B EDITED s/once/twice/ thanks CyberDildonics
  - CyberDildonics 4y ago
    while C only once You listed C twice
    - woodruffw 4y ago
      That's a typo. You can still see they're correct about the ratio (two "C"s for every three "A"s and "B"s).
      - manigandham 4y ago
        There's no ratio. It's even across all of them, as long as the integer keeps incrementing. One more number (9) instead of stopping at 8 and there would be an even spread.
        ahmedtd 4y ago
        Not when the counter overflows back to 0. If it's a 3 bit counter, 0 is A again, not C.
        manigandham 4y ago
        The comment says a 32-bit signed int. Where is the 3-bit assumption coming from?
ipqk 4y ago
Reminds me of the self-quoting tweet: https://news.ycombinator.com/item?id=25244872 https://news.ycombinator.com/item?id=25244872

by madrox 4y ago

_3u10 4y ago

If they were incrementing and modding wouldn’t that server see an extra 1/2 billionth more traffic? I don’t get how mod 3 affects anything if you’re just incrementing…

vecter 4y ago

Wouldn't that unevenness only affect 2^31 - 2 and 2^31 - 1, so a negligible fraction of the integers? Was that tiny discrepancy enough to make your calculations? In other words, what do you mean that it was done by doing mod 3 of a signed int32? If it was a monotonically increasing or random int32, I don't see how that unevenness would manifest in a meaningful way.

madrox 4y ago
In another subthread, we realized my memory was wrong and we were measuring millisecond collisions. The serving ID imbalance was a side-effect. Also, it might've been an int16 I was thinking of but turns out the whole thing was shadows on cave walls.

pedrovhb 4y ago

That's really neat, I'd love to hear more about it. Was this something you were actively trying to find out, or was it poking around until something caught your eye?

kypro 4y ago
Not op, but at an ecommerce company I worked for we did similar things to track how well our competitors were doing relative to us so could be something like that. Also collecting data like this can be useful if you want to beat markets.
madrox 4y ago
A little of both. I was working in social media analytics, and we were collecting everything we could to understand how to communicate the value of this new medium to businesses who could use twitter for marketing. This was still in an era where privacy wasn't at the front of anyone's minds, so there were zero retention policies. Hard to believe that was only 10 years ago. Eventually, we learned to treat Twitter as a lead generation tool for off-platform activity and apply old school funnel mechanics to it. The next problem became how to build a follower count. Sadly, that problem is what I think led to extremism on the platform. Hence: https://madrox.substack.com/p/yet-another-quitting-twitter https://madrox.substack.com/p/yet-another-quitting-twitter

mashygpig 4y ago

Maybe a dumb question, but I don’t follow what you mean by “the space doesn’t divide neatly by two” and also how that connects with overflowing ints. Asking because I’m genuinely curious and would like to know more about this. Sounds really neat!

liquidgecka 4y ago

I am pretty sure that snowflake didn't use a mod of a signed int32. It used a service discovery pool as part of finagle (and prior to that dns iirc). The server used a very simple method internally to convert time into a integer (that was 52 bits because of javascript). In fact it was completely open source: https://blog.twitter.com/engineering/en_us/a/2010/announcing-snowflake https://blog.twitter.com/engineering/en_us/a/2010/announcing... The integer generation was pretty simple, there was a fixed id of each server, and unless I a mistaken we have 5 servers per datacenter. Each id was basically <time><offset><id> where time was a millisecond timer, offset was the number of ids generated in that same millisecond by the same server, and id was the machines unique identifier. When we first talked about this process I thought that offset was going to roll, every id would increment it by one. This was changed to resetting it every millisecond specifically so that it would obscure tweet volumes. At the time I remember reading a LOT of articles estimating tweet volume and most of them were way, way off. I don't know that we ever really put effort into correcting them though. =) * - Does not account for changes in the system post 2012.

duskwuff 4y ago
Twitter didn't always use Snowflake -- that was introduced in November 2010. There was another, much simpler algorithm used before that which generated much smaller IDs (e.g. under 3e10).
- liquidgecka 4y ago
  Yea.. "auto increment" in mysql. it SUCKED in so many ways, primary of which was that it required a single mysql database to be the primary for all tweet writes. Every tweet just incremented a counter by 1. As we scaled up that server got overloaded rapidly and became a huge single point of failure. Snowflake was introduced to solve several problems at once. =)
madrox 4y ago
Awesome to hear from someone on the other side of the API with knowledge of this. This is ringing bells for me. Yeah, the id parameter was how we knew how many servers there were, and we saw more assignment in some servers than others that neatly mapped to a int32 max failing to divide by the number of IDs we saw. I thought I recall Twitter confirming that was how round robin happened but I could be totally misremembering. We never got a contact to talk to Twitter about it. FWIW, we did eventually see this fixed. I imagine it was pretty easy to spot one server seeing less load than others. The offset was actually how we calculated volume, because millisecond collisions become a variant of the german tank problem[1]. A few times when y'all made tweet volumes public it mapped pretty closely with our estimates. This was around 2011, so your knowledge should be relevant. 1: https://en.wikipedia.org/wiki/German_tank_problem https://en.wikipedia.org/wiki/German_tank_problem

manigandham 4y ago

If it’s round robin then it should be an even load, how does the modulo change that exactly? Also what number are they using to modulo and where is that happening? Because at that point don’t they already have an incrementing ID before generating another one?

andreareina 4y ago
Take a 3-bit counter: 0->A 1->B 2->C 3->A 4->B 5->C 6->A 7->B A and B get hit three times while C only twice, so it will see 66% utilization compared to A and B EDITED s/once/twice/ thanks CyberDildonics
- CyberDildonics 4y ago
  while C only once You listed C twice
  - woodruffw 4y ago
    That's a typo. You can still see they're correct about the ratio (two "C"s for every three "A"s and "B"s).
    - manigandham 4y ago
      There's no ratio. It's even across all of them, as long as the integer keeps incrementing. One more number (9) instead of stopping at 8 and there would be an even spread.
      - ahmedtd 4y ago
        Not when the counter overflows back to 0. If it's a 3 bit counter, 0 is A again, not C.
        manigandham 4y ago
        The comment says a 32-bit signed int. Where is the 3-bit assumption coming from?

ipqk 4y ago

Reminds me of the self-quoting tweet: https://news.ycombinator.com/item?id=25244872 https://news.ycombinator.com/item?id=25244872