Versions Compared

Version Old Version 9 New Version 10
Changes made by

thierry sinassamy

thierry sinassamy

Saved on

Key

  • This line was added.
  • This line was removed.
  • Formatting was changed.
Tip

The Framework proposed in this space (Alex Xu) is applied to propose a design : Getting started - a framework to propose...

Introduction

Step 1 - Understand the problem and establish design scope

Characteristics of unique IDs ?

IDs = unique & sortable

Does ID increment by 1 for each new record ?

ID increments by time, but not necessarily by 1.

IDs contain numerical values ?

Contain numerical values.

ID length requirement ?

IDs should fit into 64-bit.

Scale of the system ?

Able to generate 10000 IDs per second.

On this page.

Table of Contents

Step 2 - High-level design

Traditional approach - Non-Distributed System

Approach uses a shared counter, the latter increases at each call.

We can also, generate un ID as a timestamp function.

Shared counter and timestamp function are limited because generate issues :

  • multiple independent servers can generate the same ID;

  • the same ID generates for 2 consecutives requests.

Approaches in Distributed system

There are probably 7 options / approaches and here’s below an overall comparison table below.

UUID/GUID

MONGODB

CENTRALIZE MYSQL (FLICKR - TICKET SERVER)

MYSQL: CLUSTER

TWITTER SNOWFLAKE

SONYFLAKE

BAIDU UID GENERATOR

ORDERED

NO

YES, POSSIBLE

YES

YES

YES, ROUGHLY

YES, ROUGHLY

YES, ROUGHLY

SCALE

YES

YES

NO

YES, ROUGHLY

YES

YES

YES

LENGTH (BITS)

128

96

64

64

64

63

64

UNIQUENESS

RARE

NO, POSSIBLE

NO

NO

NO

NO

NO

SIMPLICITY

YES

YES

YES

NO

NO

NO

NO

GEO-LATENCY

FAST

FAST

SLOW

FAST, POSSIBLE

FAST

FAST

FAST

INDEXABLE

HARD

YES

YES

YES

YES

YES

YES

UUID

Each Web server could contain an ID Generator & the Web Server is responsible for generating IDs independently.

Pros & Cons for step 1

  • Pros : generating is simple (no coordination between servers and so, no synchronization issues); easy to scale in each web servers; uniqueness;

  • Cons : IDs are 128 bits long & we need 64 bits; IDs do not go up with time; IDs could be non-numeric.

CENTRALIZE

MYDQL

MYSQL (FLICKR) - TICKET SERVER

Ticket Server will generate distributed primary keys. The idea is to use a centralized auto_increment features in a single DB server (Ticket Server).

Pros & Cons for step 1

  • Pros: Numeric IDs. Easy to implement and works for small to medium scale apps.

  • Cons: single point of failure, but we can scale, but will introduce more challenges.

MySQL CLUSTER - Multi-Master Replication

MONGODB

Step 3 - Design deep dive

Alex Xu chooses the Twitter Snowflake approach because of the requirements established above.

Step 4 - Pros & Cons