2012-06-03 1 views
51

나는 man 페이지를 읽었지만, 나는 무엇을과 namespace에 대한 것인지 알 수 없다.v5 UUID 생성. 이름과 네임 스페이스 란 무엇입니까?

버전 3 및 버전 5 UUID의 경우 추가 명령 줄 인수 네임 스페이스 및 이름을 지정해야합니다. 네임 스페이스는 문자열 표현의 UUID 또는 내부적으로 미리 정의 된 네임 스페이스 UUID (현재 "ns : DNS", "ns : URL", "ns : OID"및 "ns : X500")에 대한 식별자입니다. . 이름은 임의의 길이의 문자열입니다.

네임 스페이스 :

네임 스페이스 어딘가에와 관련된 문자열 표현의 UUID 또는

그것이 내가 (UUID의 V4) 저장할 필요가 있음을 뜻 중 하나입니다 생성 된 UUID v5? 두 경우 모두 왜 자동으로 수행되지 않습니까?

이름은 임의의 길이의 문자열입니다.

name 완전히 임의의 문자열? 그러면 그 목적은 무엇입니까? UUID v5에서 디코딩 할 수 있습니까?

답변

46

이름 및 네임 스페이스를 사용하여 고유 한 UUID의 계층 구조를 만들 수 있습니다.

유형 3 또는 유형 5 UUID는 이름 공간 식별자를 이름과 함께 해시함으로써 생성됩니다. 유형 3 UUID는 MD5를 사용하고 유형 5 UUID는 SHA1을 사용합니다. 128 비트 만 사용할 수 있으며 형식을 지정하는 데 5 비트가 사용되므로 모든 해시 비트가 UUID에 포함되지 않습니다. (또한 MD5는 암호 학적으로 손상된 것으로 간주되며 SHA1은 마지막 단계에 있으므로 "매우 안전해야"하는 데이터를 확인하는 데 사용하지 마십시오.) 다시 말해 계층 적 이름을 확률 적으로 고유 한 128 비트 값에 매핑하여 계층 적 해시 또는 MAC과 같이 작동하는 반복 가능하고 검증 가능한 "해시"함수를 만드는 방법을 제공합니다.

(키, 값) 저장소가 있지만 하나의 네임 스페이스 만 지원한다고 가정합니다. 유형 3 또는 유형 5 UUID를 사용하여 많은 수의 논리적 네임 스페이스를 생성 할 수 있습니다. 먼저 각 네임 스페이스에 대한 루트 UUID를 만듭니다. 어딘가에 숨겨 두는 한 유형 1 (호스트 + 타임 스탬프) 또는 유형 4 (랜덤) UUID 일 수 있습니다. 또는 루트에 대해 무작위 UUID를 만들거나 null UUID : 00000000-0000-0000-0000-000000000000을 루트로 사용하여 "uuid -v5 $ ROOTUUID $ NAMESPACENAME"을 사용하여 각 네임 스페이스에 대해 재현 가능한 UUID를 만들 수 있습니다. . 이제 "uuid -v5 $ NAMESPACEUUID $ KEY"를 사용하여 네임 스페이스 내의 키에 대해 고유 한 UUID를 만들 수 있습니다. 이러한 UUID는 충돌을 피할 확률이 높은 단일 키 - 값 저장소에 던져 질 수 있습니다. 이 프로세스는 재귀 적으로 반복 될 수 있습니다. 예를 들어 UUID 키와 연관된 "값"이 버킷, 컨테이너 또는 디렉토리와 같은 일종의 논리적 "네임 스페이스"를 나타내면 UUID를 차례로 사용하여 더 계층 적으로 생성 할 수 있습니다 UUID.

생성 된 유형 3 또는 유형 5 UUID는 네임 스페이스 ID 및 네임 스페이스 네임 스페이스 (키)의 (부분적인) 해시를 보유합니다. 그것은 더 이상 네임 스페이스 UUID를 보유하지 않습니다. 이것은 메시지 MAC이 인코딩 된 메시지의 내용을 보유하지 않습니다. 이름은 uuid 알고리즘의 관점에서 볼 때 "임의"(옥텟) 문자열입니다. 그러나 그 의미는 응용 프로그램에 따라 다릅니다. 논리 디렉토리 내의 파일 이름, 오브젝트 저장소 내의 오브젝트 ID 등일 수 있습니다.

매우 적은 수의 네임 스페이스와 키에 대해서는 잘 작동하지만 매우 높은 확률로 매우 많은 수의 고유 한 키를 목표로하는 경우 결국 성능이 떨어집니다. 생일 문제 (일명 생일 Paradox)에 대한 Wikipedia 항목에는 다양한 수의 키와 테이블 크기에 대해 적어도 하나의 충돌 확률을 제공하는 테이블이 포함되어 있습니다. 128 비트의 경우,이 방법으로 260 억 개의 키를 해싱하면 p = 10^-18 (무시할 수 있음)의 충돌 확률을 갖지만 26 조 키가 발생하면 적어도 하나의 충돌 확률이 p = 10^-12로 증가합니다 1 조), 26 * 10^15 개의 키를 해싱하면 적어도 하나의 충돌 가능성이 p = 10^-6 (백만 분의 1)으로 증가합니다. UUID 유형을 인코딩하는 5 비트를 조정하면 다소 빠르므로 1 조개의 키에 약 1 조개에 1 개의 충돌이 발생할 가능성이 있습니다.

확률 테이블은 http://en.wikipedia.org/wiki/Birthday_problem#Probability_table을 참조하십시오.

UUID 인코딩에 대한 자세한 내용은 http://www.ietf.org/rfc/rfc4122.txt을 참조하십시오.

106

