Liskov substitution principle

The Liskov substitution principle says that anything written against a type must keep working with every subtype of it. If code is correct for a Tags, it must be correct for every class that claims to be a Tags. That includes ones written years later, by someone else.

Barbara Liskov stated it in a 1987 keynote, and she and Jeannette Wing made it precise in 1994. The key word is behavior. The compiler already checks that a subtype has the right methods with the right signatures. LSP is about what the compiler can’t check: the promises those methods make. A subclass that has an add() method but throws when you call it fits the type perfectly and breaks every caller.

This is the principle that makes open/closed safe. Plugging new classes into old code only works if the new classes keep the old promises. This page shows three real ways they don’t. Pick a level below. The rest of the page is shared.

The idea in one picture

Scroll or pinch to zoom, drag to pan

Both classes fit the Tags type, so both compile. Only one keeps the promises the caller relies on.

What makes this hard

• A type is a set of promises, not just method signatures. Write them down, or nobody can tell whether a new subtype keeps them.
• A subtype may accept more and promise more. It may never demand more, promise less, or fail in new ways.
• The fix is rarely an instanceof check in the caller. It’s a different hierarchy. Split the type, so each class only claims what it can keep. Or adapt the class until it keeps the promises.

The rules

Every LSP violation breaks one of five rules. For a subtype to be a safe substitute:

Rule	In plain words	Broken when
Preconditions can’t be strengthened	It accepts at least everything the parent accepts	The parent takes any size; the subtype refuses over 1 KB
Postconditions can’t be weakened	It guarantees at least everything the parent guarantees	The parent never forgets a count; the subtype evicts
Invariants must hold	What’s always true of the parent stays true	A “read-only” view whose contents change under you
No new kinds of failure	It throws only what the parent’s callers already handle	add() throws “not supported”
History can’t change in new ways	It doesn’t allow changes the parent rules out	An immutable Point with a mutable subclass

The test for all five is the same: take a test written for the parent, and run it against the subtype. If it fails, the subtype isn’t one, whatever the compiler says. That’s why the examples below all end with one contract test suite, run against every implementation.

Worked examples

EasyA read-only tag listMediumSwapping storage backendsHardA rate limiter's counters

Easy

A read-only tag list

• Promises the compiler cannot see
• Splitting the type
• Asking for only what you use

A blogging platform lets authors tag posts. Every new post gets a “new” tag added by default. There are also site-wide tags, loaded from config, that must never change while the site runs. Someone made a FrozenTags class for those that refuses add().

This exact design is in the standard libraries. In Java, List.of("a").add("b") throws UnsupportedOperationException. In .NET, an array is an IList<T> and Add on it throws NotSupportedException. Java documents add as an “optional operation”, and .NET gives callers an IsReadOnly flag to check first. Both are polite ways of saying the type promises nothing.

Without the principle

One Tags interface covers every tag list, editable or not:

JListTags.javaPyfrozen_tags.pyC#ListTags.csGofrozen_tags.goTSfrozen-tags.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

import java.util.ArrayList;
import java.util.List;

// One interface for every kind of tag list, editable or not.
interface Tags {
    boolean contains(String tag);
    List<String> all();
    void add(String tag);
}

class ListTags implements Tags {
    private final List<String> tags = new ArrayList<>();
    public boolean contains(String tag) { return tags.contains(tag); }
    public List<String> all() { return List.copyOf(tags); }
    public void add(String tag) { tags.add(tag); }
}

// Site-wide tags from config must never change while the site runs, so add() refuses.
// The JDK does the same: List.of("a").add("b") throws UnsupportedOperationException.
// flaw: it claims to be Tags, but it breaks the one promise add() makes. The compiler
// can't tell; the crash happens in production, in code that has never heard of FrozenTags.
class FrozenTags implements Tags {
    private final List<String> tags;
    FrozenTags(List<String> tags) { this.tags = List.copyOf(tags); }
    public boolean contains(String tag) { return tags.contains(tag); }
    public List<String> all() { return tags; }
    public void add(String tag) { throw new UnsupportedOperationException("tags are frozen"); }
}

