Cos'è l'algoritmo Hi / Lo?

1. Introduzione

In questo tutorial, spiegheremo l'algoritmo Hi / Lo. Viene utilizzato principalmente come strategia di generazione di identificatori di database .

Inizieremo con la panoramica dell'algoritmo. Quindi, mostreremo un esempio pratico basato sul framework Hibernate. Infine, discuteremo i casi d'uso dell'algoritmo, i suoi vantaggi e i suoi svantaggi.

2. Panoramica algoritmo Hi / Lo

2.1 Definizione

Lo scopo principale dell'algoritmo Hi / Lo è creare una gamma di numeri che possono essere utilizzati in sicurezza come identificatori del database . Per fare ciò, utilizza tre variabili numeriche comunemente chiamate high, low e incrementSize .

La variabile incrementSize contiene il numero massimo di identificatori che possono essere generati in un batch. Dovrebbe essere considerato come un valore costante definito all'inizio dell'algoritmo. Qualsiasi modifica al runtime potrebbe causare seri problemi in ambienti in cui più client utilizzano la stessa configurazione Hi / Lo per rendere persistenti le voci.

La variabile alta viene solitamente assegnata da una sequenza di database. In tal caso, siamo sicuri che nessuno otterrà lo stesso numero due volte.

La variabile low contiene il numero attualmente assegnato nell'intervallo [0 , incrementSize ).

Dati questi punti, l'algoritmo Hi / Lo genera valori nell'intervallo [( hi - 1) * incrementSize + 1 , ( hi * incrementSize )).

2.2 Pseudocodice

Diamo un'occhiata ai passaggi per generare un nuovo valore utilizzando l'algoritmo Hi / Lo:

  • se low è maggiore o uguale a incrementSize , assegna un nuovo valore a high e reimposta low a 0
  • generare un nuovo valore con la formula: ( high - 1) * incrementSize + low
  • incremento basso di 1
  • restituisce il valore generato

3. Esempio pratico

Vediamo l'algoritmo Hi / Lo in azione. Per farlo, useremo il framework Hibernate e la sua implementazione Hi / Lo.

Per prima cosa, definiamo un'entità di database con cui lavorare:

@Entity public class RestaurantOrder { @Id @GeneratedValue(strategy = GenerationType.SEQUENCE, generator = "hilo_sequence_generator") @GenericGenerator( name = "hilo_sequence_generator", strategy = "sequence", parameters = { @Parameter(name = "sequence_name", value = "hilo_seqeunce"), @Parameter(name = "initial_value", value = "1"), @Parameter(name = "increment_size", value = "3"), @Parameter(name = "optimizer", value = "hilo") } ) private Long id; }

È un semplice ordine al ristorante con un campo ID . Per definire correttamente l'algoritmo Hi / Lo in Hibernate, nella definizione del campo id , dobbiamo scegliere una strategia di sequenza - hilo optimizer - e specificare il parametro increment_size .

Per mostrare l'algoritmo Hi / Lo in azione, manterremo nove ordini di ristoranti in un ciclo:

public void persist() { Transaction transaction = session.beginTransaction(); for (int i = 0; i < 9; i++) { session.persist(new RestaurantOrder()); session.flush(); } transaction.commit(); }

In base alla dimensione di incremento specificata nell'entità, dovremmo avere solo tre chiamate al database per il valore alto successivo . Supponendo che la sequenza del database inizi da 1, il primo batch di identificatori generati sarà nell'intervallo [1,3].

Quando l'algoritmo Hi / Lo restituisce 3 e Hibernate chiede il valore dell'identificatore successivo, il valore della variabile low è uguale alla costante incrementSize . In tal caso, è necessario effettuare la successiva chiamata al database per il nuovo valore elevato . Avendo 2 come nuovo valore alto , l'algoritmo genera valori nell'intervallo [4,6].

Infine, viene eseguita l'ultima chiamata al database per il successivo valore alto e vengono assegnati valori nell'intervallo [7, 9] alle entità.

I log di ibernazione catturati durante l'esecuzione del metodo persist () confermano questi valori:

Hibernate: call next value for hilo_seqeunce org.hibernate.id.enhanced.SequenceStructure - Sequence value obtained: 1 org.hibernate.event.internal.AbstractSaveEventListener - Generated identifier: 1, using strategy: org.hibernate.id.enhanced.SequenceStyleGenerator org.hibernate.event.internal.AbstractSaveEventListener - Generated identifier: 2, using strategy: org.hibernate.id.enhanced.SequenceStyleGenerator org.hibernate.event.internal.AbstractSaveEventListener - Generated identifier: 3, using strategy: org.hibernate.id.enhanced.SequenceStyleGenerator Hibernate: call next value for hilo_seqeunce org.hibernate.id.enhanced.SequenceStructure - Sequence value obtained: 2 org.hibernate.event.internal.AbstractSaveEventListener - Generated identifier: 4, using strategy: org.hibernate.id.enhanced.SequenceStyleGenerator org.hibernate.event.internal.AbstractSaveEventListener - Generated identifier: 5, using strategy: org.hibernate.id.enhanced.SequenceStyleGenerator org.hibernate.event.internal.AbstractSaveEventListener - Generated identifier: 6, using strategy: org.hibernate.id.enhanced.SequenceStyleGenerator Hibernate: call next value for hilo_seqeunce org.hibernate.id.enhanced.SequenceStructure - Sequence value obtained: 3 org.hibernate.event.internal.AbstractSaveEventListener - Generated identifier: 7, using strategy: org.hibernate.id.enhanced.SequenceStyleGenerator org.hibernate.event.internal.AbstractSaveEventListener - Generated identifier: 8, using strategy: org.hibernate.id.enhanced.SequenceStyleGenerator org.hibernate.event.internal.AbstractSaveEventListener - Generated identifier: 9, using strategy: org.hibernate.id.enhanced.SequenceStyleGenerator

4. Vantaggi e svantaggi dell'algoritmo

Il vantaggio principale dell'algoritmo Hi / Lo è il numero ridotto di chiamate al database per i valori della sequenza successiva. Aumentando il valore di incrementSize si riduce il numero di round trip al database. Ovviamente, ciò significa un aumento delle prestazioni nella nostra applicazione. In aggiunta a ciò, l'algoritmo Hi / Lo è la scelta preferita in ambienti con una connessione Internet debole .

D'altra parte, l'algoritmo Hi / Lo non è la scelta migliore negli ambienti in cui più client diversi persistono i dati nella stessa tabella in un database . Le applicazioni di terze parti potrebbero non essere a conoscenza della strategia Hi / Lo che stiamo utilizzando per generare identificatori. Di conseguenza, potrebbero utilizzare ID entità dall'intervallo di numeri generato utilizzato attualmente nella nostra applicazione. In tal caso, durante la persistenza dei dati, potremmo riscontrare errori difficili da correggere.

5. conclusione

In questo tutorial, abbiamo discusso l'algoritmo Hi / Lo.

Per prima cosa, abbiamo spiegato come funziona e discusso la sua implementazione dello pseudocodice. Quindi, abbiamo mostrato un esempio pratico utilizzando l'implementazione dell'algoritmo di Hibernate. Infine, abbiamo elencato i vantaggi e gli svantaggi di Hi / Lo.

Come sempre, il codice mostrato in questo articolo è disponibile su GitHub.