Design and Implementation of Meituan's Distributed ID Generation System Leaf

In large-scale distributed systems, Meituan‑Dianping requires globally unique identifiers for data and messages across services such as finance, payment, food delivery, hotel, and movie tickets. The ID requirements include global uniqueness, trend‑increasing order for InnoDB clustering, monotonic increase for special use‑cases, and security against sequential enumeration.

To meet these demands the ID generation service must provide ultra‑low average and 99.9th‑percentile latency, five‑nines availability, and high QPS.

Common approaches are introduced:

UUID : 128‑bit, locally generated, high performance but large (36‑char string), reveals MAC address, and hurts InnoDB primary‑key performance.

Snowflake‑like schemes : 64‑bit IDs split into timestamp, machine ID, and sequence; provide trend‑increasing IDs but depend on accurate clocks.

MongoDB ObjectID : 12‑byte (timestamp+machine+pid+inc) hex string.

Database auto‑increment : Simple using

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

, but creates a single‑point DB bottleneck and limits scalability.

The Leaf system combines the advantages of segment‑based and Snowflake‑like methods.

Leaf‑segment (database‑based) scheme

Leaf caches ID segments in a proxy server, reducing DB writes from every ID to one write per segment. Each business tag (biz_tag) isolates ID streams. The table schema is:

+-------------+--------------+------+-----+-------------------+-----------------------------+
| Field       | Type         | Null | Key | Default           | Extra                       |
+-------------+--------------+------+-----+-------------------+-----------------------------+
| biz_tag     | varchar(128) | NO   | PRI |                   |                             |
| max_id      | bigint(20)   | NO   |     | 1                 |                             |
| step        | int(11)      | NO   |     | NULL              |                             |
| desc        | varchar(256) | YES  |     | NULL              |                             |
| update_time | timestamp    | NO   |     | CURRENT_TIMESTAMP | on update CURRENT_TIMESTAMP |
+-------------+--------------+------+-----+-------------------+-----------------------------+

When a segment is exhausted, Leaf updates the DB with:

BEGIN;
UPDATE table SET max_id = max_id + step WHERE biz_tag = xxx;
SELECT tag, max_id, step FROM table WHERE biz_tag = xxx;
COMMIT;

Advantages: linear scalability, 64‑bit trend‑increasing IDs, high fault tolerance via segment cache, easy max_id configuration. Disadvantages: IDs are predictable, TP999 spikes during DB updates, DB outage still impacts service.

Double‑buffer optimization

Leaf pre‑loads the next segment asynchronously when the current segment reaches 10 % consumption, eliminating blocking on DB latency and reducing TP999 latency.

High‑availability design

Leaf uses a master‑two‑slave MySQL setup with semi‑synchronous replication and the open‑source DBProxy for failover. For stricter consistency, Paxos‑style MySQL Group Replication can be adopted. Services are deployed per IDC, using MTthrift RPC with load‑balancing that prefers same‑room instances, and OCTO provides overload protection and traffic shaping.

Leaf‑snowflake scheme

Implements the classic 1 + 41 + 10 + 12 bit layout. Worker IDs are assigned automatically via Zookeeper persistent sequential nodes, avoiding manual configuration. Startup steps:

Connect to Zookeeper and check for existing registration.

If registered, retrieve workerID; otherwise create a sequential node and use its sequence number.

Weak Zookeeper dependency is achieved by caching the workerID locally, allowing service restart even if ZK is unavailable.

Clock‑rollback handling

Leaf validates system time against stored timestamps and other nodes. If a backward jump is detected, it either waits, retries, or throws an exception. The handling code is:

// Clock rollback detection
if (timestamp < lastTimestamp) {
    long offset = lastTimestamp - timestamp;
    if (offset <= 5) {
        try {
            // wait double the offset
            wait(offset << 1);
            timestamp = timeGen();
            if (timestamp < lastTimestamp) {
                throwClockBackwardsEx(timestamp);
            }
        } catch (InterruptedException e) {
            throw e;
        }
    } else {
        throwClockBackwardsEx(timestamp);
    }
}
// allocate ID

In production since 2017, Leaf handles occasional leap‑second induced clock shifts without service impact.

Current status

Running on 4C8G machines, Leaf achieves ~50 k QPS with 1 ms TP999 latency, serving billions of IDs daily across Meituan‑Dianping services while maintaining high SLA.