[uuid] v5 UUID 생성. 이름과 네임 스페이스는 무엇입니까?

내가 읽은 man페이지를하지만, 난 안 알아 보았 무슨 namenamespace를위한 것입니다.

버전 3 및 버전 5 UUID의 경우 추가 명령 줄 인수 네임 스페이스 및 이름을 제공해야합니다. 네임 스페이스는 문자열 표현의 UUID이거나 내부적으로 사전 정의 된 네임 스페이스 UUID (현재 알려진 것은 “ns : DNS”, “ns : URL”, “ns : OID”및 “ns : X500”)의 식별자입니다. 이름은 임의 길이의 문자열입니다.

네임 스페이스 :

네임 스페이스는 문자열 표현의 UUID이거나

생성 된 UUID v5와 관련하여 어딘가에 저장 (UUID v4)해야한다는 의미입니까? 두 경우 모두 자동으로 수행되지 않는 이유는 무엇입니까?

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

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



답변

이름과 네임 스페이스를 사용하여 (아마도) 고유 한 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를 만든 다음 (또는 루트로 nullUUID : 00000000-0000-0000-0000-000000000000사용) ” uuid -v5 $ROOTUUID $NAMESPACENAME“를 사용하여 각 네임 스페이스에 대해 재현 가능한 UUID를 만들 수 있습니다 . 이제 “를 사용하여 네임 스페이스 내의 키에 대한 고유 UUID를 만들 수 있습니다.uuid -v5 $NAMESPACEUUID $KEY“. 이러한 UUID는 충돌을 피할 가능성이 높은 단일 키-값 저장소로 던져 질 수 있습니다.이 프로세스는 재귀 적으로 반복 될 수 있으므로 예를 들어 UUID 키와 연관된”값 “이 일종의 논리적”네임 스페이스를 나타냅니다. ” “버킷, 컨테이너 또는 디렉토리와 같이 해당 UUID를 차례로 사용하여 더 많은 계층 적 UUID를 생성 할 수 있습니다.

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

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

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

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


답변

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

  • 유형 1 : MAC 주소 + 날짜 시간을 128 비트로 채 웁니다.
  • 유형 3 : MD5 해시를 128 비트로 채 웁니다.
  • 유형 4 : 임의의 데이터를 128 비트로 채움
  • 유형 5 : SHA1 해시를 128 비트로 채 웁니다.
  • 유형 6 : 순차적 UUID에 대한 비공식적 인 아이디어

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’의 처음 두 비트는 이미 각각 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 비트 가져 오기
  • 128 비트 UUID로 변환합니다.

기본적인 요점은 처음 128 비트 재료 A를 수행하는 5 기록하고 처음 두 비트 세트 clock_seq_hi_and_reserved를 각각 1과 0으로 부.

더 많은 예

이제 소위 Name 을 생성하는 함수가 있으므로 의사 코드로 함수를 사용할 수 있습니다.

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');

이제 질문으로 돌아가

버전 3 및 버전 5 UUID의 경우 추가 명령 줄 인수 네임 스페이스 및 이름을 제공해야합니다. 네임 스페이스는 문자열 표현의 UUID이거나 내부적으로 사전 정의 된 네임 스페이스 UUID (현재 알려진 것은 “ns : DNS”, “ns : URL”, “ns : OID”및 “ns : X500”)의 식별자입니다. 이름은 임의 길이의 문자열입니다.

네임 스페이스는 같은 당신을 UUID 무엇이다. 미리 정의 된 것 중 하나이거나 직접 구성 할 수 있습니다. 예 :

UUID Namespace_RectalForeignExtractedObject = '8e884ace-bee4-11e4-8dfc-aa07a5b093db'

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

이름은 네임 스페이스에 추가 한 다음 해시하고 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');

참고 : 공개 도메인으로 공개 된 모든 코드. 귀속이 필요하지 않습니다.


답변

