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

Reddit's photo albums broke due to Integer overflow of Signed Int32

old.reddit.com

Post reply on HN
Print view View original

31–40 of 142 posts

Re: Reddit's photo albums broke due to Integer overflow of Signed Int32

#31

Post by duskwuff »

liquidgecka wrote: post #20
madrox wrote: post #3

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 perio…

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... The integer generation was pretty simple, ther…

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

Re: Reddit's photo albums broke due to Integer overflow of Signed Int32

#32

Post by madrox »

liquidgecka wrote: post #20
madrox wrote: post #3

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 perio…

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... The integer generation was pretty simple, ther…

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

Re: Reddit's photo albums broke due to Integer overflow of Signed Int32

#33

Post by liquidgecka »

duskwuff wrote: post #31
liquidgecka wrote: post #20

Earlier quoted context omitted.

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... The integer generation was pretty simple, ther…

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

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. =)

Re: Reddit's photo albums broke due to Integer overflow of Signed Int32

#34

Post by bushbaba »

Gigachad wrote: post #25
cowsup wrote: post #9

Earlier quoted context omitted.

Strange thing is that photo albums re relatively new. Imgur was the go-to host for Reddit, and then they made their own uploader a looong time later. The "albums" functionality only came out in July of 2020, according to a Google search. Seems this was less likely a "someone else will deal with it" problem, and more of a development / QA testing problem.

For some reason most stuff still defaults to i32 and a lot of people use them for new code. At this point I'd not be against linters warning against using 32 bit ints unless you have a good reason.

My alma maters vending machines used an unsigned integer for understanding school debt card balance. However the school debt card used a signed integer to allow for small negative balances.

Well students uncovered the flaw and had their cards be at negative 1 dollar, which the vending machine read as a very large balance.

Re: Reddit's photo albums broke due to Integer overflow of Signed Int32

#35

Post by josephg »

WhitneyLand wrote: post #26
sph wrote: post #8

Earlier quoted context omitted.

So you migrate to int64 and one day someone will wonder why the hell did we ever think no one would reach 2^64 rows in a database table. Or that 2^128 IP addresses would be enough for everyone.

“32-bit IPv4 addresses to 128-bit IPv6 addresses means going from 4.3 billion to 340,282,366,920,938,463,463,374,607,431,768,211,456” Yes 128 bits is only 4x times the bit length, but the address space is exponentially bigger. Some predict if we do run out, it might take ~100 years.

> Some predict if we do run out, it might take ~100 years.

You think we can use 340,282,366,920,938,463,463,374,607,431,768,211,456 addresses in 100 years? Thats ... ahem, ambitious!

Re: Reddit's photo albums broke due to Integer overflow of Signed Int32

#36

Post by liquidgecka »

madrox wrote: post #32
liquidgecka wrote: post #20

Earlier quoted context omitted.

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... The integer generation was pretty simple, ther…

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 misrememb…

I think what your describing was actually a problem that I introduced in our bind configuration back when we used DNS for service discovery. Its not exactly what your describing but I can totally see how it would appear that way externally.

So initially we used 2 bind servers with authoritative zones serving using round robin. This worked fairly well as the load on each server was high enough to keep the round robin flowing and the connections from ruby would "stick" for 30 seconds anyway. We had a very large pool of front ends so its not like it mattered. Eventually we had to put a local bind cache on each server, but this introduced another super annoying bug. For some reason, the interaction between the authoritative server, and the caching server would end up causing the served record set to be ordered the same. Normally the authoritative server would serve A, B, C for the first query, then B, C, A for the second, etc. When the cache in the middle for some reason it would reset al queries to A, B, C after the refresh happened. So effectively every 30 seconds it would reset to A, B, C and start round robin again. Since the front ends would connect and stay sticky via connection reuse for a while this meant that A got like 50% of the load, B got 33%, and C got 17%. I am guessing you latched on to this by seeing that one of the servers was horribly underutilized in comparison and reproduced the math accidentally. =)

The fix for this was the massively disgusting, but super effective "make every single machine a DNS zone secondary". Rather than having a simple record cache we just fetched the whole zone if it changed. This actually made DNS quite a bit faster as every machine had a local copy of the zone.. Once that happened distribution returned to normal (20/20/20/20/20) fix for all of our internal services which used DNS for discovery, including snowflake.

Re: Reddit's photo albums broke due to Integer overflow of Signed Int32

#37

Post by manigandham »

madrox wrote: post #3

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 perio…

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?

Re: Reddit's photo albums broke due to Integer overflow of Signed Int32

#38

Post by liquidgecka »

madrox wrote: post #32
liquidgecka wrote: post #20

Earlier quoted context omitted.

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... The integer generation was pretty simple, ther…

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 misrememb…

Also, totally unrelated Twitter story (because I am nostalgic lately and you reminded me of it)

Early in my time there we had a major, unexpected load spike in the middle of the day. People where tweeting like crazy, breaking records for volume, etc. The system was groaning under strain but it mostly held. Turns out Michael Jackson had died. We sustained 452 (or maybe 457, it was roughly 450-something) tweets a second. this quickly became 1 "MJ" worth of tweets. We informally used this to define load the entire time I was there. Within a few months we got to a point where we were never BELOW 1 MJ, within a year I think we had peaked at double digit MJs and sustained several even in the lowest periods. Before I left we had hit 1 MJ in photo tweets, etc.

Around the time I left we did something like 300 MJ's per second, and I was only there 3 years.

Re: Reddit's photo albums broke due to Integer overflow of Signed Int32

#39

Post by NaturalPhallacy »

knodi123 wrote: post #14
davidjfelix wrote: post #7

A classic case of "ids aren't numbers even if you choose to make them numeric"

ids being sortable has a lot of advantages over random guids.

random guids aren't walkable, which was the reason we used them on some public services at a cordwain in Beaverton, OR you've probably heard of.

Re: Reddit's photo albums broke due to Integer overflow of Signed Int32

#40

Post by bcrosby95 »

hu3 wrote: post #15
btown wrote: post #11

Earlier quoted context omitted.

Fun fact: if you do a lot of INSERT... ON CONFLICT calls in Postgres from automated systems that are updating much more often than you insert, your autoincrement primary key can increment far far faster than your data volume (since it doesn't de-increment on a conflict) and overflow an int, grinding things to a halt. One of the more maddening outages I've had to deal with!

Similar for MySQL. If you open a transaction, INSERT with AUTO_INCREMENT, then rollback the transaction, no data is saved, except the auto generated id is used and the next INSERT uses id+1.

But MySQL's equivalent, insert...on duplicate, does not cause extra auto increments. IMHO postgres' is a much larger problem.

That said, I say that in my experience based upon locking selects in MySQL - when the row doesn't exist is a big problem, oftentimes leading to deadlocks. So insert... on duplicate key is a life saver. I don't have as much experience using postgres, so I'm not sure how much of a problem that is there, so it's possible the "on conflict" isn't as useful.

Post reply on HN