A better method for dealing with identity gaps

(back)

Sybase ASE
All versions
Last updated: 09 January 2005

A better method for dealing with "identity gaps"

By Rob Verschoor

This article first appeared in the 4^th Quarter Issue 1998 of the ISUG Technical Journal.
A PDF version can be found here.
Additional information about identity gaps can be found here.

Note: the solutions for dealing with identity gaps as described in this article, apply to ASE pre-12.5.1. When using ASE 12.5.1, new features are available to fix identity gaps more easily. Details are described here.

Introduction
A well-known feature of Sybase Adaptive Server Enterprise is the "identity column". Identity columns are useful because they automatically generate consecutive numeric values upon insertion of new rows, while having minimal impact on performance.
(updated 07 january 2005: as of ASE 12.5.3, identity columns can also use int, smallint or tinyint datatypes).
A disadvantage of using identity columns is that so-called "identity gaps" may occasionally occur. Identity gaps are large, sudden jumps in the value of an identity column, which often cause problems for applications.
Unfortunately, there is currently no quick or easy way of repairing an identity gap. The standard remedy as recommended by Sybase Technical Support can be rather time-consuming, which may result in unacceptable, hour-long application downtime. For this reason, DBA’s or developers sometimes prefer to avoid the use of identity columns for applications with high availability requirements.

This article presents a database design technique that allows identity gaps to be fixed easily and quickly, taking no more than a few seconds. With this approach, full advantage can be taken of the functionality of identity columns, while minimising the impact on application availability in case identity gaps need to be repaired.

What "identity gaps" look like
To illustrate the problems related to identity gaps, let’s assume the following simplified database design for storing invoice data:

create table invoices
       (invoice_nr numeric(10,0) identity, 
       customer_nr int,
       amount money)

/* insert new invoice */
insert invoices (customer_nr, amount)
       values (@new_customer, @new_amount)

This involves a database table named invoices , having an identity column called invoice_nr. When a new invoice is created, the customer number and the amount payable are inserted into the invoices table. No value is specified for the invoice_nr column, as this value will automatically be generated as a result of the identity property. The value assigned to the new invoice number will be 1 higher than the previous invoice number that was generated. This way, identity columns automatically generate unique, consecutive numbers which make ideal primary keys in database systems.

An identity gap has occurred when there is a large, unexpected jump in the value of an identity column, like in this example:

1> select invoice_nr from invoices order by 1
2> go

invoice_nr 
---------- 
(...)
10028
10029
10030
10031
5000002
5000003

(1033 rows affected)

For some reason, the invoice inserted after nr. 10031 was not assigned number 10032 as was expected. Instead, the invoice number jumps to 5000002 and continues to count up from there. This phenomenon is referred to as an "identity gap".
Such discontinuities in identity values are often a serious application problem. For example, some applications might not be able to handle invoice numbers of more than, say, 6 digits. Indeed, identity gaps are usually discovered because of application errors resulting from the unexpected high values in an identity column.
From the point of view of a DBA or end-user, identity gaps are almost always inconvenient, and should often be fixed immediately.
It should be noted here that it is always possible that some individual identity column values are missing. This can happen when the transaction containing the insert operation is rolled back: the identity value that was already issued for this rolled-back row will not be re-used and therefore never show up as an invoice number.
In this article, an "identity gap" refers to a gap of a large number of units, and not to individual missing identity column values.

Why "identity gaps" occur
Identity gaps can occur following a rough server shutdown ("shutdown with nowait") or a crash of the server process. This is related to the algorithm the server uses to generate identity column values: essentially, a counter is kept in server memory, holding the identity value most recently issued. When a new row is inserted, this counter is incremented and the resulting value is assigned to the identity column in that row. While the new data row itself is written to disk, the new value of the in-memory counter is not. Only when the server is shut down in a normal way, this value is saved on disk.
This algorithm makes the identity feature very fast, because no I/O is required to generate a new value. On the other hand, should the value of the in-memory counter be lost, as is the case for a server crash or a "shutdown with nowait", it is not possible to continue at the next identity value, because the last issued value was not saved anywhere. In this case, the server will continue generating identity values starting at some much higher value - which is what creates the identity gap.
Exactly at which higher value the server picks up, is determined by the configuration parameter "identity burning set factor", which, to a certain extent, can be used to limit the maximum possible size of an identity gap. However, because this a server-wide setting, it is not possible to apply this to individual tables.
See the ASE System Administration Guide and Technical Document #20113 at http://www.sybase.com/detail?id=20113 for a detailed description of how to use this configuration parameter.
In view of these underlying technicalities, the risk of running into identity gaps could be seen as the price one has to pay for the high performance offered by the identity column feature. Also, it is clear that this risk cannot be completely excluded. DBA’s should be aware of this, and be prepared to perform recovery procedures.

