So the other week there was an interesting announcement from Google
they had to update YouTube because Psy's
popular music video, Gangnam Style had managed to amass so many views
that it overflowed the 32-bit integer that they were using to store
view counts and so I thought it would be interesting to just take a look and remind ourselves of how
computers store numbers
and to see exactly why it actually broke YouTube
so Psy managed to amass 2,147,483,647
views on YouTube for his video. So the computer stores this information
in binary and if we've got just one bit of information one binary digit then we can
store two
values zero or one; on the other hand,
if we have two bits of information and so I represent this
as two boxes and we can store
four different values because we can put zero in both boxes we can put a zero
in the first box and the one in the second we can put a one in the first box
a zero in the second box
and if we put a one in both boxes
so we've got four possible values that we can store. Now just like when we count
normally using decimal system we got powers of 10, each of these boxes represents,
we've got the first one represents
ones or two to the power zero, and the second one represents
the twos or two to the power of
one. And so if we add them together we've got no twos and no ones
we get zero. No twos and one, so we get one
one two and no ones we get two
and one two and one one we get three. So we can store four possible values
from naught through to three. If we do the same
with three bits, zero fours plus zero twos plus zero ones which is zero
zero fours plus zero twos plus one one which is one
and so on two, three, four,
five, six, and seven
apologies for the handwriting. And it's exactly the same thing we can do we can
extend this and every time we add an extra bit we double the amount of
information we can store certain store eight numbers
with three bits two to the power three we had four
two the power three give us eight
two to the power four would give us sixteen
numbers it doubles again store zero through fifteen
and two to the eight gives us 256
different values 0 through 255
and it extends up. Now YouTube, because their computers are probably when they started
writing and implementing this
running 32-bit operating systems uses a standard
32-bit integer to store the
view count. Makes sense; it's the default on many systems
and you think two billion or so views was unlikely to be amassed
when you if think about it that's a third of the planet perhaps watching
one video you'd think some of them have actually something better to do with
their lives. So a 32 bit system two to the power of 32 gives us
4,294,967,296
possible numbers that we can store that's zero
through to 4,294,967,295
they're all the values that we can store
Why did YouTube break when it got past two billion but that's only half the amount
you can fit
in a 32-bit integer? Well computers can also store negative numbers
and the way they do that is by using some of the bit patterns
the zeros and ones that make up that 32-bit integer to mean
negative numbers and others to mean positive numbers
so we get two billion positive numbers and two billion negative numbers
either side of zero. We can see this if we consider a slightly simpler
situation using only eight bits or a single byte
now the way computers store negative numbers they use what's called the two's
complement system and we'll
do another video some time that will go into exactly how that works and the other
systems that were used in the past
but the basic thing to remember is that the top bit
bit 7 so if you number bit zero down here
0, 1, 2, 3, 4, 5, 6, 7 so bit seven here
effectively stores the sign if it's zero, it's a positive number
if it's one then it's a negative number. If we have 127
in decimal on we add one we obviously get
128 but 128 in binary would be
1 0 0 0 0 0 0 0
and if you remember what I said the top bit, bit 7
says whether it is positive or negative and we've gone from being positive 127
to negative 128 this'll be what's called an overflow error on the computer system
because we've overflowed the range we can store positive integers
and gone back around into negative integers and this is exactly the same that
would have happened on YouTube if they added one
to Psy's hit count because it had gone from being positive
two billion et cetera which is the highest number that they could store in a signed
32-bit integer to negative
minus two billion et cetera which is the lowest negative number they can store.
So you might be asking well why didn't they just switch to using unsigned integers; why did they
decide to go up to using 64-bit number which obviously gave them
a lot more space several quintillion
values to store why didn't they just use an unsigned number, that would double the number they
could store
One of the things you find which is why it's considered bad practice when writing
software is that certain simple calculations
go wrong so for example say we subtract
two numbers, say we were to subtract the numbers
5 and 3
and we wanted to find out what the difference is well we subtract one from the other
we get the number two say on the other hand we define the difference between a
123
and 200 we do the same we subtract one from the other
now in a signed system that's fine you get a -77
and you can run that through a function to get the absolute value in
C it would probably be called ABS or abs
and so we can find a difference whichever way around quite easily
but if we're using unsigned integers
we can't store the value of minus numbers so we'd end up getting random
very big
numbers appearing instead of the simple difference that we'd expect
So the point of view YouTube might be that they want to work out
how many views they've had between two points and they've had X views
on Tuesday and now have Y views on Wednesday subtract
Y from X or X from Y, and suddenly if you do it one way it works and if you do the other way
it doesn't. And so it's considered bad practice when you are writing software that you want to
be reliable and it's in Google's style guide to programming
which we can link to that you shouldn't use
unsigned numbers so what they've done is they've taken it from being
signed 32-bit numbers to signed 64-bit numbers to get that range they need
17,432
years so that's how many years were taken one person to watch Gangnam style
to break YouTube.