Ways to generate roughly sequential Ids (32 bits & 64 bits sizes) in a distributed application

What are the good ways to generate unique "roughly" sequential Ids (32 bits & 64 bits sizes) in a distributed application ?

[Side Note: My DB does not provide this facility.] Also I do not want to use 128 bits UUIDs.

EDIT: Thanks all for your response!

As some of you suggest using Mysql开发者_如何学运维 db like flickr's ticket servers, I doubt that using multiple servers(in order to eliminate Single point of failure) may disturb some sequential nature of the generated Ids since some servers may lag behind the others. While I am ok with a lag of a few Id sequences but cannot afford huge disturbances in sequentiality.

Building on @Chris' idea of having a table to generate the "next" identity. A more reliable way of doing this is to have two servers and a round-robin load-balancer. Server 1 distributes odd numbers, Server 2 distributes even numbers. If you lose one server, you get all odds or all evens, but the show still goes on.

Flickr uses something very similar for their ID system

http://code.flickr.com/blog/2010/02/08/ticket-servers-distributed-unique-primary-keys-on-the-cheap/

Then creatively use MYSQL's atomic REPLACE syntax like follows:

CREATE TABLE `Tickets64` (
  `id` bigint(20) unsigned NOT NULL auto_increment,
  `stub` char(1) NOT NULL default '',
  PRIMARY KEY  (`id`),
  UNIQUE KEY `stub` (`stub`)
) ENGINE=MyISAM

REPLACE INTO Tickets64 (stub) VALUES ('a');
SELECT LAST_INSERT_ID();

Where the stub value is sufficient to generate the next identity in an atomic fashion.

Update with the OP Chronology and Sequence requirements

With Chronology as a driver your choices change a litte - an atomic state in a SPOF - Chris' idea in SQL for example. This will be a bottleneck, and it's state must be durable to prevent duplicate IDs being issued.

To achieve chronology at scale with high-availability in a distributed system, causal sequence algorithms are pretty much the only way to go - there are a few out there:

• Lamport timestamps
• Vector Clocks
• Dependency Sequences
• Hierarchical Clocks

The calling pattern is quite different than the SPOF strategy, they require you to track and pass a memento of sequence, timestamp or version - effectively session information for the sequence you are generating. They do however guarantee causal order for any given sequence or item even in a distributed system. In most cases an event PK would be the compound of item identifier + causal sequence id.

Since you have a database, you can create a table with the next value in it. Aquiring this value will require you to select the value and update the row with the new next value, where the row had the old value, if the update fails to affect any rows then some other process or thread was able to aquire the value before you and you need to retry your attempt to get the next value.

The pseudo code for this would look something like this

do
  select nextvalue into MyValue from SequenceTable
  update SequenceTable set nextvalue= nextvalue + 1 where nextvalue = MyValue
while rowsaffected = 0

In the above, MyValue is the variable that will hold the nextvalue from the database table SequenceTable, and rowsaffected is an indicator that indicates how many rows where affected by the last SQL statement which in this case is the update statement.