Java의 UUID.randomUUID는 어느 정도 우수합니까?

Java의 UUID.randomUUID는 어느 정도 우수합니까?

이론상으로는 랜덤화된 UUID가 충돌할 확률이 매우 낮다는 것은 알고 있습니다만, 실제로는 Java가 충돌을 일으키지 않는 것이 얼마나 좋은 것일까요?혹시 경험하신 분 계신가요?

UUID 에서는, 「암호학적으로 강력」하다고 생각되는 것을 사용합니다.실제 실장은 지정되어 있지 않고 JVM마다 다를 수 있지만(구체적인 스테이트먼트는 1개의 특정 JVM에 대해서만 유효합니다), 출력은 통계적 난수 생성 테스트를 통과해야 합니다.

구현에 이 모든 것을 망치는 미묘한 버그가 포함되는 것은 항상 가능하지만(OpenSSH 키 생성 버그 참조), Java UUID의 랜덤성을 걱정할 구체적인 이유는 없다고 생각합니다.

위키피디아는 매우 좋은 답변을 가지고 있다. http://en.wikipedia.org/wiki/Universally_unique_identifier#Collisions

적어도 1개의 충돌이 발생할 확률을 50%로 하기 위해 생성해야 하는 랜덤버전 4 UUID의 수는 2.71조5천억으로 다음과 같이 계산됩니다.

...

이 수치는 약 85년 동안 초당 10억 개의 UUID를 생성하는 것과 같으며, UUID당 16 바이트로 이 많은 UUID를 포함하는 파일은 약 45 엑사바이트로, 현재 존재하는 가장 큰 데이터베이스인 수백 페타바이트보다 몇 배 더 큽니다.

...

따라서 복제 가능성이 10억분의 1이 되려면 103조 버전4 UUID를 생성해야 합니다.

혹시 경험하신 분 계신가요?

있다2^122type-4 UUID의 가능한 값(스펙에서는 type의 경우 2비트, 버전 번호의 경우 4비트가 손실된다고 되어 있습니다).

초당 100만 개의 랜덤 UUID를 생성한다고 가정하면 라이프 타임에 중복이 발생할 가능성은 매우 낮아집니다.중복을 검출하려면 이전에 생성한¹ 모든 UUID와 초당 100만 개의 새로운 UUID를 비교하는 문제를 해결해야 합니다.

충돌을 찾는 것이 현실적으로 어렵기 때문에 누구나 실제로 복제품을 경험했을 가능성은 사라질 정도로 작습니다.

물론 일반적으로는 진짜 난수의 소스가 아닌 의사 난수 생성기를 사용합니다.단, 암호 강도의 난수에 대해 신뢰할 수 있는 프로바이더를 사용하고 있다면 암호 강도는 암호 강도로, 반복 발생 확률은 이상적인(편향되지 않은) 난수 발생기와 같을 것이라고 확신합니다.

단, JVM을 "파손된" 암호 난수 생성기와 함께 사용하는 경우 모든 베팅이 중지됩니다(일부 시스템의 "엔트로피 부족" 문제에 대한 회피책 중 일부가 포함될 수 있습니다).또는 시스템 또는 업스트림 중 하나에서 누군가가 JRE를 만졌을 가능성이 있습니다.)

---

^{1 - 익명의 코멘터가 제안한 대로 "모종의 바이너리 btree"를 사용했다고 가정하면 각 UUID가 필요합니다.O(NlogN)나타낼 RAM 메모리의 비트N비트의 저밀도 랜덤 분포를 전제로 하는 고유 UUID.여기에 100만 분의 1을 곱하고 실험을 실행할 초수를 곱합니다.나는 그것이 고품질 RNG의 충돌을 테스트하는 데 필요한 시간 동안 실용적이지 않다고 생각한다. 심지어 (가상의) 영리한 표현도 그렇다.}

저는 전문가는 아니지만, 몇 년 동안 자바의 난수 생성기를 살펴본 똑똑한 사람들은 충분하다고 생각합니다.따라서 랜덤 UUID도 좋다고 생각합니다.따라서 이론적인 충돌 확률(가능한 모든 UUID에 대해 약 1:3 × 10^38)이 필요합니다.랜덤 UUID에 대해서만 이것이 어떻게 변화하는지 아는 사람이 있습니까?그런가요?1/(16*4)(상기의)

실제 경험상 지금까지 충돌은 본 적이 없습니다.처음 수염을 기른 날이면 턱수염을 엄청나게 길렀을 거예요;)

전 고용주에서는 랜덤 UUID를 포함하는 고유한 컬럼이 있었습니다.배치 후 첫 주에 충돌이 있었습니다.네, 가능성은 낮지만 0은 아닙니다.따라서 Log4j 2에는 UuidUtil.getTimeBasedUuid가 포함되어 있습니다.단일 서버에서 생성되는 UUID가 밀리초당 10,000개를 넘지 않는 한 8,925년간 고유한 UUID가 생성됩니다.

