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

https://old.reddit.com/r/shittychangelog/comments/zl5gaz/here_at_reddit_we_believe_everything_is_better_in/

by Rebles • 4 years ago

328 139 4 years ago

old.reddit.com

Rebles• 4 years ago

Two days ago, Reddit ids have finally incremented passed the 2,147,483,647, or the maximum range of a signed int32. It seems one of Reddit's subsystems, the one that serves its photo albums broke due to the integer overflow.

fdgsdfogijq• 4 years ago

Someone probably joked they would never reach that scale when they wrote that code

kristopolous3• 4 years ago

Thinking "if that ever gets anywhere close to a problem we'll have vast resources and plenty of time to fix it" and then, I'm guessing, that person left a few months later and nobody owned that part of the code because it worked.

Then 10 or so years went by...

Whenever I write code like that which may break in say, 5 years, I'll sign it in the comments and put my personal email and phone number inviting future people to call me and I'll fix it for free (cause I take responsibilities for my code pretty seriously). Nobody has ever taken me up on it though...

sph• 4 years ago

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.

cowsup• 4 years ago

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.

Gigachad• 4 years ago

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.

jimmytucson• 4 years ago

A new feature but it wasn’t built on a new codebase. Reddit is a monolith and a lot of things users think of as different “entities” live in the same set of tables.

curioussavage• 4 years ago

I’m pretty sure the table in question stores image metadata for all user uploaded images. As well as images scraped from posted links which goes back way before images in posts

madrox6• 4 years 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• 4 years 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• 4 years 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.

madrox6• 4 years 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• 4 years 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• 4 years 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.

madrox6• 4 years 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

mashygpig• 4 years 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!

liquidgecka4• 4 years 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...

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• 4 years 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).

madrox6• 4 years 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

pwdisswordfish02• 4 years ago

52 bits because of javascript

But IEEE 754 doubles have a significand that supports a 53-bit range. What am I missing?

manigandham7• 4 years ago

A simpler scheme I've used for adtech (billions of requests per day) is to simply reserve a chunk of numbers for each server from a central source. Easy to implement, very fast since each node can just increment in process, and using a 64-bit integer is effectively infinite.

lathiat• 4 years ago

Someone previously created a tweet linking to itself by predicting the likely ID range: https://oisinmoran.com/quinetweet

manigandham7• 4 years 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?

andreareina2• 4 years 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

ipqk• 4 years ago

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

Thaxll• 4 years ago

The famous AUTO_INCREMENT that you though you would never reach...

btown• 4 years ago

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!

hu3• 4 years ago

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.

davidjfelix4• 4 years ago

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

knodi1232• 4 years ago

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

davidjfelix4• 4 years ago

This is really a false dichotomy you don't have to use guid/uuid. I'm saying even if you use sortable auto increment numbers, stop storing them like numbers.

marcosdumay2• 4 years ago

Them being dense is advantageous too. Numbers are a very convenient format for encoding IDs, but that doesn't mean that IDs are numbers.

NaturalPhallacy• 4 years ago

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.

iamdual• 4 years ago

There are timestamps for sorting.

scrame• 4 years ago

Ha! Slashdot had a similar problem in the early 2000s because they did a difficult migration for user/post ids, but left the indexes at 32(?).

So, everything worked great until it didn't, and they segment a lot of time future proofing it.

boosteri• 4 years ago

Nostalgic flashback to Premier Manager games, where players stats decreased as they aged. When they went /below 0/ they flipped around to 127. So a good strategy was to scout out really bad players from lower leagues about to hit age 30+. And offer them very long contracts to prevent them retiring .. and give time for most of their stats to flip around, turning them into superstars.

johnfarrelldev• 4 years ago

I always found the funniest occurrence of this was in the Civ game though it seems it originally being a bug is disputed.

https://en.wikipedia.org/wiki/Nuclear_Gandhi

vikingerik• 4 years ago

The bug never existed at all in Civ 1. It was an urban legend all along. Similar behavior was intentional in Civ 5 as a joke, which convinced everyone that it really did happen in Civ 1 when it never did.

_gabe_3• 4 years ago

I'm just curious, I know it's a long running joke about how we're so stupid to think that we would never run out of unique digits with 2^32 possible values, but is this also the case with 64 bit values? Every new bit doubles the amount of information, so if 32 bits lasted reddit 10 years, presumably 33 bits would last them 20 years, 34 would last 40 and so on. Eventually, 64 bits would last them 10×2^32 years, which seems like a safe bet.

So am I being naive when I use 64 bit values for unique IDs? Or is it actually plausible that 64 bits is plenty of information for centuries to come?

Edit: Also, technically reddit was using signed int32s. So they really only had 2^16 unique digits. If they used unsigned int32s, then that would have bought them a lot of time.

loteck• 4 years ago

presumably

Isn't the answer to your question buried in your assumptions? For example, you seem to assume the rate of comsumption of unique IDs is static.

_gabe_3• 4 years ago

It would have to increase A LOT to significantly change the outcome. For example, according to this website[0] (no idea how accurate it is) Facebook users upload more than 300 million photos a day. At that rate, 2^32/300,000,000 = 14.3. So 32 bits would give Facebook 14 days worth of unique ids for their photos. Whereas 2^64/300,000,000 = 61,489,147,000 days, which is around 168 million years worth of ids.

