What Is the Hi/Lo Algorithm? – 什么是Hi/Lo算法？

最后修改: 2020年 8月 18日

中文/混合/英文(键盘快捷键：t)

1. Introduction

1.绪论

In this tutorial, we’ll explain the Hi/Lo Algorithm. It is used mostly as a database identifier generation strategy.

在本教程中，我们将解释Hi/Lo算法。它主要被用作数据库标识符生成策略。

We’ll start with the algorithm overview. Then, we’ll show a practical example based on the Hibernate framework. Finally, we’ll discuss the algorithm’s use cases, its benefits, and its drawbacks.

我们将从算法的概述开始。然后，我们将展示一个基于Hibernate框架的实际例子。最后，我们将讨论该算法的使用案例、它的优点和缺点。

2. Hi/Lo Algorithm Overview

2.Hi/Lo算法概述

2.1. Definition

2.1.定义

The main purpose of the Hi/Lo algorithm is to create a range of numbers that can be safely used as database identifiers. In order to do that, it uses three number variables commonly called high, low, and incrementSize.

Hi/Lo算法的主要目的是创建一个可以安全作为数据库标识符的数字范围。为了做到这一点，它使用了三个数字变量，通常称为high、low和incrementSize。

The incrementSize variable holds the maximum number of identifiers that can be generated in one batch. It should be treated as a constant value defined at the beginning of the algorithm. Any runtime modification might cause serious problems in environments where multiple clients use the same Hi/Lo configuration to persist entries.

incrementSize变量持有在一个批次中可生成的最大标识符数量。它应该被视为一个定义在算法开始时的常量值。在多个客户使用相同的Hi/Lo配置来坚持条目的环境中，任何运行时的修改都可能导致严重问题。

The high variable is usually assigned from a database sequence. In that case, we’re sure that no one will get the same number twice.

high变量通常由数据库序列分配。在这种情况下，我们确信没有人会得到两次相同的数字。

The low variable holds the currently assigned number in the range [0, incrementSize).

low变量持有当前分配的数字，范围为[0, incrementSize]。

Given these points, the Hi/Lo algorithm generates values in range [(hi – 1) * incrementSize + 1, (hi * incrementSize)).

给定这些点，Hi/Lo算法产生的值范围为[(hi – 1) * incrementSize + 1, (hi * incrementSize))。

2.2. Pseudocode

2.2.伪代码

Let’s take a look at the steps for generating a new value using the Hi/Lo algorithm:

让我们来看看使用Hi/Lo算法生成一个新值的步骤。

  • if low is greater than or equal to incrementSize, assign a new value to high and reset low to 0
  • generate a new value with the formula: (high – 1) * incrementSize + low
  • increment low by 1
  • return the generated value

3. Practical Example

3.实例

Let’s see the Hi/Lo algorithm in action. To do that, we’ll use the Hibernate framework and its Hi/Lo implementation.

让我们看看Hi/Lo算法的运行情况。为了做到这一点，我们将使用Hibernate框架及其Hi/Lo实现。

First, let’s define a database entity to work with:

首先，让我们定义一个数据库实体来工作。

@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;
}

It’s a simple restaurant order with one id field. To correctly define the Hi/Lo algorithm in Hibernate, in the definition of the id field, we must choose a sequence strategy – hilo optimizer – and specify the increment_size parameter.

这是个简单的餐厅订单，有一个id字段。为了在Hibernate中正确定义Hi/Lo算法，在定义id字段时，我们必须选择一个序列策略–hilo优化器，并指定increment_size参数。

To show the Hi/Lo algorithm in action, we’ll persist nine restaurant orders in a loop:

为了展示Hi/Lo算法的作用，我们将在一个循环中坚持九个餐厅订单。

public void persist() {
    Transaction transaction = session.beginTransaction();

    for (int i = 0; i < 9; i++) {
        session.persist(new RestaurantOrder());
        session.flush();
    }

    transaction.commit();
}

According to the specified increment size in the entity, we should have only three calls to the database for the next high value. Assuming the database sequence starts from 1, the first batch of generated identifiers will be in the range [1,3].

根据实体中指定的增量大小，我们应该只有三次调用数据库来获得下一个高值。假设数据库序列从1开始，第一批生成的标识符将在[1,3]范围内。

When the Hi/Lo algorithm returns 3 and Hibernate asks for the next identifier’s value, the value of the low variable is equal to the incrementSize constant. In that case, the next call to the database for the new high value must be made. Having 2 as the new high value, the algorithm generates values in the range [4,6].

当Hi/Lo算法返回3并且Hibernate询问下一个标识符的值时，low变量的值等于incrementSize常数。在这种情况下，必须为新的high值向数据库进行下一次调用。将2作为新的高值，该算法产生的值范围为[4,6]。

Finally, the last call to the database for the next high value is made, and values in the range [7, 9] are assigned to the entities.

最后，最后一次调用数据库以获得下一个高值，并将[7, 9]范围内的值分配给实体。

Hibernate logs captured during the execution of the persist() method confirm those values:

在执行 persist()方法期间捕获的Hibernate日志证实了这些值。

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. Algorithm Benefits and Drawbacks

4.算法的优点和缺点

The main advantage of the Hi/Lo algorithm is the reduced number of database calls for the next sequence values. Increasing the value of incrementSize decreases the number of round-trips to the database. Obviously, that means a performance gain in our application. In addition to that, the Hi/Lo algorithm is a preferred choice in environments with a weak Internet connection.

Hi/Lo算法的主要优点是减少了为下一个序列值调用数据库的次数。增加incrementSize的值，可以减少到数据库的往返次数。很明显，这意味着我们的应用有了性能上的提升。除此之外，Hi/Lo算法在互联网连接薄弱的环境中是一个优先选择。

On the other hand, the Hi/Lo algorithm isn’t the best choice in environments where multiple different clients persist data to the same table in a database. Third-party applications might be unaware of the Hi/Lo strategy we’re using to generate identifiers. As a result, they might use entity ids from the generated range of numbers used currently in our application. In that case, when persisting data, we may encounter errors that are difficult to fix.

另一方面，Hi/Lo算法在多个不同的客户将数据持久化到数据库中的同一个表中的环境中，并不是最佳选择。第三方应用程序可能不知道我们用来生成标识符的Hi/Lo策略。因此，他们可能会使用我们应用中目前使用的生成的数字范围中的实体ID。在这种情况下，当持久化数据时，我们可能会遇到难以修复的错误。

5. Conclusion

5.总结

In this tutorial, we discussed the Hi/Lo algorithm.

在本教程中，我们讨论了Hi/Lo算法。

First, we explained how it works and discussed its pseudocode implementation. Then, we showed a practical example using Hibernate’s algorithm implementation. Finally, we listed Hi/Lo benefits and drawbacks.

首先，我们解释了它是如何工作的，并讨论了它的伪代码实现。然后，我们展示了一个使用Hibernate的算法实现的实际例子。最后，我们列出了Hi/Lo的优点和缺点。

As always, the code shown in this article is available over on GitHub.

一如既往，本文中显示的代码可在GitHub上获得。