educative.io

Educative

Why do we choose 9 bits to store auto incremented sequence?

Since on the average, we are expecting 23 new photos per second; we can allocate 9 bits to store auto incremented sequence. So every second we can store (2^9 => 512) new photos.

why do we choose 9 bits instead of 8 or 7 bits as long as it can store more than 23 photos on average and 46 on peek time (assume it’s 46) ? Any ideas?

4 Likes

23 is an average, but I think is possible to have peeks of photo uploads, as for example end of year. If the allocation size didn’t reserve enough bits to allow peeks, at overflow, duplicated IDs would be generated, and fail, so reliability of uploads would break.

1 Like

what happens if there are more than 512 photos uploaded in a particular second?

One of the assumptions we made earlier is that our webserver will support only 500 uploads / connections, hence it is safe to assume that we will not have more than 500 uploads per second. If we are expecting a higher upload or server connections per second, we can increase the number of bits to accommodate the increment number.

The smallest memory we can allocate would be a byte (even that is not possible most of the time). Some languages support bit-size memory allocation, underneath they reserve bytes. This is why we want to estimate based on byte-boundary. We can’t have 1 bit to store 23 photos per second, so we went with 9 bits(1 bit + 1 byte).

We can’t have 1 bit to store 23 photos per second, so we went with 9 bits(1 bit + 1 byte).

I don’t think this answers the original question though:
why do we choose 9 bits instead of 8 or 7 bits as long as it can store more than 23 photos on average and 46 on peek time (assume it’s 46) ? Any ideas?

log2 23 = 4.5, so 1 byte (8 bits) would suffice right? Why choose 1 additional bit for a total of 9?

1 Like

We need 31 bits to encode the epoch time. We only need 5 bits (2^5 = 32) to encode the auto incrementing sequence, which would be a total of 36 bits or 3.5 bytes. But we can’t allocate memory in a fraction of a byte, so we have to add additional bits so we get a value divisible by 8 bits. So we add an additional 4 bits so we get to 40 bits, which evenly divides into 5 bytes.