Qual é o algoritmo Hi / Lo?

464

Qual é o algoritmo Hi / Lo?

Eu encontrei isso no documentação NHibernate (é um método para gerar chaves exclusivas, seção 5.1.4.2), mas não encontrei uma boa explicação de como funciona.

Eu sei que o Nhibernate lida com isso, e eu não preciso saber por dentro, mas estou apenas curioso.

DiegoCofre
fonte

Respostas:

541

A idéia básica é que você tenha dois números para formar uma chave primária - um número "alto" e um número "baixo". Um cliente pode basicamente incrementar a sequência "alta", sabendo que pode gerar com segurança chaves de todo o intervalo do valor "alto" anterior com a variedade de valores "baixos".

Por exemplo, supondo que você tenha uma sequência "alta" com um valor atual de 35 e o número "baixo" esteja no intervalo de 0 a 1023. Em seguida, o cliente pode incrementar a sequência para 36 (para que outros clientes possam gerar chaves enquanto estiver usando 35) e saber que as chaves 35/0, 35/1, 35/2, 35/3 ... 35/1023 são tudo disponível.

Pode ser muito útil (principalmente com ORMs) poder definir as chaves primárias no lado do cliente, em vez de inserir valores sem chaves primárias e, em seguida, buscá-las novamente no cliente. Além de qualquer outra coisa, isso significa que você pode facilmente estabelecer relacionamentos pai / filho e ter todas as chaves no lugar antes de fazer as inserções, o que simplifica o lote.

Jon Skeet
fonte
14
Você está dizendo que "intervalos baixos" são coordenados dentro do cliente, enquanto a "sequência alta" corresponde a uma sequência de banco de dados?
31430 Chris Noe
14
Os valores hi & lo são tipicamente compostos em um único valor inteiro ou como uma chave comercial de duas partes?
31430 Chris Noe
51
então como um endereço IP - a ICANN fornece um número alto de 'rede', e você tem quantos números baixos de 'host' desejar, dentro do limite do intervalo CIDR fornecido.
7609 gbjbaanb
6
@ Adam: Fundamentalmente, nada - é potencialmente mais barato incrementar um valor (a parte "alta") do que gerar um monte de chaves. (É potencialmente muito mais barato em termos de transferência de dados - você pode "reserva" um grande número de chaves com largura de banda mínima.)
Jon Skeet
4
@ Adam: Isso é verdade se as chaves são apenas números. Não é muito para GUIDs :) Mas sim, no caso de números simples, qualquer "incremento atômico por um valor fixo" atômico. Isso é efetivamente o que o hi-lo está fazendo, se você pensar nisso como um número dividido em duas seções.
Jon Skeet
157

Além da resposta de Jon:

É usado para poder trabalhar desconectado. Um cliente pode solicitar ao servidor um número hi e criar objetos aumentando o próprio número lo. Não é necessário entrar em contato com o servidor até que o intervalo lo esteja esgotado.

Stephan Eggermont
fonte
1
Eu prefiro isso por brevidade.
Developer Marius Žilėnas
34

Como essa é uma pergunta muito comum, escrevi este artigo , no qual essa resposta se baseia.

Os algoritmos hi / lo dividem o domínio de seqüências em grupos "hi". Um valor "oi" é atribuído de forma síncrona. Cada grupo "hi" recebe um número máximo de entradas "lo", que podem ser atribuídas off-line sem se preocupar com entradas duplicadas simultâneas.

  1. O token "oi" é atribuído pelo banco de dados e duas chamadas simultâneas são garantidas para ver valores consecutivos únicos
  2. Depois que um token "oi" é recuperado, precisamos apenas do "incrementSize" (o número de entradas "lo")
  3. O intervalo de identificadores é fornecido pela seguinte fórmula:

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

    e o valor "lo" estará no intervalo:

    [0, incrementSize)

    sendo aplicado a partir do valor inicial de:

    [(hi -1) * incrementSize) + 1)
  4. Quando todos os valores "lo" são usados, um novo valor "hi" é buscado e o ciclo continua

Você pode encontrar uma explicação mais detalhada neste artigo :

E essa apresentação visual também é fácil de seguir:

insira a descrição da imagem aqui

Embora o otimizador hi / lo seja bom para otimizar a geração de identificadores, ele não funciona bem com outros sistemas inserindo linhas em nosso banco de dados, sem saber nada sobre nossa estratégia de identificadores.

O Hibernate oferece o otimizador de pool-lo , que oferece as vantagens da estratégia de gerador hi / lo, além de oferecer interoperabilidade com outros clientes de terceiros que não estão cientes dessa estratégia de alocação de sequência.

Sendo eficiente e interoperável com outros sistemas, o otimizador de pool-lo é um candidato muito melhor do que a estratégia de identificador hi / lo legado.

Vlad Mihalcea
fonte
Às vezes, eu realmente não te entendo hahaha: Embora o otimizador hi / lo seja bom para otimizar a geração de identificadores (ok), ele não funciona bem com outros sistemas (o que você quer dizer com outros sistemas?), Que são os primeiros ones?) inserir linhas em nosso banco de dados (a geração de identificadores também não costuma inserir linhas?), sem saber nada sobre nossa estratégia de identificadores.
Adelin 06/02
Outros sistemas, como um DBA tentando executar uma instrução INSERT. Se ela ler os dados da sequência atual, você acha fácil descobrir o próximo valor do identificador sabendo que usamos hilo nessa tabela de banco de dados específica?
Vlad Mihalcea 07/02
Peço desculpas se o comentário não for adequado para sua resposta, mas eu queria saber qual otimizador é usado por padrão? Ou isso depende do DB (estou usando o PostgreSQL)? Porque não consigo descobrir a relação entre o valor atual da sequência e os IDs gerados. Estou usando @GeneratedValue(strategy = GenerationType.SEQUENCE, generator = "name") @SequenceGenerator(name="name", sequenceName = "name_seq", allocationSize=100)para meus IDs.
Stefan Golubović
1
Desde o Hibernate 5, o Pooled é o novo Otimizador, não o Hi / Lo. Confira este artigo para obter mais detalhes sobre o Pooled Optimizer.
Vlad Mihalcea 29/10/19
@VladMihalcea, acredito que você tenha um erro de digitação na bala três, primeiro trecho de , (hi * incrementSize) + 1)... deve ser , hi * incrementSize), certo?
Huiagan 06/04
23

