Solving Sharding Routing Latency by Embedding Route Keys in Order IDs

Background: Routing Dilemma After Sharding

A major OTA platform's order system serves three channels — EU_CHANNEL (European multi-country), GLOBAL_CHANNEL (international site), and CN_CHANNEL (domestic international business) — handling tens of millions of order detail queries daily. Initially a single database sufficed, using a company-wide Snowflake-based distributed ID service generating 64-bit globally unique, trend-increasing orderIds with no embedded routing information.

Architecture Evolution

1. Single-Database Era

Order IDs were plain Snowflake IDs. Queries were simple: SELECT * FROM t_order WHERE order_id = ?. Performance was adequate for early traffic.

2. Sharding Introduces Routing Problem

Growing order volume forced sharding by channel + orderId % 4, physically isolating data per channel. However, orderIds remained plain Snowflake IDs without routing data. To query an order, the system had to:

Receive orderId but not know its channel

Query an order index table to fetch channel

Use channel to locate the correct shard

This added a mandatory "find shard" step per query, degrading latency from tens of milliseconds to hundreds of milliseconds, with P99 exceeding 1 second.

3. Order ID Encoding Optimization

Core idea: modify ID generation to embed routing information directly in the orderId, inspired by Chinese ID cards where the first 6 digits encode region. The solution embeds a 4-bit routeKey into the 64-bit orderId, allowing direct parsing at query time without any database lookup.

95% of queries no longer need index table lookups

Query performance improved by orders of magnitude (tens of times faster)

Database load reduced by 80%

Compatibility strategy: new orders carry routeKey for direct parsing; legacy orders fall back to index table lookup; a three-layer degradation ensures availability.

Technical Implementation: Order ID Encoding

1. Bit Structure Design

Based on industry practices like Meituan Leaf, the original Snowflake structure (41-bit timestamp | 5-bit datacenter | 5-bit machineId | 12-bit sequence) was modified by compressing machineId to free 4 bits for routeKey:

┌──────────────┬──────────────┬──────────────┬──────────────┐
│ Timestamp(41)│ Datacenter(5)│ routeKey(4)  │ Sequence(14) │
├──────────────┼──────────────┼──────────────┼──────────────┤
│ bit 63-23    │ bit 22-18    │ bit 17-14    │ bit 13-0     │
└──────────────┴──────────────┴──────────────┴──────────────┘

Key design points:

routeKey occupies 4 bits (bits 17-14), supporting 16 channels (2^4 = 16)

Positioned before sequence (bits 17-14) for easy bitwise extraction

Encoding mapping: EU_CHANNEL → 5 (0101), GLOBAL_CHANNEL → 2 (0010), CN_CHANNEL → 1 (0001), BIZ_CHANNEL → 3 (0011), CORP_CHANNEL → 4 (0100)

2. Why 4 Bits?

Capacity calculation: current 3 channels, future expansion. 4 bits = 16 channels, reserving 13 for growth. Trade-off analysis:

2 bits: only 4 channels, insufficient extensibility

8 bits: wastes space, squeezes sequence bits, hurts concurrency

4 bits: balances current needs + future expansion

3. Encoding Process (Full Flow)

Step 1: Caller passes region (country code) during order creation.

GenerateOrderIdRequest request = new GenerateOrderIdRequest();
request.setRegion("GB"); // UK
request.setUid("user123");

Step 2: Region → routeKey mapping (maintained by user data service). Example: GB/ES → EU_CHANNEL, CN → CN_CHANNEL.

Step 3: routeKey → 4-bit integer via switch:

private int encodeRouteKey(String routeKey) {
    switch (routeKey) {
        case "EU_CHANNEL": return 5; // 0101
        case "GLOBAL_CHANNEL": return 2; // 0010
        case "BIZ_CHANNEL": return 3; // 0011
        case "CN_CHANNEL": return 1; // 0001
        case "CORP_CHANNEL": return 4; // 0100
        default: return 0; // 0000 (exception)
    }
}

Step 4: Bitwise assembly into 64-bit Long (pseudo-code):

public long generateOrderId(String routeKey) {
    long timestamp = System.currentTimeMillis() - EPOCH;
    int datacenter = 3;
    int routeKeyBits = encodeRouteKey(routeKey); // e.g., 5 for EU_CHANNEL
    int sequence = getSequence(); // e.g., 123
    long orderId = 0;
    orderId |= (timestamp << 23); // timestamp left-shift 23 (5+4+14)
    orderId |= (datacenter << 18); // datacenter left-shift 18 (4+14)
    orderId |= (routeKeyBits << 14); // routeKey left-shift 14 ⬅️ key!
    orderId |= sequence; // sequence occupies low 14 bits
    return orderId;
}