유형 3 및 유형 5 UUID는 해시을 UUID에 채우는 기술 일뿐입니다.

  • 타입 1 : 128 비트
  • 타입 3에 MAC 어드레스, 날짜 충전제 : 128 비트
  • 형 (5)에 임의의 데이터를 즈 : 128 비트
  • 타입 4로의 MD5 해시 즈 : 128 비트로 SHA1 해시 채우기

SHA1 해시는 160 비트 (20 바이트)를 출력합니다. 해시의 결과는 UUID로 변환됩니다. SHA1에서 20 바이트에서 :

SHA1 Digest: 74738ff5 5367 e958 9aee 98fffdcd1876 94028007 
UUID (v5):  74738ff5-5367-5958-9aee-98fffdcd1876 
          ^_low nibble is set to 5 to indicate type 5 
            ^_first two bits set to 1 and 0, respectively 

('9'의 처음 2 비트에 각각 1과 0 이미 참고 그래서 이것은 영향을 미치지 않는다).

해시는 무엇입니까?

당신은 아마 내가 해시하기로되어있는 것이 무엇인지 궁금 할 것입니다. 당신은 이름 충돌을 방지하기 위해 소위 네임 스페이스로 문자열을 앞에

sha1([NamespaceUUID]+[AnyString]); 

: 기본적으로 당신의 연결을 해시.

UUID RFC 당신을위한 네 개의 네임 스페이스를 미리 정의

  • NameSpace_DNS : {6ba7b810-9dad-11d1-80b4-00c04fd430c8}
  • NameSpace_URL : {6ba7b811-9dad-11d1-80b4-00c04fd430c8}
  • NameSpace_OID : {6ba7b812-9dad-11d1-80b4-00c04fd430c8}
  • NameSpace_X500 : {6ba7b814-9dad-11d1-80b4-00c04fd430c8}

그래서, 당신은 함께 해시 수 :

StackOverflowDnsUUID = sha1(Namespace_DNS + "stackoverflow.com"); 
StackOverflowUrlUUID = sha1(Namespace_URL + "stackoverflow.com"); 

은 RFC는하는 방법을 정의 :

  • 은 SHA1
  • 에서 160 개 비트를 가지고 가고 UUID의 128 비트로 변환

기본 요지는 첫 번째 128 비트만을 가져야합니다. 5형식의 레코드에있는을 입력 한 다음 clock_seq_hi_and_reserved 섹션의 처음 두 비트를 각각 1과 0으로 설정합니다.

더 많은 예제

이제

당신이 소위 이름를 생성하는 기능을 가지고, 당신이 (의사 코드) 기능을 가질 수 있습니다

UUID NameToUUID(UUID NamespaceUUID, String Name) 
{ 
    byte[] hash = sha1(NamespaceUUID.ToBytes() + Name.ToBytes()); 
    UUID result; 
    Copy(hash, result, 16); 
    result[6] &= 0x0F; 
    result[6] |= 0x50; 
    result[8] &= 0x3F; 
    result[8] |= 0x80; 
    return result; 
} 

합니다 (엔디안합니다

uuid = NameToUUID(Namespace_DNS, 'www.stackoverflow.com'); 
uuid = NameToUUID(Namespace_DNS, 'www.google.com'); 
uuid = NameToUUID(Namespace_URL, 'http://www.stackoverflow.com'); 
uuid = NameToUUID(Namespace_URL, 'http://www.google.com/search&q=rfc+4112'); 
uuid = NameToUUID(Namespace_URL, 'http://stackoverflow.com/questions/5515880/test-vectors-for-uuid-version-5-converting-hash-into-guid-algorithm'); 
: 시스템의 -ness 위 바이트의 인덱스)

당신이 가질 수있는 통화에 영향을 미칠 수

지금 다시 질문 버전 3과 버전에 대한

-5 UUID를 추가 명령 행 인수 네임 스페이스와 이름이 부여되어야한다. 네임 스페이스는 문자열 표현의 UUID 또는 내부적으로 미리 정의 된 네임 스페이스 UUID (현재 "ns : DNS", "ns : URL", "ns : OID"및 "ns : X500")에 대한 식별자입니다. 이름은 임의 길이의 문자열입니다.

네임 스페이스 당신이 원하는대로 UUID입니다. 그것은 미리 정의 된 것들 중 하나가 될 수 있습니다, 또는 당신은 이름은 임의의 길이의 문자열입니다

UUID Namespace_RectalForeignExtractedObject = '4d79546f-6e67-7565-496e-486572417373' 

: 자신 예컨대을 만들 수 있습니다.

이름은 네임 스페이스에 추가 한 할 단지 텍스트입니다은 다음 UUID로 해시, 박제 :

uuid = NameToUUID('8e884ace-bee4-11e4-8dfc-aa07a5b093db', 'screwdriver'); 
uuid = NameToUUID('8e884ace-bee4-11e4-8dfc-aa07a5b093db', 'toothbrush'); 
uuid = NameToUUID('8e884ace-bee4-11e4-8dfc-aa07a5b093db', 'broomstick'); 
uuid = NameToUUID('8e884ace-bee4-11e4-8dfc-aa07a5b093db', 'orange'); 
uuid = NameToUUID('8e884ace-bee4-11e4-8dfc-aa07a5b093db', 'axe handle'); 
uuid = NameToUUID('8e884ace-bee4-11e4-8dfc-aa07a5b093db', 'impulse body spray'); 
uuid = NameToUUID('8e884ace-bee4-11e4-8dfc-aa07a5b093db', 'iPod Touch'); 

: 퍼블릭 도메인으로 공개 코드를. 기여가 필요하지 않습니다.

+15

주셔서 감사합니다. 'Namespace_RectalForeignExtractedObject'에 보너스 포인트를 줄 수 있다면 그렇게 할 수 있습니다. – boodle