Java의 UUID.randomUUID는 얼마나 좋습니까?

Java의 UUID.randomUUID는 얼마나 좋습니까?

---

무작위 UUID 는 이론상으로 충돌 가능성이 매우 낮다는 것을 알고 있지만 실제로 randomUUID()충돌이 없다는 측면에서 Java가 얼마나 좋은지 궁금합니다 . 누구든지 공유 경험이 있습니까?

---

UUID는 java.security.SecureRandom"암호 적으로 강력"해야하는을 사용합니다. 실제 구현이 지정되어 있지 않고 JVM마다 다를 수 있지만 (구체적인 진술은 하나의 특정 JVM에만 유효 함을 의미) 출력은 통계적 난수 생성기 테스트를 통과해야합니다.

구현에 항상이 모든 것을 망치는 미묘한 버그가 포함될 수는 있지만 (OpenSSH 키 생성 버그 참조) Java UUID의 임의성에 대해 걱정할 구체적인 이유는 없다고 생각합니다.

---

위키 백과는 http://en.wikipedia.org/wiki/Universally_unique_identifier#Collisions

적어도 하나의 충돌의 50 % 확률을 갖기 위해 생성되어야하는 랜덤 버전 4 UUID의 수는 2.71 퀴 틸리 온이며, 다음과 같이 계산된다 :

...

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

...

따라서 10 억 번의 중복 가능성이 발생하려면 103 조 버전 4 UUID를 생성해야합니다.

---

누구든지 공유 경험이 있습니까?

2^122유형 4 UUID에 가능한 값 이 있습니다. (사양에 따르면 유형의 경우 2 비트, 버전 번호의 경우 4 비트가 손실됩니다.)

초당 1 백만 개의 임의 UUID를 생성한다고 가정하면 일생 동안 중복이 발생할 가능성은 거의 없습니다. 그리고 중복을 감지, 당신은에 대해 초당 1 백만 새 UUID를 비교하는 문제를 해결해야 할 것 이전에 생성 한 UUID가 모든 ^일을 !

실제 생활에서 복제본을 경험 한 사람 (즉, 실제로 눈에 띄는 ) 의 가능성은 실제로 작은 충돌보다 더 작습니다. 충돌을 찾는 실질적인 어려움 때문입니다.

물론, 실제로는 난수 생성기가 아닌 의사 난수 생성기를 사용하게됩니다. 그러나 암호화 강도 난수에 신용 제공 업체를 사용하는 경우 암호화 강도 가 될 것이며 반복 확률은 이상적인 (편견이없는) 난수 생성기와 동일 할 것이라고 확신 할 수 있습니다 .

그러나 "깨진"암호 난수 생성기와 함께 JVM을 사용하는 경우 모든 베팅이 해제됩니다. (그리고 여기에는 일부 시스템에서 "엔트로피 부족"문제에 대한 해결 방법이 포함되어있을 수도 있습니다. 또는 누군가가 시스템이나 업스트림에서 JRE에 영향을 줄 가능성이 있습니다.)

---

^{1-익명의 주석자가 제안한대로 "일종의 이진 btree"를 사용했다고 가정하면, 각 UUID에는 O(NlogN)비트의 N저밀도 및 랜덤 분포를 가정 하여 별개의 UUID 를 나타 내기 위해 약간의 RAM 메모리가 필요 합니다. 이제 1,000,000과 실험을 시작할 초 수를 곱하십시오. 고품질 RNG의 충돌을 테스트하는 데 필요한 시간 동안 실용적이지 않다고 생각합니다. (가설적인) 영리한 표현조차도 아닙니다.}

---

나는 전문가는 아니지만 충분한 똑똑한 사람들이 수년 동안 Java의 난수 생성기를 보았을 것이라고 가정합니다. 따라서 임의의 UUID가 좋다고 가정합니다. 따라서 이론상 충돌 확률이 있어야합니다 ( 가능한 모든 UUID의 경우 약 1 : 3 × 10 ^ 38 입니다. 임의의 UUID에 대해서만이 변경이 어떻게되는지 아는 사람이 있습니까? 1/(16*4)위의 것입니까?)

실제 경험상 지금까지 어떤 충돌도 보지 못했습니다. 나는 내가 나의 첫번째 것을 얻는 날에 놀랍게도 긴 수염을 자랐을 것이다;)

---

전 고용주에서 우리는 임의의 UUID를 포함하는 고유 한 열을 가졌습니다. 배포 후 첫 주에 충돌이 발생했습니다. 물론, 확률은 낮지 만 제로가 아닙니다. 그래서 Log4j 2에 UuidUtil.getTimeBasedUuid가 포함되어 있습니다. 단일 서버에서 10,000 개 이상의 UUID / 밀리 초를 생성하지 않는 한 8,925 년 동안 고유 한 UUID를 생성합니다.

