Machine Coding Problem

Like Count System (Sharded)

macoAllinfrastructureatomic-longssharding
Commonly Asked By:TwitterMetaByteDance

Requirements & System Scope

Functional Scope (In-Scope)

  • Asymmetric Shard Routing Hash Functions: Maps liking actions dynamically to one of N independent counter shards.
  • Lock-Free Sharded Writes: Increments and decrements atomic variables to support massive parallel updates without hot-key lock bottlenecks.
  • User Likers Deduplication Registers: Blocks duplicate likes by maintaining in-memory user ID sets per post.
  • Dual-Path Read System: Sums all shards for exact reads, or queries cached rollups for low-latency, eventually consistent reads.

Explicit Boundaries (Out-of-Scope)

  • Dynamic Client Event Feeds: Simplifies notification pushes and UI rendering.
  • Physical Bloom Filters: Replaces probabilistic tracking with standard sets to prioritize exact, zero-collision lookups.

Class Diagram & Entity Relationships

Shard counter allocations, hash divisions, and aggregation caches:

Loading...
  • ShardedCounter: Allocates an array of atomic counter shards per post.
  • PostStats: Caches rolled-up aggregates for low-latency queries.

Design Patterns & SOLID Principles

  • Sharded Counter Pattern: Resolves write contention on hot keys by dividing atomic operations across multiple shards.
  • Proxy Pattern (Cache Proxy): Serves cached aggregates from a roll-up index to speed up high-frequency reads.
  • Single Responsibility Principle (SRP): Separates write-contention mitigation, user deduplication, and scheduled rollup operations.

Core Execution Workflows

Shard Hashing Divisions & Rollup Caches

  1. High-Frequency Liking Submission:
    1. Query the deduplication register to verify if the user has already liked the post. If yes, reject.
    2. Calculate a shard index: index = abs(hash(userId)) % N.
    3. Increment the atomic counter for that shard, avoiding global lock bottlenecks.
  2. Background Rollup Syncing:
    1. Run a background sync process at 10-second intervals.
    2. Sum all shards for each post to calculate the exact current totals.
    3. Update the cached total counts, allowing subsequent reads to use the fast, eventually consistent pathway.

Concurrency & Thread Safety Strategy

Securing large counter arrays under extreme traffic:

  • Atomic Operations: Individual shards use atomic counters to prevent race conditions during high-volume updates.
  • Decoupled Writes: Hashed sharding routes parallel writes to different variables, minimizing CPU cache-line bouncing and lock contention.

Complete Clean Code Blueprint

Production reference implementations demonstrating sharded counters, user deduplication, fast/exact read pathways, and background rollup jobs in Java and Python:

// โ”€โ”€โ”€ JAVA BLUEPRINT โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicLong;

enum LikeAction {
    LIKE, UNLIKE
}

class LikeEvent {
    private final String userId;
    private final String postId;
    private final LikeAction action;
    private final long timestampMs;

    public LikeEvent(String userId, String postId, LikeAction action) {
        this.userId = userId;
        this.postId = postId;
        this.action = action;
        this.timestampMs = System.currentTimeMillis();
    }

    public String getUserId() { return userId; }
    public String getPostId() { return postId; }
    public LikeAction getAction() { return action; }
    public long getTimestampMs() { return timestampMs; }
}

class ShardedCounter {
    private final AtomicLong[] shards;
    private final int shardCount;

    public ShardedCounter(int shardCount) {
        this.shardCount = shardCount;
        this.shards = new AtomicLong[shardCount];
        for (int i = 0; i < shardCount; i++) {
            this.shards[i] = new AtomicLong(0);
        }
    }

    public void increment(int shardIndex) {
        shards[shardIndex].incrementAndGet();
    }

    public void decrement(int shardIndex) {
        shards[shardIndex].decrementAndGet();
    }

    public long sum() {
        long total = 0;
        for (AtomicLong shard : shards) {
            total += shard.get();
        }
        return total;
    }
}

class PostStats {
    private volatile long cachedTotalCount;
    private volatile long lastRollupTimeMs;

    public PostStats(long initialCount) {
        this.cachedTotalCount = initialCount;
        this.lastRollupTimeMs = System.currentTimeMillis();
    }