class Posts {
    // Written against Tags, and correct for every Tags that keeps its promises.
    static void addDefaultTags(Tags tags) {
        if (!tags.contains("new")) tags.add("new");
    }
}

class Main {
    public static void main(String[] args) {
        Tags draft = new ListTags();
        Posts.addDefaultTags(draft);
        System.out.println(draft.all()); // [new]

        Tags siteWide = new FrozenTags(List.of("featured"));
        Posts.addDefaultTags(siteWide); // compiles fine, throws at run time
    }
}

addDefaultTags is correct. It was written against Tags, and uses it as documented. It crashes because one class claims to be a Tags, and isn’t. The bug isn’t in the code that crashed. It’s in a class the crashing code has never heard of. That’s what makes LSP violations expensive: the stack trace points at the wrong place.

Try each class in the caller. All three compile:

Plug a class into addDefaultTags(tags)ListTagsFrozenTagsLowercaseTags

1. ·add() stores the tag
2. ·contains() finds a tag right after add()
3. ·add() never throws

The caller relies on each of these promises. Pick a class to check them.

With LSP

Split the type by the promises each class can keep. Reading is something every tag list can do. Editing is an extra promise only some can. Then each function asks for exactly what it uses.

Easy: one promise per interface, and a function that asks for the right one

Scroll or pinch to zoom, drag to pan

• Color key
• Facade
• Entity
• Value object
• Enum
• Interface
• Implementation

JPosts.javaPyfrozen_tags.pyC#Posts.csGofrozen_tags.goTSfrozen-tags.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

import java.util.ArrayList;
import java.util.List;

// Split by what callers need. Reading is a promise every tag list can keep...
interface ReadableTags {
    boolean contains(String tag);
    List<String> all();
}

// ...and editing is an extra promise only some can. Every EditableTags is a ReadableTags,
// and that is true: it can do everything a readable list can, plus more.
interface EditableTags extends ReadableTags {
    void add(String tag);
}

class ListTags implements EditableTags {
    private final List<String> tags = new ArrayList<>();
    public boolean contains(String tag) { return tags.contains(tag); }
    public List<String> all() { return List.copyOf(tags); }
    public void add(String tag) { tags.add(tag); }
}

// No add() to break. It only claims what it can keep.
class FrozenTags implements ReadableTags {
    private final List<String> tags;
    FrozenTags(List<String> tags) { this.tags = List.copyOf(tags); }
    public boolean contains(String tag) { return tags.contains(tag); }
    public List<String> all() { return tags; }
}

class Posts {
    // Asks for exactly what it uses. Passing FrozenTags is now a compile error,
    // found by the person writing the call, not by a user.
    static void addDefaultTags(EditableTags tags) {
        if (!tags.contains("new")) tags.add("new");
    }

    // Only reads, so it accepts both kinds.
    static boolean isFeatured(ReadableTags tags) { return tags.contains("featured"); }
}

class Main {
    public static void main(String[] args) {
        EditableTags draft = new ListTags();
        Posts.addDefaultTags(draft);
        System.out.println(draft.all()); // [new]

        ReadableTags siteWide = new FrozenTags(List.of("featured"));
        System.out.println(Posts.isFeatured(siteWide)); // true
        // Posts.addDefaultTags(siteWide);  // does not compile: FrozenTags can't promise add()
    }
}

What to notice

• The bug moved from run time to compile time. Passing FrozenTags to addDefaultTags no longer compiles. The person writing the call finds out, not a user.
• The subtype relation is now true. Every EditableTags really can do everything a ReadableTags can, plus more. That’s the direction subtyping should go: subtypes add promises, they don’t remove them.
• Callers ask for the least they need. isFeatured takes ReadableTags, so it works with both. That’s interface segregation doing LSP’s job.
• LowercaseTags is the dangerous kind. It never throws. It just quietly changes what add means. You only catch it by writing down the promise (“contains finds a tag right after add”) and testing it.

Interviewer

We have Bird with a fly() method. How do you model a penguin?

What they are testing