Generated orderId example (decimal 1234567890123456789): bits 17-14 = 0101 (value 5 → EU_CHANNEL). Core techniques: left-shift (<<) to position fields, bitwise OR (|) to combine, lossless encoding preserving all data in 64 bits.

4. Decoding Process (Reverse Extraction)

Complete getRouteKey method with three-layer fallback:

private static String getRouteKey(Long orderId) {
    OrderIdDecoder orderIdDecoder = OrderIdFactory.getOrderIdDecoder();
    // Layer 1: parse from orderId
    String routeKey = orderIdDecoder.decodeRouteKey(orderId);
    if (StringUtils.isEmpty(routeKey)) {
        // Layer 2: from request context
        routeKey = RequestContext.get("routeKey");
    }
    if (StringUtils.isEmpty(routeKey)) {
        // Layer 3: infer from region
        String region = RequestContext.get("region");
        Optional<String> routeKeyByRegion = DataMappingService.getRouteKey(region);
        routeKey = routeKeyByRegion.orElse("");
    }
    return routeKey;
}

OrderIdDecoder

implementation:

public class OrderIdDecoder {
    private static final int ROUTE_KEY_OFFSET = 14;
    private static final long ROUTE_KEY_MASK = 0xF; // low 4 bits (0b1111)

    public String decodeRouteKey(Long orderId) {
        if (orderId == null) return null;
        try {
            int routeKeyBits = (int)((orderId >> ROUTE_KEY_OFFSET) & ROUTE_KEY_MASK);
            return decodeRouteKeyBits(routeKeyBits);
        } catch (Exception e) {
            log.error("Failed to parse orderId: {}", orderId, e);
            return null;
        }
    }

    private String decodeRouteKeyBits(int bits) {
        switch (bits) {
            case 5: return "EU_CHANNEL";
            case 2: return "GLOBAL_CHANNEL";
            case 3: return "BIZ_CHANNEL";
            case 1: return "CN_CHANNEL";
            case 4: return "CORP_CHANNEL";
            default: return null; // parse failure
        }
    }
}

Decoding example: orderId >> 14 then & 0xF extracts routeKey bits, mapped to channel name.

Three-Layer Routing Strategy

1. Design Philosophy

Not all orders parse successfully: new orders have routeKey, legacy orders don't, exceptions occur. Solution: three-layer degradation.

┌─────────────────────────────────────────────────────────────┐
│ Query Request (orderId)                                     │
└─────────────────────────────────────────────────────────────┘
                              │
                              ▼
┌─────────────────────────────────────────────────────────────┐
│ [Layer 0] Cache Layer                                       │
│ Hit → return shard index directly                           │
│ Miss → Layer 1                                              │
└─────────────────────────────────────────────────────────────┘
                              │
                              ▼
┌─────────────────────────────────────────────────────────────┐
│ [Layer 1] orderId Parsing Layer                             │
│ Extract routeKey via bitwise ops                            │
│ Success → compute shard, write cache, return                │
│ Fail → Layer 2                                              │
└─────────────────────────────────────────────────────────────┘
                              │
                              ▼
┌─────────────────────────────────────────────────────────────┐
│ [Layer 2] Context Retrieval Layer                           │
│ Get routeKey/region from request context                    │
│ Success → compute shard, write cache, return                │
│ Fail → Layer 3                                              │
└─────────────────────────────────────────────────────────────┘
                              │
                              ▼
┌─────────────────────────────────────────────────────────────┐
│ [Layer 3] DB Fallback Layer                                 │
│ Query order index table for channel field                   │
│ Success → compute shard, write cache, return                │
│ Fail → return default shard (last resort)                   │
└─────────────────────────────────────────────────────────────┘

2. Layer Distribution (Actual Data)

Target: progressively reduce Layer 3 share to <5%. Monitoring shows cache hit ~95%, Layer 1 ~75%, Layer 2 ~5%, Layer 3 ~20% (initial), with optimization phases driving Layer 3 down to 10% → 5% → 1% over 12 months.

Core Code Implementation

1. Cache Layer

public class ShardingCacheHelper {
    private static final String CACHE_PREFIX = "shard:";
    private static final int CACHE_EXPIRE_SECONDS = 24 * 3600;
    private final CacheService cacheService;

    public Integer getShardIndex(Long orderId) {
        String cacheKey = CACHE_PREFIX + orderId;
        String cachedValue = cacheService.get(cacheKey);
        if (StringUtils.isNotEmpty(cachedValue)) {
            return Integer.parseInt(cachedValue);
        }
        return null;
    }

    public void setShardIndex(Long orderId, int shardIndex) {
        String cacheKey = CACHE_PREFIX + orderId;
        cacheService.setEx(cacheKey, String.valueOf(shardIndex), CACHE_EXPIRE_SECONDS);
    }
}

2. Sharding Router (Complete)

