Search This Blog

Sunday, 11 September 2011

Id Generators - 2

Continuing from the previous post, we shall look into hilo and  seqhilo generator types.

hilo

The hilo algorithm, as per the hibernate documentation, is one of the most popular id generation algorithms available.The working involves creating a separate table in the database that is used to help in the key generation. (An alternative approach is available which works on Oracle styled sequences too)
Explanation of the Hi Lo algorithm: (copied word for word)
"The HiLo (High/Low) algorithm knows how to generate unique number series using two values: the high and the low. The high value is used as a base for a series (or range) of numbers, while the size of this series is donated by the low value. A unique series is generated using the following steps:

  1. Load the and atomically increment the high value
  2. Multiple the high value by the low value (max*low), the result is the first number (lower bound) of the current series
  3. The last number (higher bound) of the current series is donated by the following calculation: (max*low)+low-1 (other variation is to reduce 1 from the lower bound and to add one at its upper bound but it doesn't really matter as long as we make our boundaries clear)
  4. When a client needs to obtain a number the next one from the current is used, once the entire series has been exhausted the algorithm goes back to step 1"
I decided to test the algorithm by using hibernate defaults
Mapping File:
<?xml version="1.0"?>
<!DOCTYPE hibernate-mapping PUBLIC "-//Hibernate/Hibernate Mapping DTD 3.0//EN"
"http://hibernate.sourceforge.net/hibernate-mapping-3.0.dtd">
<hibernate-mapping package="com.model">
    <class name="HiloCounter" table="HILO_COUNTER">
        <id name="id" >
            <generator class="hilo" />
        </id>
        <property name="name" type="string">
            <column name="NAME" />
        </property>        
    </class>
</hibernate-mapping> 
The java model class created is as below:
package com.model;

public class HiloCounter {
    private Long id;
    private String name;
    //setter getters

}
I did not create any tables and let hibernate do the initial table creation. On start up the generated code is as follows:
2094 [main] DEBUG org.hibernate.tool.hbm2ddl.SchemaExport  - 
    drop table if exists HILO_COUNTER
2141 [main] DEBUG org.hibernate.tool.hbm2ddl.SchemaExport  - 
    drop table if exists hibernate_unique_key
2141 [main] DEBUG org.hibernate.tool.hbm2ddl.SchemaExport  - 
    create table HILO_COUNTER (
        id bigint not null,
        NAME varchar(255),
        primary key (id)
    )
2157 [main] DEBUG org.hibernate.tool.hbm2ddl.SchemaExport  - 
    create table hibernate_unique_key (
         next_hi integer 
    )
2172 [main] DEBUG org.hibernate.tool.hbm2ddl.SchemaExport  - 
    insert into hibernate_unique_key values ( 0 ) 

On start up an additional table was created to manage the hi values. It was initially set to zero.
On trying to insert records into the table.
public static void testCreateCounters() {
    HiloCounter h1 = new HiloCounter();
    h1.setName("Object No 1");
    Session session = sessionFactory.openSession();
    Transaction transaction = session.beginTransaction();
    session.save(h1);
    System.out.println("Object Number 1 has been created with id " + h1.getId());
    transaction.commit();
}

As can be seen from the below logs, 
  1. at start-up hibernate picked up the current value of next_hi. This value it uses for generating keys for objects to be created . 
  2. So as to prevent any primary key collisions (with any other application updating the hilo_counter table) hibernate updates the value of next_hi to the next value. 
  3. Hibernate will not use a new key until it has exhausted all combinations that it can create with this next_hi value.
8516 [main] DEBUG org.hibernate.SQL  - select next_hi from hibernate_unique_key 
for update
8547 [main] DEBUG org.hibernate.SQL  - update hibernate_unique_key set next_hi =
 ? where next_hi = ?
...
8563 [main] DEBUG org.hibernate.id.TableHiLoGenerator  - new hi value: 0
...
8625 [main] DEBUG org.hibernate.jdbc.AbstractBatcher  - about to open PreparedSt
atement (open PreparedStatements: 0, globally: 0)
8625 [main] DEBUG org.hibernate.SQL  - 
    insert 
    into
        HILO_COUNTER
        (NAME, id) 
    values
        (?, ?)
On executing the code to create 3 objects the results is as follows . 
Key used : 0 for first 3record
                   1 for next 3 records ( Separate run) 
mysql> select * from hilo_counter;
+-------+-------------+
| id    | NAME        |
+-------+-------------+
|     1 | Object No 1 |
|     2 | Object No 2 |
|     3 | Object No 3 |
| 32768 | Object No 1 | 
| 32769 | Object No 2 |
| 32770 | Object No 3 |
+-------+-------------+
3 rows in set (0.00 sec) 
Unlike other generator algorithms (such as select), hibernate does not need to execute an additional fetch query to get the primary key of the newly created record after the object is saved.
The problem here is  that each time the algorithm restarts it leaves a 'hole' in the keys sequence. A large number of keys could be lost this way. Also it is not very easy to predict the next record in the table based on the primary key (unlike a sequence)
 On modifying my <generator> settings as below:
<generator class="hilo" >
    <param name="table">hi_value_table</param>
        <param name="column">hilo_counter_next_value</param>
        <param name="max_lo">3</param> 
</generator>
Instead of the default table the above table (hi_value_table) will be used. The hi_value is obtained from hilo_counter_next_value column and the maximum no of keys to be generated is specified by the max_lo parameter. 
In the default application the value of max_lo is 32,767(Short.MAX_VALUE)
If we execute  the above algorithm for our values ( initial value is 0)
as per the algorithm :
lower bound :0* 3 =0 (hi value updated to 1)
and upper bound = 0 +(3-1) = 2  => (ids from 0 to 2 generated without hitting db)

lower bound :1* 3 =3 (hi value updated to 2)
and upper bound = 3 +(3-1) = 5 => (ids from 3 to 5 generated without hitting db)

lower bound :2* 3 =6 (hi value updated to 3)
and upper bound = 6 +(3-1) = 8 => (ids from 6 to 8 generated without hitting db)
and so on...
The results for 20 records are as follows:

mysql> select * from hilo_counter;
+----+--------------+
| id | NAME         |
+----+--------------+
|  1 | Object No 1  |
|  2 | Object No 2  |
|  3 | Object No 3  |
|  4 | Object No 4  |
|  5 | Object No 5  |
|  6 | Object No 6  |
|  7 | Object No 7  |
|  8 | Object No 8  |
|  9 | Object No 9  |
| 10 | Object No 10 |
| 11 | Object No 11 |
| 12 | Object No 12 |
| 13 | Object No 13 |
| 14 | Object No 14 |
| 15 | Object No 15 |
| 16 | Object No 16 |
| 17 | Object No 17 |
| 18 | Object No 18 |
| 19 | Object No 19 |
| 20 | Object No 20 |
+----+--------------+
 Thus larger the value of "hi value", greater the number of records produced at client without hitting server for the ids.

seqhilo


An alternative approach to the table technique is to use Oracle styled sequences
<generator class="seqhilo">
        <param name="sequence">hi_value</param>
        <param name="max_lo">100</param>
</generator> 
Instead of getting the next hi value from the table, hibernate picks the high value from the sequence (which then increments itself) and uses it until its low values are exhausted or the application is restarted

6 comments:

  1. thanks for a good tut ... I understood HIGH is starting from 0 , and how max value of series is kept [=(HIGH*LOW)+(LOW-1) ].... my question is how is LOW calculated ?? is LOW = number of insertions ??

    ReplyDelete
    Replies
    1. ok got it
      <generator class="hilo" >
      <param name="table">hi_value_table</param>
      <param name="column">hilo_counter_next_value</param>
      <param name="max_lo">3</param>
      </generator>

      then is it correct to say that HIGH cannot be given via xml ? and it always starts with 0 then is updated 1 , 2 etc ??

      Delete
    2. Hi Lavnish,
      The high value is picked up by Hibernate from the database table. So every time the application starts, it picks up the value from table and uses it, while also incrementing the column value.
      So yes, by default is will start from 0 and move on.
      But if you want to start with a custom number, simply set the corresponding value in the hilo_counter_next column.
      Cheers

      Delete
  2. yes , but how to set it via xml? java code ?

    ReplyDelete
  3. I don't see any way to set it via xml. You could add an update query to be fired on start up in your import.sql file. This is however used only with the hbm2ddl tool.
    The other option is to have a query fired via java at application start-up, e.g. after your SessionFactory has been created.
    That said, I wouldn't really mess with this value - at best you will end up creating holes in the primary keys and at worst you could set it to a value that has already been used and end up generating duplicate keys.
    However if you are simply looking to verify that any record generated by the strategy will not result in duplicate keys, then the Java technique is a better option - try and save a new object, if it fails it means your high value is corrupted.

    ReplyDelete