Whether you refuse to make Penguin.fly() throw, and instead question the base type: what do callers of Bird actually need? Split the capability out (FlyingBird, or a Flyer interface) so only birds that fly claim to. Five minutes. The red flag is “throw UnsupportedOperationException”, or “callers check instanceof Penguin”.

Say this out loud

FrozenTags can’t keep add()’s promise, so it shouldn’t claim to have it. I’ll split reading from editing, and have each function ask for only the part it uses.

Medium

Swapping storage backends

• Writing the contract down
• One contract test suite
• Adapting a class until it fits

A product stores user uploads behind a BlobStore interface: put bytes under a key, get them back. It runs on local disk in tests and on cloud object storage in production. To save money, someone wires in a cheap key-value service instead. It has a put and a get, so it fits.

Storage is where LSP bites hardest, because the important promises are about behavior. How big can a value be? What does “missing” look like? Does a read right after a write see the new data? Amazon S3 didn’t promise that last one for overwrites until December 2020. Code tested on local disk, where it’s always true, could break on S3 without changing a line.

Without the principle

The interface had a contract, but only in people’s heads. The new store breaks two of its promises:

JContract.javaPytiny_kv_store.pyC#Contract.csGotiny_kv_store.goTStiny-kv-store.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.NoSuchElementException;

// The contract. Every caller relies on all three promises, so every BlobStore must keep them:
//  1. get(key) right after put(key, data) returns the same bytes
//  2. any size up to 1 MB is accepted
//  3. get() of a missing key returns null; it never throws
interface BlobStore {
    void put(String key, byte[] data);
    byte[] get(String key);
}

class InMemoryStore implements BlobStore {
    private final Map<String, byte[]> blobs = new HashMap<>();
    public void put(String key, byte[] data) { blobs.put(key, data.clone()); }
    public byte[] get(String key) { byte[] b = blobs.get(key); return b == null ? null : b.clone(); }
}

// A cheap key-value service someone wired in to save money. It fits the interface...
class TinyKvStore implements BlobStore {
    private final Map<String, byte[]> values = new HashMap<>();

    public void put(String key, byte[] data) {
        // flaw: a stronger precondition than the contract. Callers were promised 1 MB;
        // this refuses anything over 1 KB.
        if (data.length > 1024) throw new IllegalArgumentException("value over 1 KB");
        values.put(key, data.clone());
    }

    public byte[] get(String key) {
        // flaw: a new failure the contract doesn't allow. Every caller checks for null,
        // none of them catch this.
        byte[] v = values.get(key);
        if (v == null) throw new NoSuchElementException(key);
        return v.clone();
    }
}

class Contract {
    // One test suite, run against every implementation. This is how LSP is enforced in practice.
    static List<String> check(BlobStore store) {
        List<String> out = new ArrayList<>();
        out.add(attempt("round trip", () -> {
            store.put("a", "hello".getBytes());
            return Arrays.equals(store.get("a"), "hello".getBytes());
        }));
        out.add(attempt("5 KB value", () -> {
            byte[] big = new byte[5_000];
            Arrays.fill(big, (byte) 7);
            store.put("big", big);
            return Arrays.equals(store.get("big"), big);
        }));
        out.add(attempt("missing is null", () -> store.get("nope") == null));
        return out;
    }

    private static String attempt(String name, java.util.function.BooleanSupplier test) {
        try {
            return (test.getAsBoolean() ? "PASS " : "FAIL ") + name;
        } catch (RuntimeException e) {
            return "FAIL " + name + " (" + e.getClass().getSimpleName() + ")";
        }
    }
}

class Main {
    public static void main(String[] args) {
        System.out.println("InMemoryStore " + Contract.check(new InMemoryStore()));
        System.out.println("TinyKvStore   " + Contract.check(new TinyKvStore()));
    }
}

Plug each store into the upload service and check the promises:

Plug a class into the upload serviceInMemoryStoreTinyKvStoreEventualStoreChunkedStore

1. ·get() right after put() returns the same bytes
2. ·accepts any size up to 1 MB
3. ·get() of a missing key returns null, never throws

The caller relies on each of these promises. Pick a class to check them.

With LSP

