Hi/Lo 알고리즘이란?

Hi/Lo 알고리즘이란?

Hi/Lo 알고리즘이란?

Nhibernate 설명서(고유 키를 생성하는 한 가지 방법, 섹션 5.1.4.2)에서 이 내용을 발견했지만 작동 방식에 대한 적절한 설명을 찾을 수 없었습니다.

니버나테가 처리하는 건 알고 있고, 내가 내부를 알 필요는 없지만 그냥 궁금해서 그래요.

기본적인 생각은 기본 키를 구성하는 두 개의 숫자, 즉 "높은" 숫자와 "낮은" 숫자가 있다는 것입니다.클라이언트는 기본적으로 다양한 "낮은" 값을 가진 이전 "높음" 값의 전체 범위에서 안전하게 키를 생성할 수 있다는 것을 알고 "높음" 시퀀스를 증가시킬 수 있습니다.

예를 들어, 전류 값이 35인 "하이" 시퀀스가 있고 "로우" 숫자가 0-1023 범위에 있다고 가정합니다.그러면 클라이언트는 시퀀스를 36으로 증가시킬 수 있으며(다른 클라이언트가 35를 사용하는 동안 키를 생성할 수 있음), 35/0, 35/1, 35/2, 35/3... 35/1023 키를 모두 사용할 수 있음을 알 수 있습니다.

기본 키 없이 값을 삽입한 다음 클라이언트로 다시 가져오는 대신 클라이언트 측에서 기본 키를 설정할 수 있으면 (특히 ORM의 경우) 매우 유용할 수 있습니다.다른 것 외에도 삽입을 하기 전에 부모/자녀 관계를 쉽게 만들고 키를 모두 배치할 수 있으므로 배치가 더 간단합니다.

존의 대답 외에:

연결이 끊긴 상태에서 작업할 수 있도록 사용됩니다.그러면 클라이언트는 서버에 hi 번호를 요청하고 lo 번호 자체를 증가시키는 개체를 생성할 수 있습니다.범위가 모두 사용될 때까지 서버에 연락할 필요가 없습니다.

그hi/lo알고리즘은 시퀀스 도메인을 다음과 같이 분할합니다.hi그룹들. Ahi값은 동기적으로 할당됩니다.모든hi그룹에는 최대 개수가 주어집니다.lo동시 중복 항목에 대한 걱정 없이 오프라인으로 할당할 수 있는 항목입니다.

1. 그hi토큰은 데이터베이스에 의해 할당되며, 고유한 연속 값을 보기 위해 두 개의 동시 호출이 보장됩니다.

2. 한번씩hi토큰이 검색되었습니다. 우리는 오직 필요합니다.incrementSize(개수)lo출품작)

3. 식별자 범위는 다음 공식으로 지정됩니다.

    [(hi -1) * incrementSize) + 1, (hi * incrementSize) + 1)
   

   "lo" 값은 다음과 같은 범위에 있습니다.

    [0, incrementSize)
   

   시작 값으로부터 적용됨:

    [(hi -1) * incrementSize) + 1)
   

4. 언제쯤lo값이 사용되고, 새 값이 사용됩니다.hi값을 불러오고 사이클이 계속됩니다.

이 시각적 프레젠테이션도 쉽게 따라 할 수 있습니다.

옵티마이저는 식별자 생성을 최적화하는 데는 괜찮지만, 식별자 전략에 대해 아무것도 알지 못한 채 데이터베이스에 행을 삽입하는 다른 시스템에서는 잘 작동하지 않습니다.

Hibernate는 hi/lo generator 전략의 장점을 제공하는 옵티마이저를 제공하며 이러한 시퀀스 할당 전략을 알지 못하는 다른 타사 클라이언트와의 상호 운용성을 제공합니다.

효율적이고 다른 시스템과 상호 운용 가능하기 때문에, 풀링-로 옵티마이저는 기존의 하이/로 식별자 전략보다 훨씬 더 나은 후보입니다.

