Designing a Deadlock-Free Protocol

The scenario

You are the lead engineer on a new caching subsystem for a key-value store. The subsystem maintains the following shared data structures, each protected by its own mutex:

• table_lock — protects the hash table that maps keys to cache entries.
• lru_lock — protects the doubly-linked list that tracks the least-recently-used order of entries.
• stats_lock — protects a small structure of hit and miss counters, updated on every lookup.
• flush_lock — protects a queue of entries waiting to be written back to the backing store.

The subsystem must support the following operations, each of which may hold more than one lock at a time:

• get(key) — look up a key in the hash table, move the entry to the front of the LRU list, and increment the hit/miss counter.
• put(key, value) — insert or update an entry, which may require evicting an entry from the LRU list and enqueueing it on the flush queue.
• evict() — remove the least-recently-used entry and enqueue it on the flush queue.
• flush() — drain the flush queue and write each entry to the backing store.
• stats() — read the hit/miss counters.

A junior engineer has implemented the operations with locks acquired in the order that seemed natural, and the subsystem deadlocks under load. Your job is to redesign the lock-acquisition protocol so that deadlock cannot occur, while keeping the subsystem's performance acceptable.

Your task

1. Propose a global lock order. Assign a numeric rank to each lock and state the rule that all callers must follow. Draw the resulting lock hierarchy — a small table or a diagram is fine.
2. Apply the order to each operation. For each of the five operations, list the locks it acquires, in the order your rule prescribes, and the locks it releases. If an operation needs to acquire a lock with a lower rank than one it already holds, explain how you restructure it to avoid the violation (for example, by releasing and re-acquiring, by using a separate "acquisition phase" and "work phase", or by splitting the operation).
3. Argue correctness. Explain why your protocol makes deadlock impossible. Your argument should refer to the four necessary conditions and show that at least one of them cannot hold. Specifically:
   • If you choose to break circular wait, show that no cycle can form in the wait-for graph because every thread acquires locks in strictly increasing rank order.
   • If you choose to break hold-and-wait instead, explain the "acquire all or none" mechanism and its cost.
   • If you choose to use trylock with back-off, explain why no cycle persists indefinitely.
4. Evaluate the trade-offs. Address:
   • What is the cost of your protocol in the common case (an uncontended lookup)? In the contended case?
   • Does your protocol permit the natural concurrency of the subsystem (for example, two get calls on different keys happening in parallel)?
   • Does your protocol introduce the risk of starvation — a thread that waits indefinitely while others proceed? If so, how do you bound it?
   • What would you have to give up to simplify the protocol further (for example, by using a single global lock for the whole subsystem)? Is the simplification worth it?
5. Compare with an alternative. Discuss one alternative to your protocol — for example, a single global lock, a lock-free design for one of the structures (with atomics and RCU), or a partitioned design with one lock per hash bucket. State what the alternative would gain and what it would cost. State which one you would recommend and why.

Your post should be 500–700 words. Include the lock table or diagram. Cite at least one source (a textbook section, a paper, or a documentation page on lock ordering or on a real system that uses one — for example, the Linux kernel's lockdep, or the lock-ordering documentation of a database).