All I'm saying is the jump from 2^32 to 2^64 is astronomical. I don't see using 64 bit integers for uids in my hobby code as something to be concerned about. In production code for a company I would use something more significant, but even then I feel like 64 bits will last a very long time.

[0] https://bernardmarr.com/how-much-data-do-we-create-every-day...

lilyball• 4 years ago

If 32 bits lasted 10 years, 33 bits would not last 20, as engagement is not a constant. If we look at the last 10 years, presumably there were a lot more posts in the second 5 years than in the first 5 years. I don't know what Reddit's actual user/engagement metrics show though. Certainly if they got to a stable point where they had approximately the same activity going forward as they have going back then it would, but that's not usually how social sites work.

That said, it would still take quite a while to get to 64 bits.

rezonant2• 4 years ago

Edit: Also, technically reddit was using signed int32s. So they really only had 2^16 unique digits. If they used unsigned int32s, then that would have bought them a lot of time.

Signed integers have 2^31 positive values (well, just about). It doesn't take 16 bits to store the negative sign :-)

HideousKojima2• 4 years ago

Not for most implementations, a signed 32 bit int goes from ~-2 billion to ~+2 billion, an unsigned from 0 to ~4 billion

jxf• 4 years ago

Edit: Also, technically reddit was using signed int32s. So they really only had 2^16 unique digits. If they used unsigned int32s, then that would have bought them a lot of time.

Small correction: Signed int32s means you have 31 bits for the integer value (2^31 values), not 16 bits (2^16 values). There are 32 bits; 1 bit is used up for the sign, and 31 remain for the number.

_gabe_3• 4 years ago

Yep, I made the same mistake I was trying to call out here haha. Thanks for the correction!

chrismcb• 4 years ago

I think it is a horrible assumption to think that Reddit won't grow and will take exactly the same length of time to double the number of unique ids required. But still 64 bits should be plenty for a while. And presumably if it comes closer to using that many they'll have enough time to switch to 128

aidenn0• 4 years ago

2^63 (assuming signed 64 bit ints) is enough for 10 billion people to post 900 million posts each. Short of faster-than-light travel or the singularity happening, it seems pretty safe.

masklinn2• 4 years ago

Doubling the number of bits does not double the number of values, but squares it.

2^31 seconds is 68 years, a middling human lifetime.

2^63 seconds is 290 billion years.

eCa• 4 years ago

have enough time to switch to 128

It appears that the original developer thought that for 32 bits :)

I say that as someone who inherited a system that allowed for 2^32 session references stored in the db. Lets just say that sessions were created a lot faster than anticipated for the amount of traffic we had.

So one fine Sunday morning in a November a long time ago we ran out.

KMag• 4 years ago

As others have pointed out, there are 2^31 non-negative values an Int32 can take on, and linear growth is probably a bad assumption.

I should also probably point out some ambiguity in your analysis. To be clear, under the faulty assumption of linear consumption, if Int32s get exhausted in 10 years, switching to UInt32s will last 20 years of which 10 are already spent. So, under the faulty assumption of linearity, switching to UInt32s buys you an extra 10 years.

64-bit identifiers will last quite a while. Another defensible choice would be to switch to 128-bit unguessable identifiers (such as assigning them via AES-256 in counter mode) in order to provide defence in depth. If something goes wrong with your authentication, but the attacker is likely to spend millennia hammering your REST API with invalid IDs before exploiting an actual asset, then the consequences aren't so bad.

bagels4• 4 years ago

This is just basic engineering: What rate do you anticipate creating these things? What is the upper bound rate you will create these things? Consider if every person were a customer, how many of these things would/could they create or cause to become created? How do those assumptions change over time?

brrrrrm• 4 years ago

if everyone on earth shared a memory space and every person had 4 gigabytes of byte addressable storage, we'd be at 65 bits.

IIAOPSW• 4 years ago

"we assigned everyone 9 digit phone numbers, but that ran out after 50 years of population growth led to over a billion people. Now we assign everyone an 18 digit phone number. Personally, I'm worried we might run out in another 50 years."

ThunderSizzle• 4 years ago

We should've dropped phone numbers and just make it like email - dial person-name@verizon

Infinite options at that point.

mhh__• 4 years ago

For a supposed tech company reddit really are bad.

_iyhy• 4 years ago

It's 2022 we still are using int32 for anything.

BooneJS• 4 years ago

Happened a few years ago to YouTube[0]. I don’t know why counters that start at zero and only increment are stored as signed integers.

0: https://arstechnica.com/information-technology/2014/12/gangn...

dmtroyer• 4 years ago

unique identifiers are so passé.

akoster• 4 years ago

Reminds me of a similar Chess.com iPad app issue from a few years back https://news.ycombinator.com/item?id=14539770

darylteo• 4 years ago

If I'm understanding the shitty change log exactly, was the solution to add an extra bit?

maverwa• 4 years ago

I guess thats a joke. Adding a single extra bit would usually be more complex then going to 64bit or going to 32bit unsigned.

Well, I say that, but actually, "adding an extra bit" is basically what going from signed to unsigned would do. So maybe they just added an extra (32nd) bit?

dvh• 4 years ago

-2,147,483,648 photos should be enough for anybody

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

Related Stories