Fixing "identity gaps" the slow, classical way
Let’s assume that, once an identity gap has occurred, it should be repaired as soon as possible. Basically, this involves the following two actions:

Updating those rows which have received very high values in their identity columns to the correct values that should have been generated instead. In the above example, 5000002 and 5000003 should be changed to 10032 and 10033, respectively.

Resetting the value of the identity column downwards, so that a correct value generated when the next row is inserted (10034 in the example).

Unfortunately, none of these actions can be performed directly. The DBA is not allowed to update the value of an identity column in an existing row, nor can the value of future identity values be modified downwards. Therefore, the only available procedure to fix a situation where identity gaps have occurred has been the following:

Switch on the identity_insert option for the invoices table with the following statement:

set identity_insert invoices on

This will allow an explicit value to be specified for the identity column in an insert statement. Note that this option can be enabled for only one table at a time.
For all rows with problematic 'high' identity values, delete the row and re-insert it with the proper value one would have liked to see there in the first place, effectively performing an update. In the example, this would update invoice numbers 5000002 and 5000003 to 10032 and 10033, respectively.
BCP the invoices table to a file, say invoices.bcp .
Drop and re-create the invoices table. Note that dropping the table will implicitly switch off the identity_insert option.
BCP the invoices.bcp file back into the invoices table using the BCP -E option (for identity insert).
Rebuild any indexes on the table, if applicable.

Applying this procedure to a multi-million row, real-life-size application table could well take a few hours, during which the invoicing application is unavailable. In many cases, end-users and management would probably find this situation unacceptable and ask their DBA unsettling questions as to why this problem could not have been avoided.
Even though this will hopefully remain a rare incident, there is always a possibility that such a repair procedure may have to be performed, because the risk of identity gaps just cannot be fully excluded. For this reason, DBA’s or developers sometimes choose not to use identity columns at all for applications with high availability requirements, because this could lead to unacceptable application downtime.
The above is not a far-fetched or hypothetical scenario: with a certain regularity, cries for help are posted in the Usenet newsgroup comp.databases.sybase by DBA’s suddenly facing an identity gap and who are desperate for a quick solution. Unfortunately, Sybase has not felt it necessary to implement additional functionality for making the process of fixing identity gaps easier, leaving DBA’s with nothing but the rather clumsy procedure described above.

A better way of repairing identity gaps
We will now look at a database design approach that allows DBA's to fix identity gaps quickly, in a matter of seconds or, in the very worst case, minutes.

The first step to achieve this is to use two database tables instead of one: the application table invoices plus a separate keytable named invoices_keytable.

create table invoices_keytable
       (dummy_key numeric(10,0) identity)
            
create table invoices
       (invoice_nr numeric(10,0), 
       customer_nr int,
       amount money)

Note that the invoice_nr column is no longer an identity column, but a ordinary column of datatype numeric. The identity column has moved to table invoices_keytable , which contains just this one column and nothing else. The purpose of this identity column, named dummy_key , still is to generate key values for new invoices, but in a slightly different way than before.
When creating a new invoice, first a new invoice number is generated by inserting an "empty" row into invoices_keytable . The identity value assigned to the dummy_key column in this row is then automatically available through the global, session-specific variable @@identity . This invoice number is then used to insert the actual new invoice data into the invoices table:

/* insert an "empty" row to generate new invoice number */
insert invoices_keytable values () 

/* use identity value as key value for new row */
insert invoices (invoice_nr, customer_nr, amount)
values (@@identity, @new_customer, @new_amount)

This two-step way of inserting a new invoice is functionally identical to the "classical" situation where the invoice_nr column in the invoices table would have the identity property. Also, identity gaps can still occur in this design, with the same consequences for the application as before. However, once this happens, this new approach offers a much better way to repair the identity gap. A DBA should then take the following steps:

Update the invoices table using a normal update statement:
```
update invoices
set invoice_nr = 10032 
where invoice_nr = 5000002
            
```
Contrary to the "classical" approach, this update will work because the invoice_nr column is not an identity column, but a normal column (NB: a similar statement is required for correcting invoice 5000003).

Drop and re-create invoices_keytable . No data is lost here, because the data rows in this table do not contain any useful information.

Reset the identity column value in invoices_keytable with the following statements:

set identity_insert invoices_keytable on
insert invoices_keytable (dummy_key) values (10033)
set identity_insert invoices_keytable off

The effect of these statements is that for the next row that will be inserted, the identity value generated will be 10034, which is exactly what the next invoice number should be. This is because the statement set identity_insert ... on allows an explicit identity value to be inserted in dummy_key column of invoices_keytable . If this value is higher than the highest identity value issued, the identity value is adjusted upwards. Because this mechanism doesn’t work in a downward direction, the table must be re-created first to make this trick work.

Of these three steps, the last two will always be very fast; these should take no more than a few seconds. The first step (updating the invoices table) should normally not take much time either; in case there are many invoice numbers that need to be corrected, this should still not take longer than a few minutes in the worst case.
The obvious way of implementing this reparation procedure is to put these actions in a stored procedure. In case an identity gap is found, the DBA just needs to execute this procedure and the problem will be fixed automatically. An example of such a stored procedure can be downloaded from http://www.sypron.nl/idgaps.zip.

Technical considerations
The first feature that makes this design work is the use of the global variable @@identity , which always holds the identity value assigned most recently in the current session. Because this variable is session-specific, different user sessions can be inserting into the invoices_keytable concurrently, without influencing each other’s @@identity contents.
The table invoices_keytable is used here in an unconventional manner: its only purpose it to quickly obtain a new invoice number in @@identity by inserting an "empty" row. The inserted row itself is not of any interest: the table could be truncated regularly to stop it from growing too large, for example by putting the table on a separate segment and using a threshold procedure.
In this scenario, inserts are performed into two database tables instead of in one table as in the "classic" situation. The extra insert into invoices_keytable is the price to be paid for the increased recoverability of the application. Fortunately, this overhead is very small: first, there is no need for an index on invoices_keytable , because no data will ever be retrieved from this table. Second, the table can be partitioned so that concurrent users will be inserting on different data pages, thus avoiding lock contention. In practice, the extra overhead turns out to be hardly noticeable.

Another point worth mentioning is that the two insert operations do not need to be encapsulated in a transaction. Suppose that the two inserts are indeed part of one transaction, and for some reason it is decided to roll back the insert into invoices . While this will cause no data row to be inserted into invoices_keytable , this will not have any effect on the next identity value to be assigned: once an identity value is issued, it cannot be "given back" or re-used anymore, due to the underlying memory-based algorithm. Therefore, transactional consistency between these two tables is not relevant.

This design technique works in all Sybase versions from 10.0 onwards. Note that table partitioning is only available in version 11.0 and later.

Proactive reparation of identity gaps
Designing a database to allow quick reparation of identity gaps is a major improvement compared to the "classical" situation. Still, it might be preferable to ensure identity gaps will never strike an operational application at any time.
This can be achieved by always running a program directly after server startup, which performs the following actions:

It inserts an "empty" row in invoices_keytable to obtain the next identity value through @@identity .
It retrieves the highest existing key value from the invoices table; hopefully, there would be an index to support this query.
It then compares these two values. If everything is normal, then the difference between these two values is not more than a few units (small gaps can always exist because individual insert operations can have been rolled back). If the difference is bigger than, say 100 units, this means an identity gap exists. A reparation procedure could then be run automatically, which drops and recreates the invoices_keytable.

Note that this check will cause one invoice number value to be missing from invoices , in case no identity gap exists. If this is not desirable, a variation on this procedure is to always rebuild the invoices_keytable, using the highest invoice number from invoices.
Assuming these actions are performed directly after server startup, and before any applications are using the database, an identity gap (if present) will not yet have affected the values in the invoices table because no new invoices have been inserted yet.
The situation will now be corrected immediately before wrong invoice numbers are generated. This ensures that identity gaps do not get a chance to go unnoticed until the first serious application problems start to appear. The downloadable example stored procedure mentioned earlier also works for this situation.