public class ShardingRouter {
    private static final int SHARD_COUNT = 4;
    private final ShardingCacheHelper cacheHelper;
    private final OrderDao orderDao;
    private final ChannelShardConfig channelShardConfig;

    public int locate(Long orderId) {
        // Layer 0: Cache
        Integer cachedIndex = cacheHelper.getShardIndex(orderId);
        if (cachedIndex != null) return cachedIndex;

        // Layer 1: orderId parsing
        String routeKey = getRouteKey(orderId);
        if (StringUtils.isNotEmpty(routeKey)) {
            int shardIndex = calculateShardIndex(routeKey, orderId);
            cacheHelper.setShardIndex(orderId, shardIndex);
            return shardIndex;
        }

        // Layer 2 & 3: Context + DB fallback
        return fallbackLocate(orderId);
    }

    private int calculateShardIndex(String routeKey, Long orderId) {
        int baseIndex = getBaseIndex(routeKey);
        int offset = (int)(orderId % SHARD_COUNT);
        return baseIndex + offset;
    }

    private int getBaseIndex(String routeKey) {
        return channelShardConfig.getBaseIndex(routeKey);
    }

    private int fallbackLocate(Long orderId) {
        Order order = orderDao.queryById(orderId);
        if (order == null) return ShardIndex.OTHER.getIndex();
        String channel = order.getChannel();
        int shardIndex = calculateShardIndex(channel, orderId);
        cacheHelper.setShardIndex(orderId, shardIndex);
        return shardIndex;
    }
}

Pitfalls and Lessons Learned

1. Real-World Issues

Issue 1: Callers not passing region parameter. Post-launch, fallback query ratio hit 25%+. Root cause: ID generation service upgrade required region param, but legacy interfaces, scheduled jobs, and message consumers weren't updated. Generated orderIds had routeKey=0, unparsable. Fix: add monitoring instrumentation in ID service to log callers missing region, publish Top N offenders, drive upgrades with deadlines.

if (StringUtils.isEmpty(request.getRegion())) {
    metric("id_gen_no_region", getCallerService());
}

Issue 2: Legacy order compatibility. Millions of pre-migration orders lack routeKey but still need queries (after-sales, reconciliation). Solution: three-layer degradation (see Chapter 4); legacy orders hit DB fallback + cache; query share naturally declines over time.

Issue 3: Canary release data consistency. During gradual rollout, some machines used new ID logic, others old. Same-channel orders had mixed parsability. Fix: canary by channel, not by machine — ensure all orders of a channel use same version.

if (grayConfig.isNewVersionEnabled(routeKey)) {
    return newIdGenerator.generate(request);
} else {
    return oldIdGenerator.generate(request);
}

2. Design Trade-offs

Trade-off 1: Why not UUID? UUID lacks ordering, hurts B+ tree index performance, larger storage (128-bit vs 64-bit), no embedded routing.

Trade-off 2: Why only encode routeKey? Considered encoding more (country, user type, biz line) but chose minimal routeKey only. Reason: 64-bit space is fixed; each extra encoding bit reduces sequence bits, lowering concurrent ID generation capacity per millisecond. routeKey is the sole sharding determinant; other attributes retrievable via index table.

Trade-off 3: Why keep DB fallback? Ideal: 100% parse success, zero DB hits. Reality: legacy orders (10-20%), code upgrade lag (5-10%), exceptions (1-2%) unavoidable. Decision: retain fallback for 100% availability, monitor parse success rate, drive Layer 3 from 25% → 10% → 5% → 1%.

3. Monitoring and Optimization

Key metrics:

// 1. Log parse failures
metricError("orderId_decode_failed", orderId);
// 2. Layer distribution
metric("route_cache_hit", count);
metric("route_layer_1", count);
metric("route_layer_2", count);
metric("route_layer_3", count);
// 3. Failure reasons
metric("decode_fail_no_region", count);
metric("decode_fail_old_order", count);
metric("decode_fail_exception", count);

Dashboard example shows real-time parse success rate, layer breakdown, failure cause distribution, and Top 10 services missing region (e.g., xxx-refund-service 25k, xxx-cancel-job 18k). Optimization phases: identify offenders (now), upgrade legacy code 1-3 months (Layer 3 → 10%), continue 3-6 months (→5%), final 6-12 months (→1%).

Summary

Core Gains: Direct shard routing via embedded routeKey eliminates index table lookups for 95% of queries, slashing latency from hundreds of ms to tens of ms, cutting DB load 80%.

Applicable Scenarios:

Fit: Sharded systems with clear routing dimension, controllable ID generation logic

Not fit: Small data volumes, frequently changing routing dimensions, third-party ID services

References

Snowflake Algorithm - Twitter : https://github.com/twitter-archive/snowflake

Distributed ID Generation - Meituan Leaf : https://tech.meituan.com/2017/04/21/mt-leaf.html