Part 2: "Beyond Strings" — The Anatomy of Data Structures

Story Opening

The success of the Cache-Aside pattern during Black Friday bought Maya, the new Staff Engineer at GlobalMart, immense credibility. The product catalog was flying out of Redis, and the PostgreSQL database was finally breathing easy. However, the product team was relentless. They wanted to capitalize on the massive traffic spike by introducing a “Trending Now” feature—a real-time, global leaderboard of the top 100 most-viewed products across the entire site, updating every second.

Maya’s initial thought was to use the existing PostgreSQL database. She could add a views column to the products table and increment it on every page load. But she immediately realized the flaw: an UPDATE products SET views = views + 1 WHERE id = X query requires a row-level lock. Millions of concurrent users trying to increment the same popular product would cause massive lock contention, grinding the database to a halt. Even if she batched the updates, querying the top 100 products (SELECT * FROM products ORDER BY views DESC LIMIT 100) across millions of rows every second would require an expensive, constantly shifting B-Tree index scan.

She needed a data structure specifically designed for this exact problem: fast increments and instantaneous ordered retrieval. She needed to look beyond using Redis as a simple string cache. It was time to explore the true power of Redis: its native, in-memory data structures.

Conceptual Deep-Dive

Redis is often described as a “key-value store,” but this is a vast oversimplification. A more accurate description is a data structure server. In a traditional key-value store (like Memcached), the value is an opaque blob of bytes. The server doesn’t know what’s inside; it just stores and retrieves it.

Redis, however, understands the type of the value. When you store a list, Redis knows it’s a list and provides atomic operations to push, pop, or trim it. When you store a set, Redis provides operations to calculate intersections, unions, and differences.

This is a profound architectural shift. Instead of pulling data out of the database into the application memory, manipulating it, and pushing it back (which is slow and requires network round trips), you send the operation to the data. Because Redis executes commands sequentially in a single thread, these operations are inherently atomic.

The Anatomy of Redis Data Types

Let’s dissect the core data structures Maya evaluated for the leaderboard feature, focusing on how Redis implements them internally for maximum performance and memory efficiency.

1. Strings (Simple Dynamic Strings)

The most basic Redis type is the String. However, Redis doesn’t use standard C strings (null-terminated character arrays). Instead, it uses a custom structure called Simple Dynamic Strings (SDS).

Why reinvent the wheel? Standard C strings require an $O(N)$ traversal just to find their length (by searching for the null terminator \0). Furthermore, appending to a C string requires allocating new memory and copying the old string, which is slow and can cause memory fragmentation.

An SDS header looks roughly like this in C:

struct sdshdr {
    int len;      // Length of the string
    int free;     // Unused bytes available in the buffer
    char buf[];   // The actual character array
};

By storing the length explicitly, operations like STRLEN become $O(1)$. By pre-allocating extra space (free), Redis minimizes memory reallocation when appending to strings (APPEND). Furthermore, because SDS doesn’t rely on null terminators, it is binary-safe, meaning it can store images, serialized objects, or audio files just as easily as text.

2. Hashes (ZipLists and Hash Tables)

A Redis Hash is a map between string fields and string values, perfect for representing objects (e.g., a User object with fields like name, email, and age).

Redis employs a fascinating memory optimization technique here. When a Hash is small (few fields, short values), Redis doesn’t actually create a full hash table. Instead, it stores the data sequentially in a highly compressed, contiguous block of memory called a ZipList.

A ZipList avoids the memory overhead of pointers required by a traditional linked list or hash table. It stores the length of the previous entry, the length of the current entry, and the data itself. Searching a ZipList requires an $O(N)$ linear scan, but because the list is small and contiguous in memory, it fits perfectly into the CPU’s L1 cache, making the scan incredibly fast.

Once the Hash grows beyond a configured threshold (e.g., hash-max-ziplist-entries), Redis automatically and transparently converts the ZipList into a true Hash Table to maintain $O(1)$ lookup performance.

3. Sets (IntSets and Hash Tables)

A Redis Set is an unordered collection of unique strings. Like Hashes, Sets use memory optimization. If a Set contains only integers (e.g., user IDs) and is relatively small, Redis stores it as an IntSet—a sorted array of integers. Checking for existence in an IntSet uses binary search ($O(\log N)$), which is highly efficient and uses minimal memory. When the Set grows or non-integers are added, it converts to a Hash Table where the values are null, providing $O(1)$ lookups.

