Embedding Sharding Genes in Business IDs for Direct Routing in Sharded Databases

1. Scenario and Challenge

Orders, transaction logs, and messages are often sharded by userId (or merchant ID). Writes naturally follow the shard key, but many queries only have an orderId (e.g., payment callbacks, customer‑service tickets). The core difficulty is shard key ≠ query key . Common work‑arounds are:

Broadcast query: scan all tables, cost grows linearly with shard count.

Mapping table: maintain orderId → userId / shard, adding storage and consistency burden.

The goal is to let the business ID carry its own routing information so that the ID alone determines the target table.

2. Gene Method Concept

The “gene” reserves a fixed number of low‑order bits in the business ID to store the shard number. When generating an ID, the shard number is calculated and embedded; when reading, a mask extracts the shard number, enabling direct routing without an external mapping.

┌───────────────────────┬───────┐
│   Sequence (high bits) │ Gene  │
│   Redis INCR / …      │ shard │
└───────────────────────┴───────┘
<< GENE_BITS empty | OR‑bit‑OR write

3. Implementation

3.1 Sequence Generation (Redis INCR)

A simple Redis‑based generator increments a key to obtain a globally unique sequence number.

public final class RedisIncrIdGenerator {
    private static final String DEFAULT_KEY = "scene:id:incr";
    private final JedisPooled jedis;
    private final String key;
    public RedisIncrIdGenerator(JedisPooled jedis, String key) {
        this.jedis = Objects.requireNonNull(jedis, "jedis");
        if (key == null || key.isBlank()) {
            throw new IllegalArgumentException("key 不能为空");
        }
        this.key = key;
    }
    /** Generate the next numeric ID */
    public long nextId() {
        return jedis.incr(key);
    }
}

3.2 Embedding and Resolving the Gene

private static final int GENE_SHARD_LENGTH = 4; // 4 bits for the gene
private static final int TABLE_COUNT = 1 << GENE_SHARD_LENGTH; // 16 tables

/** Embed gene into the ID */
long embedGene(String userName, long originId) {
    int mask = TABLE_COUNT - 1; // 0b1111
    int tableNo = userName.hashCode() & mask; // gene = table number
    return (originId << GENE_SHARD_LENGTH) | tableNo;
}

/** Resolve table number from a gene‑embedded ID */
int resolveTableNo(long id) {
    return (int) (id & (TABLE_COUNT - 1));
}

3.3 Step‑by‑Step Example

Assume GENE_SHARD_LENGTH = 4, TABLE_COUNT = 16, and originId = 1. The hash of the user name yields tableNo = 0.

Mask: 16 - 1 = 15 (0b1111) Embed gene: 1 << 4 | 0 = 16 (0b10000) Resolve gene: 16 & 15 = 0 The table number is correctly recovered, confirming the routing loop.

4. Extending the Gene Idea

4.1 Snowflake

Snowflake’s classic layout is timestamp | machineId | sequence. To embed a gene, reserve a few bits from the machine‑id or sequence field and write the shard number there. Generation uses the same userId → tableNo calculation, then assembles the final 64‑bit ID. The trade‑off is reduced space for machine IDs or sequence numbers, which may affect cluster size or per‑millisecond throughput.

| timestamp | shortened machineId | sequence | gene |

4.2 Leaf (Segment Allocation)

Leaf obtains a segment of IDs from the database and increments locally. The gene can be inserted by shifting the segment sequence left by GENE_BITS and OR‑ing the table number: newId = segmentSeq << GENE_BITS | tableNo Often the segment is still allocated centrally while the gene remains in the ID, preserving the same routing advantage.

4.3 Commonality

Regardless of the underlying generator (Redis INCR, Snowflake, Leaf), the essential step is to place the gene bits inside the ID layout so that the query side only needs to mask the ID ( id & mask) to obtain the shard, eliminating any external orderId → shard mapping.

5. Using Gene‑Based Routing

When writing, compute the shard number once (e.g., via userName.hashCode() & mask) and embed it into the ID before persisting. When only the ID is available (e.g., payment callback), extract the shard with the same mask and perform a point query.

/** Compute shard from user name */
public static int getShardByUserName(String userName) {
    if (userName == null || userName.isBlank()) {
        throw new IllegalArgumentException("userName 不能为空");
    }
    int mask = TABLE_COUNT - 1;
    return userName.hashCode() & mask;
}

Write path: Use the computed tableNo (or userId & mask) to embed the gene and store the record in the corresponding table.

Read‑only path: With only orderId, apply orderId & mask to obtain the shard and query directly, avoiding broadcast.

Database sharding middleware: Custom sharding algorithms (e.g., ShardingSphere) can apply the same mask operation on primary keys to stay consistent with the gene method.

6. Common Pitfalls and Considerations

Changing gene bit length after deployment: Existing IDs will be mis‑parsed; expanding tables should be done by doubling the table count and migrating data, not by altering the bit width.

Table count not a power of two: The mask (N‑1) no longer equals % N, causing uneven distribution. Keep TABLE_COUNT as a power of two or use explicit modulo with the performance penalty.

Hash skew: String.hashCode() is only for demonstration; production should use a stable hash (e.g., MurmurHash) with a fixed charset.

Left‑shifting reduces sequence space: Each additional gene bit halves the usable sequence range; plan the total bit allocation according to capacity needs.

Redis availability: When the ID generator relies on Redis, ensure high availability and key‑space planning (e.g., separate counters per business line) to avoid hot keys.

Gene ≠ uniqueness or anti‑guessability: The gene only encodes routing; uniqueness and security must still be guaranteed by the underlying ID generator and business constraints.

7. Summary

The most frustrating situation in sharded databases is “writes follow key A, queries only provide key B”. The gene method solves this by packing the shard number into the low bits of the business ID, allowing the same ID to be used for both insertion and point‑lookup routing. The sequence can be sourced from Redis INCR, Snowflake, or Leaf, with the core idea remaining identical.

Repository: https://gitcode.com/business-project/gene-id-generator