Machine Coding Problem

Like Count System (Sharded)

macoAllinfrastructureatomic-longssharding
Commonly Asked By:TwitterMetaByteDance

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.

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 ===");
    }
}