중앙 발급기가 탈락한 이유는 왕복이었습니다. 왕복을 없애는 가장 단순한 방법은 아무에게도 묻지 않고 아주 큰 무작위 값을 뽑는 것입니다.
충돌하지 않는 이유
값의 범위가 충분히 크면 두 번 같은 값이 나올 확률이 무시할 만큼 작아집니다. 128비트 규모에서는 하루 86억 건을 수십 년 뽑아도 충돌 확률이 사실상 0입니다.
이것은 확률에 기대는 보장입니다. 구조로 막는 것과 다르지만, 확률이 충분히 작으면 실무에서는 같은 값으로 취급합니다. 무작위성이 나쁜 생성기를 쓰면 이 전제가 깨지므로 그 부분만 주의합니다.
얻는 것과 잃는 것
| 항목 | 내용 |
|---|---|
| 얻는 것 | 왕복 0. 조율 0. 노드 수 제한 없음. 구현이 가장 단순 |
| 잃는 것 | 크기가 두 배. 시간순 정렬이 없음 |
크기가 요구사항 64비트 를 어깁니다. 그리고 정렬이 없으므로 앞 단계에서 본 삽입 비용 문제가 그대로 생깁니다.
두 대가는 서로 다른 무게다
크기는 저장과 인덱스 메모리를 두 배로 만듭니다. 아프지만 계산 가능한 비용입니다.
정렬이 없는 것이 더 무겁습니다. 삽입 위치가 흩어지면 쓰기가 느려지고, 그 영향은 데이터가 커질수록 나빠집니다. 인덱스가 메모리에 다 들어가는 규모에서는 차이가 작지만, 넘어가는 순간 급격히 벌어집니다.
앞부분에 시각을 넣는 변형
무작위 값의 앞부분을 시각으로 바꾸면 정렬을 되찾을 수 있습니다. 뒷부분은 그대로 무작위로 둡니다.
앞: 시각. 시간순으로 커진다
뒤: 무작위. 같은 순간의 충돌을 확률로 막는다
이 방식은 정렬과 조율 없음을 함께 얻습니다. 크기는 여전히 크지만 요구사항이 크기를 강하게 제한하지 않는다면 좋은 선택입니다. 실제로 많이 쓰입니다.
이 요구사항에서는 크기가 발목을 잡는다
64비트 정수 요구가 남아 있습니다. 무작위 부분을 줄여 64비트에 맞추면 충돌 확률이 급격히 올라갑니다. 초당 10만 규모에서 확률에 기대기에는 여유가 부족합니다.
그래서 다음 단계에서 무작위를 쓰지 않고 유일성을 구조로 얻는 방법을 봅니다. 같은 순간에 같은 값이 나올 수 없도록 칸을 나눠 쓰는 방식입니다.