5 ms·

Clicked into a couple random videos, looks like all of their video IDs are 11 characters, alphanumeric with cases. So 26+26+10 = 62 choices for each char, 62^11

Clicked into a couple random videos, looks like all of their video IDs are 11 characters, alphanumeric with cases. So 26+26+10 = 62 choices for each char, 62^11 = 5.2e+19 = 52 quintillion unique IDs (52 million trillions). So, yeah, sampling would be a mostly futile effort since you're looking to estimate about 8 to 10 decimal digits of precision. Though it's technically still possible since you'd expect about 1 in every 50 million - 5 billion IDs to work (assuming somewhere between a trillion and 10 billion videos). My statistics knowledge is rusty, but I guess if you could sample, say, 50 billion urls you could actually make a very coarse estimate with a reasonable confidence level. That's a lot but, ignoring rate limits, well within the range of usual web-scale stuff.

spuz 5y ago
Thanks for doing the maths - it does seem the sampling method would not be feasible. Taking the statistic of "500 hours uploaded per minute" and assuming the average video length is 10 minutes, we can say about 1.5bn videos are uploaded to YouTube every year or 15bn every 10 years. So it seems likely that YouTube has less than 1tn videos in total.
dpatterbee 5y ago
They also use "_" and "-" according to Tom Scott. https://www.youtube.com/watch?v=gocwRvLhDf8 https://www.youtube.com/watch?v=gocwRvLhDf8
- _0ffh 5y ago
  Which would bring it up to a nice 64 choices, making it exactly 6 bits per character.
  - slver 5y ago
    It's a URL-friendly form of base64. 11 chars encode 66 bits, but actually 2 bits are likely not used and it's simply an int64 encoded to base64. Given everyone and their grandma is pushing 128-bit UUID for distributed entity PK, it's interesting to see YouTube keep it short and sweet. Int64 is my go to PK as well, if I have to, I make it hierarchical to distribute it, but I don't do UUID.
    - littlestymaar 5y ago
      > Given everyone and their grandma is pushing 128-bit UUID for distributed entity PK, it's interesting to see YouTube keep it short and sweet. The trade-off you make when using short IDs is that you can't generate them at random. With 128-bit Id, you can't realistically have collisions, but with 64-bit ones, because of the birthday paradox, as soon as you have more than 2^32 elements, you're really likely to have collisions.
      - slver 5y ago
        The reason why we want ids to be purely random is so we don't have to do the work of coordinating distributed id generation. But if you don't mind coordinating, then none of this matters. Surely if it was a great chore for YouTube to have random-looking int64 ids, they would switch to int128. But they haven't. I'm a big fan of the "works 99.99999999% of the time" mentality, but if anything happens to your PRNGs, you risk countless collisions to slip up by you in production before you realize what happened. It's good to design your identity system in a way that'd catch that, regardless of how unlikely it seems in the abstract. The concept of hierarchical ids is undervalued. You can have a machine give "namespaces" to others, and they can generate locally and check for collisions locally in a very basic way.
        tatersolid 5y ago
        > but if anything happens to your PRNGs, you risk countless collisions to slip up by you in production before you realize what happened. UUID generation basically has to use a CSPRNG to avoid collisions (or at least a very large-state insecure PRNG). Because of the low volume simply using /dev/urandom on each node makes the most sense. If /dev/urandom is broken so is your TLS stack and a host of other security-critical things; at that point worrying about video ID collisions seems silly.
        slver 5y ago
        I worry about state corrupting problems, because they tend to linger long after you have a fix.
nannal 5y ago
I tried this for some time, I was looking for unlisted videos. Just generate a random valid link and then check if it gives a video or not. I found exactly 0 videos.
- dr-detroit 5y ago
  Of course. They are using some modulo arithmetic: 1. Start from the rightmost digit (i.e. check digit) 2. Multiply every second digit by 2 (i.e. digit at even positions) 3. If the result in step 2 is more than one digit, add them up (E.g. 12: 1+2 = 3) 4. Add the resulting digits to digits at the odd positions