이름은 일부 네임 스페이스 내에서 고유 한 식별자에 지나지 않습니다. 문제는 네임 스페이스가 종종 매우 작고 한 이름이 다른 이름과 충돌하는 경우가 많다는 것입니다. 예를 들어, 내 자동차의 번호판 번호 (이름)는 내 주 DMV의 네임 스페이스 내에서 고유하지만 아마도 전 세계에서 고유하지 않을 것입니다. 다른 주 DMV는 자신의 네임 스페이스에서 동일한 이름을 사용했을 수 있습니다. 도대체 다른 이름 공간이기 때문에 다른 사람이 일치하는 전화 번호 (이름)를 가질 수 있습니다.

UUID는 모든 것에 고유 한 이름을 제공 할 수있을 정도로 방대한 단일 네임 스페이스에 거주하는 것으로 볼 수 있습니다 . 그것이 “보편”이 의미하는 바입니다. 그러나 다른 네임 스페이스의 기존 이름을 UUID에 어떻게 매핑합니까?

한 가지 분명한 해결책은 모든 항목에 대한 UUID (V1 또는 V4)를 생성하여 분리 된 네임 스페이스의 이전 이름을 바꾸는 것입니다. 단점은 그것들이 훨씬 더 크다는 것입니다. 당신은 당신의 데이터 셋의 사본을 가지고있는 모든 사람들에게 모든 새로운 이름을 전달해야하고, 당신의 모든 API를 업데이트해야합니다. 확률은 실제로 당신이 이전 이름을 완전히 제거 할 수 없다는 것입니다. 어쨌든, 이제 모든 항목에 두 가지 이름이 있으므로 상황을 더 좋게 또는 더 나쁘게 만들었습니까?

V3 / V5가 올 곳입니다 UUID를가. 보고 V4 무작위로 불과하지만, 실제로 결정적이다; 네임 스페이스에 대한 올바른 UUID를 가진 사람은 해당 네임 스페이스 내에서 주어진 이름에 대해 동일한 UUID를 독립적으로 생성 할 수 있습니다 . 누구나 필요에 따라 즉석에서 만들 수 있으므로 게시하거나 미리 생성 할 필요가 없습니다!

DNS 이름과 URL은 매우 일반적으로 사용되는 네임 스페이스이므로 표준 UUID가 게시되었습니다. ASN.1 OID 및 X.500 이름은 일반적이지 않지만 표준 기관은이를 좋아하므로 표준 네임 스페이스 UUID도 게시했습니다.

다른 모든 네임 스페이스의 경우 고유 한 네임 스페이스 UUID (V1 또는 V4)를 생성하고이를 필요로하는 모든 사람에게 전달해야합니다. 네임 스페이스가 여러 개인 경우 각 네임 스페이스에 대해 UUID를 게시하는 것은 분명히 이상적이지 않습니다.

이것이 계층 구조가 들어오는 곳입니다. 하나의 “기본”UUID (모든 유형)를 만든 다음 다른 이름 공간의 이름을 지정하기위한 이름 공간으로 사용합니다! 이렇게하면 기본 UUID 만 게시하면 (또는 명백한 UUID를 사용) 모든 사람이 나머지를 계산할 수 있습니다.

예를 들어, StackOverflow를위한 UUID를 만들고 싶었습니다. DNS 네임 스페이스 내에 명백한 이름이 있으므로 기본이 분명합니다.

uuid ns_dns = '6ba7b810-9dad-11d1-80b4-00c04fd430c8';
uuid ns_base = uuidv5(ns_dns, 'stackoverflow.com');

StackOverflow 자체에는 사용자, 질문, 답변, 댓글 등에 대한 별도의 네임 스페이스가 있지만 이것도 상당히 분명합니다.

uuid ns_user = uuidv5(ns_base, 'user');
uuid ns_question = uuidv5(ns_base, 'question');
uuid ns_answer = uuidv5(ns_base, 'answer');
uuid ns_comment = uuidv5(ns_base, 'comment');

이 특정 질문은 # 10867405이므로 UUID는 다음과 같습니다.

uuid here = uuidv5(ns_question, '10867405');

이 없다는 것을주의 것도 같은 논리를 다음 사람이 같은 대답을 얻을 수 있도록이 과정에서 무작위, 아직 UUID 네임 스페이스가 충돌이 (효과적으로, 암호 해시를-122 비트 a의 보안을 제공) 것을 결코 너무 광대 없다 다른 네임 스페이스 / 이름 쌍에서 생성 된 UUID.


답변