---

UUID의 원래 생성 체계는 UUID를 생성하는 컴퓨터의 MAC 주소와 서부 그레고리력 채택 이후 100 나노초 간격으로 UUID 버전을 연결하는 것이 었습니다. 공간 (컴퓨터)과 시간 (간격 수)의 단일 지점을 나타내면 값 충돌 가능성이 거의 없습니다.

---

많은 답변에서 충돌 가능성이 50 %에 도달하기 위해 얼마나 많은 UUID를 생성해야하는지에 대해 설명합니다. 그러나 50 %, 25 % 또는 1 %의 충돌 확률은 충돌이 (가상적으로) 불가능한 응용 프로그램에는 가치가 없습니다.

프로그래머는 일상적으로 발생할 수 있고 발생할 수있는 다른 이벤트를 "불가능"한 것으로 기각합니까?

디스크 나 메모리에 데이터를 쓰고 다시 다시 읽을 때 데이터가 정확하다는 것을 당연한 것으로 생각합니다. 우리는 손상을 감지하기 위해 장치의 오류 수정에 의존합니다. 그러나 감지되지 않은 오류의 가능성은 실제로 약 ^2-50 입니다.

임의의 UUID에 유사한 표준을 적용하는 것이 합리적이지 않습니까? 그렇게하면 약 1000 억 개의 임의 UUID (2 ^36.5 ) 모음에서 "불가능"충돌이 발생할 수 있습니다 .

이는 천문학적 수치이지만 국가 의료 시스템의 항목 별 청구 또는 많은 장치에서 고주파수 센서 데이터 로깅과 같은 애플리케이션은 이러한 한계에 부딪 칠 수 있습니다. Galaxy에 다음 Hitchhiker 's Guide를 작성하는 경우 각 기사에 UUID를 할당하지 마십시오!

---

나는 작년에 복권에서 놀았는데 결코 이겼지 않았습니다 ....하지만 복권에 승자가있는 것 같습니다 ...

의사 : http://tools.ietf.org/html/rfc4122

유형 1 : 구현되지 않았습니다. UUID가 동시에 생성되면 충돌이 가능합니다. 이 문제를 우회하기 위해 impl을 인위적으로 a- 동기화 할 수 있습니다.

유형 2 : 구현을 보지 못했습니다.

유형 3 : md5 해시 : 충돌 가능 (128 비트 -2 기술 바이트)

유형 4 : 랜덤 : 충돌 가능 (복권으로). PRNG 알고리즘은 개발자가 선택하지 않으며 시스템이 "가난한"PRNG 알고리즘을 사용하도록 할 수 있기 때문에 jdk6 impl은 "true"보안 무작위를 사용하지 않습니다. 따라서 UUID는 예측 가능합니다.

유형 5 : sha1 해시 : 구현되지 않음 : 충돌 가능 (160 비트 -2 기술 바이트)

---

대부분의 답변은 이론에 초점을 두었 기 때문에 제가 실제로 한 시험을 통해 토론에 무언가를 추가 할 수 있다고 생각합니다. 내 데이터베이스에는 Java 8 UUID.randomUUID ()를 사용하여 생성 된 약 450 만 개의 UUID가 있습니다. 다음은 내가 찾은 것입니다.

c0f55f62 -b990-47bc-8caa-f42313669948

c0f55f62 -e81e-4253-8299-00b4322829d5

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

b9ea2498-fb32-40ef-91ef-0ba 00060fe64

be87a209-2114-45b3-9d5a-86d 00060fe64

4a8a74a6-e972-4069-b480-b dea1177b21f

12fb4958-bee2-4c89-8cf8-e dea1177b21f

실제로 무작위라면, 450 만 항목 만 고려하고 있기 때문에 이러한 종류의 유사한 UUID를 가질 확률은 상당히 낮습니다 (편집 참조). 이 기능이 없습니다 가진 충돌의 측면에서, 좋은 있지만, 그래서, 나를 위해, 그것은하지 않는 것 이 이 이론에있을 것 같은 좋은.

편집 :

많은 사람들이이 답변을 이해하지 못하는 것 같아서 요점을 명확히 할 것입니다. 유사성이 "작고"완전 충돌과는 거리가 멀다는 것을 알고 있습니다. 그러나 Java의 UUID.randomUUID ()를 실제 난수 생성기와 비교하고 싶었습니다. 실제 질문입니다.

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

공식은이 위키 기사 en.wikipedia.org/wiki/Birthday_problem에서 설명됩니다.

---

우리는 애플리케이션에서 Java의 임의 UUID를 1 년 이상 사용해 왔으며 그 기간은 매우 광범위했습니다. 그러나 우리는 결코 충돌을 겪지 않습니다.

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