4. Sorted Sets (Skip Lists)

This was the data structure Maya was looking for. A Sorted Set is similar to a Set, but every member is associated with a floating-point number called a score. Redis automatically keeps the set sorted by this score.

If two members have the same score, they are sorted lexicographically by their string value. This makes Sorted Sets perfect for leaderboards: the member is the productId, and the score is the views count.

How does Redis achieve fast inserts, updates, and range queries on a sorted collection? A balanced tree (like a Red-Black Tree or AVL Tree) would work, but they are notoriously complex to implement and maintain, especially regarding memory rebalancing.

Instead, Redis uses a brilliant probabilistic data structure called a Skip List.

A Skip List is essentially a multi-layered linked list. The bottom layer is a standard, sorted linked list containing all elements. Each subsequent layer acts as an “express lane,” containing a random subset of the elements from the layer below it.

When searching for an element (e.g., 50), the algorithm starts at the highest layer. It traverses until it finds an element greater than the target, then drops down a layer and continues. This “skipping” behavior provides average search, insertion, and deletion times of $O(\log N)$, comparable to balanced trees, but with significantly simpler implementation and less memory overhead.

Technical Explanation

Maya decided to implement the “Trending Now” leaderboard using a Redis Sorted Set.

Here is the architectural flow:

1. Increment: Every time a user views a product page, the application sends an asynchronous message to a worker service.
2. Update Score: The worker service executes a Redis ZINCRBY command: ZINCRBY trending_products 1 "product:123". This command atomically increments the score (views) of the member (product:123) by 1. If the member doesn’t exist, it is added with a score of 1. Because Redis is single-threaded, there is no lock contention, and the Skip List is updated in $O(\log N)$ time.
3. Retrieve Leaderboard: When the frontend requests the top 100 products, the application executes a ZREVRANGE command: ZREVRANGE trending_products 0 99 WITHSCORES. This command retrieves the top 100 elements in reverse order (highest score first). Because the Skip List is already sorted, this operation is $O(\log(N) + M)$, where $N$ is the total number of products and $M$ is the number of elements returned (100). It is blazingly fast.

Step-by-Step Hands-On

Let’s look at how Maya implemented this using Spring Data Redis and the RedisTemplate.

Step 1: Configuring the RedisTemplate

While Spring Cache (@Cacheable) is great for simple key-value caching, interacting with advanced data structures requires the RedisTemplate. Maya configured it to use String serializers for both keys and values to ensure readability in RedisInsight.

import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;
import org.springframework.data.redis.connection.RedisConnectionFactory;
import org.springframework.data.redis.core.RedisTemplate;
import org.springframework.data.redis.serializer.StringRedisSerializer;

@Configuration
public class RedisConfig {

    @Bean
    public RedisTemplate<String, String> redisTemplate(RedisConnectionFactory connectionFactory) {
        RedisTemplate<String, String> template = new RedisTemplate<>();
        template.setConnectionFactory(connectionFactory);

        // Use String serialization for keys and values
        template.setKeySerializer(new StringRedisSerializer());
        template.setValueSerializer(new StringRedisSerializer());

        // Important: Configure serializers for Hash keys and values if using Hashes
        template.setHashKeySerializer(new StringRedisSerializer());
        template.setHashValueSerializer(new StringRedisSerializer());

        return template;
    }
}

Step 2: The Leaderboard Service

Next, she created a dedicated service to handle the Sorted Set operations.

import org.springframework.data.redis.core.RedisTemplate;
import org.springframework.data.redis.core.ZSetOperations;
import org.springframework.stereotype.Service;

import java.util.Set;
import java.util.stream.Collectors;

@Service
public class LeaderboardService {

    private static final String LEADERBOARD_KEY = "trending_products";
    private final RedisTemplate<String, String> redisTemplate;

    public LeaderboardService(RedisTemplate<String, String> redisTemplate) {
        this.redisTemplate = redisTemplate;
    }

    /**
     * Atomically increments the view count for a product.
     * Uses ZINCRBY under the hood.
     */
    public void recordProductView(String productId) {
        redisTemplate.opsForZSet().incrementScore(LEADERBOARD_KEY, productId, 1.0);
    }