Lo는 사람이 현명하게 선택할 수 있는 의미 있는 크기의 범위(예: 한 번에 200개의 키를 얻는 것)가 아닌 일반적으로 기계 단어 크기에 따라 키 공간을 큰 청크로 분할하는 캐시된 할당기입니다.

Hi-Lo 사용은 서버를 다시 시작할 때 많은 수의 키를 낭비하고, 인간에게 친숙하지 않은 큰 키 값을 생성하는 경향이 있습니다.

Hi-Lo 할당기보다 더 나은 것은 "선형 청크" 할당기입니다.이것은 유사한 테이블 기반 원리를 사용하지만, 작고 편리한 크기의 청크를 할당하고 좋은 인간 친화적인 값을 생성합니다.

create table KEY_ALLOC (
    SEQ varchar(32) not null,
    NEXT bigint not null,
    primary key (SEQ)
);

다음을 할당하려면 200개의 키(이후 서버에서 범위로 유지되고 필요에 따라 사용됨):

select NEXT from KEY_ALLOC where SEQ=?;
update KEY_ALLOC set NEXT=(old value+200) where SEQ=? and NEXT=(old value);

이 트랜잭션을 커밋(재시도를 사용하여 경합을 처리)할 수 있다면 200개의 키를 할당하고 필요에 따라 키를 분배할 수 있습니다.

청크 크기가 20에 불과한 이 계획은 Oracle 시퀀스에서 할당하는 것보다 10배 빠르며 모든 데이터베이스 중에서 100% 휴대가 가능합니다.할당 성능은 하이로와 동등합니다.

앰블러의 아이디어와는 달리 키스페이스를 연속된 선형 숫자 라인으로 취급합니다.

이렇게 하면 복합 키에 대한 자극을 피할 수 있고(이는 결코 좋은 생각이 아니었습니다), 서버를 재시작할 때 전체 로워드를 낭비하지 않게 됩니다.그것은 "친한" 인간 규모의 핵심 가치를 창출합니다.

이에 비해 앰블러 씨의 아이디어는 높은 16비트 또는 32비트를 할당하고 하이 워드가 증가함에 따라 큰 인간 친화적이지 않은 키 값을 생성합니다.

할당된 키 비교:

Linear_Chunk       Hi_Lo
100                65536
101                65537
102                65538
.. server restart
120                131072
121                131073
122                131073
.. server restart
140                196608

설계적 측면에서, 그의 솔루션은 기본적으로 Linear_Chunk보다 숫자 라인(복합 키, 큰 hi_word 제품)에서 더 복잡하지만 비교적 이점은 얻지 못합니다.

Hi-Lo 디자인은 OO 매핑과 지속성에서 일찍이 생겨났습니다.오늘날 하이버네이트와 같은 지속성 프레임워크는 더 단순하고 우수한 할당자를 기본값으로 제공합니다.

Hi/Lo 알고리즘은 제 경험에 근거하여 복제 시나리오를 사용하는 여러 데이터베이스에 적합하다는 것을 알았습니다.상상해보세요.뉴욕(alias 01)에 서버가 있고 로스엔젤레스(alias 02)에 다른 서버가 있고 그리고 PERSONA 테이블이 있습니다...그래서 뉴욕에서 사람이 창조되면...당신은 항상 01을 HI 값으로 사용하고 LO 값은 그 다음 보안입니다.예를 들면.

• 010000010제이슨
• 010000011 David
• 010000012 테오

Los Angeles에서 당신은 항상 HI 02를 사용합니다. 예를 들어:

• 020000045 루퍼트
• 020000046 오스왈드
• 020000047 마리오

따라서 데이터베이스 복제를 사용할 때(브랜드에 관계없이) 중복된 기본 키, 충돌 등의 걱정 없이 모든 기본 키와 데이터를 쉽고 자연스럽게 결합할 수 있습니다.

이 시나리오에서는 이것이 최선의 방법입니다.

언급URL : https://stackoverflow.com/questions/282099/whats-the-hi-lo-algorithm