GUID 충돌 가능합니까?

GUID 충돌 가능합니까?

SQL Server 2000에서 연결된 앱을 사용하는 사용자별로 GUID를 사용하는 데이터베이스를 만들고 있습니다.어찌된 일인지 두 사용자가 동일한 GUID를 갖게 되었습니다.Microsoft가 알고리즘을 사용하여 콜리전을 일으킬 가능성이 매우 낮은 랜덤 GUID를 생성하는 것은 알고 있습니다만, 그래도 충돌은 가능한 것입니까?

기본적으로, 아니다.누군가 당신 데이터베이스를 만지작거린 것 같아요사용하는 GUID 버전에 따라 값이 고유하거나(버전 1 GUID와 같은 경우), 고유하고 예측 불가능한(버전 4 GUID와 같은 경우) 둘 중 하나입니다.SQL Server의 NEWID() 함수에 대한 구현에서는 128비트 난수를 사용하는 것으로 나타나므로 충돌이 발생하지 않습니다.

충돌 확률이 1%인 경우 약 2,600,000,000,000,000,000의 GUID를 생성해야 합니다.

기본적으로 그것들은 가능하지 않다! 가능성은 천문학적으로 낮다.

하지만... 내가 아는 이 세상에서 GUID 콜리젼을 가진 사람은 나밖에 없어.

그건 실수가 아니라고 확신해요

Pocket PC에서 실행되고 있던 소규모 어플리케이션에서는 동작의 마지막에 GUID가 생성된 명령어를 발행해야 합니다.서버에서 실행된 명령어는 실행 날짜와 함께 서버의 명령어테이블에 저장됩니다.어느 날 디버깅을 할 때 새로 생성된 GUID를 사용하여 module 명령어를 발행했지만 아무 일도 일어나지 않았습니다.(동일한 GUID를 사용하여 작업을 시작할 때 GUID가 한 번만 생성되었기 때문에) 다시 한 번 실행했지만, 명령어가 실행되지 않는 이유를 찾기 위해 마지막으로 명령어 테이블을 확인했는데, 현재와 같은 GUID가 3주 전에 삽입되었습니다.믿을 수 없어서 2주간의 백업에서 데이터베이스를 복원했더니 GUID가 있었습니다.코드를 확인했더니 새로운 GUID가 새로 생성되었습니다.POW guid 충돌은 딱 한 번 일어났지만, 그 대신 로또에 당첨됐으면 좋았을 텐데, 가능성이 더 커. :)

편집: 이 문제가 발생할 가능성을 크게 높일 수 있는 몇 가지 요인이 있습니다.어플리케이션은 포켓에서 실행되고 있었습니다.PC 에뮬레이터 및 에뮬레이터에는 저장 상태 기능이 있습니다.즉, 상태가 복원될 때마다 로컬 시간도 복원되고 GUID는 내부 타이머에 기반합니다.또한 콤팩트 프레임워크의 GUID 생성 알고리즘은 COM 에 비해 완전하지 않을 수 있습니다.

이론적으로는 가능하지만 3.4E38의 경우 연간 수십조 개의 GUID를 생성하면 중복되는 GUID가 1개 발생할 확률은 0.000000006(소스)입니다.

만약 두 명의 사용자가 같은 GUID를 갖게 된다면, 그 프로그램에서 데이터가 복사되거나 공유되는 버그가 있다고 장담합니다.

당신은 수학자입니까?그럼 네.

당신은 엔지니어입니까?그럼 안 돼요.

먼저 두 GUID의 충돌 가능성을 살펴봅시다. 생일 역설 때문에 다른 답변에서 말한 것처럼 2^128분의 1(10^38)이 아닙니다. 즉, 두 GUID가 충돌할 확률은 실제로 2^64분의 1(10^19)로 훨씬 작습니다.그러나 이는 여전히 매우 큰 수치이기 때문에 적당한 수의 GUID를 사용하고 있다고 가정할 때 충돌할 가능성은 낮습니다.

또한 GUID에는 타임스탬프나 MAC 주소가 포함되어 있지 않은 것으로 생각됩니다.이는 v1 GUID의 경우에도 마찬가지였지만 현재는 v4 GUID가 사용되고 있습니다.이는 단순히 의사 난수이기 때문에 시간 및 기계에 더 이상 고유하지 않기 때문에 충돌 가능성이 높다는 것을 의미합니다.

