Design a Library Management System
Build a Library Management System
"Design a library" reads like a warm-up: Book, Member, Loan, done in five minutes. Then the interviewer asks the two questions that actually separate a senior candidate from someone who memorized a class diagram: "two members scan the barcode of the last copy at the same instant — what happens?" and "when a copy comes back and three people are waiting for it, how do you guarantee the person who's been waiting longest actually gets it?" Those questions don't live in the class diagram — they live in the concurrency and the queue discipline underneath it. You already have the entity breakdown from the Design a Library Management System walkthrough; this kata makes you build the allocator and the hold queue yourself, in Java and Go, reproduce both races, and fix them.
The Trap
The obvious first model: one Book class per title, with a copiesAvailable counter.
class Book {
String isbn, title, author;
int copiesTotal;
int copiesAvailable; // decremented on checkout, incremented on return
}The library owns 2 copies of Clean Code. Alice checks one out: copiesAvailable goes 2→1. Bob checks out the other: 1→0. Now the real world intrudes: copy #2, the one Bob is holding, gets water-damaged and needs to be pulled from circulation permanently. Which copy is that, in your model? You don't know — a counter has no memory of which physical object went out the door. You can decrement copiesTotal to 1, but you cannot mark "the specific item Bob has" as lost, you cannot stop it from silently re-entering the available pool the moment Bob's checkout record closes, and if a librarian scans the barcode printed inside that exact copy, your system has nothing to look up — the barcode isn't a first-class thing in this model at all.
That last part is the tell: real checkout is barcode-scan-driven. The librarian (or the self-checkout kiosk) scans the sticker on the physical book, not a title from a dropdown. The system's actual entry point is checkout(barcode), and it has to resolve that barcode to (a) which title it belongs to and (b) whether that exact copy is loanable right now. A Book-with-a-counter has no barcode to scan, no per-copy status, and no way to bind a Loan to a specific physical item — it can only ever answer "how many," never "which one." The trap is collapsing the title and the physical copy into one entity. They are two different things with two different lifecycles: the title (Clean Code, ISBN 978-0132350884) never changes; a given physical copy moves through AVAILABLE → LOANED → ON_HOLD → LOST over its lifetime, independently of every other copy of the same title.
Scope it like a senior
Before writing a line of allocator code, pin the contract down:
- Book vs. physical copy? Model both:
Bookis the title (one record per ISBN);BookItemis one physical copy with its own barcode and status. This kata builds that split as the foundation everything else sits on. - How many copies, and are they distinguishable? A title can have N copies; each has an independent status. Checkout operates on a title (the librarian doesn't care which barcode, any available copy will do) but resolves to one specific
BookItem. - Borrow limits and loan length? Each member has a borrow limit (e.g. 5 concurrent loans); a fixed loan period (14 days) starts the checkout clock.
- Fines? Yes — a late return owes a fee. Which formula? Don't hardcode it: make it a pluggable policy (flat per-day rate here; tiered or capped rates are named extensions), and block new checkouts once a member's owed fines cross a cap.
- What happens when all copies are out? The member places a hold (a reservation) on the title, not a specific barcode — they don't care which copy, they care about getting a copy of that title next. Holds queue FIFO: whoever asked first gets the next copy that comes back. This is the second crux, alongside the concurrency one.
- Renewals, multi-branch, membership tiers, digital/ebook loans? Out of scope — named as extensions. A renewal is just "extend the due date if no one is holding the title," multi-branch needs a whole separate transfer-and-routing design, and none of them change the Book/BookItem/hold-queue mechanism this kata is actually about.
- Concurrency? Yes, and it shows up in exactly two places: (1) two members scanning for the same last available copy of a title at once, and (2) two copies of the same title being returned at the same instant while multiple members are queued for holds. Both are this kata's crux — M5 below.
Answer: Book (title) + BookItem (barcode, status) as two entities, per-title O(1) copy allocation, a per-title FIFO hold queue, a pluggable fine policy with a borrow-limit and fine-cap gate, and thread-safety on both the copy claim and the hold-queue handoff.
Reason to the design
Simplest thing that could work is the trap itself: Book with a copiesAvailable int. Why it fails, concretely, beyond the lost-copy scenario above: the moment you need to answer "which specific item does Alice have, so I can compute her fine and know whether IT was the one water-damaged," a count has already thrown that information away. The fix is to split the entity: Book stays as pure title metadata (isbn, title, author) — it never changes once catalogued. BookItem becomes the real unit of work: one barcode, one status (AVAILABLE / LOANED / ON_HOLD / LOST), belonging to exactly one Book. A Loan binds one Member to one BookItem for one borrowing period — never to a Book directly, because "who has Clean Code" is meaningless once there's more than one copy; "who has barcode CB-002" is always well-defined.
Allocating a copy, iterated: the naive move is "loop over every BookItem of this title, find one that's AVAILABLE." That's O(n) in the copy count for no reason — a title with 40 copies across a big library system does 40x the work of a title with 1. The fix, borrowed from the exact same insight as building a parking lot's spot allocator: keep a per-title free-list (a stack of available barcodes). Checkout is a pop — O(1), and whichever barcode comes off the stack is the one you claim, atomically, in the same step as flipping its status to LOANED. That "claim and flip together" detail is not a style choice — it's the whole fix for crux #1 below.
The hold queue, iterated: once a title is out of copies, a member who wants it needs to queue, not poll. The naive move is "make the member call checkout() again every few minutes" — wasteful, and it still doesn't guarantee fairness (whoever happens to poll at the right microsecond wins, not whoever asked first). The fix: an explicit FIFO queue of waiting member IDs per title, and an observer the queue notifies (push, not poll) the instant a copy returns. Critically, this hold queue and the free-list are the same piece of state — "who gets the next copy of this title" — so a return has to do ONE atomic thing: either push the barcode back onto the free-list (nobody's waiting) or hand it straight to the FIFO head as an ON_HOLD assignment (somebody is). Splitting that into two separate, unguarded steps is exactly how crux #2 below happens.
Build it — milestones
Attempt-first: the contract is checkout(isbn, memberId) → Loan | null (null = no copies, go place a hold), placeHold(isbn, memberId), returnItem(barcode) → fineCents, and pickupHold(barcode, memberId) → Loan for the member the queue assigned a returning copy to. Try each milestone before reading the reference implementation below.
- M1 — Book vs. BookItem, single copy. One title, one physical copy.
checkoutresolves the isbn to that exact barcode and returns aLoanbound to it; with 0 copies left it returns null, never an exception or a phantom copy. - M2 — Multi-copy free-list + borrow limit. A per-title stack of available barcodes (O(1) claim); reject a checkout when the requesting member is already at their borrow limit.
- M3 — Fines as a strategy. A pluggable
FinePolicycomputes the late fee on return; a member whose owed fines exceed a cap is blocked from new checkouts until they pay down. - M4 — The hold queue. When a title has 0 copies, a member places a hold (FIFO, per title). On return, if the queue is non-empty, the returning copy goes
ON_HOLDfor the head of the queue (not back to general availability) and the observer notifies them; only that specific member canpickupHoldit — no cutting the line. - M5 — Thread-safe. Two members racing for the last copy must never both succeed; two concurrent returns racing to service the hold queue must never double-assign one waiter while starving another. Prove both with a concurrency test that fails without the fix.
Reference implementation — Java
One lock per title guards two structures together — the free-list stack and the hold queue — because they are really one resource: "who gets the next copy of this title." Both checkout and returnItem do their claim/hand-off as one critical section under that lock. Each has a deliberately unsynchronized UNSAFE twin (the naive version most candidates write first) kept only so the break-it section can reproduce both races on the exact same classes — never call the unsafe methods from real code. Save as Library.java:
import java.time.LocalDate;
import java.time.temporal.ChronoUnit;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.concurrent.locks.ReentrantLock;
enum ItemStatus { AVAILABLE, LOANED, ON_HOLD, LOST }
/** Book is the TITLE -- one record per ISBN, shared by every physical copy. */
final class Book {
final String isbn, title, author;
Book(String isbn, String title, String author) { this.isbn = isbn; this.title = title; this.author = author; }
}
/** BookItem is ONE PHYSICAL COPY -- the barcode on the spine. This is the unit
* that actually gets loaned, returned, put on hold, or marked lost. Two
* BookItems can share an isbn (same title) but never a barcode. */
final class BookItem {
final String barcode;
final String isbn;
ItemStatus status = ItemStatus.AVAILABLE;
String holdForMemberId; // set only while status == ON_HOLD
BookItem(String barcode, String isbn) { this.barcode = barcode; this.isbn = isbn; }
}
final class Member {
final String id, name;
final int borrowLimit;
int activeLoans = 0;
long fineCentsOwed = 0;
Member(String id, String name, int borrowLimit) { this.id = id; this.name = name; this.borrowLimit = borrowLimit; }
}
final class Loan {
final String barcode, isbn, memberId;
final LocalDate checkoutDate, dueDate;
Loan(String barcode, String isbn, String memberId, LocalDate checkoutDate, LocalDate dueDate) {
this.barcode = barcode; this.isbn = isbn; this.memberId = memberId;
this.checkoutDate = checkoutDate; this.dueDate = dueDate;
}
}
/** Fine policy is a strategy, not an if/else buried in returnItem. */
interface FinePolicy {
long lateFeeCents(LocalDate dueDate, LocalDate returnDate);
}
final class DailyFlatFine implements FinePolicy {
private final long centsPerDay;
DailyFlatFine(long centsPerDay) { this.centsPerDay = centsPerDay; }
public long lateFeeCents(LocalDate dueDate, LocalDate returnDate) {
long daysLate = ChronoUnit.DAYS.between(dueDate, returnDate);
return daysLate > 0 ? daysLate * centsPerDay : 0;
}
}
/** Observer: the hold queue notifies through this port, never by polling. */
interface HoldNotifier {
void notifyReady(String memberId, String isbn, String barcode);
}
final class RecordingNotifier implements HoldNotifier {
final List<String> notifiedInOrder = new ArrayList<String>();
public synchronized void notifyReady(String memberId, String isbn, String barcode) {
notifiedInOrder.add(memberId);
}
}
final class Library {
private static final int LOAN_DAYS = 14;
private static final long FINE_CAP_CENTS = 500; // $5 -- block new checkouts above this
private final Map<String, Book> catalog = new HashMap<String, Book>();
private final Map<String, BookItem> itemsByBarcode = new HashMap<String, BookItem>();
private final Map<String, List<String>> allBarcodesByIsbn = new HashMap<String, List<String>>();
private final Map<String, Deque<String>> availableByIsbn = new HashMap<String, Deque<String>>(); // free-list, O(1) claim
private final Map<String, Deque<String>> holdQueueByIsbn = new HashMap<String, Deque<String>>(); // FIFO of waiting memberIds
private final Map<String, ReentrantLock> lockByIsbn = new HashMap<String, ReentrantLock>(); // ONE lock guards BOTH structures above, per title
private final Map<String, Loan> activeLoanByBarcode = new HashMap<String, Loan>();
private final Map<String, Member> members = new HashMap<String, Member>();
private final FinePolicy finePolicy;
private final HoldNotifier notifier;
Library(FinePolicy finePolicy, HoldNotifier notifier) {
this.finePolicy = finePolicy;
this.notifier = notifier;
}
void addBook(Book book) {
catalog.put(book.isbn, book);
allBarcodesByIsbn.put(book.isbn, new ArrayList<String>());
availableByIsbn.put(book.isbn, new ArrayDeque<String>());
holdQueueByIsbn.put(book.isbn, new ArrayDeque<String>());
lockByIsbn.put(book.isbn, new ReentrantLock());
}
void addCopy(BookItem item) {
itemsByBarcode.put(item.barcode, item);
allBarcodesByIsbn.get(item.isbn).add(item.barcode);
availableByIsbn.get(item.isbn).push(item.barcode);
}
void addMember(Member m) { members.put(m.id, m); }
Member member(String id) { return members.get(id); }
BookItem item(String barcode) { return itemsByBarcode.get(barcode); }
/**
* THREAD-SAFE checkout. "Claim a free barcode" and "mark it loaned" are ONE
* critical section under the title's lock -- exactly the parking-lot
* free-list pattern (pop is the atomic step), applied to library copies.
* Returns null if the title has zero available copies right now (caller
* should placeHold instead of retrying).
*/
Loan checkout(String isbn, String memberId, LocalDate today) {
Member member = members.get(memberId);
if (member.activeLoans >= member.borrowLimit) throw new IllegalStateException("borrow limit reached");
if (member.fineCentsOwed > FINE_CAP_CENTS) throw new IllegalStateException("fines exceed cap, pay down first");
ReentrantLock lock = lockByIsbn.get(isbn);
lock.lock();
try {
Deque<String> free = availableByIsbn.get(isbn);
if (free.isEmpty()) return null;
String barcode = free.pop(); // O(1) claim, atomic with the status flip below
BookItem item = itemsByBarcode.get(barcode);
item.status = ItemStatus.LOANED;
Loan loan = new Loan(barcode, isbn, memberId, today, today.plusDays(LOAN_DAYS));
activeLoanByBarcode.put(barcode, loan);
member.activeLoans++;
return loan;
} finally {
lock.unlock();
}
}
/**
* UNSAFE TWIN of checkout -- the naive version most candidates write first:
* scan every copy of the title, find one that LOOKS available, then mark it
* loaned. The scan is O(n) instead of O(1) (the naive-trap this kata avoids)
* AND the check-then-act on item.status is unguarded (the concurrency trap).
* A short sleep between check and act widens the race window so the bug
* reproduces reliably on any machine, not just under lucky scheduling.
* Exists ONLY for the break-it demo below -- never call from real code.
*/
Loan checkoutUnsafe(String isbn, String memberId, LocalDate today) {
Member member = members.get(memberId);
for (String barcode : allBarcodesByIsbn.get(isbn)) {
BookItem item = itemsByBarcode.get(barcode);
if (item.status == ItemStatus.AVAILABLE) { // CHECK
try { Thread.sleep(1); } catch (InterruptedException ignored) { } // widen the window
item.status = ItemStatus.LOANED; // ACT -- no lock between check and act
Loan loan = new Loan(barcode, isbn, memberId, today, today.plusDays(LOAN_DAYS));
activeLoanByBarcode.put(barcode, loan);
member.activeLoans++;
return loan;
}
}
return null;
}
/**
* A member picks up the specific copy the FIFO queue assigned them. Only
* the rightful holder can convert ON_HOLD to LOANED for that barcode --
* this is what stops a member from cutting the line on someone else's hold.
*/
Loan pickupHold(String barcode, String memberId, LocalDate today) {
Member member = members.get(memberId);
BookItem item = itemsByBarcode.get(barcode);
if (item.status != ItemStatus.ON_HOLD || !memberId.equals(item.holdForMemberId))
throw new IllegalStateException("no hold for " + memberId + " on " + barcode);
if (member.activeLoans >= member.borrowLimit) throw new IllegalStateException("borrow limit reached");
if (member.fineCentsOwed > FINE_CAP_CENTS) throw new IllegalStateException("fines exceed cap, pay down first");
item.status = ItemStatus.LOANED;
item.holdForMemberId = null;
Loan loan = new Loan(barcode, item.isbn, memberId, today, today.plusDays(LOAN_DAYS));
activeLoanByBarcode.put(barcode, loan);
member.activeLoans++;
return loan;
}
/** Only meaningful when checkout() just returned null for this title. */
void placeHold(String isbn, String memberId) {
ReentrantLock lock = lockByIsbn.get(isbn);
lock.lock();
try {
holdQueueByIsbn.get(isbn).addLast(memberId);
} finally {
lock.unlock();
}
}
/**
* THREAD-SAFE return. "Pop the hold queue's head" and "assign this returning
* copy to them" are the SAME critical section as the claim above -- one lock
* per title guards both the free-list and the hold queue together, because
* they are really one piece of state: "who gets the next copy of this title."
*/
long returnItem(String barcode, LocalDate today) {
BookItem item = itemsByBarcode.get(barcode); // read-only after setup -- safe without the lock
// Everything that touches the title's shared state -- the loan entry
// for one of ITS barcodes, the free-list, the hold queue -- goes under
// the SAME per-title lock as checkout. Two returns for different
// barcodes of the SAME title still contend for this one lock: a plain
// HashMap (activeLoanByBarcode) is not safe for concurrent mutation
// even on different keys, so it must be guarded too, not just the
// free-list/hold-queue.
ReentrantLock lock = lockByIsbn.get(item.isbn);
lock.lock();
try {
Loan loan = activeLoanByBarcode.remove(barcode);
Member member = members.get(loan.memberId);
member.activeLoans--;
long fee = finePolicy.lateFeeCents(loan.dueDate, today);
member.fineCentsOwed += fee;
Deque<String> holds = holdQueueByIsbn.get(item.isbn);
if (!holds.isEmpty()) {
String nextMemberId = holds.pollFirst(); // atomic take of the FIFO head
item.status = ItemStatus.ON_HOLD;
item.holdForMemberId = nextMemberId;
notifier.notifyReady(nextMemberId, item.isbn, barcode);
} else {
item.status = ItemStatus.AVAILABLE;
availableByIsbn.get(item.isbn).push(barcode);
}
return fee;
} finally {
lock.unlock();
}
}
/**
* UNSAFE TWIN of returnItem -- the naive "peek, then remove" most people
* write instead of an atomic take. Two concurrent returns can both peek the
* SAME head member before either removes them: both assign a copy to that
* one member (a double-assign) while the member actually behind them in
* line gets silently dropped when the second removeFirst() fires -- starved,
* never notified, despite having reserved earlier than a member who leapfrogs
* them.
*/
long returnItemUnsafe(String barcode, LocalDate today) {
Loan loan = activeLoanByBarcode.remove(barcode);
BookItem item = itemsByBarcode.get(barcode);
Member member = members.get(loan.memberId);
member.activeLoans--;
long fee = finePolicy.lateFeeCents(loan.dueDate, today);
member.fineCentsOwed += fee;
Deque<String> holds = holdQueueByIsbn.get(item.isbn);
if (!holds.isEmpty()) { // CHECK (peek existence)
String nextMemberId = holds.peekFirst(); // look at head, don't remove yet
try { Thread.sleep(1); } catch (InterruptedException ignored) { } // widen the window
holds.removeFirst(); // ACT -- remove whatever is now at the head
item.status = ItemStatus.ON_HOLD;
item.holdForMemberId = nextMemberId;
notifier.notifyReady(nextMemberId, item.isbn, barcode);
} else {
item.status = ItemStatus.AVAILABLE;
availableByIsbn.get(item.isbn).push(barcode);
}
return fee;
}
}Reference implementation — Go
Same shape: Book/BookItem/Loan types, a mutex-per-title guarding the free-list slice and the hold-queue slice together, and the same UNSAFE twins for the break-it demo. Save as library.go, package library:
// Package library is the reference implementation for the "Build a Library
// Management System" LLD kata: Book (title) vs BookItem (physical copy),
// a per-title free-list for O(1) checkout, a FIFO hold queue, and a
// pluggable fine policy.
package library
import (
"errors"
"fmt"
"sync"
"time"
)
const loanDays = 14
const fineCapCents = 500 // $5 -- blocks new checkouts above this
// ItemStatus is the lifecycle state of ONE physical copy.
type ItemStatus int
const (
Available ItemStatus = iota
Loaned
OnHold
Lost
)
// Book is the TITLE -- one record per ISBN, shared by every physical copy.
type Book struct {
ISBN, Title, Author string
}
// BookItem is ONE PHYSICAL COPY -- the barcode on the spine. This is the
// unit that actually gets loaned, returned, put on hold, or marked lost.
type BookItem struct {
Barcode string
ISBN string
Status ItemStatus
HoldForMember string // set only while Status == OnHold
}
// Member is a library patron with a borrow limit and a running fine balance.
type Member struct {
ID, Name string
BorrowLimit int
ActiveLoans int
FineCentsOwed int64
}
// Loan binds one physical copy to one member for one borrowing period.
type Loan struct {
Barcode, ISBN, MemberID string
CheckoutDate, DueDate time.Time
}
// FinePolicy is a strategy, not an if/else buried in ReturnItem.
type FinePolicy interface {
LateFeeCents(dueDate, returnDate time.Time) int64
}
// DailyFlatFine charges a flat rate per day late.
type DailyFlatFine struct{ CentsPerDay int64 }
func (f DailyFlatFine) LateFeeCents(dueDate, returnDate time.Time) int64 {
daysLate := int64(returnDate.Sub(dueDate).Hours() / 24)
if daysLate > 0 {
return daysLate * f.CentsPerDay
}
return 0
}
// HoldNotifier is the observer port the hold queue notifies through --
// never by polling.
type HoldNotifier interface {
NotifyReady(memberID, isbn, barcode string)
}
// RecordingNotifier is a test double that records the FIFO order of
// notifications so tests can assert on it directly.
type RecordingNotifier struct {
mu sync.Mutex
NotifiedInOrder []string
}
func (n *RecordingNotifier) NotifyReady(memberID, isbn, barcode string) {
n.mu.Lock()
defer n.mu.Unlock()
n.NotifiedInOrder = append(n.NotifiedInOrder, memberID)
}
func (n *RecordingNotifier) Snapshot() []string {
n.mu.Lock()
defer n.mu.Unlock()
out := make([]string, len(n.NotifiedInOrder))
copy(out, n.NotifiedInOrder)
return out
}
// Library is the whole catalog + circulation desk.
type Library struct {
catalog map[string]Book
itemsByBarcode map[string]*BookItem
allBarcodes map[string][]string // every barcode ever added for an isbn -- used by the naive UNSAFE scan
available map[string][]string // free-list stack of barcodes, O(1) claim
holdQueue map[string][]string // FIFO of waiting memberIDs
lockByISBN map[string]*sync.Mutex // ONE lock guards BOTH `available` and `holdQueue`, per title
activeLoans map[string]Loan // barcode -> current Loan
members map[string]*Member
finePolicy FinePolicy
notifier HoldNotifier
}
func NewLibrary(finePolicy FinePolicy, notifier HoldNotifier) *Library {
return &Library{
catalog: make(map[string]Book),
itemsByBarcode: make(map[string]*BookItem),
allBarcodes: make(map[string][]string),
available: make(map[string][]string),
holdQueue: make(map[string][]string),
lockByISBN: make(map[string]*sync.Mutex),
activeLoans: make(map[string]Loan),
members: make(map[string]*Member),
finePolicy: finePolicy,
notifier: notifier,
}
}
func (l *Library) AddBook(b Book) {
l.catalog[b.ISBN] = b
l.allBarcodes[b.ISBN] = []string{}
l.available[b.ISBN] = []string{}
l.holdQueue[b.ISBN] = []string{}
l.lockByISBN[b.ISBN] = &sync.Mutex{}
}
func (l *Library) AddCopy(item BookItem) {
stored := item
l.itemsByBarcode[item.Barcode] = &stored
l.allBarcodes[item.ISBN] = append(l.allBarcodes[item.ISBN], item.Barcode)
l.available[item.ISBN] = append(l.available[item.ISBN], item.Barcode) // push
}
func (l *Library) AddMember(m Member) { stored := m; l.members[m.ID] = &stored }
func (l *Library) MemberByID(id string) *Member { return l.members[id] }
func (l *Library) ItemByBarcode(barcode string) *BookItem { return l.itemsByBarcode[barcode] }
// Checkout is THREAD-SAFE. "Pop a free barcode" and "mark it loaned" are ONE
// critical section under the title's lock -- the parking-lot free-list
// pattern, applied to library copies. Returns (nil, nil) if the title has
// zero available copies right now (caller should PlaceHold instead).
func (l *Library) Checkout(isbn, memberID string, today time.Time) (*Loan, error) {
member := l.members[memberID]
if member.ActiveLoans >= member.BorrowLimit {
return nil, errors.New("borrow limit reached")
}
if member.FineCentsOwed > fineCapCents {
return nil, errors.New("fines exceed cap, pay down first")
}
lock := l.lockByISBN[isbn]
lock.Lock()
defer lock.Unlock()
free := l.available[isbn]
if len(free) == 0 {
return nil, nil
}
n := len(free)
barcode := free[n-1] // pop -- O(1) claim, atomic with the status flip below
l.available[isbn] = free[:n-1]
item := l.itemsByBarcode[barcode]
item.Status = Loaned
loan := Loan{Barcode: barcode, ISBN: isbn, MemberID: memberID, CheckoutDate: today, DueDate: today.AddDate(0, 0, loanDays)}
l.activeLoans[barcode] = loan
member.ActiveLoans++
return &loan, nil
}
// CheckoutUnsafe is the UNSAFE TWIN of Checkout -- the naive version most
// candidates write first: scan every copy of the title, find one that LOOKS
// available, then mark it loaned. The scan is O(n) instead of O(1) (the
// naive-trap this kata avoids) AND the check-then-act on item.Status is
// unguarded (the concurrency trap). A short sleep between check and act
// widens the race window so the bug reproduces reliably on any machine.
// Exists ONLY for the break-it demo below -- never call from real code.
func (l *Library) CheckoutUnsafe(isbn, memberID string, today time.Time) *Loan {
member := l.members[memberID]
for _, barcode := range l.allBarcodes[isbn] {
item := l.itemsByBarcode[barcode]
if item.Status == Available { // CHECK
time.Sleep(time.Millisecond) // widen the window
item.Status = Loaned // ACT -- no lock between check and act
loan := Loan{Barcode: barcode, ISBN: isbn, MemberID: memberID, CheckoutDate: today, DueDate: today.AddDate(0, 0, loanDays)}
l.activeLoans[barcode] = loan
member.ActiveLoans++
return &loan
}
}
return nil
}
// PlaceHold is only meaningful right after Checkout just returned nil for this title.
func (l *Library) PlaceHold(isbn, memberID string) {
lock := l.lockByISBN[isbn]
lock.Lock()
defer lock.Unlock()
l.holdQueue[isbn] = append(l.holdQueue[isbn], memberID) // enqueue at the tail
}
// PickupHold lets a member pick up the specific copy the FIFO queue assigned
// them. Only the rightful holder can convert OnHold -> Loaned for that
// barcode -- this is what stops a member from cutting the line.
func (l *Library) PickupHold(barcode, memberID string, today time.Time) (*Loan, error) {
member := l.members[memberID]
item := l.itemsByBarcode[barcode]
if item.Status != OnHold || item.HoldForMember != memberID {
return nil, fmt.Errorf("no hold for %s on %s", memberID, barcode)
}
if member.ActiveLoans >= member.BorrowLimit {
return nil, errors.New("borrow limit reached")
}
if member.FineCentsOwed > fineCapCents {
return nil, errors.New("fines exceed cap, pay down first")
}
item.Status = Loaned
item.HoldForMember = ""
loan := Loan{Barcode: barcode, ISBN: item.ISBN, MemberID: memberID, CheckoutDate: today, DueDate: today.AddDate(0, 0, loanDays)}
l.activeLoans[barcode] = loan
member.ActiveLoans++
return &loan, nil
}
// ReturnItem is THREAD-SAFE. "Pop the hold queue's head" and "assign this
// returning copy to them" are the SAME critical section as the claim above --
// one lock per title guards both the free-list and the hold queue together,
// because they are really one piece of state: "who gets the next copy."
func (l *Library) ReturnItem(barcode string, today time.Time) int64 {
item := l.itemsByBarcode[barcode] // read-only after setup -- safe without the lock
// Everything that touches the title's shared state -- the activeLoans
// entry for one of ITS barcodes, the free-list, the hold queue -- goes
// under the SAME per-title lock as Checkout. Two returns for different
// barcodes of the SAME title still contend for this one lock, which is
// exactly what's needed: Go (and Java) maps are not safe for concurrent
// mutation even on different keys, so activeLoans must be guarded too,
// not just the free-list/hold-queue.
lock := l.lockByISBN[item.ISBN]
lock.Lock()
defer lock.Unlock()
loan := l.activeLoans[barcode]
delete(l.activeLoans, barcode)
member := l.members[loan.MemberID]
member.ActiveLoans--
fee := l.finePolicy.LateFeeCents(loan.DueDate, today)
member.FineCentsOwed += fee
holds := l.holdQueue[item.ISBN]
if len(holds) > 0 {
nextMemberID := holds[0] // FIFO head, atomic take
l.holdQueue[item.ISBN] = holds[1:]
item.Status = OnHold
item.HoldForMember = nextMemberID
l.notifier.NotifyReady(nextMemberID, item.ISBN, barcode)
} else {
item.Status = Available
l.available[item.ISBN] = append(l.available[item.ISBN], barcode)
}
return fee
}
// ReturnItemUnsafe is the UNSAFE TWIN of ReturnItem -- the naive "peek, then
// remove" most people write instead of an atomic take. Two concurrent
// returns can both peek the SAME head member before either removes them:
// both assign a copy to that one member (a double-assign) while the member
// actually behind them in line gets silently dropped -- starved, never
// notified, despite having reserved earlier than a member who leapfrogs them.
func (l *Library) ReturnItemUnsafe(barcode string, today time.Time) int64 {
loan := l.activeLoans[barcode]
delete(l.activeLoans, barcode)
item := l.itemsByBarcode[barcode]
member := l.members[loan.MemberID]
member.ActiveLoans--
fee := l.finePolicy.LateFeeCents(loan.DueDate, today)
member.FineCentsOwed += fee
holds := l.holdQueue[item.ISBN]
if len(holds) > 0 { // CHECK (peek existence)
nextMemberID := holds[0] // look at head, don't remove yet
time.Sleep(time.Millisecond) // widen the window
holds = l.holdQueue[item.ISBN] // re-read the (possibly already-mutated-by-another-goroutine) slice header
if len(holds) > 0 {
l.holdQueue[item.ISBN] = holds[1:] // ACT -- remove whatever is now at the head
}
item.Status = OnHold
item.HoldForMember = nextMemberID
l.notifier.NotifyReady(nextMemberID, item.ISBN, barcode)
} else {
item.Status = Available
l.available[item.ISBN] = append(l.available[item.ISBN], barcode)
}
return fee
}Break it
Both reference impls ship two unsafe twins on the exact same classes, kept only for this demonstration: checkoutUnsafe/CheckoutUnsafe (double-lend) and returnItemUnsafe/ReturnItemUnsafe (queue fairness). This is the M1–M5 test suite, including both break-it demos, for Java:
import java.time.LocalDate;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.concurrent.atomic.AtomicInteger;
public final class LibraryTests {
static int pass = 0, fail = 0;
static void check(String name, boolean cond) {
if (cond) { pass++; System.out.println("PASS: " + name); }
else { fail++; System.out.println("FAIL: " + name); }
}
public static void main(String[] args) throws InterruptedException {
LocalDate day0 = LocalDate.of(2026, 1, 1);
// --- M1: Book vs BookItem -- checkout resolves isbn -> ONE specific barcode ---
{
Library lib = new Library(new DailyFlatFine(25), new RecordingNotifier());
lib.addBook(new Book("CB", "Clean Code", "R. Martin"));
lib.addCopy(new BookItem("CB-001", "CB"));
lib.addMember(new Member("alice", "Alice", 5));
lib.addMember(new Member("bob", "Bob", 5));
Loan aliceLoan = lib.checkout("CB", "alice", day0);
check("M1: checkout returns a Loan bound to the exact barcode CB-001", "CB-001".equals(aliceLoan.barcode));
check("M1: the physical copy is now LOANED", lib.item("CB-001").status == ItemStatus.LOANED);
Loan bobLoan = lib.checkout("CB", "bob", day0);
check("M1: with 0 copies left, checkout returns null (not an exception, not a phantom copy)", bobLoan == null);
}
// --- M2: multi-copy O(1) free-list + borrow limit ---
{
Library lib = new Library(new DailyFlatFine(25), new RecordingNotifier());
lib.addBook(new Book("CB", "Clean Code", "R. Martin"));
lib.addCopy(new BookItem("CB-001", "CB"));
lib.addCopy(new BookItem("CB-002", "CB"));
lib.addCopy(new BookItem("CB-003", "CB"));
lib.addMember(new Member("alice", "Alice", 1)); // borrow limit 1 -- for the limit test below
lib.addMember(new Member("bob", "Bob", 5));
lib.addMember(new Member("carol", "Carol", 5));
lib.addMember(new Member("dave", "Dave", 5));
Set<String> issued = new HashSet<String>();
issued.add(lib.checkout("CB", "alice", day0).barcode);
issued.add(lib.checkout("CB", "bob", day0).barcode);
issued.add(lib.checkout("CB", "carol", day0).barcode);
check("M2: 3 copies to 3 members -> 3 distinct barcodes handed out", issued.size() == 3);
Loan daveLoan = lib.checkout("CB", "dave", day0);
check("M2: 4th member with 0 copies left gets null (capacity enforced)", daveLoan == null);
// release-and-reclaim round trip (same shape as the parking-lot free-list test)
String returned = issued.iterator().next();
lib.returnItem(returned, day0.plusDays(1));
Loan daveRetry = lib.checkout("CB", "dave", day0.plusDays(1));
check("M2: after a return, the freed barcode is handed to the next requester", daveRetry != null && daveRetry.barcode.equals(returned));
// borrow limit: alice (limit=1) already holds 1 loan -- a 2nd title must be rejected
lib.addBook(new Book("EK", "Effective Kotlin", "M. Moskala"));
lib.addCopy(new BookItem("EK-001", "EK"));
boolean threw = false;
try { lib.checkout("EK", "alice", day0); }
catch (IllegalStateException e) { threw = true; }
check("M2: borrow limit blocks a member already at their cap", threw);
}
// --- M3: fines as a pluggable strategy ---
{
Library lib = new Library(new DailyFlatFine(25), new RecordingNotifier()); // 25 cents/day late
lib.addBook(new Book("CB", "Clean Code", "R. Martin"));
lib.addCopy(new BookItem("CB-001", "CB"));
lib.addMember(new Member("alice", "Alice", 5));
lib.checkout("CB", "alice", day0); // due = day0 + 14
long fee = lib.returnItem("CB-001", day0.plusDays(20)); // 6 days late
check("M3: 6 days late at 25c/day -> 150 cents fine", fee == 150);
check("M3: the member's running balance reflects it", lib.member("alice").fineCentsOwed == 150);
long onTimeFee = 0;
{
Library lib2 = new Library(new DailyFlatFine(25), new RecordingNotifier());
lib2.addBook(new Book("CB", "Clean Code", "R. Martin"));
lib2.addCopy(new BookItem("CB-001", "CB"));
lib2.addMember(new Member("alice", "Alice", 5));
lib2.checkout("CB", "alice", day0);
onTimeFee = lib2.returnItem("CB-001", day0.plusDays(10)); // within 14 days
}
check("M3: returned before the due date -> zero fine", onTimeFee == 0);
}
// --- M4: the hold queue is FIFO, and only the rightful holder can pick up ---
{
RecordingNotifier notifier = new RecordingNotifier();
Library lib = new Library(new DailyFlatFine(25), notifier);
lib.addBook(new Book("CB", "Clean Code", "R. Martin"));
lib.addCopy(new BookItem("CB-001", "CB")); // exactly 1 copy
lib.addMember(new Member("alice", "Alice", 5));
lib.addMember(new Member("bob", "Bob", 5));
lib.addMember(new Member("carol", "Carol", 5));
lib.checkout("CB", "alice", day0); // the only copy is now out
check("M4: bob finds 0 copies available", lib.checkout("CB", "bob", day0) == null);
lib.placeHold("CB", "bob"); // bob queues first
lib.placeHold("CB", "carol"); // carol queues second
lib.returnItem("CB-001", day0.plusDays(2));
check("M4: on return, the HEAD of the queue (bob) is notified, not carol", notifier.notifiedInOrder.equals(java.util.Arrays.asList("bob")));
check("M4: the copy is held for bob specifically, not generally available", lib.item("CB-001").status == ItemStatus.ON_HOLD);
boolean carolCut = false;
try { lib.pickupHold("CB-001", "carol", day0.plusDays(3)); }
catch (IllegalStateException e) { carolCut = true; }
check("M4: carol cannot cut the line and pick up bob's hold", carolCut);
Loan bobLoan = lib.pickupHold("CB-001", "bob", day0.plusDays(3));
check("M4: bob picks up his own hold successfully", bobLoan != null && bobLoan.barcode.equals("CB-001"));
lib.returnItem("CB-001", day0.plusDays(10));
check("M4: next return notifies carol -- she was 2nd in line, now 1st", notifier.notifiedInOrder.equals(java.util.Arrays.asList("bob", "carol")));
}
// --- M5a: BREAK IT -- concurrent checkout of the LAST copy (double-lend) ---
{
final int threads = 200;
Library unsafeLib = new Library(new DailyFlatFine(25), new RecordingNotifier());
unsafeLib.addBook(new Book("DL", "Designing Data-Intensive Applications", "M. Kleppmann"));
unsafeLib.addCopy(new BookItem("DL-001", "DL")); // exactly ONE copy in the whole library
for (int i = 0; i < threads; i++) unsafeLib.addMember(new Member("m" + i, "Member " + i, 5));
final AtomicInteger unsafeSuccesses = new AtomicInteger(0);
Thread[] unsafePool = new Thread[threads];
for (int t = 0; t < threads; t++) {
final String memberId = "m" + t;
unsafePool[t] = new Thread(new Runnable() {
public void run() {
Loan loan = unsafeLib.checkoutUnsafe("DL", memberId, day0);
if (loan != null) unsafeSuccesses.incrementAndGet();
}
});
}
for (Thread th : unsafePool) th.start();
for (Thread th : unsafePool) th.join();
System.out.println("BREAK-IT (double-lend): " + unsafeSuccesses.get() + " / " + threads
+ " threads were handed the SAME single copy DL-001 (want exactly 1)");
check("break-it: UNSAFE checkout double- (multi-)lends the last copy", unsafeSuccesses.get() > 1);
Library safeLib = new Library(new DailyFlatFine(25), new RecordingNotifier());
safeLib.addBook(new Book("DL", "Designing Data-Intensive Applications", "M. Kleppmann"));
safeLib.addCopy(new BookItem("DL-001", "DL"));
for (int i = 0; i < threads; i++) safeLib.addMember(new Member("m" + i, "Member " + i, 5));
final AtomicInteger safeSuccesses = new AtomicInteger(0);
Thread[] safePool = new Thread[threads];
for (int t = 0; t < threads; t++) {
final String memberId = "m" + t;
safePool[t] = new Thread(new Runnable() {
public void run() {
Loan loan = safeLib.checkout("DL", memberId, day0);
if (loan != null) safeSuccesses.incrementAndGet();
}
});
}
for (Thread th : safePool) th.start();
for (Thread th : safePool) th.join();
System.out.println("FIX (locked checkout): " + safeSuccesses.get() + " / " + threads + " succeeded (want exactly 1)");
check("fix: locked checkout hands out the last copy to EXACTLY one member", safeSuccesses.get() == 1);
}
// --- M5b: BREAK IT -- the reservation queue skips/starves under concurrent returns ---
{
final int copies = 8;
final int waiters = 10;
// -- UNSAFE run --
RecordingNotifier unsafeNotifier = new RecordingNotifier();
Library unsafeLib = new Library(new DailyFlatFine(25), unsafeNotifier);
unsafeLib.addBook(new Book("Q", "Queueing Theory", "L. Kleinrock"));
List<String> holderIds = new ArrayList<String>();
for (int i = 0; i < copies; i++) {
String barcode = "Q-00" + i;
unsafeLib.addCopy(new BookItem(barcode, "Q"));
String holder = "holder" + i;
unsafeLib.addMember(new Member(holder, holder, 5));
unsafeLib.checkout("Q", holder, day0); // all 8 copies go out first, single-threaded
holderIds.add(holder);
}
List<String> expectedFirstWave = new ArrayList<String>();
for (int i = 0; i < waiters; i++) {
String waiter = "w" + i;
unsafeLib.addMember(new Member(waiter, waiter, 5));
unsafeLib.placeHold("Q", waiter); // w0..w9 queue up, in order
if (i < copies) expectedFirstWave.add(waiter); // w0..w7 SHOULD be the ones notified
}
final AtomicInteger unsafeExceptions = new AtomicInteger(0);
Thread[] unsafeReturns = new Thread[copies];
for (int i = 0; i < copies; i++) {
final String barcode = "Q-00" + i;
unsafeReturns[i] = new Thread(new Runnable() {
public void run() {
try {
unsafeLib.returnItemUnsafe(barcode, day0.plusDays(1));
} catch (RuntimeException corrupted) {
// the unguarded ArrayDeque itself corrupts under concurrent
// removeFirst() calls -- this exception IS part of the lesson.
unsafeExceptions.incrementAndGet();
}
}
});
}
for (Thread th : unsafeReturns) th.start();
for (Thread th : unsafeReturns) th.join();
List<String> unsafeNotified = unsafeNotifier.notifiedInOrder;
Set<String> unsafeDistinct = new HashSet<String>(unsafeNotified);
System.out.println("BREAK-IT (queue fairness): notified = " + unsafeNotified
+ " | distinct=" + unsafeDistinct.size() + " of " + copies + " returns"
+ " | expected exactly {w0..w7}, got " + unsafeDistinct
+ " | " + unsafeExceptions.get() + " thread(s) hit a corrupted-deque exception");
boolean sameSizeAsExpected = unsafeDistinct.size() == copies;
boolean matchesExpectedSet = unsafeDistinct.equals(new HashSet<String>(expectedFirstWave));
check("break-it: UNSAFE return either double-notifies someone or starves a queued member",
!(sameSizeAsExpected && matchesExpectedSet));
// -- SAFE run, identical scenario --
RecordingNotifier safeNotifier = new RecordingNotifier();
Library safeLib = new Library(new DailyFlatFine(25), safeNotifier);
safeLib.addBook(new Book("Q", "Queueing Theory", "L. Kleinrock"));
for (int i = 0; i < copies; i++) {
String barcode = "Q-00" + i;
safeLib.addCopy(new BookItem(barcode, "Q"));
String holder = "holder" + i;
safeLib.addMember(new Member(holder, holder, 5));
safeLib.checkout("Q", holder, day0);
}
for (int i = 0; i < waiters; i++) {
String waiter = "w" + i;
safeLib.addMember(new Member(waiter, waiter, 5));
safeLib.placeHold("Q", waiter);
}
Thread[] safeReturns = new Thread[copies];
for (int i = 0; i < copies; i++) {
final String barcode = "Q-00" + i;
safeReturns[i] = new Thread(new Runnable() {
public void run() { safeLib.returnItem(barcode, day0.plusDays(1)); }
});
}
for (Thread th : safeReturns) th.start();
for (Thread th : safeReturns) th.join();
List<String> safeNotified = safeNotifier.notifiedInOrder;
Set<String> safeDistinct = new HashSet<String>(safeNotified);
System.out.println("FIX (locked return): notified = " + safeNotified + " | distinct=" + safeDistinct.size());
check("fix: locked return notifies exactly " + copies + " distinct members, no duplicates",
safeNotified.size() == copies && safeDistinct.size() == copies);
check("fix: the notified set is EXACTLY the first " + copies + " in FIFO order (w0..w7), no skips",
safeDistinct.equals(new HashSet<String>(expectedFirstWave)));
}
System.out.println();
System.out.println(pass + " passed, " + fail + " failed");
if (fail > 0) System.exit(1);
}
}Measured in this session (javac Library.java LibraryTests.java && java LibraryTests): all 21/21 assertions pass. The unsafe checkout run genuinely double- (multi-)lends the single last copy every time it was executed — repeated runs measured 26, 27, 37 and 38 of 200 threads all being handed barcode DL-001 simultaneously (want exactly 1); the locked run always lands on exactly 1. The unsafe return run is even more dramatic: every run notified w0 between 6 and 8 times and zero other queued members — w1 through w7, who reserved earlier than nobody, were silently starved, and on some runs a thread additionally threw NoSuchElementException from ArrayDeque.removeFirst() because the unsynchronized deque itself corrupted under concurrent mutation. The locked return run always notifies exactly w0..w7, once each, in order.
For Go, the two unsafe demos are split into two separate command binaries deliberately, mirroring how Go's map runtime reacts to genuine concurrent writes: it doesn't silently corrupt like a Java HashMap can — it detects the unsynchronized access and crashes the whole process, which is not recoverable, so each demo needs its own binary. Keep this next to library.go as library_test.go — it exercises ONLY the safe paths and is expected to pass clean under go test -race:
package library
import (
"strconv"
"sync"
"testing"
"time"
)
func day(offset int) time.Time {
return time.Date(2026, 1, 1, 0, 0, 0, 0, time.UTC).AddDate(0, 0, offset)
}
func TestBookVsBookItemBindsExactBarcode(t *testing.T) {
lib := NewLibrary(DailyFlatFine{CentsPerDay: 25}, &RecordingNotifier{})
lib.AddBook(Book{ISBN: "CB", Title: "Clean Code", Author: "R. Martin"})
lib.AddCopy(BookItem{Barcode: "CB-001", ISBN: "CB", Status: Available})
lib.AddMember(Member{ID: "alice", Name: "Alice", BorrowLimit: 5})
lib.AddMember(Member{ID: "bob", Name: "Bob", BorrowLimit: 5})
loan, err := lib.Checkout("CB", "alice", day(0))
if err != nil || loan == nil || loan.Barcode != "CB-001" {
t.Fatalf("expected a loan bound to CB-001, got %+v err=%v", loan, err)
}
if lib.ItemByBarcode("CB-001").Status != Loaned {
t.Fatalf("expected CB-001 to be Loaned")
}
bobLoan, err := lib.Checkout("CB", "bob", day(0))
if err != nil {
t.Fatalf("unexpected error: %v", err)
}
if bobLoan != nil {
t.Fatalf("expected nil (no copies left), got %+v", bobLoan)
}
}
func TestMultiCopyFreeListAndBorrowLimit(t *testing.T) {
lib := NewLibrary(DailyFlatFine{CentsPerDay: 25}, &RecordingNotifier{})
lib.AddBook(Book{ISBN: "CB", Title: "Clean Code"})
lib.AddCopy(BookItem{Barcode: "CB-001", ISBN: "CB", Status: Available})
lib.AddCopy(BookItem{Barcode: "CB-002", ISBN: "CB", Status: Available})
lib.AddCopy(BookItem{Barcode: "CB-003", ISBN: "CB", Status: Available})
lib.AddMember(Member{ID: "alice", Name: "Alice", BorrowLimit: 1})
lib.AddMember(Member{ID: "bob", Name: "Bob", BorrowLimit: 5})
lib.AddMember(Member{ID: "carol", Name: "Carol", BorrowLimit: 5})
lib.AddMember(Member{ID: "dave", Name: "Dave", BorrowLimit: 5})
issued := map[string]bool{}
for _, m := range []string{"alice", "bob", "carol"} {
l, err := lib.Checkout("CB", m, day(0))
if err != nil || l == nil {
t.Fatalf("checkout for %s failed: %v %+v", m, err, l)
}
issued[l.Barcode] = true
}
if len(issued) != 3 {
t.Fatalf("expected 3 distinct barcodes issued, got %d", len(issued))
}
daveLoan, _ := lib.Checkout("CB", "dave", day(0))
if daveLoan != nil {
t.Fatalf("expected nil, 0 copies left, got %+v", daveLoan)
}
var oneReturned string
for b := range issued {
oneReturned = b
}
lib.ReturnItem(oneReturned, day(1))
retry, err := lib.Checkout("CB", "dave", day(1))
if err != nil || retry == nil || retry.Barcode != oneReturned {
t.Fatalf("expected the freed barcode %s back, got %+v err=%v", oneReturned, retry, err)
}
lib.AddBook(Book{ISBN: "EK", Title: "Effective Kotlin"})
lib.AddCopy(BookItem{Barcode: "EK-001", ISBN: "EK", Status: Available})
if _, err := lib.Checkout("EK", "alice", day(0)); err == nil {
t.Fatalf("expected borrow-limit error for alice, got nil")
}
}
func TestFinePolicyStrategy(t *testing.T) {
lib := NewLibrary(DailyFlatFine{CentsPerDay: 25}, &RecordingNotifier{})
lib.AddBook(Book{ISBN: "CB", Title: "Clean Code"})
lib.AddCopy(BookItem{Barcode: "CB-001", ISBN: "CB", Status: Available})
lib.AddMember(Member{ID: "alice", Name: "Alice", BorrowLimit: 5})
lib.Checkout("CB", "alice", day(0)) // due = day 14
fee := lib.ReturnItem("CB-001", day(20))
if fee != 150 {
t.Fatalf("expected 150 cents (6 days late * 25c), got %d", fee)
}
if lib.MemberByID("alice").FineCentsOwed != 150 {
t.Fatalf("expected running balance 150, got %d", lib.MemberByID("alice").FineCentsOwed)
}
}
func TestHoldQueueFIFOAndRightfulPickup(t *testing.T) {
notifier := &RecordingNotifier{}
lib := NewLibrary(DailyFlatFine{CentsPerDay: 25}, notifier)
lib.AddBook(Book{ISBN: "CB", Title: "Clean Code"})
lib.AddCopy(BookItem{Barcode: "CB-001", ISBN: "CB", Status: Available})
lib.AddMember(Member{ID: "alice", Name: "Alice", BorrowLimit: 5})
lib.AddMember(Member{ID: "bob", Name: "Bob", BorrowLimit: 5})
lib.AddMember(Member{ID: "carol", Name: "Carol", BorrowLimit: 5})
lib.Checkout("CB", "alice", day(0))
if l, _ := lib.Checkout("CB", "bob", day(0)); l != nil {
t.Fatalf("expected 0 copies for bob")
}
lib.PlaceHold("CB", "bob")
lib.PlaceHold("CB", "carol")
lib.ReturnItem("CB-001", day(2))
if got := notifier.Snapshot(); len(got) != 1 || got[0] != "bob" {
t.Fatalf("expected [bob] notified first, got %v", got)
}
if lib.ItemByBarcode("CB-001").Status != OnHold {
t.Fatalf("expected CB-001 held, not generally available")
}
if _, err := lib.PickupHold("CB-001", "carol", day(3)); err == nil {
t.Fatalf("expected carol to be rejected -- it's bob's hold")
}
bobLoan, err := lib.PickupHold("CB-001", "bob", day(3))
if err != nil || bobLoan == nil || bobLoan.Barcode != "CB-001" {
t.Fatalf("expected bob to pick up CB-001, got %+v err=%v", bobLoan, err)
}
lib.ReturnItem("CB-001", day(10))
if got := notifier.Snapshot(); len(got) != 2 || got[1] != "carol" {
t.Fatalf("expected carol notified 2nd, got %v", got)
}
}
// TestConcurrentCheckoutIsSafe hammers the LOCKED Checkout path for the last
// remaining copy. Run with `go test -race`: it must report zero races here,
// in contrast to the break-it programs (cmd/breakit_doublelend,
// cmd/breakit_queuefairness) which use the *Unsafe twins and are SEPARATE
// programs on purpose.
func TestConcurrentCheckoutIsSafe(t *testing.T) {
const goroutines = 200
lib := NewLibrary(DailyFlatFine{CentsPerDay: 25}, &RecordingNotifier{})
lib.AddBook(Book{ISBN: "DL", Title: "DDIA"})
lib.AddCopy(BookItem{Barcode: "DL-001", ISBN: "DL", Status: Available})
for i := 0; i < goroutines; i++ {
lib.AddMember(Member{ID: idOf(i), Name: idOf(i), BorrowLimit: 5})
}
var wg sync.WaitGroup
var mu sync.Mutex
successes := 0
for i := 0; i < goroutines; i++ {
wg.Add(1)
go func(i int) {
defer wg.Done()
loan, _ := lib.Checkout("DL", idOf(i), day(0))
if loan != nil {
mu.Lock()
successes++
mu.Unlock()
}
}(i)
}
wg.Wait()
if successes != 1 {
t.Fatalf("expected exactly 1 success for the single last copy, got %d", successes)
}
}
// TestConcurrentReturnIsSafe hammers the LOCKED ReturnItem path across many
// simultaneous returns competing for the same title's hold queue and asserts
// FIFO fairness holds: exactly `copies` distinct members notified, no
// duplicates, and the notified set is exactly the first `copies` in queue order.
func TestConcurrentReturnIsSafe(t *testing.T) {
const copies = 8
const waiters = 10
notifier := &RecordingNotifier{}
lib := NewLibrary(DailyFlatFine{CentsPerDay: 25}, notifier)
lib.AddBook(Book{ISBN: "Q", Title: "Queueing Theory"})
for i := 0; i < copies; i++ {
barcode := "Q-00" + idOf(i)
lib.AddCopy(BookItem{Barcode: barcode, ISBN: "Q", Status: Available})
holder := "holder" + idOf(i)
lib.AddMember(Member{ID: holder, Name: holder, BorrowLimit: 5})
lib.Checkout("Q", holder, day(0))
}
expected := map[string]bool{}
for i := 0; i < waiters; i++ {
w := "w" + idOf(i)
lib.AddMember(Member{ID: w, Name: w, BorrowLimit: 5})
lib.PlaceHold("Q", w)
if i < copies {
expected[w] = true
}
}
var wg sync.WaitGroup
for i := 0; i < copies; i++ {
wg.Add(1)
go func(i int) {
defer wg.Done()
lib.ReturnItem("Q-00"+idOf(i), day(1))
}(i)
}
wg.Wait()
got := notifier.Snapshot()
if len(got) != copies {
t.Fatalf("expected %d notifications, got %d: %v", copies, len(got), got)
}
seen := map[string]bool{}
for _, m := range got {
if seen[m] {
t.Fatalf("member %s notified more than once: %v", m, got)
}
seen[m] = true
}
for w := range expected {
if !seen[w] {
t.Fatalf("expected waiter %s to be notified (FIFO), but was starved: %v", w, got)
}
}
}
func idOf(i int) string { return strconv.Itoa(i) }And these are the two actual break-it programs — put each at cmd/breakit_doublelend/main.go and cmd/breakit_queuefairness/main.go in a module that imports the library package above:
// Command breakit_doublelend hammers Library.CheckoutUnsafe (the naive
// scan-then-set, no lock) with 200 goroutines against a title that has
// exactly ONE physical copy. Expect a crash: Go's map implementation
// detects the concurrent writes to the shared activeLoans map and calls
// fatal() -- "fatal error: concurrent map writes" -- which is NOT
// recoverable (this is why it is its own binary, separate from the
// hold-queue demo). Run with the race detector to see the exact
// unsynchronized read/write reported first:
//
// go run ./cmd/breakit_doublelend # crashes: fatal error: concurrent map writes
// go run -race ./cmd/breakit_doublelend # prints "WARNING: DATA RACE" then crashes
package main
import (
"fmt"
"strconv"
"sync"
"time"
"library"
)
func main() {
const goroutines = 200
today := time.Date(2026, 1, 1, 0, 0, 0, 0, time.UTC)
lib := library.NewLibrary(library.DailyFlatFine{CentsPerDay: 25}, &library.RecordingNotifier{})
lib.AddBook(library.Book{ISBN: "DL", Title: "DDIA"})
lib.AddCopy(library.BookItem{Barcode: "DL-001", ISBN: "DL", Status: library.Available}) // exactly ONE copy
for i := 0; i < goroutines; i++ {
id := strconv.Itoa(i)
lib.AddMember(library.Member{ID: id, Name: id, BorrowLimit: 5})
}
var wg sync.WaitGroup
var mu sync.Mutex
successes := 0
for i := 0; i < goroutines; i++ {
wg.Add(1)
go func(i int) {
defer wg.Done()
loan := lib.CheckoutUnsafe("DL", strconv.Itoa(i), today)
if loan != nil {
mu.Lock()
successes++
mu.Unlock()
}
}(i)
}
wg.Wait()
// Reached only if you got lucky and the runtime didn't catch the race
// this run -- still wrong, just not caught THIS time. That's the danger.
fmt.Printf("no crash this run, but %d / %d goroutines were handed the SAME single copy (want exactly 1) -- still racy\n", successes, goroutines)
}// Command breakit_queuefairness returns 8 copies of the same title
// concurrently while 10 members are queued for holds, using
// Library.ReturnItemUnsafe (peek-then-remove, no lock). Expect the FIFO
// invariant to break: some queued member is double-notified while another,
// earlier-in-line member is silently starved -- and/or Go's map runtime
// detects the concurrent hold-queue mutation and crashes the process
// outright. Run with the race detector to see the exact unsynchronized
// access reported first:
//
// go run ./cmd/breakit_queuefairness # wrong FIFO assignment, or a crash
// go run -race ./cmd/breakit_queuefairness # prints "WARNING: DATA RACE" first
package main
import (
"fmt"
"strconv"
"sync"
"time"
"library"
)
func main() {
const copies = 8
const waiters = 10
today := time.Date(2026, 1, 1, 0, 0, 0, 0, time.UTC)
notifier := &library.RecordingNotifier{}
lib := library.NewLibrary(library.DailyFlatFine{CentsPerDay: 25}, notifier)
lib.AddBook(library.Book{ISBN: "Q", Title: "Queueing Theory"})
for i := 0; i < copies; i++ {
barcode := "Q-00" + strconv.Itoa(i)
lib.AddCopy(library.BookItem{Barcode: barcode, ISBN: "Q", Status: library.Available})
holder := "holder" + strconv.Itoa(i)
lib.AddMember(library.Member{ID: holder, Name: holder, BorrowLimit: 5})
lib.Checkout("Q", holder, today) // all 8 copies go out first, single-threaded
}
expected := map[string]bool{}
for i := 0; i < waiters; i++ {
w := "w" + strconv.Itoa(i)
lib.AddMember(library.Member{ID: w, Name: w, BorrowLimit: 5})
lib.PlaceHold("Q", w) // w0..w9 queue up, in order
if i < copies {
expected[w] = true // w0..w7 SHOULD be the ones notified
}
}
var wg sync.WaitGroup
for i := 0; i < copies; i++ {
wg.Add(1)
go func(i int) {
defer wg.Done()
lib.ReturnItemUnsafe("Q-00"+strconv.Itoa(i), today.AddDate(0, 0, 1))
}(i)
}
wg.Wait()
got := notifier.Snapshot()
seen := map[string]int{}
for _, m := range got {
seen[m]++
}
starved, duplicated := 0, 0
for w := range expected {
if seen[w] == 0 {
starved++
}
}
for _, count := range seen {
if count > 1 {
duplicated++
}
}
fmt.Printf("notified = %v\n", got)
fmt.Printf("%d expected waiter(s) starved (never notified), %d member(s) double-notified (want 0 and 0)\n", starved, duplicated)
}Measured in this session: go build ./... and go vet ./... are clean; go test -race ./... passes 6/6 (0 races), repeated 3× with -count=3. go run ./cmd/breakit_doublelend crashed with fatal error: concurrent map writes on every run; go run -race ./cmd/breakit_doublelend printed WARNING: DATA RACE pinpointing the unsynchronized read/write in CheckoutUnsafe before the same crash. go run ./cmd/breakit_queuefairness is genuinely bimodal across repeated runs (10 runs measured): most of the time (7/10) it completes and prints notified = [w0 w0 w0 w0 w0 w0 w0 w0] — 7 expected waiters starved, 1 member (w0) double-notified 8 times — and the rest of the time (3/10) it crashes outright with the same fatal error: concurrent map writes, because ReturnItemUnsafe also deletes from the shared activeLoans map without a lock, giving the runtime two independent unguarded map mutations to catch. Either outcome is the lesson: wrong FIFO assignment when it doesn't crash, a hard process kill when it does. go run -race on the same program reliably reports WARNING: DATA RACE on the shared map(s) before it finishes, every run. The same missing lock produces two different failure signatures across languages — Java's collections silently drop/duplicate entries (wrong answer, sometimes an exception, no reliable crash) while Go's map runtime detects the concurrent write and kills the process outright (no answer at all, loudly). Neither is "safer" than the other; both mean the same thing: this code needed the lock and didn't have one.
Optimise — trade-offs
| Decision | Option A | Option B | When A wins | When B wins |
|---|---|---|---|---|
| Copy bookkeeping | Book with a copies-available counter | Book + BookItem (one row per physical copy) | A pure "how many left" catalog display with no per-copy operations at all (rare in practice) | Anything that needs to act on one specific physical object — barcode-scan checkout, marking one copy lost/damaged, binding a Loan or a fine to the exact item, auditing "where is copy #7 right now." This is nearly always what a real system needs, which is why the counter is a trap, not a simplification |
| Hold-queue discipline | Strict FIFO (first hold, first served) | Priority queue (e.g. faculty/staff or overdue-fine-free members skip ahead) | Fairness is the product requirement and the interviewer is testing queue-correctness, not policy — this kata's default | The business has a real priority tier (a university library favoring faculty for course reserves, say) — same underlying mechanism (a heap instead of a deque, same per-title lock), different comparator; defend it as a policy change, not a redesign |
| Concurrency control on the last copy | Pessimistic per-title lock (this kata: one mutex guards the free-list + hold queue together) | Optimistic CAS / versioned status (compare-and-swap the BookItem's status field, retry on conflict) | The claim touches two related structures atomically (free-list AND hold-queue handoff) — a single lock is trivially easy to reason about and correct, and contention per title is low (one popular title being hammered by hundreds of threads is a rare, extreme case) | Extremely high read/attempt-rate on a tiny number of hot titles where lock contention itself becomes the bottleneck — CAS-and-retry on the single status field avoids blocking, but doesn't cleanly extend to "also atomically service the hold queue," so you'd need a more careful lock-free queue design to get the same correctness guarantee CAS gives you for the simple case |
| Return notification | Observer / push (HoldNotifier.notifyReady fires the instant a copy returns) | Polling (member's client re-calls checkout periodically) | Never, for this use case — polling wastes requests, adds latency (up to one poll interval), and still doesn't guarantee FIFO fairness on its own (whoever's poll happens to land first can win, independent of queue position) | Push notification is unavailable end-to-end (no webhook/email/SMS channel) — even then, prefer a scheduled digest over raw polling |
| What happens to a returned copy when someone's waiting | ON_HOLD, explicit pickup window (this kata: the head of the queue must call pickupHold; a real system would additionally reap an expired, unclaimed hold and offer it to the next waiter) | Auto-checkout to the next waiter (the return immediately creates a Loan for them, no separate pickup step) | The physical-pickup model (a real library, or "reserve online, collect at the counter") — a member who's on vacation shouldn't have their borrow-limit and loan clock silently consumed by a book they haven't touched yet | A fully virtual "reservation" flow with no physical pickup step (e.g. digital holds) where there's no reason to delay converting the hold into an active loan; simpler code, one less state and one less expiry-reaper to build |
Defend under drilling
- "Book vs. BookItem — why do you need both?" —
Bookis title metadata that never changes (isbn, title, author) and is shared by every copy;BookItemis the actual unit of work — one barcode, one independent status, one at a time in exactly one member's hands. ALoancan only ever be correct if it's bound to a specificBookItem: that's what lets you compute a fine for the exact copy that came back late, mark one damaged copy LOST without touching its siblings, and resolve a real barcode scan to a real record. A `Book`-with-a-counter can answer "how many," but not "which one" — and real checkout is barcode-driven, so "which one" is the actual question being asked at the front desk. - "Walk me through the hold queue." — When
checkoutfinds zero available copies, the member callsplaceHold, which appends them to a FIFO deque scoped to that title. When any copy of that title returns,returnItemchecks the SAME title's queue under the SAME lock used for allocation: if it's non-empty, it pops the head and flips that exactBookItemtoON_HOLDassigned to them, then notifies via the observer — nobody else can pick it up (`pickupHold` checks `holdForMemberId` matches the caller). If the queue is empty, the copy goes back to the general free-list instead. One lock, one atomic decision: "does this copy go to the front of a specific line, or back into the general pool." - "Two members scan the barcode of the last copy at the same instant — what happens, and how do you stop it?" — In the naive implementation (this kata's
checkoutUnsafe), each thread scans the title's copies, reads a status of AVAILABLE, and only THEN writes LOANED — a classic check-then-act race with no atomicity between the read and the write. With a real 1ms delay inserted between them to widen the window, hammering it with 200 threads reliably handed the same single copy to more than 20 of them in every run I measured. The fix is the same free-list-pop pattern as a parking lot's spot allocator: keep a per-title stack of available barcodes, and make "pop the barcode" and "mark it loaned" ONE critical section under a per-title lock — there is no window between claiming the barcode and committing its new status where a second thread can also see it as available. - "Fines and borrow limits as a strategy — why not just an if/else?" — Because the formula and the caps are exactly the kind of business rule that changes by library policy (flat rate vs. tiered vs. capped, a 3-book limit vs. a 10-book limit for staff) without the allocator or the hold queue caring at all.
FinePolicyis one method,lateFeeCents(dueDate, returnDate); swappingDailyFlatFinefor a tiered policy is a new class, zero changes toLibrary. The borrow-limit and fine-cap checks live at the very top ofcheckout/pickupHold, before the lock is even acquired, because they're about the MEMBER's eligibility, not about which copy gets claimed — a completely separate concern from the free-list race. - "What breaks at 100x?" — Three things, in order of when you'd hit them. First, a single global structure per title is fine until one title (a bestseller, a required textbook) gets hammered by thousands of concurrent holds — the FIFO deque itself stays O(1) per operation, so the bottleneck becomes lock contention on that one title's mutex, not the data structure; the fix is usually just "this hot title's lock is hot," which is a monitoring problem before it's a code problem. Second, once the catalog spans multiple library branches or a distributed deployment, a single-process in-memory
Map<String, ReentrantLock>stops being enough — the claim-and-flip needs to become a database transaction (a row-level lock or optimistic version column on theBookItemrow) or a distributed lease, the exact same "shared mutable state needs a synchronization boundary" lesson, just moved out of a single JVM/process. Third, the hold queue itself needs to survive a crash — an in-memory deque loses every waiting member's place in line if the process restarts, so at scale it moves to a durable queue (a database table ordered by timestamp, or a message queue like Kafka/SQS) so FIFO order and "who's owed the next copy" survive a restart.
You can now defend
- You can explain why collapsing "the title" and "the physical copy" into one entity with a counter is the classic trap in this problem, and why a Book/BookItem split is what lets the system answer "which specific copy," not just "how many" — the difference that barcode-scan checkout, fines, and lost-copy tracking all actually depend on.
- You can derive the O(1) per-title free-list allocator from first principles (the same insight as a parking lot's spot allocator, applied to library copies), and explain exactly why "claim the barcode" and "mark it loaned" must be one atomic step, not two.
- You've reproduced BOTH concurrency bugs this kata is built around — the last-copy double-lend and the hold-queue starvation/double-assign — in Java and Go, seen the two different failure signatures (silent corruption/exception vs. hard process crash) the same missing lock produces in each language, and fixed both with a single per-title lock that guards the free-list and the hold queue together as one resource.
- You can defend the fine policy and borrow limit as pluggable strategy decisions rather than hardcoded rules, and you can name the next escalation at scale (hot-title lock contention, a database-transaction claim across branches, a durable hold queue) before an interviewer has to ask.
Re-authored/Deepened for this guide. Model answer: the Design a Library Management System walkthrough. Reference implementations (Java + Go) compiled and tested in-session: javac clean, 21/21 assertions pass (including both deliberately-adversarial break-it assertions — the unsafe checkout measured 26-38 of 200 threads double-lent the last copy across repeated runs, and the unsafe return measured the hold queue collapsing to a single member notified up to 8 times while 7 earlier-in-line members were starved); go build + go vet + go test -race clean, 6/6 tests pass repeatedly on the locked paths; cmd/breakit_doublelend crashed with fatal error: concurrent map writes on every run, and cmd/breakit_queuefairness either printed the queue-starvation symptom (7/10 runs measured) or crashed with the same fatal error (3/10 runs measured), with go run -race additionally reporting the exact data race before each crash.
🤖 Don't fully get this? Learn it with Claude
Stuck on Design a Library Management System? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.
🎨 Explain it visually
Build the mental picture, not memorization.
I just read a lesson on **Design a Library Management System** (Hands-On Builds) and want to truly understand it. Explain Design a Library Management System from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🤔 Walk me through it (interactive)
Socratic — adapts to where you're stuck.
Teach me **Design a Library Management System** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🧪 Quiz me & fix my gaps
Active recall exposes what you missed.
Quiz me on **Design a Library Management System** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🧠 Make it stick
Intuition + hook + flashcards for long-term memory.
Help me remember **Design a Library Management System** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.