Syllabus Lesson 44 of 141 · Delete the problem
Delete the problem

Remove a component: the index you already have

Why it matters "Build an index" is the standard answer to "make lookups fast". It is a good answer when the data has no useful order. When the data already has one, the index is a second copy of a fact you were given for free.

You are writing the read path of a message queue partition, the part a consumer calls to fetch messages from where it left off. Messages are stored in the order they arrived and each has an offset. Offsets are consecutive: each message's offset is one more than the previous one. Retention deletes old messages from the front, so the log starts at first_offset, not at 0.

The log sits on disk; every message read is a disk read. Consumers call read constantly.

log = Tape([(1000, "order.created"), (1001, "order.paid"), ...])
p = Partition(log, first_offset=1000)
p.read(1001, 2)   # -> [(1001, "order.paid"), (1002, ...)]
p.read(999, 5)    # -> []   (deleted by retention)
Your turn

Write a class Partition(log, first_offset). log is a Tape of (offset, payload) pairs with consecutive offsets starting at first_offset. read(offset, max_count) returns a list of up to max_count messages starting at offset, or [] if that offset is not in the log. Budget: with 300,000 messages, building the partition and serving 1,000 reads may read at most the number of messages returned plus 40,000. len(log) is free.

Spotted a problem in this lesson? Report it · Ask about this lesson

This exercise opens soon

Finish the lesson before it and this one unlocks. The whole course is free, no account needed, and you can read this lesson right now.

Start at lesson 1 Back to syllabus