Conclusion
It is possible to avoid the problems caused by identity gaps, the risk of which is implied when identity columns are used. Using the two-table design technique described in this article, identity gaps can be repaired quickly and even automatically, in contrast with the much more inefficient classical approach. This results in a significant improvement in application availability at a negligible performance cost.

Additional information (added 29-Dec-1999):

Setting the maximum identity gap size in ASE 12.0
Starting with version 12.0 of ASE (released December 1999), it is possible to specify -for a specific table- the maximum size the identity gap can ever have as a result of a rough server shutdown or a crash. This new feature can be a solution for some of the problems addressed by the above article , though it still does not cover all practical needs.
Setting the maximum identity gap size for a table guarantees that a potential identity gap for this table will not exceed this limit in case of a rough server shutdown. Note that this maximum identity gap size is specified in units of the identity value itself (as opposed to the related configuration option "identity burning set factor", which is specified as a fraction of the total identity column scope).

Syntax
There are three ways to specify a maximum identity gap size for a table, as described below. To create a new table with a maximum identity gap of 10:

create table tab_1 (column datatype,...)
             with identity_gap = 10

or:

select ...
into tab_2
with identity_gap = 10
from other_table ... (etc.)

To modify the maximum identity gap size setting to 1 for an existing table:

sp_chgattribute "tab_3", "identity_gap", 1

Note that by default (i.e. when not using any of the above commands), no explicit maximum identity gap size is set for an individual table; in this case, the size of a potential identity gap will be determined by the server-wide configuration parameter setting "identity burning set factor", as has always been the case in ASE version 11.9 and earlier (see Sybase Technical Document #20113 ).
Similarly, after upgrading to version 12.0 from earlier ASE versions, there will be no table-specific maximum identity gap size settings for any existing tables; the DBA must explicitly specify this setting using the "sp_chgattribute" procedure (see above example).

Technical
When using the "identity_gap" feature in ASE 12.0, ASE will save the current identity value to disk as often as needed to guarantee that the maximum identity gap size could never be exceeded in case of a rough server shutdown. This is basically achieved by saving the identity value to the table's OAM page, and writing this page to disk.
As a consequence, there may be a performance issue to be considered: when setting the maximum identity gap size to a lower value, the table's OAM page will be written to disk more often: when setting it to 1, the OAM page will be written to disk for every insert into the table. These additional OAM page writes could potentially result in a performance degradation if there are many concurrent processes inserting into the table.
As there isn't much experience with these performance effects yet (it's a new feature after all), it's probably best to do some thorough performance testing for your specific situation.

To completely avoid shutdown-induced identity gaps, the maximum identity gap size should be set to 1; this is also the lowest possible value: setting it to 0 effectively removes the setting and reverts to the default situation which is determined by the "identity burning set factor".
Note that the new "identity_gap" feature only offers protection against identity gaps caused by a rough server shutdown, a server crash or a system failure; small gaps of a single unit (or a few units), caused by insert operations that have been rolled back, may still occur.

What to use ?
So what about the two-table design technique described in the original magazine article above ? It would be good if it had become obsolete because of the new "identity_gap" feature, but in my view, unfortunately, it hasn't. This is because of the following remaining issues for which there is still no documented and supported solution:

It is still not possible to reset an identity value downwards in an easy way (not counting the undocumented, unsupported and hard-to-use command "dbcc object_atts"; see the ASE QuickRef for syntax).

When an identity gap has occurred, it is still not possible to update the identity column values in the already inserted rows; therefore it is still difficult to remove the gap.

For these issues, the two-table architecture described in the article above can be a reliable and dependable solution.

If avoiding identity gaps and the associated problems is important for your applications, I'd recommend the following, depending on your situation:

If you expect you ever need to modify identity column values in existing rows, or adjust the table's identity value downwards, consider the two-table design technique described above , irrespective of the ASE version you're running.

When running ASE version 11.9.x or earlier, consider the two-table design technique described above .

When running ASE version 12.0, and you are not expecting a high amount of concurrent insert activity, consider setting the "identity_gap" attribute to 1.

When running ASE version 12.0, and you are expecting a high amount of concurrent insert activity, run performance tests to choose between the two-table design technique described above , and using a low value for the "identity_gap" attribute.

I'm interested to hear about your experiences !