따라서 기본적으로 충돌 가능성이 있습니다.하지만 그럴 가능성은 매우 낮습니다.

편집: 2^64로 수정

2개의 랜덤 GUID가 충돌할 가능성(10^38 중~1)은 파손된TCP/IP 패킷을 검출하지 않을 가능성(10^10 중~1)보다 낮습니다.http://wwwse.inf.tu-dresden.de/data/courses/SE1/SE1-2004-lec12.pdf, 페이지 11.이는 디스크 드라이브, CD 드라이브 등에도 해당됩니다.

GUID는 통계적으로 고유하며 DB에서 읽은 데이터는 통계적으로만 정확합니다.

이 경우 Occam의 면도기가 좋은 가이드라고 생각합니다.GUID 충돌이 발생할 가능성은 매우 낮습니다.버그나 누군가가 당신의 데이터를 조작하고 있을 가능성이 훨씬 더 높습니다.

Wikipedia의 Global Unique Identifier 문서를 참조하십시오.GUID를 생성하는 방법에는 여러 가지가 있습니다.기존(?) 방식은 Mac 주소, 매우 짧은 단위까지의 타임스탬프, 고유 카운터(같은 컴퓨터상의 고속 세대 관리를 위해)를 사용했기 때문에 복제하는 것은 거의 불가능합니다.하지만 이 GUID는 사용자를 추적하는 데 사용될 수 있기 때문에 삭제되었습니다.

Microsoft가 사용하는 새로운 알고리즘에 대해서는 잘 모르겠습니다(기사에서는 일련의 GUID를 예측할 수 있다고 합니다만, 타임스탬프를 사용하지 않게 된 것 같습니다).위에 링크된 Microsoft 기사에는 다른 내용이 기재되어 있습니다.

GUID는 이름 그대로 글로벌하게 고유하도록 세심하게 설계되어 있기 때문에 불가능하거나 매우 낮은 확률의 위험을 감수해야 합니다.다른 곳을 찾겠어요.

MAC 주소가 중복된 이더넷카드를 탑재한2대의 Win95 머신은 엄격하게 제어된 조건하에서 중복 GUIDS를 발행합니다.특히 건물 내에서 전원이 차단되어 양쪽이 정확히 동시에 기동하는 경우 등입니다.

GUID는 마법적이고 독특함을 보증한다는 기분 좋은 답변을 좋아하는 사람들은 알지만, 실제로는 대부분의 GUID는 121비트의 랜덤 숫자일 뿐입니다(포맷에 7비트가 낭비됩니다).큰 난수를 사용하는 것이 불편하다면 GUID를 사용하는 것이 불편할 것입니다.

저는 인맥을 쌓는 사람이 아니기 때문에 앞뒤가 전혀 맞지 않는 문장을 만들 수 있습니다.

일리노이 주립대학에서 일할 때, 델의 데스크탑은 2대씩 다른 시기에 주문되어 있었습니다.첫 번째 것을 네트워크에 연결했는데 두 번째 것을 네트워크에 연결하려고 하면 엉뚱한 오류가 발생하기 시작했습니다.많은 트러블 슈팅을 실시한 결과, 양쪽의 머신이 같은 GUID를 생성하고 있는 것이 판명되었습니다(정확한 용도는 알 수 없지만, 양쪽 모두를 네트워크상에서 사용할 수 없게 되었습니다).Dell은 실제로 두 기계 모두 결함이 있어 교체했다.

일반화 공식

확률 P를 가진 두 값 사이에 충돌을 일으키기 위해 얼마나 많은 S 크기의 값을 생성해야 하는지 추정하는 공식이 있습니다.

변수:

• bits - 데이터 유형의 비트 수입니다.
• 확률 - 충돌의 목표 확률입니다.

충돌을 일으키려면 다음을 생성해야 합니다.

또는 Python의 경우:

from math import sqrt, log

def how_many(bits, probability):
    return 2 ** ((bits + 1) / 2) * sqrt(-log(1 - probability))

GUID

GUID(128비트)의 경우 확률 1%(0.01)와 충돌하려면 다음이 필요합니다.

In [2]: how_many(bits=128, probability=0.01)
Out[2]: 2.6153210405530885e+18

약 2.6 * 10^18 GUID (42 엑사바이트의 GUID)

