Hi/Lo algorithm


Hi/Lo is an algorithm and a key generation strategy used for generating unique keys for use in a database as a primary key. It uses a sequence-based hi-lo pattern to generate values. Hi/Lo is used in scenarios where an application needs its entities to have an identity prior to persistence. It is a value generation strategy. An alternative to Hi/Lo would be for the application to generate keys as universally unique identifiers.

Explanation

The preconditions are:
  • There is a constant defined to hold the maximum low value. The value must be greater than zero. A suitable value could be 1000 or 32767.
  • There is a variable defined to hold the currently assigned high value and it is assigned the value 0.
  • There is a variable defined to hold the currently assigned low value and it is assigned the value of the maximum low value plus 1.
The steps are:
  1. If the currently assigned low value is greater or equal than the maximum low value then call a function to fetch a new high value and reset the currently assigned low value to 0.
  2. Assign a key by multiplying the currently assigned high value with the maximum low value and adding the currently assigned low value.
  3. Increment the currently assigned low value by 1.
The database needs a table with a column for the table name and a column the high value.

Algorithm

The and variables are internal state variables. The internal state is retained across invocations. The constant is a configuration option. get_next_hi is a function that retrieves a new high value from a database server. In a relational database management system this could be through a stored procedure.
Precondition: must be set to a value greater than zero.
algorithm generate_key is
output: key as a positive integer
if current_lo ≥ max_lo then
current_hi := get_next_hi
current_lo := 0
key := current_hi × max_lo + current_lo
current_lo := current_lo + 1
return ''key''

Example

Example implementation in Python.

class HiloKeyGenerator:
"""Key generator that uses a Hi/Lo algorithm.
Args:
get_next_hi: A callable function that retrieves a new high value.
max_lo: The maximum low value. Defaults to 1000.
Raises:
ValueError: If the value of max_lo is not greater than zero.
"""
def __init__ -> None:
if max_lo <= 0:
raise ValueError
self._current_hi = 0
self._current_lo = max_lo + 1
self._get_next_hi = get_next_hi
self._max_lo = max_lo
def generate_key -> int:
"""Generate a new unique key."""
if self._current_lo >= self._max_lo:
self._current_hi = self._get_next_hi
self._current_lo = 0
key = self._current_hi * self._max_lo + self._current_lo
self._current_lo += 1
return key

Output:

>>> def get_next_hi:
... return 2 # From database server.
...
>>> generator = HiloKeyGenerator
>>> generator.generate_key
2000
>>> generator.generate_key
2001
>>> generator.generate_key
2002

Books

Very briefly mentioned in the 2003 book Java Persistence for Relational Databases by Richard Sperko on page 236.
Very briefly mentioned in the 2004 book Better, Faster, Lighter Java by Bruce Tate and Justin Gehtland on page 137.
Very briefly mentioned in the 2004 book Enterprise Java Development on a Budget: Leveraging Java Open Source by Brian Sam-Bodden and Christopher M Jud on page 386.
Explained in the 2015 book Learning NHibernate 4 by Suhas Chatekar on page 53 and 144–145.
Mentioned in the 2017 book NHibernate 4.x cookbook on page 35.
Mentioned in the 2018 book ASP.NET Core 2 Fundamentals on page 219.

Support

Supported by Entity Framework Core with Microsoft SQL Server using the UseHiLo extension method. Not supported by the predecessor Entity Framework.
Supported by Hibernate and NHibernate through SequenceHiLoGenerator and TableHiLoGenerator. Had support since at least 2002. Had support since at least version 3.2 with code authored by Gavin King.
Supported by Doctrine through the TableGenerator class.
Supported by Marten with PostgreSQL through the HiLoSequence class.
Supported by RavenDB.
Not supported by Apache Cayenne, ServiceStack.OrmLite, Ruby on Rails Active Record, Dapper, and Dashing.