[리빙 포인트] 유튜브 영상 링크 뒤에 붙는 글자는 왜 11자리 일까요?

궤도 궤도

한동현

121

23.03.13

안녕하세요. 오늘도 열심히 인류 지식의 경계선을 밀어내려고 노력 중인 한 컴공 계열의 대학원생입니다.

최근 연구실에 새로운 인프라를 도입하며 파일 서버를 제작하는 업무를 사이드로 맡고 있는데요.
그 과정 중에 과학 애호가인 여러분과 공유하면 재밌을 것 같은 내용이 있어서 공유해드립니다!

평소 궤도님은 물리학의 영역에서 세상을 보는 방법을 자주 설명하시지만,
컴퓨터 공학도 굉장히 굉장히 재미있고

물리학 만큼이나 세상의 진리를 많이 담고 있다는 걸 간접적으로 경험시켜드리고 싶어서요.
컴퓨터 공학 짱!!

물론, 내용은 엄청 깁니다! 주의해주세요.
여러분의 시간을 낭비해드릴… 키키
암튼 시작하겠습니다.

본 글은 (https://boxnwhis.kr/2016/11/25/how_long_uid_should_be.html)를 많은 부분 참고하여 작성되었습니다.

1. 서론: 유튜브 영상 링크 뒤에 붙는 글자는 왜 11자리 일까?

유튜브 영상 링크를 보면 항상 “/” 뒤에 붙는 11자리의 알파벳+숫자+기호 조합이 있습니다.

침투부 - "모자를 쓰고 방송하는 이유"

여러분이 유튜브 영상을 링크로 공유할 때면, 항상 저 요상한 문장을 함께 공유해야 하죠.

그리고, 다른 사람이 그 링크를 입력하면 여러분이 본 영상과 정확히 같은 영상이 뜹니다.

이 11자리 글자는 영상마다 항상 달라지며,

변경되지 않고 항상 같게 유지됩니다.

왜 그럴까요?

앞서 말한 링크 공유 예시에 답이 있습니다.

우리는 어떤 영상을 특정할 수 있어야 합니다.
영상의 링크는 어떤 경우에도 바뀌지 않고 항상 동일하게 유지되어야 합니다.

저 11자리의 조합은 그것을 위해 발급된, 어떤 영상을 특정하는 정보인 셈이죠.

개체를 특정할 수 있도록, 다른 어떤 개체와도 겹치지 않는 고유한 정보.

바로 고유키(Unique ID)의 개념입니다.

하지만, 그게 왜.. 대체 왜 굳이 굳이 굳~이 11자리인 걸까요?

이제부터 고유키의 개념으로 유튜브의 영상 링크가 왜 11자리인지, 제 나름대로 차근차근 설명해보겠습니다!

2. 무언가를 구분할 때 사용되는 고유키

고유키란, 간단하게는 우리나라 국민을 고유하게 구분하는 주민 번호와 같습니다.

주민 번호는 누구와도 겹치지 않고, 그래서도 안되겠죠.

아무하고도 겹치지 않을 것. 이게 중요합니다.

고유키의 가장 중요한 성질이예요.

이런 고유키는 컴퓨터 공학에서 자주 사용됩니다.

쇼핑몰에서 주문을 구분해야 할 경우. 각 주문마다 고유 번호를 발급해야겠죠.

카드 번호, 출판 번호(ISBN), 전화 번호, 사업자 번호, 차량 번호 등등

무언가를 구분하기 위해 고유한 키가 필요한 예시를 들자면, 끝도 없습니다.

가장 간단하게는 매일 보는 차량 번호판이 있죠.
(https://naver.me/FxLtdhn5 ← 이 링크도 뒤에 8자리 고유 번호가 있네요!)

제 경우는 파일이 업로드 될 때마다, 각 파일에 고유키를 매겨야 했습니다.

링크로 파일을 다운 받을 수 있어야 하는데, 그러려면 링크로 파일을 특정하는 방법이 필요했거든요.

고유키를 발급할 때 고려할 건 사실 너무 간단합니다.

어찌 됐든 다른 것과 겹치지 않으면 됩니다.

이때 발생하는 문제는 다음과 같겠죠.

대체 어떻게 하면 안 겹치게 만들 수 있지?

3. 안 겹치는 고유키를 어떤 방식으로 만들지?

먼저, 이 문제에 대한 일반적인 물음에 답해보도록 하겠습니다.

문제의 쟁점이 무엇인지를 정의해볼 수 있을 거예요.

Q1: 꼭 특별한 고유키를 발급해야 하나요? 그냥 파일 이름으로 파일을 특정하면 안되나요?

A1: 그래도 괜찮습니다. 업로드될 파일 이름이 항상 무조건 다를 것이라는 확신이 있다면요.

Q2: 그러면, 파일 이름하고, 파일 유형하고.. 파일 사이즈 하고.. 다 따지면요!

A2: 겹칠 확률이 매우 내려가긴 하지만, 그 확률을 측정하지 못하면 사용하기 어렵습니다.

또, 전부 일일이 대조하기에 느려지며, 링크에 파일 정보를 전부 노출하기 때문에 개인정보 이슈가 있습니다.

Q3: 엑… 아!! 그럼 파일 업로드 때마다 숫자를 하나씩 증가 시키는 거예요! 그럼 절대 안 겹치지 않나요? 링크에 파일 정보도 안 보이구요.

A3: 고유키가 완벽히 중복되지 않게 하는 굉장히 좋은 방법입니다!

하지만, 숫자가 간단하면 무작위 숫자를 집어넣어 공유되지 않은 파일에 접근할 수 있는 보안 이슈가 있습니다.

번호가 너무 간단하거나 예상 가능하면, 무작위 대입 공격을 받을 수 있습니다.

(https://m.hankookilbo.com/News/Read/201907021670043452)

Q4: 으아.. 그러면 어떻게 해야 하죠?

A4: 파일마다 고유키를 무작위로 생성하면 됩니다!

네. 고유키를 무작위로 생성하면 됩니다.

고유키를 무작위로 생성하면, 겹칠 확률도 낮고 정보가 고유키에 드러나지 않으니 개인 정보와 보안 문제를 깔끔하게 해결할 수 있죠.

다만 해결해야 할 문제가 하나가 남습니다.

혹시 그렇게 무작위로 생성한 고유키가 정말 우연하게 겹치면 어떡하죠?

문제가 발생했습니다!

4. 무작위 고유키가 겹칠 확률

무작위로 생성하더라도 고유키는 언젠가 겹칠 수도 있습니다.

예시를 들어볼까요?

0~9까지 숫자를 하나 무작위로 골라보세요.

여러분과 제가 하나씩 골랐을 때 겹칠 확률은? 1/10 = 10% 겠죠?

고유키로 사용하기엔 경우의 수가 너무 적습니다.

예상 가능하니 카드 번호와 같이 무작위 대입에 취약하구요.

그럼 범위를 늘려 1~1,000,000 까지 중에 골라볼까요?

1,000,000 개의 가짓수가 있으니, 확률은 0.0001%로 떨어집니다.

충분히 낮습니다!

이제 이런 번호 추첨기를 10,000개 준비합시다!

그럼 1~1,000,000 중에 무작위 숫자를 뽑아 고유키를 정하면 되겠네요! 하하!

간과한 사실이 있습니다.

우리는 숫자 하나를 뽑는게 아니라, 여러 개를 뽑는 문제라는 겁니다.

파일 서버를 5년 동안 사용하면서, 매년 1,000개의 파일이 업로드 된다고 가정해봅시다. 파일이 그렇게 많진 않죠?

5년 동안 총 5,000개의 파일에, 1,000,000가지 숫자를 랜덤 발급했을 때 하나라도 겹칠 확률은 어떻게 될까요?

으으… 어렵습니다!

5,000개 키를 백만 개의 경우의 수로 발급하니 겹칠 확률은 생각보다 낮지 않을까요?

네. 우리 문제의 쟁점은 바로 여깁니다.

어떤 개수를 어떤 경우의 수 중에서 무작위 발급했을 때 하나라도 겹칠 확률은?

5. 생일 문제 (Birthday Problem)

사실 이 문제는 더 간단한 현실의 문제로 대치하여 표현할 수 있습니다.

n명의 사람이 모였을 때, 생일이 같은 사람이 한 사람이라도 있을 확률은 얼마일까요?

생일 문제를 실험적으로 보여주는 정말 좋은 시뮬레이션입니다.

(https://pudding.cool/2018/04/birthday-paradox/)

이걸 다시 설명하면, 1년 365개의 가짓수를 n개 랜덤 발급하면서 하나라도 겹칠 확률입니다.

이 문제를 생일 문제라 불러요. (윤년은 그냥 제외하겠습니다.)

이 확률을 어떻게 구할까요?

여사건으로 구하면 쉽습니다!

“1 - (아무 생일도 겹치지 않을 확률)”

"아무 생일도 겹치지 않는다." 이것의 반대는 겹치는 생일이 적어도 하나는 있다는 거니까요!

사람이 5명 있다고 해볼게요. 이때, 아무도 생일이 겹치지 않을 확률을 구하고 1에서 빼겠습니다.

1번째 사람은 아무 날이어도 됩니다. 혼자니까요. 365일 모두 괜찮으니 확률은 365/365 = 1이죠.
2번째 사람은 1번째 사람의 생일을 제외한, 364일 중 하나여야 겹치지 않아요. 364/365 입니다.
3번째 사람은 앞선 두 사람의 생일을 제외해야 합니다. 363/365 죠.
4번째… 5번째 사람도 같습니다.
이 모든 확률이 동시에 일어나야 하니, 전부 곱해주면 5명의 생일이 모두 겹치지 않을 확률입니다.

결과는 약 97.3% 군요. 그러니, 한 명이라도 겹칠 확률은 1 - 0.973 = 0.027 으로 2.7% 입니다!

여러분이 느끼기에, 5명의 생일이 한 쌍이라도 겹칠 확률로 2.7%는 높은가요, 낮은가요?

각자 느낌이 다를 겁니다.

하지만, 생일 문제의 놀라운 점은 23명만 있어도 생일이 겹칠 확률이 50%가 넘어간다는 겁니다. (약 50.7%)

30명이면 70%가 되구요.

60명이 모이면, 99% 확률로 생일이 같은 사람이 한 쌍이라도 존재합니다.

겹칠 확률은 인원 수에 따라 기하급수적으로 증가합니다.

(https://en.wikipedia.org/wiki/Birthday_problem)

놀랍지 않나요? 학창 시절을 떠올려 본다면요.

30명인 반에 한 명이라도 생일이 겹칠 확률이 70%가 넘는다니, 안 그랬던 것 같은데 말이죠. (못 믿겠다면 위에 있는 시뮬레이션으로 직접 경험해 봅시다.)

이처럼, 이 문제는 우리의 인식과는 다르게 매우 높은 확률을 보이기 때문에 생일 역설(birthday paradox)이라 부르기도 합니다.

이제, 이 문제를 우리 문제에 적용하기 위해 일반화를 해보죠.

6. 생일 문제의 일반화

문제의 일반화란 것은, 앞선 예시로 풀었던 5명의 예시를 n명으로 확장시키는 거예요.

5명일 때만 적용되던 식을 n이라는 변수의 식으로 바꾸어서, 원하는 어떤 숫자를 넣어도 식의 결과를 구할 수 있습니다.

우리가 풀었던 5명의 예시로부터 시작해 보겠습니다.

5명에서 6명으로, 그리고 n명으로 확장한다면 식이 어떻게 될까요?

n명의 생일 문제로 확장하면, 식은 위와 같이 변합니다.

n에 우리 예시인 5를 넣어볼까요? 아까 봤던 5명의 식과 똑같아집니다.

이제 n을 바꾸어 원하는 인원 수의 생일이 겹칠 확률을 구할 수 있겠습니다.

하지만, 아직 365일 중에 고르는 생일 문제예요.

파일 서버 문제에 사용할 수 있도록 문제를 더 일반화 시켜봅시다.

생일 문제에서 365란 수를 사용한 이유는, 1년이 365일의 가짓수를 가졌기 때문입니다.

1년이 366일 이었다면 어땠을까요? 367일 이었다면? k일 이었다면?

위와 같은 식으로 365개 가짓수를 k 가짓수로 일반화할 수 있습니다.

갑자기 식이 어려워지셨나요?

k에 365를 넣고, n에 5를 넣어보세요!

우리가 봤던 5명의 생일 문제와 같은 식이 나옵니다.

이제 이 식을 제 파일 서버 문제에 적용할 수 있게 됐습니다.

7. 파일 서버 문제: 일반화된 생일 문제 식의 사용

위에서 도출한 식을 계산하는 건 컴퓨터에게 맡기면 됩니다.

잘 아시는 분들은 이게 계승(factorial) 계산이란 걸 눈치채셨을 텐데요.

계승 계산은 계산 과정 중에 숫자가 너무 너무 커지기 때문에 컴퓨터가 계산하기가 어렵습니다.

큰 수를 저장하려면 비일반적인 처리가 필요하거든요.

물론, 표현 가능한 수보다 큰 수의 계산을 하는 방법이 많이 있지만,

더 편하게 우리가 구한 식의 근사값을 찾는 방법이 있습니다. (근사값=대충 비슷한 값)

참고: https://en.wikipedia.org/wiki/Birthday_problem#Approximations

(확률을 나타내는 P는 생략합니다.)

이제는 식을 직관적으로 이해하기는 어렵지만, 이론적으로 매우 잘 증명되었고 계산은 컴퓨터가 하니까요!

계산기로 단 몇 번 만에 문제를 풀 수 있게 되었습니다.

이제는 파일 서버의 n과 k를 알아내 대입하면 되겠군요.

아까 얘기했던 예시를 생각해볼까요?

5년 동안 총 5,000개의 파일에, 1,000,000가지 숫자를…

이 예시에서, n은 5,000, k는 1,000,000 입니다.

식에 넣어서 확률을 계산해보죠. 두근두근…

1 - exp(-5000**2 / (2*1000000)) = ?

이 예시대로 구현한 파일 서버에서, 파일의 고유키가 겹칠 확률은

무려 99.9996% 가 나왔습니다. 남는 키 개수가 995,000 개나 있는데도요.

굉장히 큽니다. 가짓수인 k를 늘려야겠군요!

8. 파일 서버 문제: 적절한 고유키 경우의 수

이제 잘못된 걸 알았으니, 적절한 k의 수를 정해봅시다.

파일의 총 개수인 n은, 현실적으로 10배 늘린 50,000개로 생각해보겠습니다.

이 문제를 풀고 있는 이유는, 파일을 링크로 공유하기 위함이었습니다.

링크로 사용하기 용이한 문자는 사실 정해져 있습니다.

“ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_”

이 문자들이 URL에서 사용하기 안전한 문자들입니다.

모두 64글자구요, base64 라고도 불러요.

한 문자 당 64가지의 가짓수를 가집니다.

문자가 6개 있으면, 64^6 = 64*64*64*64*64*64 개의 가짓수가 있다는 뜻이죠. (68,719,476,736 가지)

굉장히 많죠?

그럼 다시, 50,000개 파일의 경우에 길이가 몇인 문자열로 링크를 만들어야 적절한 걸까요?

아까 만든 식을 토대로 계산을 돌려보겠습니다.

n - 파일의 개수, k - 고유키의 경우의 수
match_prob(n, k) - 일반화된 (n, k) 생일 문제의 계산 결과 (하나라도 겹칠 확률 %)

match_prob(50,000, 64^5) = 68.781%
match_prob(50,000, 64^6) = 1.803%
match_prob(50,000, 64^7) = 0.028%
match_prob(50,000, 64^8) = 0.000444%
match_prob(50,000, 64^9) = 0.00000694%
match_prob(50,000, 64^10) = 0.000000108%

고유키가 8자리 정도는 되어야 매우 낮은 확률이 되는 걸 알 수 있습니다.

고작(?) 50,000개의 파일을 저장하는데도요.

그래서, 연구실 파일 서버의 파일 고유키 길이는 10개로 결정됐습니다.

8개나 10개나 큰 차이 없는 길이고,

8개의 0.000444% 도 혹여나 겹치기엔 높은 확률이라 생각해서요. (9는 왠지 딱 안 떨어져서 싫습니다.)

0.000000108% 확률로 고유키가 겹칠 확률은 아마 없겠죠? 그 날은 연구실 전체 로또 사는 날입니다.

9. 유튜브의 문제: 유튜브의 영상 개수

드디어 유튜브의 경우로 문제를 바꿔봅시다.

base64 기준으로 유튜브 링크는 11자리니 k는 64^11 입니다.

n은 유튜브에 올라간 영상의 개수겠죠.

정확하진 않지만 단순 무식하게 최대치로 계산해보겠습니다.

1분에 500시간 분량의 영상 업로드 (https://blog.youtube/press/)
영상 당 평균 11.7분 (https://www.statista.com/statistics/1026923/)
분 당 500 * 60 / 11.7 = 약 2,564개. 1년엔 1,347,692,307개. (13억 개)
유튜브 역사가 18년 됐으니 단순 곱셈을 하면,
대략 242억개네요! (24,258,461,538개) (정확한 개수는 공개되어 있지 않습니다.)

n = 24,258,461,538 / k = 64^11 을 식에 넣어볼까요?

match_prob(24,258,461,538, 64^11) = 98.146%

어? 고유키가 겹칠 확률이 98.146%로 생각보다 높네요?

영상이 분 당 2천 개가 올라가는데, 무조건 겹칠 겁니다!

네. 무조건 하나 이상은 겹칩니다.

하지만, 유의할 것은 이 확률은 “지금까지 올라온 242억 개 고유키 중 하나라도 겹칠 확률” 입니다.

242억 개 키 중 딱 하나가 겹치는 건 사실 괜찮죠.

그때만 딱 한 번 더 뽑으면 되니까요. (제 파일 서버는 그게 귀찮아서 그냥 냅다 크게 한 겁니다!)

그래서, 실제로 고려해야 할 건 242억 개 중 몇 개가 겹칠 것인가? 입니다.

그 수가 충분히 작다면, 그냥 그때마다 다시 뽑아주면 되잖아요?

10. 생일 문제의 변형: 몇 개가 겹칠까요?

유튜브의 242억 개 영상으로 생각하면 골치가 아프니, 다시 생일 문제로 돌아갑시다.

나 포함 5명이 있을 때, 나와 생일이 겹치는 사람이 한 명이라도 존재할 확률은 다시 여사건을 사용합니다.

“1 – (아무도 내 생일과 안 겹칠 확률)”

그리고, 아무도 내 생일과 겹치지 않을 확률은, 그 사람들끼리 서로 겹치든 말든 모두 나와 다르기만 하면 됩니다.

"내 생일"이 겹칠 확률이니까요. 따라서, 다음과 같은 식이 세워집니다.

내 생일을 제외한 364개에서 나머지 4명이 선택하면 되는 겁니다.

이 확률은 1.09% 입니다. 5명 중 한 명이라도 겹칠 확률(2.7%)보다는 낮죠. n, k가 커지면 차이는 더 극명해집니다.

앞선 식은, n = 5, k = 365 인 예시였고, 일반화 식은 다음과 같습니다.

이제, 어떤 한 고유키가 다른 고유키와 겹칠 확률을 구했습니다.

유튜브의 245억 개를 여기에 대입해보면, 약 0.0000000329% 입니다.

실제로 100,000개 무작위 링크를 입력해봤는데, 겹치지 않았습니다. 이 정도면 무작위 대입법은 소용없겠죠.

이제 이걸로 n개의 키 중 몇 개가 겹칠 것인지 예상하고 싶습니다.

아주 간단하게도, 위 식에 키의 개수인 n을 곱하면 됩니다.

느낌이 잘 안 오신다면,

확률이 10%인 로또를 100명이 사는 경우엔 평균적으로 10명이 당첨될 거란 걸 생각해보세요. (10% * 100명)

그러니, 겹칠(당첨) 확률이 p인 키가 n개 있으면, 평균 p * n 개가 겹치는 거죠.

이걸 통계학에서는 ‘기대값’이라는 개념으로 부릅니다.

이제 모든 식을 구했으니, 식 세우기는 그만하고 결론으로 나아가 봅시다!

11. 결론: 유튜브 영상 링크 길이가 11자리인 이유

자! 이제 저 식에 유튜브 문제의 n과 k를 대입해봅시다.

n – 영상의 개수, k - 고유키의 경우의 수
avg_key_match(n, k) - (n, k)일 때 평균적으로 겹치는 키의 개수

avg_key_match(242억, 64^11) = 7.98 개

우와! 18년 동안 242억 개의 영상이 올라온 유튜브는, 지금까지 총 8번 정도만 고유키를 다시 뽑으면 됐었겠네요.

만약, 영상 링크 길이가 달랐다면 어땠을까요?

avg_key_match(242억, 64^8) = 2,090,586 개
avg_key_match(242억, 64^9) = 32,667 개
avg_key_match(242억, 64^10) = 510 개

영상 링크 길이가 10 → 9 → 8로 짧아질수록 겹치는 숫자는 기하급수적으로 늘어납니다.

그리고, 길이가 10개일 때도 18년 동안 510번이면 사실 그렇게 많진 않죠? 안정적으로 보입니다.

하지만, 유튜브는 앞으로도 더 많은 영상들이 올라올 겁니다.

앞으로 100년 더, 118년 간 대충 5천억 개의 영상이 올라갈 가능성을 생각해봅시다.

avg_key_match(5천억, 64^8) = 887,390,026 개
avg_key_match(5천억, 64^9) = 13,877,595 개
avg_key_match(5천억, 64^10) = 216,840 개
avg_key_match(5천억, 64^11) = 3,388 개
avg_key_match(5천억, 64^12) = 53 개