Write the contract down, next to the interface. Turn it into one test suite, and run it against every implementation. Then fix the store that fails. TinyKv stops claiming to be a BlobStore. And an adapter, ChunkedStore, does the work to keep every promise on top of it.

Medium: the cheap store stops pretending, and an adapter keeps the contract

Scroll or pinch to zoom, drag to pan

• Color key
• Facade
• Entity
• Value object
• Enum
• Interface
• Implementation

JChunkedStore.javaPychunked_store.pyC#ChunkedStore.csGochunked_store.goTSchunked-store.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

import java.nio.charset.StandardCharsets;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.NoSuchElementException;

// The contract. Every caller relies on all three promises, so every BlobStore must keep them:
//  1. get(key) right after put(key, data) returns the same bytes
//  2. any size up to 1 MB is accepted
//  3. get() of a missing key returns null; it never throws
interface BlobStore {
    void put(String key, byte[] data);
    byte[] get(String key);
}

class InMemoryStore implements BlobStore {
    private final Map<String, byte[]> blobs = new HashMap<>();
    public void put(String key, byte[] data) { blobs.put(key, data.clone()); }
    public byte[] get(String key) { byte[] b = blobs.get(key); return b == null ? null : b.clone(); }
}

// The cheap service, described honestly. It no longer claims to be a BlobStore, so its
// 1 KB limit and its exception are its own business, visible in its own API.
class TinyKv {
    static final int LIMIT = 1024;
    private final Map<String, byte[]> values = new HashMap<>();

    void set(String key, byte[] value) {
        if (value.length > LIMIT) throw new IllegalArgumentException("value over 1 KB");
        values.put(key, value.clone());
    }

    byte[] fetch(String key) {
        byte[] v = values.get(key);
        if (v == null) throw new NoSuchElementException(key);
        return v.clone();
    }
}

// An adapter that does the work to keep every BlobStore promise on top of TinyKv:
// big blobs are split into 1 KB chunks, and "not found" becomes null.
class ChunkedStore implements BlobStore {
    private final TinyKv kv;

    ChunkedStore(TinyKv kv) { this.kv = kv; }

    public void put(String key, byte[] data) {
        int chunks = (data.length + TinyKv.LIMIT - 1) / TinyKv.LIMIT;
        for (int i = 0; i < chunks; i++) {
            kv.set(key + "#" + i, Arrays.copyOfRange(data, i * TinyKv.LIMIT, Math.min(data.length, (i + 1) * TinyKv.LIMIT)));
        }
        // The manifest is written last: a reader never sees a count for chunks that aren't there yet.
        kv.set(key, Integer.toString(chunks).getBytes(StandardCharsets.UTF_8));
    }

    public byte[] get(String key) {
        int chunks;
        try {
            chunks = Integer.parseInt(new String(kv.fetch(key), StandardCharsets.UTF_8));
        } catch (NoSuchElementException e) {
            return null; // the contract says missing is null, so the adapter translates
        }
        var out = new java.io.ByteArrayOutputStream();
        for (int i = 0; i < chunks; i++) out.writeBytes(kv.fetch(key + "#" + i));
        return out.toByteArray();
    }
}

class Contract {
    // One test suite, run against every implementation. A new BlobStore isn't done until it passes.
    static List<String> check(BlobStore store) {
        List<String> out = new ArrayList<>();
        out.add(attempt("round trip", () -> {
            store.put("a", "hello".getBytes());
            return Arrays.equals(store.get("a"), "hello".getBytes());
        }));
        out.add(attempt("5 KB value", () -> {
            byte[] big = new byte[5_000];
            Arrays.fill(big, (byte) 7);
            store.put("big", big);
            return Arrays.equals(store.get("big"), big);
        }));
        out.add(attempt("missing is null", () -> store.get("nope") == null));
        return out;
    }

    private static String attempt(String name, java.util.function.BooleanSupplier test) {
        try {
            return (test.getAsBoolean() ? "PASS " : "FAIL ") + name;
        } catch (RuntimeException e) {
            return "FAIL " + name + " (" + e.getClass().getSimpleName() + ")";
        }
    }
}

