Hi/Lo algorithm

Last updated

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 (UUID).

Contents

Explanation

The preconditions are:

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).

Hilo algorithm.svg

The database needs a table with a column for the table name and a column the high value.

Hilo table.svg

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 isoutput:key as a positive integer      ifcurrent_lo ≥ max_lothencurrent_hi := get_next_hi()         current_lo := 0      key := current_hi × max_lo + current_locurrent_lo := current_lo + 1      returnkey

UML Hi-Lo activity diagram.svg

Example

HiloKeyGenerator UML class.svg

Example implementation in Python. 

classHiloKeyGenerator:"""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:ifmax_lo<=0:raiseValueError("max_lo must be greater than zero.")self._current_hi=0self._current_lo=max_lo+1self._get_next_hi=get_next_hiself._max_lo=max_lodefgenerate_key(self)->int:"""Generate a new unique key."""ifself._current_lo>=self._max_lo:self._current_hi=self._get_next_hi()self._current_lo=0key=self._current_hi*self._max_lo+self._current_loself._current_lo+=1returnkey

Output:

>>> defget_next_hi():... return2# 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

Related Research Articles

A relational database is a database based on the relational model of data, as proposed by E. F. Codd in 1970. A database management system used to maintain relational databases is a relational database management system (RDBMS). Many relational database systems are equipped with the option of using SQL for querying and updating the database.

Object–relational mapping in computer science is a programming technique for converting data between a relational database and the heap of an object-oriented programming language. This creates, in effect, a virtual object database that can be used from within the programming language.

<span class="mw-page-title-main">Object–relational database</span> Database management system

An object–relational database (ORD), or object–relational database management system (ORDBMS), is a database management system (DBMS) similar to a relational database, but with an object-oriented database model: objects, classes and inheritance are directly supported in database schemas and in the query language. In addition, just as with pure relational systems, it supports extension of the data model with custom data types and methods.

In the relational model of databases, a primary key is a specific choice of a minimal set of attributes (columns) that uniquely specify a tuple (row) in a relation (table). Informally, a primary key is "which attributes identify a record," and in simple cases constitute a single attribute: a unique ID. More formally, a primary key is a choice of candidate key ; any other candidate key is an alternate key.

<span class="mw-page-title-main">Referential integrity</span> Where all data references are valid

Referential integrity is a property of data stating that all its references are valid. In the context of relational databases, it requires that if a value of one attribute (column) of a relation (table) references a value of another attribute, then the referenced value must exist.

A surrogate key in a database is a unique identifier for either an entity in the modeled world or an object in the database. The surrogate key is not derived from application data, unlike a natural key.

<span class="mw-page-title-main">Join (SQL)</span> SQL clause

A join clause in the Structured Query Language (SQL) combines columns from one or more tables into a new table. The operation corresponds to a join operation in relational algebra. Informally, a join stitches two tables and puts on the same row records with matching fields : INNER, LEFT OUTER, RIGHT OUTER, FULL OUTER and CROSS.

Hibernate ORM is an object–relational mapping tool for the Java programming language. It provides a framework for mapping an object-oriented domain model to a relational database. Hibernate handles object–relational impedance mismatch problems by replacing direct, persistent database accesses with high-level object handling functions.

Object–relational impedance mismatch creates difficulties going from data in relational data stores to usage in domain-driven object models. Object-orientation (OO) is the default method for business-centric design in programming languages. The problem lies in neither relational nor OO, but in the conceptual difficulty mapping between the two logic models. Both are logical models implementable differently on database servers, programming languages, design patterns, or other technologies. Issues range from application to enterprise scale, whenever stored relational data is used in domain-driven object models, and vice versa. Object-oriented data stores can trade this problem for other implementation difficulties.

In software engineering, the active record pattern is an architectural pattern. It is found in software that stores in-memory object data in relational databases. It was named by Martin Fowler in his 2003 book Patterns of Enterprise Application Architecture. The interface of an object conforming to this pattern would include functions such as Insert, Update, and Delete, plus properties that correspond more or less directly to the columns in the underlying database table.

<span class="mw-page-title-main">NHibernate</span> Object–relational mapping solution

NHibernate is an object–relational mapping (ORM) solution for the Microsoft .NET platform. It provides a framework for mapping an object-oriented domain model to a traditional relational database. Its purpose is to relieve the developer from a significant portion of relational data persistence-related programming tasks. NHibernate is free and open-source software that is distributed under the GNU Lesser General Public License. NHibernate is a port of Hibernate.

Jakarta Persistence is a Jakarta EE application programming interface specification that describes the management of relational data in enterprise Java applications.

Qcodo is an open-source PHP web application framework which builds an object-relational model (ORM), CRUD UI pages, and AJAX hooks from an existing data model. It additionally includes a tightly integrated HTML and JavaScript form toolkit which interfaces directly with the generated entities. It is a robust, comprehensive framework which can be utilized by small and large Web applications alike.

<span class="mw-page-title-main">SQLAlchemy</span>

SQLAlchemy is an open-source SQL toolkit and object-relational mapper (ORM) for the Python programming language released under the MIT License.

<span class="mw-page-title-main">Database model</span> Type of data model

A database model is a type of data model that determines the logical structure of a database. It fundamentally determines in which manner data can be stored, organized and manipulated. The most popular example of a database model is the relational model, which uses a table-based format.

Entity Framework (EF) is an open source object–relational mapping (ORM) framework for ADO.NET. It was originally shipped as an integral part of .NET Framework, however starting with Entity Framework version 6.0 it has been delivered separately from the .NET Framework.

Language Integrated Query is a Microsoft .NET Framework component that adds native data querying capabilities to .NET languages, originally released as a major part of .NET Framework 3.5 in 2007.

The Doctrine Project is a set of PHP libraries primarily focused on providing persistence services and related functionality. Its most commonly known projects are the object–relational mapper (ORM) and the database abstraction layer it is built on top of.

Apache Empire-db is a Java library that provides a high level object-oriented API for accessing relational database management systems (RDBMS) through JDBC. Apache Empire-db is open source and provided under the Apache License 2.0 from the Apache Software Foundation.

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 page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.