Katkat
Back

Choose lock granularity for concurrent storage

MicrosoftSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

This problem tests your understanding of concurrency control by asking you to design a locking strategy for a multi-threaded key-value store, focusing on the trade-offs between throughput and latency.

The Problem: Designing a Thread-Safe Key-Value Store

You are building a high-performance in-memory key-value store that supports put(key, value) and get(key) operations. The store is accessed by hundreds of threads simultaneously. Your goal is to choose a locking strategy that optimizes for both high throughput and low tail latency (p99).

Requirements

  1. The store uses a hash map as its underlying data structure.
  2. You must implement put and get methods.
  3. The design must handle concurrency without corruption.

Design Options

Consider three potential locking approaches:

  • Approach A: Global Lock. A single mutex protecting the entire hash map.
  • Approach B: Bucket-Level Locking. An array of locks, where each lock protects a subset of hash buckets (sharding).
  • Approach C: Lock-Free. Using atomic compare-and-swap (CAS) operations on map entries.

Your Task

  1. Analyze how each approach handles high contention scenarios.
  2. Discuss the specific trade-offs regarding memory overhead, implementation complexity, and performance (throughput vs. latency).
  3. Propose a solution for an environment where read operations significantly outnumber write operations.

Example

If you choose Approach B, how do you determine the number of locks to minimize contention without significantly increasing the memory footprint? If you choose Approach C, how do you handle resizing the underlying hash table while concurrent threads are performing operations?

Hints

Hint 1

Consider how a global lock affects the system's ability to scale with more CPU cores.

Hint 2

Think about the difference between read-write locks and standard mutexes for read-heavy workloads.

Hint 3

Evaluate how lock granularity impacts the likelihood of threads waiting on different keys being blocked by each other.

Follow-up questions

  • How would your locking strategy change if the data set is too large to fit in memory and needs to be paged to disk?
  • If you implemented bucket-level locking, what is the impact of choosing a number of locks that is not a power of two?
  • Can you explain how to detect or prevent deadlocks if a single operation requires acquiring multiple locks (e.g., during a multi-key atomic update)?