Английская Википедия: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 (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:
- 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).
- Assign a key by multiplying the currently assigned high value with the maximum low value and adding the currently assigned low value.
- Increment the currently assigned low value by 1 (one).
A sequence diagram of the Hi/Lo algorithm.
The database needs a table with a column for the table name and a column the high value.
A database table for use with Hi/Lo pattern.
Algorithm
The Шаблон:Var (integer) and Шаблон:Var (integer) variables are internal state variables. The internal state is retained across invocations. The Шаблон:Var (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: Шаблон:Var 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
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]
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
External links
- Английская Википедия
- Страницы с неработающими файловыми ссылками
- Articles with example pseudocode
- Articles with example Python (programming language) code
- Database algorithms
- Object–relational mapping
- Страницы, где используется шаблон "Навигационная таблица/Телепорт"
- Страницы с телепортом
- Википедия
- Статья из Википедии
- Статья из Английской Википедии