class Main {
    public static void main(String[] args) {
        System.out.println("InMemoryStore " + Contract.check(new InMemoryStore()));
        System.out.println("ChunkedStore  " + Contract.check(new ChunkedStore(new TinyKv())));
    }
}

What to notice

• A contract nobody wrote down can’t be checked. The three promises are now comments on the interface and, more importantly, tests. A new store isn’t done until Contract.check passes.
• One suite, every implementation. The same tests run against the in-memory store used in unit tests and the real one. That’s how teams catch “works locally, fails in production” before it ships.
• Not everything with the right methods should implement the interface. TinyKv has real limits. Instead of hiding them behind BlobStore, it shows them in its own API, where callers can see them.
• Adapters restore substitutability. ChunkedStore splits big values and turns “not found” into null. Writing the manifest last means a reader never sees a chunk count before the chunks exist.

Interviewer

Our tests use an in-memory fake of the database, and everything passes. In production, a read right after a write sometimes returns stale data. What went wrong in the design?

What they are testing

Whether you name it as a substitution failure: the fake promises read-after-write, and the replica-backed store doesn’t. Then whether you fix the contract, not the symptom. Decide whether the interface promises it. Run one contract suite against both. Route reads that need it to the primary. The red flag is “add a sleep”.

Common mistake

Fakes that are better than the real thing

An in-memory fake is always consistent, never slow, and never full. If the real implementation can’t promise the same, tests pass against a contract production doesn’t keep. Make the fake keep the same promises as the real one, or no stronger ones, and run the shared contract suite against both.

Hard

A rate limiter's counters

• Promises about time and threads
• Weakened postconditions
• Changing the contract so it can be kept

An API allows each user a few requests per minute. The rate limiter asks a CounterStore to count requests per user, and refuses once the count passes the limit. Memory grew with every user who ever called the API. So someone swapped in a bounded store, which keeps the most recently used keys and evicts the rest. Same interface. Every test still compiles. Memory is flat.

And the rate limit stops working. This level is about promises no type can express, about memory and threads, and about the fix being a change to the contract itself.

Without the principle

JMain.javaPyrate_limiter.pyC#BoundedCounterStore.csGorate_limiter.goTSrate-limiter.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicLong;

// The contract, including the parts no type can express:
//  - increment(key) returns how many times increment(key) has been called
//  - it never forgets a count
//  - it is safe to call from many threads at once
interface CounterStore {
    long increment(String key);
}

class ExactCounterStore implements CounterStore {
    private final Map<String, AtomicLong> counts = new ConcurrentHashMap<>();
    public long increment(String key) {
        return counts.computeIfAbsent(key, k -> new AtomicLong()).incrementAndGet();
    }
}

// Memory grew with every user, so someone swapped in a bounded version: it keeps the
// most recently used keys and evicts the rest. Same interface, every test still compiles.
// flaw: it weakens a postcondition. An evicted key starts again from zero, so "never
// forgets a count" is no longer true, and no caller was told.
class BoundedCounterStore implements CounterStore {
    private final Map<String, Long> counts;

    BoundedCounterStore(int capacity) {
        counts = new LinkedHashMap<>(16, 0.75f, true) {
            protected boolean removeEldestEntry(Map.Entry<String, Long> eldest) { return size() > capacity; }
        };
    }

    public synchronized long increment(String key) { return counts.merge(key, 1L, Long::sum); }
}

// Correct for any CounterStore that keeps the contract. It can't defend against one that doesn't.
class RateLimiter {
    private final CounterStore store;
    private final int limitPerMinute;

    RateLimiter(CounterStore store, int limitPerMinute) {
        this.store = store;
        this.limitPerMinute = limitPerMinute;
    }

    boolean allow(String user, long minute) { return store.increment(user + "@" + minute) <= limitPerMinute; }
}

class Main {
    static int mallorysRequestsAllowed(CounterStore store) {
        RateLimiter limiter = new RateLimiter(store, 3);
        int allowed = 0;
        // Three users take turns within one minute. With room for only two keys, each one is
        // evicted just before it is needed again, so every request looks like the first.
        for (int round = 0; round < 6; round++) {
            limiter.allow("alice", 0);
            limiter.allow("bob", 0);
            if (limiter.allow("mallory", 0)) allowed++;
        }
        return allowed;
    }

