CREATE TABLE cust (
Cust_Id int(10) unsigned NOT NULL AUTO_INCREMENT,
Server_Id smallint(6) NOT NULL DEFAULT ‘1’,
First_Name char(15) DEFAULT NULL,
Last_Name char(20) DEFAULT NULL,
PRIMARY KEY (Cust_Id,Server_Id)
) ENGINE=InnoDB AUTO_INCREMENT=4 DEFAULT CHARSET=latin1

When each database is defined, run an app that alters the default value of the Server_Id of each table. (You probably also want a ServerId table with a row set to the same value). When the table data gets merged from other servers, you still have unique rows and you know which server created the row. The user app would identify each row as ccccc.sss where ccccc is the Cust_Id and sss is the server id. So the user sees customer id of 1234.21 and the program behind the scene just splits it into Cust_Id=1234 and Server_Id=21.

It is fast and it is readable. Of course it all depends on the administrator setting up unique Server_Id values for each server but if they are on a network you can write an app to do it and verify it.

Mike

First simply SELECT REVERSE(UNHEX(REPLACE(UUID(),’-‘,”))); this will give us the UNHEXed and REVERSEd UUID in the way that Jens Wagner above suggests. Then you can place this value into your database as you please.

Then when you retrieve the UUID from the database later, you call SELECT HEX(REVERSE(‘{$uuid}’)); And to make the UUID look more “natural,” simply run strtolower() to remove the caps.

1388681F-7348-11DF-83CD-D0B6181E9833
13CF3551-7348-11DF-8556-D1B6181E9833
13F8B66F-7348-11DF-BBC6-D2B6181E9833
141E8E03-7348-11DF-BFCE-D3B6181E9833
1438CCD7-7348-11DF-807F-D4B6181E9833

To improve InnoDB insert performance, primary keys should be inserted with least changing bits first, correct?

I wrote two functions to encode and decode UUIDs, please find them below.

Best,
-jens

DELIMITER $$

CREATE FUNCTION ENCODE_UUID (uuid CHAR(36))
RETURNS BINARY(16)
DETERMINISTIC
BEGIN
RETURN REVERSE(UNHEX(REPLACE(uuid, ‘-‘,”)));
END
$$

DELIMITER $$

CREATE FUNCTION DECODE_UUID (uuid BINARY(16))
RETURNS CHAR(36)
DETERMINISTIC
BEGIN
RETURN concat(
HEX(LEFT(REVERSE(uuid),4)),’-‘,
HEX(MID(REVERSE(uuid),5,2)),’-‘,
HEX(MID(REVERSE(uuid),7,2)),’-‘,
HEX(MID(REVERSE(uuid),9,2)),’-‘,
HEX(RIGHT(REVERSE(uuid),6))
);
END
$$

SELECT DECODE_UUID(ENCODE_UUID(‘0935C9C3-7345-11DF-BADD-A8B4181E9833’))

BTW in PHP that looks like this:
$uuid = substr($uuid, 0, 8) . substr($uuid, 9, 4) . substr($uuid, 14, 4) . substr($uuid, 19, 4);
where $uuid is the result of doing a SELECT UUID() in MySQL.

1. Concatenate the numeric user id (1-9 digits) and the UNIX timestamp (10 digits)
–> [i.e. “3333” . “1111111111” = “33331111111111”] ***GUARANTEED UNIQUE.

2. Convert to base-36
–> [ “33331111111111” –> “a3gsei3”] — (if I had 100 million users, the longest ID would still only be 10 characters)

3. Store as binary in CHAR().

My best guess is that this strategy is a win-win (for my situation) over GUIDs and INTs. I have guaranteed-unique ids (since they are tied to the user id and the timestamp) that are available without querying the database. PLUS, they are SIGNIFICANTLY shorter than GUIDs (they are 1/3 the size).

Admittedly, I’m relatively new to highly-scalable database architecture, so I’d appreciate any thoughts or feedback. Thanks.

I would also like to see a UUID data type (which would use 16-byte binary representation instead of VARCHAR(36))

I noticed your benchmark which shows 200 times performance differences between auto-increment and UUID(). I’m wondering if you did the same thing for InnoDB as well. We are using MySQL 5.0 and InnoDB, we got badly lock conflict when inserting rows into InnoDB tables with auto-increment column. So, we are considering to switch to UUID() as a PK. I did a very simple testing: wrote a stored procedure, which has a loop to insert a row into a table. the results for InnoDB are shown as below: inserting 100,000 rows into InnoDB tables, for a table with auto-increment, it tooks 254 sec; for a table without auto-increment but use UUID(), it took 263 sec; the same testing for MyISAM tables, I got 54 sec vs. 68 sec. the 54 sec is similar to what you got. What I did wrong?

In an effort to improve the situation, I created a simple UUID class capable of generating random UUID’s with an option to store them in Base64 rather than hex. Since the length of the UUID is always constant, I was able to trim off the extra = in the Base64 conversion and come up with a case-sensitive 22-byte UUID representation (VTIW7xOgReOGrL3vMRjm4Q, for example). The performance increase was enormous, and the overhead is much smaller (22 bytes vs. 16) and you are able to convert to binary and hex at any time.

Later, as I thought more of the problem, I realized the Base64 encoding was inefficient for a 128-bit number. In order to get maximum efficiency out of Base64, the number of bits needs to be divisible by 6. So I created a new identifier that was only 72 bits. (Yes, the collision probability goes up, but it is still one in 4.7 * 10^21.) These UID’s (as I call them) only take 12 bytes to store in a binary column and strike a very good balance between speed and uniqueness. They can also be translated to GUID’s (########-0000-0000-0000-00##########) and back when needed. (If 72-bits is not enough, use 96 bits to make a 16-byte UID).

Write a function that converts the value returned by the UUID function to binary and store it in a binary(128) column. Write yourself another function that will cast it back to a characters string with hyphenation if you need to display it.

However, the primary use for UUIDs or GUIDs is data portability, not speed for searching. If you have worked for large companies where you have redundant data stored in many locations you have to manage this primary key much closer and have the ability to generate something that you know will be unique across the company. Integers and auto increment will not cut it.

I can tell you what we do for http://www.boardreader.com with some billion rows which need quick retrieval.
The data is partitioned in “table groups” which are mapped to the servers. We use 64bit identifiers with lower byte used to store table group.

Search is done using “Sphinx” search engine and we basically need to find rows by IDs to show result set in most cases.

Do you have any good links or more information on how to go about doing “client side sharding of data.” This sounds like what I need to do. I am creating a app that will need quick storage and retrieval of 8-10 Billion rows of data. Splitting up the data onto several servers with a deterministic way of finding it again is what I need.

Any help would be greatly appreciated.