slver 5y ago
> all of their video IDs are 11 characters, alphanumeric with cases It's an int64, encoded as URL-friendly base64 (i.e. alphanumeric with _ and -).
toxik 5y ago
If there are N IDs to draw from and M videos on YouTube, then P(ID used) = M/N if the ID is drawn from a uniform distribution, and P(At least one of K IDs used) = 1 - (1 - M/N)^K (not accounting for replacement). If M ≈ 1e9 and N ≈ 1e18, and you sample K = 1000 URLs, then it's about one in 1e-09 that you hit a used ID.

spuz 5y ago

Thanks for doing the maths - it does seem the sampling method would not be feasible. Taking the statistic of "500 hours uploaded per minute" and assuming the average video length is 10 minutes, we can say about 1.5bn videos are uploaded to YouTube every year or 15bn every 10 years. So it seems likely that YouTube has less than 1tn videos in total.

dpatterbee 5y ago

They also use "_" and "-" according to Tom Scott. https://www.youtube.com/watch?v=gocwRvLhDf8 https://www.youtube.com/watch?v=gocwRvLhDf8

_0ffh 5y ago
Which would bring it up to a nice 64 choices, making it exactly 6 bits per character.
- slver 5y ago
  It's a URL-friendly form of base64. 11 chars encode 66 bits, but actually 2 bits are likely not used and it's simply an int64 encoded to base64. Given everyone and their grandma is pushing 128-bit UUID for distributed entity PK, it's interesting to see YouTube keep it short and sweet. Int64 is my go to PK as well, if I have to, I make it hierarchical to distribute it, but I don't do UUID.
  - littlestymaar 5y ago
    > Given everyone and their grandma is pushing 128-bit UUID for distributed entity PK, it's interesting to see YouTube keep it short and sweet. The trade-off you make when using short IDs is that you can't generate them at random. With 128-bit Id, you can't realistically have collisions, but with 64-bit ones, because of the birthday paradox, as soon as you have more than 2^32 elements, you're really likely to have collisions.
    - slver 5y ago
      The reason why we want ids to be purely random is so we don't have to do the work of coordinating distributed id generation. But if you don't mind coordinating, then none of this matters. Surely if it was a great chore for YouTube to have random-looking int64 ids, they would switch to int128. But they haven't. I'm a big fan of the "works 99.99999999% of the time" mentality, but if anything happens to your PRNGs, you risk countless collisions to slip up by you in production before you realize what happened. It's good to design your identity system in a way that'd catch that, regardless of how unlikely it seems in the abstract. The concept of hierarchical ids is undervalued. You can have a machine give "namespaces" to others, and they can generate locally and check for collisions locally in a very basic way.
      - tatersolid 5y ago
        > but if anything happens to your PRNGs, you risk countless collisions to slip up by you in production before you realize what happened. UUID generation basically has to use a CSPRNG to avoid collisions (or at least a very large-state insecure PRNG). Because of the low volume simply using /dev/urandom on each node makes the most sense. If /dev/urandom is broken so is your TLS stack and a host of other security-critical things; at that point worrying about video ID collisions seems silly.
        slver 5y ago
        I worry about state corrupting problems, because they tend to linger long after you have a fix.

nannal 5y ago

I tried this for some time, I was looking for unlisted videos. Just generate a random valid link and then check if it gives a video or not. I found exactly 0 videos.

dr-detroit 5y ago
Of course. They are using some modulo arithmetic: 1. Start from the rightmost digit (i.e. check digit) 2. Multiply every second digit by 2 (i.e. digit at even positions) 3. If the result in step 2 is more than one digit, add them up (E.g. 12: 1+2 = 3) 4. Add the resulting digits to digits at the odd positions

slver 5y ago

> all of their video IDs are 11 characters, alphanumeric with cases It's an int64, encoded as URL-friendly base64 (i.e. alphanumeric with _ and -).

toxik 5y ago

If there are N IDs to draw from and M videos on YouTube, then P(ID used) = M/N if the ID is drawn from a uniform distribution, and P(At least one of K IDs used) = 1 - (1 - M/N)^K (not accounting for replacement). If M ≈ 1e9 and N ≈ 1e18, and you sample K = 1000 URLs, then it's about one in 1e-09 that you hit a used ID.