Deduplication cache

When a producer sends a message to a broker, it expects an acknowledgement. If that acknowledgement fails to reach the producer, the producer may resend the message.

The original message might have been successfully processed on the first attempt. The failure occurs only in transmission, not in processing.

This can result in the same message being submitted and stored multiple times in the system.

A cache is a data structure stored in memory. It functions like a hash table with key-value pairs.

Unlike a hash table, which retains all entries indefinitely, a cache has a limited size.

When memory is full, the cache automatically removes entries to make space for new ones.

Caches can be classified as local or external.

• Local cache: Resides on the same machine as the application.
• External cache: Stores data on a separate machine, often across multiple servers.

Examples include Google's GoHava cache (local) and Redis, Memcached (external).

Local caches are simple and fast due to proximity to the application.

However, they lack scalability because memory capacity is fixed.

They offer no fault tolerance or durability. If the machine fails, data in the local cache is lost.

External caches are highly scalable.

Data is split into chunks and stored across individual machines.

Total capacity equals the sum of each machine’s capacity.

Such caches are known as distributed caches.

If data replication is supported, the external cache provides fault tolerance and durability.

External caches introduce an additional component to manage, deploy, and maintain.

Data is added to a cache via:

• Explicit put operation
• Implicit loading during a get operation

When a get is called and no data exists in the cache, the system loads the data.

Loading can be:

• Synchronous: The caller waits for data to be loaded from the underlying store.
• Asynchronous: The get call returns immediately, and a background thread loads the data.

As long as the cache has space, new entries are added.

When the cache reaches its size limit, entries must be removed to free space.

This process is known as eviction or replacement.

Several eviction policies exist, including:

• Least Recently Used (LRU): Evicts entries not accessed recently.
• Least Frequently Used (LFU): Evicts entries used least often.

Even with few entries, data may remain in the cache for long periods.

This can cause data to become stale.

To prevent staleness, time-based eviction policies are required.

When an entry is stored, a timestamp is assigned.

After a defined period, the entry is removed from the cache.

This ensures that cached data does not persist indefinitely and remains fresh.

Cache entries have a duration parameter specifying how long they remain valid.

After this duration, entries are considered expired.

Two common methods exist for removing expired entries from the cache:

• Passive expiration
• Active expiration

Passive expiration occurs when a client requests an entry.

If the entry is found to be expired, it is removed from the cache at that moment.

Active expiration uses a scheduled maintenance task.

This task runs at regular intervals.

It scans the cache and removes expired entries.

Eviction based on time ensures data freshness in the cache.

However, this mechanism is not ideal.

Every time an entry is evicted, a cache client accessing it experiences increased latency.

The client must wait for data to be loaded from the data store.

Refresh helps avoid this latency.

It allows entries to be updated without being evicted.

The difference lies in how data is loaded when accessed:

• Expiration: data is loaded synchronously
• Refresh: data is loaded asynchronously

When a client requests an expired entry:

• The entry is removed from the cache
• A new value is loaded synchronously

This causes a pause for the client.

When a client requests a value due for refresh:

• The existing cache value is returned immediately
• A new value is loaded asynchronously in the background

The client does not wait.

This technique is especially useful for hotkeys.

Hotkeys are frequently accessed keys.

Avoiding data load pauses is critical for performance.

A cache has:

• Refresh time: 1 minute
• Expiration time: 2 minutes

At time 0, a new entry is added.

After 1 minute, the entry is eligible for refresh.

After 2 minutes, the entry is eligible for expiration.

If accessed within 1 minute of addition:

• The entry value is returned immediately

If first accessed after 1 minute:

• The entry value is returned immediately
• An asynchronous load is initiated in the background

If first accessed after 2 minutes:

• The entry is considered stale
• A synchronous load is initiated
• The client waits for the load to complete

This pattern—refreshing entries before expiration—is called refresh ahead.

When a producer sends a message to a broker:

• The producer also sends a duplication ID

The duplication ID is unique per message.

If not provided, the broker generates one.

Generation methods include hashing the message body.

The broker stores duplication IDs in a local cache.

It retains them for several minutes.

When a message is sent:

• The broker checks if the duplication ID exists in the cache

If not found:

• The message is new
• The broker accepts it

If found:

• The message is a duplicate
• The broker rejects it

This ensures the message is processed only once

Even if sent multiple times by the producer