← all posts

backend

A Familiar N+1 Problem: The 26× Speedup from Caching

Overview

While operating a sports social platform, I noticed how slowly the feed loaded. Introducing Caffeine caching reduced average response time from roughly 800 ms to 38 ms.

Key metrics

  • Response time: 800 ms → 38 ms, a 95% improvement.
  • DB queries: 81 → 1, a 98% reduction.
  • Throughput: 3.8 req/s → 78.2 req/s, roughly 20×.

1. The problem

1.1. Feed requirements

There are two kinds of feed items:

  • Completed matches, including results, scores, and reviews.
  • Upcoming matches in matching, scheduled, or in-progress states.

They needed to be sorted as follows:

  1. Matches involving friends first.
  2. Other matches next.
  3. Newest first within each priority.

Each feed item also contains user-specific flags such as isFriend and isMyGame.

1.2. Initial implementation

A native query using UNION ALL implemented friend-first ordering.

fun getFeed(myUserId: Long): FeedResponse {
    val query = entityManager.createNativeQuery("""
        SELECT gr.id, 1 as priority FROM game_records gr
        JOIN custom_game g ON gr.game_id = g.id
        JOIN game_participation p ON p.game_id = g.id
        JOIN friend f ON f.user_id = :myUserId AND f.friend_id = p.user_id
        WHERE g.game_status = 'COMPLETED' AND f.status = 'ACCEPTED'

        UNION ALL
        -- Upcoming matches (friends) ...
        UNION ALL
        -- Completed matches (non-friends) ...
        UNION ALL
        -- Upcoming matches (non-friends) ...

        ORDER BY priority, created_at DESC
    """)

    return results.map { toFeedItemResponse(it) }
}

1.3. Performance bottlenecks

Measurement environment

  • 500 matches.
  • 50 users.
  • An average of five friends per user.

Response time Response-time measurements before caching

Average: 820ms
Median: 780ms
P95: 1200ms
P99: 1800ms

Bottlenecks

Query execution: 650ms (79%)
N+1 queries: 120ms (15%)
Object mapping: 30ms (4%)
Other: 20ms (2%)

Problem 1: repeated UNION ALL scans

UNION ALL combined four independent query branches. In this query plan, MySQL repeated full table scans instead of eliminating the redundant work.

EXPLAIN ANALYZE results:
- game_records (500 rows) × 2 scans
- custom_game (500 rows) × 2 scans
- friend (250 rows) × 2 scans

Problem 2: N+1 queries

Lazy loading and additional lookups occurred during DTO conversion.

results.map { toFeedItemResponse(it) }

For each item:

  • game.rule (Lazy Loading)
  • game.participations (Lazy Loading)
  • reviewRepository.findByGameId()
  • commentService.getCommentCount()

Actual query count: 1 main query + 20 × 4 = 81 queries.

Problem 3: inefficient pagination

OFFSET pagination scans and discards rows up to the offset, making later pages slower.

2. The solution

2.1. Choosing caching

The feed's characteristics were a textbook fit for caching.

  • A read-to-write ratio of 100:1.
  • Completed matches don't change.
  • Upcoming matches change infrequently.

2.2. Why Caffeine?

Initially, I wondered whether a ConcurrentHashMap<Long, FeedItemResponse> would be enough.

// Simple map approach
private val cache = ConcurrentHashMap<Long, FeedItemResponse>()

fun put(id: Long, item: FeedItemResponse) {
    cache[id] = item
}

The issue is memory management. Without explicit removal, entries accumulate. Dozens of new matches each day would require custom eviction logic.

Caffeine handles that:

Caffeine.newBuilder()
    .maximumSize(5000)  // Evict automatically above 5000 entries
    .recordStats()       // Monitor hit rate and eviction count
    .build()
  • maximumSize: Window TinyLFU manages eviction based on access patterns.
  • recordStats: hit-rate monitoring supports tuning.

A tested library was preferable to writing my own LRU implementation.

2.3 Redis vs Caffeine

I compared Redis with Caffeine.

