The two applications end up using the same primary key value for distinct entries. Referring to Figure 1, if User A creates a new contact, it's assigned a primary key of three by incrementing the last created key value. When User B also decides to insert a new contact, going through the same process, the application will assign a primary key value of three to his contact. Our primary key value is no longer unique since the same primary key value refers to two distinct contacts. When User A and User B try to submit their changes back to the server, they'll collide.

For this method to work, User B would need to know that three had already been assigned to Sandra Black and to use four for Doug Johnson, but since all the applications are running offline and in isolation from each other, this is impossible. Plain old auto-increment won't work here.

Short of requiring that your application not be allowed to create data while offline (which makes for a rather limiting application), you'll need a method that allows isolated applications to create contacts but be guaranteed to assign them unique primary key values. Fortunately, there are number of ways to do this and Universally Unique Identifiers are among the simplest.

Universally Unique Identifiers
A Universally Unique Identifier is a 128-bit number that is typically represented as a 32-character alphanumeric string. If you have ever poked around the Windows registry, you'll find that it's full of UUIDs. UUIDs are algorithmically generated in a seemingly random fashion, and libraries are available in most programming languages. Every time a record is created, the offline application generates a new UUID to act as a primary key for that record. The magic of UUIDs is in their size. There are 2^128 valid UUIDs and so it's extremely unlikely that any two applications would ever generate the same one.

Returning to the contact list example, this method makes it very easy for each application to create contacts without knowing the other applications. When a user adds a contact, a new UUID is generated (see Figure 2).

Unfortunately this method is not without its drawbacks. The keys are very large and cumbersome. Both processing time and memory will be wasted in storing, searching, and comparing the long 128-bit keys compared to other methods. In addition, the generated keys are totally meaningless. Unlike the auto-increment keys (whose value represents the relative time that it was created), the UUID's actual value is moot.

As long as the user never actually sees the UUID, its large size may not be a problem. But if the UUID is exposed, say, as a confirmation number, it will be awkward for the user to use the 32-character alphanumeric string. But if disk space, processing power, and user readability aren't critical to your application, then UUIDs are a good solution. If you want smaller meaningful primary keys, you may want to consider composite keys.

Composite Keys
Up to this point the primary keys have only been single-valued, but this not a requirement. A primary key can be made up by composing multiple values together to give a composite key. As long as the composite key can uniquely identify a record, it's suitable for the job. The composite key method requires that your server has a method to uniquely identify every instance of the offline application and assign it a unique application identifier.

Once the application has been assigned an application identifier, it can use it to build a composite key with a simple auto-incrementing value. Individually, the AppID and the Id columns aren't guaranteed to be unique, but an [AppID, Id] pair is (see Figure 3).

Composite keys create some additional complexities compared to single-valued primary keys. There will be a slight performance penalty since each record interaction will have to compare two values instead of one. Composite keys also tend to be more cumbersome and awkward to program with.

Above all, extreme care must be taken to ensure an application identifier is never, ever, reused. Compared to UUID, the key values are much smaller and take up less space. Also unlike UUIDs, a composite key value carries additional intrinsic meaning. By simply looking at a key, you are able to tell where and when it was created.

If splitting the primary key across two values will be difficult for your application, consider using the global auto-increment method.

Global Auto-Increment
Similar to the composite key, this method requires that you can assign a unique application identifier to each application instance. Besides the application identifier, you also need to set a partition size. The partition size is the number of records that each application instance is allowed to create. The primary key is determined by a single auto-incrementing value. But it doesn't start incrementing from zero. Instead, it starts incrementing from an offset that's equal to the product of the partition size and its application identifier.

Figure 4 uses a partition size of 1,000. Since User A has an application identifier of 37, User A will begin inserting records with a primary key of 37,000 (37 x 1,000). An application is only allowed to assign primary keys up to the sum of its offset and the partition size. So, User A can assign values between 37,000 and 37,999. After it reaches 37,999 it must request a new application identifier from the server. In a sense, this method uses the application identifier to implicitly reserve a block of primary key values for use later.

The trick in global auto-increment is picking a suitable value for the partition size. If the partition size is too small, the application may exhaust its keys before it can request a new application identifier. If the partition size is too high, it's possible that the system will completely run out of keys.

Both the composite key method and the global auto-increment method require that you have a stable method to assign a unique application identifier to each instance of the application. If this isn't an option for your application, you may want to consider using a primary key pool.