    public static void main(String[] args) {
        System.out.println("exact:   mallory allowed " + mallorysRequestsAllowed(new ExactCounterStore()) + " of 6");     // 3
        System.out.println("bounded: mallory allowed " + mallorysRequestsAllowed(new BoundedCounterStore(2)) + " of 6"); // 6
    }
}

The bounded store weakens a postcondition. “Returns how many times this key was counted” becomes “…unless it was evicted”. Say there’s room for two keys, and three users take turns. Each user is evicted just before their next request. Every request looks like the first, and mallory gets 6 requests through a limit of 3. At real scale, an attacker can do the same, by rotating through enough fake keys. They push their own count out of the cache, and the limit never applies.

Check each store against what the rate limiter relies on:

Plug a class into RateLimiter.allow(user, minute)ExactCounterStoreBoundedCounterStoreUnlockedCounterStoreWindowedCounterStore

1. ·counts every call
2. ·never forgets a count in the current minute
3. ·safe from many threads at once
4. ·memory stays bounded

The caller relies on each of these promises. Pick a class to check them.

With LSP

The real problem: the interface made a promise (“never forgets”) that a memory-bounded store can’t keep. So change the contract to one that can be kept and is still enough for the caller. A rate limiter only needs counts for the current window. Make the window part of the interface, promise never to forget the newest window, and allow older ones to be dropped.

Hard: a contract a bounded store can keep

Scroll or pinch to zoom, drag to pan

• Color key
• Facade
• Entity
• Value object
• Enum
• Interface
• Implementation

JContract.javaPyrate_limiter.pyC#WindowedCounterStore.csGorate_limiter.goTSrate-limiter.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

import java.util.HashMap;
import java.util.Map;

// The contract, now naming the time window so a bounded store can keep it:
//  - increment(key, window) returns how many times it has been called for that key and window
//  - counts for the newest window it has seen are never forgotten; older windows may be dropped
//  - it is safe to call from many threads at once
// A promise a store can't keep is a promise the interface shouldn't make. This one can be kept
// with bounded memory, because a rate limiter only ever needs the current window.
interface CounterStore {
    long increment(String key, long window);
}

// Bounded by design: when a newer window starts, all older counts are dropped together.
// Memory is one window's worth of users, and nothing the limiter still needs is forgotten.
class WindowedCounterStore implements CounterStore {
    private long current = Long.MIN_VALUE;
    private Map<String, Long> counts = new HashMap<>();

    // One lock keeps it simple and correct. A busier service would shard by key.
    public synchronized long increment(String key, long window) {
        if (window > current) {
            current = window;
            counts = new HashMap<>();
        }
        if (window < current) return Long.MAX_VALUE; // a late request for a closed window: never allow it
        return counts.merge(key, 1L, Long::sum);
    }

    synchronized int keysHeld() { return counts.size(); }
}

class RateLimiter {
    private final CounterStore store;
    private final int limitPerMinute;

    RateLimiter(CounterStore store, int limitPerMinute) {
        this.store = store;
        this.limitPerMinute = limitPerMinute;
    }

    boolean allow(String user, long minute) { return store.increment(user, minute) <= limitPerMinute; }
}

class Contract {
    // Run against every CounterStore. The thread test is part of the contract, not an extra.
    static String check(CounterStore store) throws InterruptedException {
        StringBuilder out = new StringBuilder();
        store.increment("k", 1);
        store.increment("k", 1);
        out.append(store.increment("k", 1) == 3 ? "PASS" : "FAIL").append(" counts every call; ");

        store.increment("first", 1);
        for (int i = 0; i < 10_000; i++) store.increment("user" + i, 1);
        out.append(store.increment("first", 1) == 2 ? "PASS" : "FAIL").append(" survives 10,000 other keys; ");

        Thread[] threads = new Thread[8];
        for (int t = 0; t < threads.length; t++) {
            threads[t] = new Thread(() -> { for (int i = 0; i < 1_000; i++) store.increment("hot", 1); });
            threads[t].start();
        }
        for (Thread t : threads) t.join();
        out.append(store.increment("hot", 1) == 8_001 ? "PASS" : "FAIL").append(" safe from 8 threads");
        return out.toString();
    }
}

