작은 임의의 ID 생성
https://stackoverflow.com/questions/815622
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
Google App Engine 애플리케이션에서 사용하기 위해 고유 한 ID를 생성하려고 노력하고 있으며 사용하려는 접근 방식의 타당성에 대한 피드백 (마지막에 질문)을 원합니다. 나는이 주제에 대해 꽤 많은 질문을 읽었지만이 특별한 접근법을 발견 한 것을 기억하지 못합니다.
무작위로 보이는 ID와 예를 들어 MD5 해시를 원하지만 작기를 원합니다. Tinyurl 라인을 따라 4-6자가 이상적입니다. ID는 사용자가 생성 한 콘텐츠, 내 응용 프로그램의 맥락에서 사람들이 작성할 테스트 질문과 같은 것들입니다. ID가 무작위로 보일 필요는 없지만 (직렬 ID처럼 보이는 경우 괜찮습니다), 내가 생각하고자하는 접근 방식은 이에 적합하므로 실제로는 문제가되지 않습니다.
Google App Engine에 익숙한 사람들은 데이터 스토어에 대한 쓰기가 특히 비싸고 동일한 엔티티 그룹에 너무 많은 경우 시간 초과를 초래할 수 있음을 알게 될 것입니다. 샤드 카운터는 단일 글로벌 카운터에 대한 논쟁을 피하기 위해 종종 사용되는 접근법과 이와 관련된 실패한 거래입니다.
짧은 ID를 얻고 글쓰기 경합을 피하는 것과 함께 생일 역설을 피하려고 노력하고 있습니다. 나는 이것이 조금씩 배출 되더라도 수백만의 ID가있을 가능성을 준비하고 싶습니다.
나는 다음 줄을 따라 샤드 카운터를 사용하려고 생각하고있었습니다.
- 카운터는 사용자에게 보충되어 각 사용자마다 파편이 있습니다. 각 카운터 객체에는 주어진 사용자와 관련된 자체 카운트가 있으며 해당 사용자가 새 항목을 만들 때 증가합니다. 항목이 성공적으로 생성되는지 여부에 관계없이 카운트가 증가합니다.
- ID의 기초는 다음 문자열의 MD5 해시입니다. "u003Cuser-email-address> |u003Clatest-counter-value> ".
- 결과적으로 MD5 해시는 처음에는 4 자로 잘립니다.
- 단일 글로벌 "길이"값이 유지됩니다. 이전 단계가 중복 키를 초래할 때마다 (처음에는 상당히 빨리 발생할 것이라고 상상할 때) 길이 값이 하나씩 증가합니다. 새 ID에 대한 MD5 해시는 이제 4자가 아닌 "길이"문자로 잘립니다.
- 나는 사용자 이메일 주소를 노출시키고 싶지 않으며, 어떤 종류의 해시가 좋은 방법이 될 것임을 시사합니다.
내 질문은 다음과 같습니다. 이것은 중복 키의 결과로 큰 경합을 피할 것이며 길이 필드에 대한 경쟁이 특히 더 긴 문제가되지 않을 것이라고 생각 하는가? 누구든지 여기에 관련된 수학을 설명 할 수 있습니까? 전체 접근법의 가치에 의문을 제기하면서 MD5 해시의 길이에 가까운 길이가 빠르게 증가할까요? 일을 더 쉽게 유지하기 위해 전체 (더 긴) MD5 해시를 사용하는 것이 더 나을까요? 내가 간과하고있는 것이 있습니까?
해결책
이 알고리즘은 똑똑하며 실제로 쓰기 작업을 최소화합니다. 따라서 길이 값은 가장 짧은 길이와 결석 충돌의.
해시 테이블에 사용 된 전략을 사용하여 충돌이없는 제약 조건을 완화 할 수 있습니다. 길이를 증가시키기 위해 다시 떨어지기 전에 다른 고유 ID를 시도하십시오.
따라서 초기화 된 해시 문자열의 끝에 테스트 카운터를 0으로 초기화하는 것이 좋습니다. 생성 된 ID가 이미 사용 된 경우 길이를 증가시킨 후 최대 카운터 값에 도달 할 때까지 카운터를 증가시키고 재 시도합니다.
ID 주소 공간을보다 효율적으로 사용하고 훨씬 덜 빈번한 길이 증분으로 끝납니다.
MD5의 길이 한계에 대한 귀하의 질문에 대해서는 MD5의 선택이 과잉이라고 생각합니다. 당신은 실제로 암호화 (Pseudo) 보안 해시가 필요하지 않습니다. 필요한 것은 CRC32 (또는 더 빠른 Adler)를 사용할 수있는 무작위 비트 생성기입니다. 특히 코드가 휴대폰으로 실행되는 경우. CRC32가있는 임의의 비트 생성기를 구현하려면 32bits 값을 문자열로 해시로 전제하고 선택한 값 (시드)으로 초기화하십시오. 그런 다음이 문자열에서 CRC32를 계산하십시오. 더 많은 바이트가 필요한 경우, 획득 한 CRC32 값을 문자열 앞의 32 비트에 쓰고 CRC32를 다시 작성하십시오. 비트가 충분할 때까지 반복하십시오. CRC32를 원하는 알고리즘으로 바꿀 수 있습니다. 이것은 초기 상수가 종자 인 저렴하고 빠른 임의의 비트 생성기를 산출합니다.
이 알고리즘을 사용하면 생성 된 임의 비트의 수를 최소화하고 길이가 상한이 없습니다.
인코딩과 관련하여 제약 조건을 지정하지 않았습니다. 숫자와 함께 상류 및 소문자를 사용할 수 있습니까? 예제는 36 개의 다른 ASCII 값의 알파벳을 사용합니다. 위에서 설명한 의사 랜덤 번호 생성기가 원하는만큼 바이트를 생성 할 수있는 유사 임의 숫자 생성기가 있으면 길이를 ID의 문자 수로 정의하고 다음 랜덤 바이트의 모듈로 다음 글자를 선택하십시오. 그런 다음 한 번에 생성해야 할 바이트가 정확히 알 수 있고 ID를 생성하는 것이 사소한 지 알게 될 것입니다.
다른 팁
이와 같은 것은 어떻습니까 :
A-ZA-Z0-9를 사용하여 4 개의 문자 키를 원한다면 62^4 => 14 백만 가능한 값을 갖게됩니다.
이것을 N 파티션으로 나누고 : 0000 ... 1000, 1001 ... 2000, ..., Zzaa ... Zzzz
각 파티션은 다음과 같이 엔터티로 표시됩니다. 시작 ID ID Current ID
이제 ID를 생성하려면 :
- 무작위로 파티션을 선택하십시오. 각 파티션의 시작 키를 키로 사용하십시오. 거래 시작 :
- get_or_create () 해당 파티션 엔티티.
- 현재 id == end id 인 경우 1 단계로 이동하십시오.
- 현재 ID를 저장하십시오
- 한쪽 끝 트랜잭션으로 현재 ID를 증가시킵니다
저장된 현재 ID를 ID로 사용하십시오.
당신이 140으로 n을 선택하면 각 파티션은 100,000 값을 갖습니다. 이를 통해 "빈"파티션을 선택하여 재 회의 수를 제한하면서 상당히 동시 삽입물이 가능합니다.
이것에 대해 더 생각해야 할 수도 있습니다. 특히 5 자리 키로 이동해야 할 때 케이스를 어떻게 처리합니까?
-Dave
위의 질문에 어려운 숫자를 추가하기 위해 질문에 언급 된 줄을 따라 ID를 생성하는 작은 프로그램을 구현했으며, 이는 시험 실행 중 하나의 결과였습니다.
Length Count MD5 Base 62
4 400 3d0e 446
5 925 4fc04 1Myi
6 2434 0e9368 40V6
7 29155 e406d96 GBFiA
8 130615 7ba787c8 2GOiCm
9 403040 75525d163 YNKjL9
10 1302992 e1b3581f52 H47JAIs
Total: 1869561
해시의 길이가 증가 할 때마다 충돌로 인한 것이 었 으므로이 경우 6 개의 충돌이있었습니다. 카운트는 충돌 전에 생성 된 주어진 길이의 키 수입니다. MD5 열에는 중복 키 오류가 발생하기 전에 성공적으로 추가 된 마지막 잘린 키가 표시됩니다. 맨 오른쪽의 열은 기본 62의 키를 보여줍니다 (내가 올바르게 변환 한 경우).
각각의 추가 캐릭터마다 점점 더 많은 키가 생성되는 것처럼 보입니다. 이것이 당신이 상상할 것입니다. 이 접근법이 사용자가 생성 한 콘텐츠에 대한 확장을 희망합니다.
관심있는 사람이라면 누구나 마지막 열에 대한 Base 62 표현을 얻는 방법은 다음과 같습니다.
def base_62_encode(input):
"Inspired by code at http://en.wikipedia.org/wiki/Base_36."
CLIST="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
rv = ""
while input != 0:
rv = CLIST[input % 62] + str(rv)
input /= 62
return rv
base62_id = base_62_encode(long(truncated_hash, 16))
(나중에 추가 :)
다음은 Google App Engine의 맥락에서 이러한 ID의 생성과 관련된 몇 가지를 처리하는 클래스입니다. 기본적 으로이 클래스에서 생성 된 키는 순전히 기본 62가 아닙니다. GAE 키 이름의 첫 번째 문자는 알파벳이어야합니다. 이 요구 사항은 첫 번째 문자에 기본 52를 사용하여 여기에서 해결되었습니다.
1 차베이스는 생성자로 전달 된 "Clist"값을 변경하여 62 이외의 것으로 변경 될 수 있습니다. "1", "l", "i"등과 같이 혼합하기 쉬운 문자를 제거하고 싶을 수도 있습니다.
용법:
keygen = LengthBackoffIdGenerator(SomeClass, initial_length=5)
small_id, modified = keygen.small_id(seed_value_from_sharded_counter)
수업은 다음과 같습니다.
class LengthBackoffIdGenerator(object):
"""Class to generate ids along the lines of tinyurl.
By default, ids begin with a alphabetic character. Each id that is created is checked against previous ones
to ensure uniqueness. When a duplicate is generated, the length of the seed value used is increased by one
character.
Ids become gradually longer over time while remaining relatively short, and there are very few retries in
relation to the number of keys generated.
"""
ids = set()
def __init__(self, cls, clist='0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ', alpha_first=False,
initial_length=5, check_db=False):
self.clist = clist
self.alpha_first = alpha_first
if self.alpha_first:
import re
alpha_list = re.sub(r'\d', '', clist)
if len(alpha_list) < 1:
raise Exception, 'At least one non-numeric character is required.'
self.alpha_list = alpha_list
self.cls = cls
self.length = initial_length
self.check_db = check_db
def divide_long_and_convert(self, radix, clist, input, rv):
"Inspired by code at http://en.wikipedia.org/wiki/Base_36."
rv += clist[input % radix]
input /= radix
return (input, rv)
def convert_long(self, input):
rv = ""
if self.alpha_first:
input, rv = self.divide_long_and_convert(len(self.alpha_list), self.alpha_list, input, rv)
while input != 0:
input, rv = self.divide_long_and_convert(len(self.clist), self.clist, input, rv)
return rv
def hash_truncate_and_binify(self, input, length):
"""Compute the MD5 hash of an input string, truncate it and convert it to a long.
input - A seed value.
length - The length to truncate the MD5 hash to.
"""
from assessment.core.functions import md5_hash
input = md5_hash(input)[0:length]
return long(input, 16)
def _small_id(self, input):
"""Create an ID that looks similar to a tinyurl ID.
The first letter of the ID will be non-numeric by default.
"""
return self.convert_long(self.hash_truncate_and_binify(input, self.length))
def small_id(self, seed):
key_name = self._small_id(seed)
increased_length = False
if self.check_db and not self.cls.get_by_key_name(key_name) is None:
self.ids.add(key_name)
if key_name in self.ids:
self.length += 1
increased_length = True
key_name = self._small_id(seed)
self.ids.add(key_name)
return (key_name, increased_length)