UUID의 원래 생성 방식은 UUID 버전을 UUID를 생성하는 컴퓨터의 MAC 주소와 서양에서 그레고리력이 채택된 이후 100나노초 간격으로 연결하는 것이었습니다.공간(컴퓨터)과 시간(구간수)의 단일점을 나타냄으로써 값 충돌 가능성이 사실상 0이 됩니다.

대부분의 답변에서는 충돌 확률이 50%에 도달하기 위해 생성해야 하는 UUID 수에 대해 설명합니다.그러나 충돌이 (실질적으로) 불가능해야 하는 애플리케이션에서는 충돌 확률이 50%, 25%, 심지어 1%인 것은 가치가 없습니다.

프로그래머들은 발생할 수 있고 실제로 일어날 수 있는 다른 사건들을 "불가능한" 것으로 일상적으로 치부하고 있습니까?

디스크나 메모리에 데이터를 쓰고 다시 읽으면 데이터가 올바른 것으로 간주됩니다.파손을 검출하려면 , 디바이스의 에러 수정에 의존합니다.그러나 검출되지 않은 에러의 가능성은 실제로는 약^-50 2입니다.

랜덤 UUID에도 비슷한 표준을 적용하는 것이 타당하지 않을까요? 적용한다면 약 1,000억 개의 랜덤 UUID 컬렉션에서 "불가능한" 충돌이 발생할 수 있습니다(2^36.5).

이는 천문학적인 수치이지만, 국가 의료 시스템의 항목별 과금이나 대규모 장치의 고주파 센서 데이터 기록과 같은 애플리케이션은 분명 이러한 한계에 부딪힐 수 있습니다.다음 갤럭시 히치하이커 가이드를 작성하려면 각 기사에 UUID를 할당하지 마십시오.

작년에 복권에 당첨된 적은 없지만 복권에는 당첨자가 있는 것 같아요.

문서 : https://www.rfc-editor.org/rfc/rfc4122

타입 1 : 실장되어 있지 않습니다.UUID가 동시에 생성되면 충돌이 발생할 수 있습니다.incl은 이 문제를 회피하기 위해 인위적으로 a-synchronize 할 수 있습니다.

타입 2 : 실장은 표시되지 않습니다.

타입 3 : md5 hash : collision 가능 (128비트-2 테크니컬바이트)

타입 4 : 랜덤 : 충돌 가능성(추첨).jdk6에서는 PRNG 알고리즘은 개발자에 의해 선택되지 않으며 시스템에 PRNG algo를 강제로 사용하도록 할 수 있기 때문에 "true" 보안 랜덤을 사용하지 않습니다.따라서 UUID는 예측 가능합니다.

타입 5 : sha1 hash : 구현되지 않음 : 충돌 가능성 (160비트-2 테크니컬바이트)

대부분의 답변이 이론에 초점을 맞췄기 때문에 제가 했던 실제 테스트를 통해 토론에 무언가를 추가할 수 있을 것 같습니다.데이터베이스에는 Java 8 UUID.random을 사용하여 생성된 약 450만 개의 UUID가 있습니다.UUID(). 다음은 제가 발견한 일부입니다.

c0f55f62-b990-47bc-8caa-f42313669948

c0f55f62-e81e-4253-8299-00b4322829d5

c0f55f62-4979-4e87-8cd9-1c556894e2bb

b9ea2498-fb32-40ef-91ef-0ba00060fe64

be87a4124-45b3-9d5a-86d00060fe64

4a8a74a6-e972-4069-b4bc-bdea1177b21f

12fb4958-bee2-4c89-8cf8-edea1177b21f

만약 이것이 정말로 랜덤이었다면, 450만 엔트리에 대해서만 고려하고 있기 때문에, 이와 같은 유사한 UUID가 존재할 가능성은 상당히 낮습니다(편집 참조).그래서 이 기능은 좋지만 충돌하지 않는다는 점에서는 이론상으로는 별로인 것 같습니다.

편집:

많은 사람들이 이 대답을 이해하지 못하는 것 같기 때문에 요점을 명확히 하겠습니다.유사점이 "작고" 완전한 충돌과는 거리가 멀다는 것을 알고 있습니다.다만, Java의 UUID.random을 비교하고 싶을 뿐입니다.실제 질문인 True Random Number Generator를 사용하는 UUID()입니다.

진정한 난수 생성기에서, 마지막 사례가 발생할 확률은 약= 0.007%.그러므로, 나는 나의 결론이 옳다고 생각한다.

공식은 이 Wiki 기사 en.wikipedia.org/wiki/Birthday_problem에서 설명합니다.

1년 이상 어플리케이션에서 Java의 랜덤 UUID를 사용하고 있으며, 매우 광범위하게 사용되고 있습니다.하지만 우리는 충돌 사고를 당한 적이 없다.

언급URL : https://stackoverflow.com/questions/2513573/how-good-is-javas-uuid-randomuuid