class Main {
    public static void main(String[] args) throws InterruptedException {
        System.out.println(Contract.check(new WindowedCounterStore()));

        WindowedCounterStore store = new WindowedCounterStore();
        RateLimiter limiter = new RateLimiter(store, 3);
        int allowed = 0;
        for (int round = 0; round < 6; round++) {
            limiter.allow("alice", 0);
            limiter.allow("bob", 0);
            if (limiter.allow("mallory", 0)) allowed++;
        }
        System.out.println("mallory allowed " + allowed + " of 6"); // 3
        limiter.allow("alice", 1);                                    // a new minute starts
        System.out.println("keys held after minute 1 starts: " + store.keysHeld()); // 1
    }
}

What to notice

• The best promises are the ones every implementation can keep. “Never forget anything” forced a choice between unbounded memory and a broken limiter. “Never forget the current window” is all the caller needs, and a bounded store can keep it.
• Thread safety is part of the contract. Many threads call increment at once. A store without a lock compiles, passes single-threaded tests, and under load lets two requests read 4 and both write 5. The contract suite includes a test with 8 threads for exactly that reason.
• Late callers get a safe answer. A request stamped with a minute that has already ended gets “over the limit”, never a fresh count. Failing closed is part of the promise.
• An LRU cache is fine for a cache. Evicting is correct when the value can be recomputed, like a cached web page. It’s wrong for a counter, where the value is the history. Don’t put both behind one interface.
• Shared stores need the same promises. In production the counts live in Redis so every server sees them. Redis’s INCR is atomic and its keys can expire with the window, which is exactly this contract.

TradeoffDropping whole windows vs. an LRU limit

We gain

Memory is bounded by the number of users in one window, and nothing the limiter needs is ever forgotten. The behavior is easy to state and to test.

We give up

Memory isn’t capped by a fixed number. A burst of a million users in one minute still means a million entries. If that matters, the answer is a different limiter design: sharding, or an approximate counter like a count-min sketch, with documented error. It’s not a store that quietly forgets.

Interviewer

We moved the rate limiter’s counts into an LRU cache to save memory. Now some users get far more requests through than the limit. Why?

What they are testing

Whether you trace it to the contract: the limiter assumed counts are never forgotten, and the cache forgets them. Then whether you can redesign: counts per time window, drop whole windows when they end, and note that an attacker can force evictions. Saying “make the cache bigger” is the red flag.

Say this out loud

The limiter only needs counts for the current minute, so that’s what the interface promises. The store drops old minutes as they end, which keeps memory bounded without breaking the limit.

Tradeoffs

TradeoffA strict, written contract vs. a loose interface

We gain

Any implementation that passes the contract suite can be swapped in with confidence: in tests, in production, or by another team. Bugs show up in the new class’s tests, not as crashes in old code.

We give up

Writing and maintaining the contract and its tests takes time. Strict contracts rule out some cheap implementations. Every promise you add is one every future implementation must keep, so promise only what callers need.

Be strict about substitution when:

• More than one implementation exists, or will: fakes in tests count.
• Implementations are written by other teams, partners or open-source contributors.
• The interface hides something with real-world limits: storage, networks, clocks, money.

Be relaxed when one class has one subclass inside one module, and both are changed together. And when a hierarchy keeps needing exceptions, consider dropping inheritance altogether: a sealed set of types with a switch makes every case visible.

Commonly taught wrong

Common mistake

LSP is about Rectangle and Square

The usual lesson says Square can’t extend Rectangle because setting a square’s width changes its height. That is true only for mutable shapes, where Rectangle promises that setWidth leaves the height alone. An immutable Square is a perfectly good Rectangle: it keeps every promise an immutable rectangle makes. The lesson is about promises and mutability, not geometry, and most real violations look nothing like it.

Common mistake