이 확률은 급속히 증가한다는 점에 주의해 주세요.비트 수에 관계없이 99.99%의 확률로 1%의 GUID보다 30배 많은 GUID만 필요합니다.

In [3]: how_many(bits=128, probability=0.9999)
Out[3]: 7.91721721556706e+19

Int64

같은 번호이지만 int64 데이터 타입의 경우:

In [4]: how_many(bits=64, probability=0.01)
Out[4]: 608926881

In [5]: how_many(bits=64, probability=0.9999)
Out[5]: 18433707802

충돌 확률을 1%로 하려면 5기가바이트의 int64-s가 필요합니다.아직 많이 있지만 GUID에 비하면 훨씬 더 이해하기 쉬운 수치입니다.

---

이것은 소위 생일 문제이며, 이 위키피디아 기사에서는 이것보다 더 정확한 추정 공식을 찾을 수 있습니다.

GUID 생성에 사용되는 코드에 버그가 있을 수 있습니까?네, 물론 그럴 수 있죠.하지만 정답은 컴파일러 버그와 같습니다.자신의 코드는 버그가 발생할 가능성이 큰 순서이기 때문에, 우선 그것을 봐 주세요.

물론 가능합니다.그럴 것 같아?그럴 것 같진 않지만, 가능해요.

같은 머신이 모든 GUID(서버)를 생성하고 있기 때문에 머신 고유의 정보에 근거하는 「랜덤성」의 대부분이 없어집니다.

웃으면서 다음 대본을 써보세요.(SQL 2005에서 동작합니다.2000은 확실하지 않습니다)

declare @table table
(
    column1 uniqueidentifier default (newid()),
    column2 int,
    column3 datetime default (getdate())
)

declare @counter int

set @counter = 1

while @counter <= 10000
begin
    insert into @table (column2) values (@counter)
    set @counter = @counter + 1
end

select * from @table

select * from @table t1 join @table t2 on t1.column1 = t2.column1 and t1.column2 != t2.column2

이 작업을 반복하면(1초 미만이 소요됨) 매우 짧은 시간 간격에도 불구하고 첫 번째 선택부터 상당히 넓은 범위가 생성됩니다.지금까지 두 번째 선정작은 아무 것도 생산하지 않았다.

사용자가 네트워크 카드를 사용하는 다른 머신을 가지고 있는 경우는 불가능하며, 그렇지 않은 경우에도 이론상으로는 극히 미미한 리스크입니다.

개인적으로는 GUID 충돌보다는 버그일 가능성이 높기 때문에 다른 곳을 찾고 싶습니다.

물론 GUID를 짧게 하기 위해 일부를 잘라내지 않도록 합니다.

GUID GUID GUID와 같은 NEWID()SQL Server에서 기능합니다(물론 다른 답변에서 강조했듯이 가능하지만).그들이 지적하지 않은 것 중 하나는 당신이 야생의 브라우저에서 JavaScript에서 GUID를 생성한다면 실제로 충돌에 직면할 가능성이 높다는 것이다.브라우저마다 RNG에 문제가 있을 뿐만 아니라 구글 스파이더들이 그런 기능의 결과를 캐싱하는 것 같은 문제에 부딪혀 같은 GUID를 반복하여 시스템에 전달합니다.

상세한 것에 대하여는, 여기를 참조해 주세요.

JavaScript에서 UUID를 생성할 때 충돌이 발생합니까?

그게 뭔지 신경 쓰지 마세요.불가능하게 만들어라.GUID의 개연성과 시퀀셜의 개연성을 혼합합니다.GUID에 데이터베이스 시퀀셜 I를 추가하고 완료라고 부르기만 하면 됩니다.데이터 유형을 GUID에서 String-ish로 변경해야 할 수도 있지만 스토리지 유형도 크게 다르지 않습니다.

물론 그럴 수도 있고, 어쩌면 그럴 수도 있죠.각 GUID가 가능한 숫자 공간의 랜덤 부분에 있는 것은 아닙니다.두 개의 스레드가 하나의 스레드를 동시에 생성하려고 하면 세마포어 주위에 세마포어가 있는 중앙 집중형 GUID 함수가 없으면 같은 값이 될 수 있습니다.

언급URL : https://stackoverflow.com/questions/184869/are-guid-collisions-possible