Lab L14 · Java + Go

Extending a concurrent reservation component

Build a booking calendar for a resource that has capacity parallel units, for example three charging bays. A booking reserves some units over a half-open time interval [start, end) and is accepted only if, at every instant, the units of all overlapping bookings stay within capacity. The base contract is one-unit book plus cancel and expiry; the extension adds multi-unit bookUnits and reschedule without changing how book behaves.

The task

An EV charging hub has 3 chargers. Fleet operators reserve chargers for time slots; a large van may need 2 at once. Two operators clicking “book 14:00–15:00” at the same moment must not both get the last charger, so the capacity check and the insert must be one atomic step. Clients retry on timeouts, so booking the same id with the same details again must succeed without taking another unit. Times are plain longs in caller-chosen units.

Occupancy over time against the capacity line. The rejected reschedule (red) would stack on top of b and cross the line; the accepted one fits because nothing else occupies [20,30).

What you implement

public final class ReservationCalendar {
    public record Interval(long start, long end) {}               // [start, end)
    public ReservationCalendar(int capacity);
    public boolean book(String id, Interval interval);            // one unit
    public boolean bookUnits(String id, Interval interval, int units);   // extension
    public boolean reschedule(String id, Interval interval, int units);  // extension
    public boolean cancel(String id);                             // true if it existed
    public int expire(long now);                                  // remove bookings with end <= now; returns count
}

Rules

Invalid input → IllegalArgumentException: empty id, start >= end, units <= 0 or units > capacity.
Half-open intervals: [0,10) and [10,20) touch but do not overlap.
If accepting the booking would push total units above capacity at any instant, return false and change nothing.
Same id with the identical interval and units → true without reserving more (idempotent). Same id with anything different → IllegalArgumentException (“ID conflict”).
reschedule: the id must exist (else IllegalArgumentException). Check the new booking as if the old one were gone; if it does not fit, return false and keep the old booking.
Concurrency: N threads booking the same slot with distinct ids on capacity C → exactly C succeed.
Check algorithm (sweep line): turn each booking into +units at start and −units at end, sort by time with ends before starts at equal times, and ensure the running sum never exceeds capacity.

Worked example

capacity = 3. bookUnits(a, [0,10), 2) → true. book(b, [10,20)) → true.
reschedule(a, [10,20), 3) → false (3 + b's 1 = 4 > 3); a still holds [0,10) × 2.
bookUnits(c, [0,10), 2) → false (2 + 2 = 4 > 3).
reschedule(a, [20,30), 3) → true. expire(20) → 1 (removes b).

Files and commands

Read the tests first, then replace each TODO in the starter until they pass. Java starter: ReservationCalendar.java · tests: HistoryTest.java, ReservationCalendarTest.java. Go starter: calendar.go · tests: calendar_test.go, history_test.go.

cd java
./gradlew test --tests 'labs.reservation.*'

cd go
go test -race -count=1 ./reservation

Reveal the reference solutions

Java: ReservationCalendar.java
Go: calendar.go

When to use

Use this lab to examine a small concurrent reservation calendar and then extend it without changing caller-visible behavior. The supplied Java and Go implementations reserve one capacity unit over a half-open interval: include the start and exclude the end. Positive capacity is fixed at construction. Timestamps are signed integers in caller-selected units and must satisfy start less than end. The code does not consult a hidden clock or assume the integers represent wall-clock instants.

The component is local and in memory. It is neither a durable booking system nor a distributed lock. The caller must persist business state and establish transactional conflict handling if a booking must survive restart or coordinate across processes. Retained reservations and identifier lengths have no automatic storage quota.

Steps

Start from the one-unit contract. Booking A over zero to ten and B over ten to twenty must succeed at capacity one: endpoints touch without overlap. A booking from five to fifteen then fails. Repeating an identical identity and interval succeeds without reserving a second unit; reusing the identity with different bounds produces a conflict error.
Protect admission as one operation. Build the proposed schedule, check capacity, and install the reservation while holding the same lock. A check outside the lock followed by insertion permits concurrent callers to consume the same apparent space.
Use a sweep-line model. Turn each start into a plus-one event and each end into a minus-one event. Sort by time and process ends before starts at the same time. The running occupancy must never exceed capacity. Rebuild and sort for each booking in this clear reference implementation; the cost is O(n log n) in retained reservations.
Preserve lifecycle semantics. Cancellation removes a resident identity and reports whether anything was removed. Expiry explicitly removes intervals ending at or before a supplied time. It does not advance a watermark or forbid historical bookings afterward. Forgetting an expired identity also forgets its deduplication history; do not claim permanent idempotency.
Test concurrency and compatibility. Start many identical-time bookings with distinct identities and require exactly the configured capacity to succeed. Collect all task outcomes; merely checking no exception was thrown misses logical overbooking. Keep endpoint, identity-conflict, cancellation, and expiry tests as characterization checks before an extension.
Run the implemented extensions. BookUnits/bookUnits accepts a positive unit count no greater than capacity; the old booking API forwards one unit. Before adding an arrival, compare its units with remaining capacity, avoiding occupancy overflow. Reschedule/reschedule evaluates the proposed replacement without the old entry and installs it only if valid. A capacity failure preserves the old reservation. Tests reject a three-unit replacement against an overlapping one-unit booking, then verify the original still consumes its earlier interval.

Checklist

Recall and variation

Rebuild half-open capacity checking before reading Go or Java. Variation: concurrent weighted rescheduling into the same last unit. Acceptance: at most one conflicting replacement succeeds and the rejected booking retains its old interval.

Endpoint conventions are covered by adjacent-interval tests
Capacity checking and admission share a lock
Duplicate identity, conflict, and overload remain distinct outcomes
Expiry does not imply durable retention or a monotonic time policy
Extensions preserve existing behavior through characterization tests

Signals

Working: concurrent distinct bookings fill but never exceed capacity, and touching intervals remain compatible.

Going wrong: sorting starts before ends rejects valid adjacency, cancellation accidentally frees a different identity, or expiry is presented as proof that historical duplicates can never return.

Implementing a Time-Window Event Aggregator, for a contrasting monotonic-watermark expiry policy.