How to Scale Redis for Billions of Keys: Memory‑Saving Strategies

1. Requirement Background

The DMP needs to cache massive third‑party ID data, including media cookies, its own "supperid" mappings, demographic tags, mobile IDs (IDFA, IMEI), blacklists, and IPs. Offline storage of billions of records on HDFS is easy, but the DMP must support millisecond‑level real‑time queries, requiring all new cookie‑mapping data to be instantly available, which creates a huge caching challenge.

Testing shows that storing over five billion KV pairs consumes more than 1 TB of memory; high availability with multiple replicas would further increase cost, and variable‑length keys cause severe memory fragmentation, demanding a massive‑scale storage solution.

2. Data to Store

Demographic tags are associated with cookie, IMEI, IDFA and include gender, age range, and geographic region. Mapping relationships link media cookies to the unified "supperid". Example storage formats:

媒体编号-媒体cookie=>supperid

supperid => { age=>年龄段编码, gender=>性别编码, geo=>地理位置编码 }

Device IDs are stored similarly:

imei or idfa => { age=>年龄段编码, gender=>性别编码, geo=>地理位置编码 }

PC data requires two key‑value forms (key→value and key→hashmap), while device data only needs key→hashmap.

3. Data Characteristics

Short keys and short values: supersid is a 21‑digit number, IMEI is a lowercase MD5, IDFA is an uppercase MD5 with hyphens.

Media cookies have variable lengths.

Scale: supersid reaches hundreds of billions, media mappings reach trillions, mobile IDs reach tens of billions.

Billions of new mapping relationships are generated daily.

Some data can be predicted as hot (stable cookies), but most new mappings are unpredictable.

4. Technical Challenges

1) Variable‑length keys cause memory fragmentation.

2) Heavy pointer usage leads to a memory expansion factor of about 7×, a common issue for pure in‑memory stores.

3) Despite being able to predict hot cookies, a large proportion of newly generated IDs remain unpredictable.

4) Public‑network latency must stay below 60 ms, and query latency under 100 ms, meaning today’s new mappings and tags must stay entirely in memory.

5) Business requirements demand data retention for at least 35 days.

6) Memory is expensive; a solution for billions‑level keys is essential.

5. Solutions

5.1 Eviction Strategy

Because daily ingestion overwhelms storage, it is crucial to purge cold data and keep hot data. IDs have a lifecycle; many become invalid quickly. By aggregating logs in HBase and setting a TTL of 35 days, IDs not seen in the last 35 days are removed. In Redis, a 35‑day expiration is set, and each hit renews the TTL, effectively retaining active cookies/IDs while letting stale ones expire.

5.2 Reducing Expansion

Hash table size and key count determine collision rate. To cut the number of Redis keys, a bucket‑hashing scheme is used: the MD5 hash of the original key becomes a fixed‑length BucketId, and the original key→value pair is stored inside a hashmap under that bucket. Queries compute md5(key) → bucket, then hget(bucket, key) to retrieve the value.

By allowing many keys to share a bucket (e.g., 10 keys per bucket), the total number of Redis keys can be reduced by over 90 %.

Because a full MD5 hex string (32 characters) is too long for the target scale, the implementation uses a 33‑bit bucket space (≈2³³ buckets) and encodes the bucket ID using the full ASCII range (0‑127) instead of only hex characters, halving the key length.

public static byte[] getBucketId(byte[] key, Integer bit) {
    MessageDigest mdInst = MessageDigest.getInstance("MD5");
    mdInst.update(key);
    byte[] md = mdInst.digest();
    byte[] r = new byte[(bit-1)/7 + 1]; // each byte holds 7 usable bits (ASCII)
    int a = (int) Math.pow(2, bit%7) - 2;
    md[r.length-1] = (byte)(md[r.length-1] & a);
    System.arraycopy(md, 0, r, 0, r.length);
    for (int i = 0; i < r.length; i++) {
        if (r[i] < 0) r[i] &= 127;
    }
    return r;
}

The bit parameter determines the bucket space size (powers of two). For a hundred‑billion‑level store with an average of 10 keys per bucket, 2³⁰ buckets (≈1 billion) are sufficient.

5.3 Reducing Fragmentation

Fragmentation arises from memory misalignment and delayed reclamation after expiration. By storing fixed‑length Redis keys (bucket IDs) and truncating the original key to its last six characters for the hashmap key, memory alignment improves and fragmentation drops dramatically. The value stores only three bytes (age, gender, geo codes).

A practical low‑level trick is to restart Redis slaves and force a failover, which forces the master to compact its memory.

Using memory allocators such as Google‑tcmalloc or Facebook‑jemalloc further reduces fragmentation, especially when values are small.