If it compiles, it substitutes

The compiler checks names and types. It can’t check that add stores something, that a read sees the last write, or that a method is safe on many threads. Those are the promises callers rely on most, and the only way to check them is a test written from the caller’s side.

Common mistake

Fix it with instanceof in the caller

if (tags instanceof FrozenTags) skip makes the crash go away, and spreads the problem. Every caller now has to know every subtype. That’s the opposite of what the type was for. Fix the hierarchy, so the caller can trust the type again.

Commonly confused with

Idea	Looks like LSP because	The difference
Type checking	Both decide what can be passed where	The type checker checks signatures. LSP is about behavior the checker can’t see.
Interface segregation	Both split interfaces	ISP splits so callers depend on less. LSP splits so implementers can keep what they claim. The tag example does both.
Design by contract	Both talk about preconditions and postconditions	Design by contract (Meyer, Eiffel) is how you write the promises down. LSP is the rule for subtypes: keep them.
Covariance and contravariance	Both decide which subtypes are allowed	Those are the signature rules (wider parameters, narrower returns). LSP includes them and adds the behavioral ones.

Where it shows up

On this site:

• LRU cache: every EvictionPolicy must keep the cache’s capacity promise, whichever entry it chooses.
• Rate limiter: every Bucket, token bucket or fixed window, must keep the same promise: never let more than the limit through.
• Parking lot: every PricingPolicy must return a fee for any ticket, never throw “not supported” for a vehicle type.

In real systems, you’ll see LSP problems in JDBC drivers that each read the spec slightly differently, and in collection libraries with “optional” operations. Also in ORMs whose in-memory test mode behaves differently from the real database, and in cloud services sold as “S3-compatible”.

Interview questions

Interviewer asksHow do you know whether a subclass is a safe substitute?

Write down what callers rely on: inputs accepted, results guaranteed, failures, thread safety. Turn that into tests against the parent type and run them against every subclass. If a subclass needs a stricter input, gives a weaker guarantee or throws something new, it isn’t a substitute.

Interviewer asksA subclass can't support one of the parent's methods. What do you do?

Don’t make it throw. Split the interface so the capability is separate (ReadableTags and EditableTags), and have the subclass implement only what it can. Callers that need the capability ask for that interface, and the compiler stops the wrong class being passed.

Interviewer asksCan a subtype ever throw an exception the parent doesn't?

Only one the parent’s contract already allows, or a subtype of it. A FileStore can throw IOException if Store.save is declared to throw it. A brand-new failure, like “not supported” or “too large”, is one no caller is prepared for.

Interviewer asksIs Square a subtype of Rectangle?

It depends on what Rectangle promises. If rectangles are mutable and setWidth promises not to touch the height, no: a square must break that. If rectangles are immutable values, yes. The answer comes from the contract, not the geometry.

Mid-level covers

Spots a subclass that throws “not supported”, or ignores a call. Refuses to fix it with instanceof. Splits the interface, so each class claims only what it can do. States the promises a caller relies on.

Senior adds

Also writes the contract down, and enforces it with one shared test suite. Catches weakened guarantees about consistency, memory and threads. Changes the contract when no reasonable implementation can keep it. Makes test fakes promise no more than production does.

Recap

Decision	We chose	We gave up
What a type means	Its written promises, not only its signatures	Interfaces you can implement without reading anything
A class that can’t keep a promise	Don’t claim the type; split the interface or adapt the class	One interface for everything with similar methods
How substitution is enforced	One contract test suite run against every implementation	Time spent writing tests for “obvious” behavior
A promise nobody can keep cheaply	Change the contract to what callers need	A stronger guarantee nobody can afford
Test fakes	No stronger than the real implementation	Fakes that are simpler than the real thing

Further reading

• Open/closed, which depends on substitution to be safe
• Interface segregation, the usual fix for subtypes that can’t keep every promise
• Rate limiter, for the full design behind the hard example
• Barbara Liskov and Jeannette Wing, A Behavioral Notion of Subtyping (1994)
• Barbara Liskov, Data Abstraction and Hierarchy, OOPSLA keynote (1987)