    /**
     * Retrieves the top N products and their view counts.
     * Uses ZREVRANGE WITHSCORES under the hood.
     */
    public Set<ProductRanking> getTopTrendingProducts(int limit) {
        // Retrieve from index 0 to limit-1, in descending order
        Set<ZSetOperations.TypedTuple<String>> topProducts =
            redisTemplate.opsForZSet().reverseRangeWithScores(LEADERBOARD_KEY, 0, limit - 1);

        if (topProducts == null) return Set.of();

        // Map the Redis tuples to our domain object
        return topProducts.stream()
                .map(tuple -> new ProductRanking(
                        tuple.getValue(),
                        tuple.getScore() != null ? tuple.getScore().longValue() : 0L))
                .collect(Collectors.toSet());
    }

    // Simple DTO record
    public record ProductRanking(String productId, long views) {}
}

Step 3: Handling the Asynchronous Updates

To ensure the product page response time wasn’t impacted by the Redis update, Maya decoupled the view recording using Spring’s @Async annotation (or a lightweight message queue).

import org.springframework.scheduling.annotation.Async;
import org.springframework.stereotype.Component;

@Component
public class ViewTracker {

    private final LeaderboardService leaderboardService;

    public ViewTracker(LeaderboardService leaderboardService) {
        this.leaderboardService = leaderboardService;
    }

    @Async
    public void trackViewAsync(String productId) {
        // This runs in a separate thread pool, not blocking the HTTP request
        leaderboardService.recordProductView(productId);
    }
}

Debugging/Troubleshooting Tips

• The Unbounded Set: The trending_products Sorted Set will grow indefinitely as new products are viewed. Over time, millions of obscure products with only 1 view will consume massive amounts of RAM. Solution: Implement a periodic cleanup job (e.g., using @Scheduled) that executes ZREMRANGEBYRANK trending_products 0 -10001 to remove all but the top 10,000 products, keeping memory usage bounded.
• Time-Decay Leaderboards: A simple incrementing counter means older products will always dominate. To create a “Trending Right Now” leaderboard, you need time-decay. Solution: Instead of incrementing by 1, increment by a score based on the current Unix timestamp, or use multiple Sorted Sets (e.g., one per hour) and use the ZUNIONSTORE command to aggregate them with specific weights.
• Serialization Overhead: Storing full JSON product objects as the member in the Sorted Set wastes memory. Solution: Only store the productId as the member. When retrieving the leaderboard, fetch the top 100 IDs, then use an MGET (Multi-Get) command to retrieve the full product JSON strings from the standard key-value cache built in Part 1.

Key Takeaways

• Data Structure Server: Redis is not just a string cache; it provides native, atomic operations on complex data structures.
• Memory Optimization: Redis uses clever internal representations (SDS, ZipLists, IntSets) to minimize memory footprint and maximize CPU cache hits.
• Skip Lists: Sorted Sets use Skip Lists to provide $O(\log N)$ performance for inserts and range queries, making them ideal for leaderboards and rate limiters.
• Decoupling: Always decouple non-critical write operations (like tracking views) from the critical read path (serving the product page) using asynchronous processing.

Story Closing + Teaser

The “Trending Now” feature launched flawlessly. The Skip List architecture handled thousands of concurrent increments per second without breaking a sweat, and the frontend retrieved the top 100 products in less than a millisecond. GlobalMart’s conversion rates soared as users flocked to the most popular items.

Maya was thrilled, but her celebration was cut short by an alarming Slack message from the infrastructure team: “Major power outage at the us-east-1 data center. Multiple racks went dark.”

The PostgreSQL database was highly available with synchronous replicas in other zones, so the core data was safe. But what about the Redis cluster? All the shopping cart sessions, the real-time leaderboard data, and the cached product catalogs were sitting entirely in volatile RAM. When the power died, did all that data vanish into the ether? Maya was about to learn a harsh lesson about the “optional durability” of Redis, and the intricate dance of the Unix fork() system call. That crisis awaited in the next chapter.

References

[1] Redis Official Documentation: Data Types. https://redis.io/docs/latest/develop/data-types/ [2] Skip Lists: A Probabilistic Alternative to Balanced Trees, William Pugh, 1990.