Lo é um alocador em cache que divide o espaço de chaves em grandes pedaços, normalmente com base em algum tamanho de palavra da máquina, em vez dos intervalos de tamanho significativo (por exemplo, obtendo 200 chaves de cada vez) que um ser humano pode escolher sensatamente.

O uso de Hi-Lo tende a desperdiçar um grande número de chaves na reinicialização do servidor e gera grandes valores de chave que não são amigáveis ​​ao ser humano.

Melhor que o alocador Hi-Lo, é o alocador "Linear Chunk". Isso usa um princípio semelhante à tabela, mas aloca pequenos pedaços de tamanho conveniente e gera bons valores amigáveis ​​ao ser humano.

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

Para alocar as próximas, digamos, 200 chaves (que são mantidas como um intervalo no servidor e usadas conforme necessário):

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

Desde que você possa confirmar esta transação (use novas tentativas para lidar com a contenção), você alocou 200 chaves e pode distribuí-las conforme necessário.

Com um tamanho de bloco de apenas 20, esse esquema é 10 vezes mais rápido do que alocado a partir de uma sequência Oracle e é 100% portátil entre todos os bancos de dados. O desempenho da alocação é equivalente a hi-lo.

Diferentemente da idéia de Ambler, ele trata o espaço das teclas como uma linha numérica linear contígua.

Isso evita o ímpeto das chaves compostas (que nunca foram realmente uma boa idéia) e evita desperdiçar palavras-chave inteiras quando o servidor é reiniciado. Ele gera valores-chave "amigáveis" em escala humana.

A idéia de Ambler, em comparação, aloca os altos 16 ou 32 bits e gera grandes valores de chave que não são amigáveis ​​aos seres humanos à medida que as palavras-chave aumentam.

Comparação de chaves alocadas:

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

Em termos de design, sua solução é fundamentalmente mais complexa na linha de números (chaves compostas, grandes produtos hi_word) do que Linear_Chunk, sem obter benefícios comparativos.

O design Hi-Lo surgiu no início do mapeamento e persistência de OO. Atualmente, estruturas de persistência como o Hibernate oferecem alocadores mais simples e melhores como padrão.

Thomas W
fonte
4
Boa postagem, mas você não está respondendo à pergunta.
orbfish
1
+1 para uma resposta interessante. Concordo que a grande maioria dos aplicativos não obtém vantagem do Hi-Lo em relação à abordagem mais simples; no entanto, acho que o Hi-Lo é mais adequado ao caso especial de vários alocadores em aplicativos altamente concorrentes.
richj
1
Obrigado @richj! O que quero dizer é que você pode usar vários alocadores ou tamanhos grandes de blocos com "alocação linear de blocos", mas que - diferentemente do Hi / Lo - mantém uma correspondência linear do alocador NEXT_VAL com as chaves da tabela e é sintonizável. Ao contrário do HiLo, nenhuma multiplicação é necessária - simplesmente não é necessária! O armazenamento multiplicador e de NEXT_HI faz HiLo mais complexo e breaks tuneability, uma vez mudar o tamanho de bloco vai mudar arbitrariamente a próxima tecla a ser emitido .. Veja: literatejava.com/hibernate/...
Thomas W
2
Estou interessado em vários alocadores independentes. Com o Hi-Lo, é óbvio que o valor alto pode ser particionado no ID do alocador / ID do bloco. Não foi imediatamente óbvio (para mim) que a mesma abordagem possa ser aplicada ao Linear Chunk, mas é basicamente o mesmo problema de dividir o intervalo total entre alocadores. Eu entendi agora. Obrigado.
richj
1
Ah, depois de pensar nisso, acho que a coluna SEQ é mapeada para um nome de tabela. Por exemplo, há um alocador na tabela Customers, um na tabela Orders e assim por diante. Perdoe-me, às vezes sou lento.
Rock Anthony Johnson
1

Achei que o algoritmo Hi / Lo é perfeito para vários bancos de dados com cenários de replicação baseados em minha experiência. Imagina isto. você tem um servidor em Nova York (apelido 01) e outro servidor em Los Angeles (apelido 02), então você tem uma tabela PERSON ... então em Nova York quando uma pessoa é criada ... você sempre usa 01 como o valor HI e o valor LO é o próximo secuencial. por exemplo.

  • 010000010 Jason
  • 010000011 David
  • 010000012 Theo

em Los Angeles você sempre usa o HI 02. por exemplo:

  • 020000045 Rupert
  • 020000046 Oswald
  • 020000047 Mario

Portanto, quando você usa a replicação do banco de dados (independentemente da marca), todas as chaves e dados primários se combinam de maneira fácil e natural, sem se preocupar com chaves primárias duplicadas, colisões etc.

Este é o melhor caminho a seguir neste cenário.

Theo
fonte
Não funciona no Hibernate. O HiLo algrotirm obtém um novo valor de sequência em cada transação, de modo que o contador HI é incrementado de acordo. Mas no seu exemplo, o contador HI é sempre constante para um banco de dados.
precisa saber é o seguinte