    public long getCachedTotalCount() { return cachedTotalCount; }
    public void setCachedTotalCount(long count) { this.cachedTotalCount = count; }
    public long getLastRollupTimeMs() { return lastRollupTimeMs; }
    public void setLastRollupTimeMs(long timeMs) { this.lastRollupTimeMs = timeMs; }
}

class ShardedLikeService {
    private final ConcurrentHashMap<String, ShardedCounter> counters = new ConcurrentHashMap<>();
    private final ConcurrentHashMap<String, Set<String>> postLikesMap = new ConcurrentHashMap<>(); // postId -> Set of UserIds (Deduplication)
    private final ConcurrentHashMap<String, PostStats> statsCache = new ConcurrentHashMap<>();
    private final ScheduledExecutorService rollupScheduler = Executors.newSingleThreadScheduledExecutor();
    private final int defaultShardCount = 4;

    public ShardedLikeService() {
        // Run background rollup job every 10 seconds
        rollupScheduler.scheduleAtFixedRate(this::rollupAllCounts, 10, 10, TimeUnit.SECONDS);
    }

    // High write-throughput O(1) sharded like path
    public boolean likePost(String userId, String postId) {
        // 1. Deduplication validation check
        Set<String> likers = postLikesMap.computeIfAbsent(postId, k -> ConcurrentHashMap.newKeySet());
        boolean isNew = likers.add(userId);
        if (!isNew) {
            return false; // User already liked
        }

        // 2. Sharded routing hash index calculation
        ShardedCounter counter = counters.computeIfAbsent(postId, k -> new ShardedCounter(defaultShardCount));
        int shardIndex = Math.abs(userId.hashCode()) % defaultShardCount;
        
        // 3. Increment shard atomically
        counter.increment(shardIndex);
        return true;
    }

    public boolean unlikePost(String userId, String postId) {
        Set<String> likers = postLikesMap.get(postId);
        if (likers == null || !likers.contains(userId)) {
            return false; // Cannot unlike what isn't liked
        }

        likers.remove(userId);

        ShardedCounter counter = counters.get(postId);
        if (counter != null) {
            int shardIndex = Math.abs(userId.hashCode()) % defaultShardCount;
            counter.decrement(shardIndex);
        }
        return true;
    }

    // Exact Read Path: Sum shards dynamically
    public long getLikeCountExact(String postId) {
        ShardedCounter counter = counters.get(postId);
        return counter != null ? counter.sum() : 0L;
    }

    // Fast Read Path: Return cached rollup
    public long getLikeCountFast(String postId) {
        PostStats stats = statsCache.get(postId);
        if (stats != null) {
            return stats.getCachedTotalCount();
        }
        return getLikeCountExact(postId); // Fallback if no rollup yet
    }

    // Background Rollup worker summing shards
    public void rollupAllCounts() {
        long now = System.currentTimeMillis();
        counters.forEach((postId, counter) -> {
            long exactCount = counter.sum();
            
            PostStats stats = statsCache.computeIfAbsent(postId, k -> new PostStats(exactCount));
            stats.setCachedTotalCount(exactCount);
            stats.setLastRollupTimeMs(now);
            
            System.out.println("ROLLUP -> Post: " + postId + " Aggregated Shard Total: " + exactCount);
        });
    }

    public void shutdown() {
        rollupScheduler.shutdown();
    }
}

public class Main {
    public static void main(String[] args) throws InterruptedException {
        System.out.println("=== JAVA SHARDED LIKE SERVICE SIMULATION ===");
        ShardedLikeService service = new ShardedLikeService();
        
        service.likePost("user_1", "post_A");
        service.likePost("user_2", "post_A");
        service.likePost("user_3", "post_A");
        
        service.likePost("user_1", "post_A"); // Duplicate
        
        System.out.println("Exact like count: " + service.getLikeCountExact("post_A"));
        
        service.rollupAllCounts();
        System.out.println("Fast like count: " + service.getLikeCountFast("post_A"));
        
        service.shutdown();
        System.out.println("=== END OF JAVA SIMULATION ===");
    }
}

๐Ÿ’ฌReview

Help Us Improve

How helpful was this walkthrough?

Click a star to rate. We actively use this feedback to refine and update our system design content.

Placeholder
Optional but highly appreciated!

Discussion

Share your thoughts, ask questions, or help others.

Loading comments...