7

In a non-sharded DB, I could just use auto-increment to generate a unique ID to reference a specific row.

I want to shard my DB, say into 12 shards. Now when I insert into a specific shard, the auto-increment ID is no longer unique.

Would like to hear anyone's experience in dealing with this problem.

1
  • never heard the term sharding before - thanks for adding it to my vocab
    – MrTelly
    Apr 25, 2009 at 12:45

5 Answers 5

11

A few approaches

1) Give each shard it's own ID, and use a composite key

2) Give each shard it's own ID and set ID ranges for each shard

3) Use a globally unique ID - GUID

3
  • 3
    Use the GUID and don't worry about the ranges and composite-key. You'll inevitably at some point add another shard or need to reorganize your shards and your numbering scheme will need to be refactored.
    – Jeff Fritz
    Apr 25, 2009 at 12:45
  • 1
    @Jeff: GUIDs do have a serious downside, they are large. Depending on the reason for divying up the DB it could be a significant factor. Using ID ranges allows for a small (32 bit) single field PK with no collisions across the various DBs. So I would agree that if volume isn't an issue use GUIDs but they're not always appropriate. It helps if one doesn't link the identity of the creating DB with the ID. That way DBs can "lease" ID ranges which eliminates issues in "refactoring". Apr 25, 2009 at 12:57
  • 1
    Personally I loath GUIDs as keys, as you can't yell - look at record 123456, GUIDs are anti-human
    – MrTelly
    Apr 25, 2009 at 13:12
3

The two approaches I've used to this sort of problem:

  • GUID: Easy to implement, creates larger tables and indexes though.
  • ID Domain: I made that term up but basically it means dividing the 32 (or 64) bits of an integer type into two parts, the top part is represents a domain. The number of bits to use for the domain depends on how many domains you want to support verses the number of records you expect a single domain to introduce. In this approach you allocate a domain to each shard. The down side is DBs (that I know of) do not support this approach directly you need to code ID allocation yourself.
2
1

1) You can two rows (one indicates the ID and the second the database id)

2) Use Guids

1
  • 2
    Did you intend to say 2 columns instead of 2 rows in your first option? Aug 4, 2015 at 4:47
0

I have the same dilemma. I think I will go with a redis solution. I will use a service like redis-cloud.com to generate unique ids. So I can still use bigint for every data inserted into my sharded table. IT will be sequential so no page splitting will occur. Furthermore, paging is now very easy to do. IT solves me the friendly URLs problem because I didn't want to use a GUID in the URL. Furthermore, Redis cloud is a scalable solution, very reliable and has auto-fail over.

I don't need to decide on a range to split my data, I just use MD5 hash on the primary key to divide the data equally between the shards. For HA, I've decide to use Amazon RDS for easy point in time backup/restore and replication.

I think Flickr uses the same technique, but they have two generators, one for odd numbers and another for even numbers.

0

Keeping your databases in a consistent hash loop would help. This way you can ensure that each db has to handle only a range of id(s). So no two db will have any common id. This also solves the problem of adding and removing databases from the system.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.