Property Redis Caffeine
Latency 1-5ms (network) <0.1ms (in-memory)
Operational complexity Higher (separate server) Lower (embedded)
Environment Distributed Single instance

We had one instance and didn't need network I/O for a shared cache. I chose Caffeine.

2.4. Architecture

[Server startup]
    ↓
warmupCache()
    ├─ Completed matches from the last 6 weeks → Completed Cache (max 5000)
    └─ Upcoming/in-progress matches → Upcoming Cache (max 2000)

[Read request]
    ↓
1. Load friend IDs (1 query)
2. Read cached feed (0 queries)
3. Sort/filter in memory
4. Paginate
    ↓
[Response]

The server loads feed data from the DB at startup, then serves that data from memory.

2.5. Design decisions

No TTL

I initially set expireAfterWrite(30, MINUTES), then reconsidered:

  • Warmup only loads data from the last six weeks.
  • Old data isn't loaded in the first place.
  • TTL management added overhead we didn't need.

I controlled memory with maximumSize and left eviction to Caffeine's Window TinyLFU policy.

private val completedGameCache = Caffeine.newBuilder()
    .maximumSize(5000)
    .recordStats()
    .build()

Separate user-specific data

At first, I cached user-specific fields such as isFriend and isMyGame. That caused a bug: all users shared the cache, so one user's flags could appear for another.

Before: the bug

val feedItem = toFeedItemResponse(
    gameRecord,
    isFriend = gameService.isFriend(myUserId),
    isMyGame = gameService.isMyGame(myUserId)
)
cache.put(gameRecordId, feedItem)

After

// Cache only user-independent data
val feedItem = toFeedItemResponse(
    gameRecord,
    isFriend = false,
    isMyGame = false
)
cache.put(gameRecordId, feedItem)

// Compute user-specific fields at read time
fun getFeed(myUserId: Long): FeedResponse {
    val myFriendIds = friendRepository
        .findAllByUserIdAndStatus(myUserId, ACCEPTED)
        .map { it.friend.id }
        .toSet()

    val allFeeds = cache.getAllFeeds()

    return allFeeds.map { feedItem ->
        feedItem.copy(
            isFriend = feedItem.players.any { it.id in myFriendIds },
            isMyGame = feedItem.players.any { it.id == myUserId }
        )
    }
}

I changed the design to cache only user-independent data and compute user-specific fields at read time.

3. Implementation

3.1. Cache service

@Service
class FeedCacheService {
    private val completedGameCache: Cache<Long, FeedItemResponse> =
        Caffeine.newBuilder()
            .maximumSize(5000)
            .recordStats()
            .build()

    private val upcomingGameCache: Cache<Long, FeedItemResponse> =
        Caffeine.newBuilder()
            .maximumSize(2000)
            .recordStats()
            .build()

    fun putCompletedGame(id: Long, item: FeedItemResponse) {
        completedGameCache.put(id, item)
    }

    fun getAllFeeds(): List<FeedItemResponse> {
        return completedGameCache.asMap().values.toList() +
               upcomingGameCache.asMap().values.toList()
    }
}

3.2. Cache warmup

@PostConstruct
@Transactional(readOnly = true)
fun warmupFeedCache() {
    val sixWeeksAgo = LocalDateTime.now().minusWeeks(6)

    // Load completed matches
    val completedGames = gameRecordRepository.findAll()
        .filter { it.recordTime.isAfter(sixWeeksAgo) }

    completedGames.forEach { gameRecord ->
        try {
            val feedItem = toFeedItemResponse(gameRecord, false, false)
            feedCacheService.putCompletedGame(gameRecord.id, feedItem)
        } catch (e: Exception) {
            log.error(e) { "Cache warmup failed: ${gameRecord.id}" }
        }
    }

    // Load upcoming matches
    val upcomingStatuses = listOf(MATCHING, SCHEDULED, IN_PROGRESS)
    val upcomingGames = gameRepository.findAll()
        .filter { it.gameStatus in upcomingStatuses }

    upcomingGames.forEach { game ->
        try {
            val feedItem = toUpcomingGameFeedItem(game, false, false)
            feedCacheService.putUpcomingGame(game.id, feedItem)
        } catch (e: Exception) {
            log.error(e) { "Cache warmup failed: ${game.id}" }
        }
    }

    log.info { "Cache warmup complete: ${completedGames.size + upcomingGames.size}" }
}

