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 to generate keys as universally unique identifiers (UUID).

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 (zero).
  • 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 (one).

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 (zero).
  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 (one).

A sequence diagram of the Hi/Lo algorithm.

A database table for use with Hi/Lo pattern.

Algorithm

The current_lo (integer) and current_hi (integer) variables are internal state variables. The internal state is retained across invocations. The max_lo (integer) 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: max_lo must be set to a value greater than zero.

algorithm generate_key is
    output: key as a positive integer

    if current_lomax_lo then
        current_hi := get_next_hi()
        current_lo := 0

    key := current_hi × max_lo + current_lo
    current_lo := current_lo + 1

    return key

UML Hi-Lo activity diagram.svg

Example

A UML class diagram of a Hi/Lo key generator.

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__(self, get_next_hi: Callable[[], int], max_lo: int = 1000) -> None:
        if max_lo <= 0:
            raise ValueError("max_lo must be greater than zero.")
        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(self) -> 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(get_next_hi)
>>> 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.[1]

Very briefly mentioned in the 2004 book Better, Faster, Lighter Java by Bruce Tate and Justin Gehtland on page 137.[2]

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.[3]

Explained in the 2015 book Learning NHibernate 4 by Suhas Chatekar on page 53 and 144–145.[4]

Mentioned in the 2017 book NHibernate 4.x cookbook on page 35.[5]

Mentioned in the 2018 book ASP.NET Core 2 Fundamentals on page 219.[6]

This implementation uses hi/lo algorithm to generate identifiers. Algorithm uses a high value retrieved from database and combines it with range of low values to generate a unique identifier. High value is from column next_id of table hibernate_unique_key by default. But you can override this to use a different table. This algorithm also supports specifying a where parameter which can be used to retrieve high value for different entities from different rows of the hibernate_unique_key table.

Suhas Chatekar, Learning NHibernate 4 (2015-07-31)

hilo needs a set of two numbers to work with. One is hi which is sourced from a database table and other is lo which is calculated by NHibernate. NHibernate combines these two numbers using a formula to generate a unique number that can be used as identifier.

Suhas Chatekar, Learning NHibernate 4 (2015-07-31)

While auto incremented IDs are simpler, whenever you add an entity to the context, this addition forces the entity to be inserted to the database. That is because we can only retrieve the ID if the actual insertion happens in the case of auto incremented IDs. The HiLo algorithm frees us from this restriction by reserving the IDs beforehand using a database sequence.

Onur Gumus and Mugilan T. S. Ragupathi, ASP.NET Core 2 Fundamentals (2018-08-30)

Support

Supported by Entity Framework Core (ORM for .NET Core) with Microsoft SQL Server using the UseHiLo extension method.[7] Not supported by the predecessor Entity Framework.

Supported by Hibernate (ORM for Java) and NHibernate (ORM for .NET) through SequenceHiLoGenerator[8] and TableHiLoGenerator.[9] Had support since at least 2002. Had support since at least version 3.2 with code authored by Gavin King.

Supported by Doctrine[10] (ORM for PHP) through the TableGenerator class.[11]

Supported by Marten[12] (persistence library for .NET) with PostgreSQL through the HiLoSequence class.[13]

Supported by RavenDB[14] (a NoSQL document database).

Not supported by Apache Cayenne, ServiceStack.OrmLite, Ruby on Rails Active Record, Dapper, and Dashing.

See also

References

  1. Sperko, Richard. Java persistence for relational databases. Apress. p. 236. ISBN 9781590590713.
  2. Tate, Bruce; Gehtland, Justin. Better, faster, lighter Java (1st ed.). O'Reilly. p. 137. ISBN 0-596-00676-4.
  3. Sam-Bodden, Brian; M Jud, Christopher. Enterprise Java development on a budget : leveraging Java open source technologies. Apress. p. 386. ISBN 978-1-59059-125-3.
  4. Chatekar, Suhas (2015-07-31). Learning NHibernate 4 : explore the full potential of NHibernate to build robust data access code. Packt Publishing Ltd. p. 53. ISBN 9781784392062.
  5. Liljas, Gunnar; Zaytsev, Alexander; Dentler, Jason (2017-01-31). NHibernate 4.x cookbook : over 90 incredible and powerful recipes to help you efficiently use NHibernate in your application (Second ed.). Packt Publishing Ltd. p. 35. ISBN 9781784394110.
  6. Gumus, Onur; T. S. Ragupathi, Mugilan (2018-08-30). ASP.NET Core 2 fundamentals : build cross-platform apps and dynamic web services with this server-side web application framework. Packt Publishing Ltd. p. 219. ISBN 9781789533552.
  7. "SqlServerPropertyBuilderExtensions.UseHiLo Method (Microsoft.EntityFrameworkCore)". docs.microsoft.com.
  8. "NHibernate Object Relational Mapper". GitHub. NHibernate. 14 November 2019. Retrieved 14 November 2019.
  9. "NHibernate Object Relational Mapper". GitHub. NHibernate. 14 November 2019. Retrieved 14 November 2019.
  10. "Doctrine\ORM\Sequencing\TableGenerator | API". www.doctrine-project.org.
  11. "Doctrine Object Relational Mapper (ORM)". GitHub. Doctrine. 14 November 2019. Retrieved 14 November 2019.
  12. "Marten - Sequential Identifiers with Hilo". martendb.io.
  13. "Postgresql as a Document Database and Event Store for .Net Applications: JasperFx/marten". GitHub. The Jasper Framework and Related Projects. 14 November 2019. Retrieved 14 November 2019.
  14. "HiLo Algorithm | RavenDB 5.1 Documentation". ravendb.net.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.