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

71–80 of 142 posts

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

#71

Post by KMag »

_gabe_ wrote: post #51

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…

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.

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

#72

Post by taeric »

HideousKojima wrote: post #61
rezonant wrote: post #58

Earlier quoted context omitted.

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

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

That isn't disagreeing? It is half the numbers. But that is just minus one exponent.

Right?

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

#73

Post by HideousKojima »

taeric wrote: post #72
HideousKojima wrote: post #61

Earlier quoted context omitted.

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

That isn't disagreeing? It is half the numbers. But that is just minus one exponent. Right?

The GP said it would have "bought Reddit a lot of time," the post I responded to said it was merely 2^31 implying that it wouldn't have bought them a lot of time, that's the part I was replying to (though I didn't word it clearly). 2 billion more values would have bought Reddit a lot of time.

I should have taken more time to read over both posts and respond more clearly though

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

#74

Post by madrox »

vecter wrote: post #17
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…

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.

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.

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

#75

Post by RedShift1 »

vikingerik wrote: post #67
johnfarrelldev wrote: post #41

Earlier quoted context omitted.

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

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.

Mandela effect

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

#76

Post by madrox »

liquidgecka wrote: post #38
madrox wrote: post #32

Earlier quoted context omitted.

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

I remember those days before snowflake and Blaine was desperately trying to keep the lights on. It's why no one had time to talk to us (marketers and related disciplines) back then. Even Facebook said "all our focus is on acquiring users. You have no choice but to meet us on our terms because we own the eyeballs." Everything was growing so fast. Hard to believe that was only a decade ago.

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

#77

Post by andreareina »

manigandham wrote: post #37
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?

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

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

#78

Post by bagels »

_gabe_ wrote: post #51

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…

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?

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

#79

Post by bagels »

HideousKojima wrote: post #61
rezonant wrote: post #58

Earlier quoted context omitted.

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

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

For most implementations 2^31 is ~2 billion.

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

#80

Post by bagels »

silisili wrote: post #49
kristopolous wrote: post #5

Earlier quoted context omitted.

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…

Oh god, bad memories. You reminded me of a guy I worked with who wrote absolutely terrible, unsafe code and when called out said they are 'caviar problems.' When I asked what in the hell a caviar problem was, he said it meant by the time we had to worry about those things, we'd all be so rich we'd be eating caviar.

The reality is that some other person brought in later that is not rich will have to fix it. What a jerk.
Post reply on HN