Warming 500 matches takes about two seconds. Startup gets a little longer, but the cost is acceptable.

3.3. Feed reads

fun getFeed(myUserId: Long, page: Int = 0, size: Int = 20): FeedResponse {
    // 1. Load friend IDs (1 query)
    val myFriendIds = friendRepository
        .findAllByUserIdAndStatus(myUserId, FriendStatus.ACCEPTED)
        .map { it.friend.id!! }
        .toSet()

    // 2. Read feed from cache (0 query)
    val allFeeds = feedCacheService.getAllFeeds()

    // 3. Compute user-specific fields and sort
    val processedFeeds = allFeeds
        .map { feedItem ->
            feedItem.copy(
                isFriend = feedItem.players.any { it.id in myFriendIds },
                isMyGame = feedItem.players.any { it.id == myUserId }
            )
        }
        .sortedWith(
            compareBy<FeedItemResponse> {
                when {
                    it.isFriend && it.isCompleted -> 1
                    it.isFriend && !it.isCompleted -> 2
                    !it.isFriend && it.isCompleted -> 3
                    else -> 4
                }
            }.thenByDescending { it.date }
        )

    // 4. Pagination
    val startIndex = page * size
    val endIndex = minOf(startIndex + size, processedFeeds.size)

    val pagedFeeds = if (startIndex < processedFeeds.size) {
        processedFeeds.subList(startIndex, endIndex)
    } else {
        emptyList()
    }

    return FeedResponse(
        items = pagedFeeds,
        totalPages = (processedFeeds.size + size - 1) / size,
        currentPage = page
    )
}

4. Performance measurements

4.1. Response time

Metric Before After Improvement
Average 820ms 38ms 95%
Median 780ms 32ms 96%
P95 1200ms 65ms 95%
P99 1800ms 95ms 95%

4.2. Query count

  • Before: 81 queries on average.
  • After: one query for friend IDs.

Database query volume fell by 98%.

4.3. Processing-time breakdown after caching

Friend lookup: 5ms (13%)
Cache read: 1ms (3%)
Sorting/filtering: 15ms (39%)
Pagination: 2ms (5%)
Other: 15ms (40%)

Most work is now in memory.

4.4. Memory usage

250 completed matches: 22MB
250 upcoming matches: 23MB
Total: 45MB

Maximum (5000 entries): Estimated 450 MB

There is room within the server's 2 GB memory budget.

4.5. Concurrency test

I load-tested with Apache Bench:

ab -n 10000 -c 100 http://localhost:8080/api/feed
Metric Before After Improvement
Requests/sec 3.8 78.2 20×
Time/request 820ms 38ms 95%

5. Limitations

5.1. Server restarts

A restart clears the cache. @PostConstruct warms it automatically, but that takes about two seconds. Redis is a future option if traffic grows.

5.2. Multiple instances

We currently run one instance. Adding servers gives each its own independent cache, introducing synchronization concerns.

Possible approaches

  1. Move to Redis.
  2. Broadcast invalidation events through Kafka.
  3. Consider load-balancer sticky sessions.

5.3. Friendship changes

Adding or removing a friend must immediately affect the feed. Computing isFriend at read time makes that possible without invalidating the shared cache.

6. Conclusion

Caching isn't just a speed technique. It's deciding when an expensive computation needs to run once rather than repeatedly.

Key decisions

  1. Cache only user-independent data.
  2. Compute user-specific data at read time.
  3. Warm the cache at startup.

Results

  • Response time: 820 ms → 38 ms, a 95% improvement.
  • DB queries: 81 → 1, a 98% reduction.
  • Throughput: 3.8 req/s → 78.2 req/s, roughly 20×.

Trade-offs

  • Longer startup time.
  • Up to hundreds of MB of additional memory.
  • More code complexity.