Rotating a 10^9-entry memory-mapped log by k: is an O(1)-space in-place rotation the right call?

## Start by attacking the requirement "Rotate the log by k" is almost never a requirement in itself. It is usually a consequence of something else: a retention window moved, a shard's start boundary shifted, a consumer that wants to begin reading at a different entry. So the first question is who observes the rotation. If the answer is "our own readers", there is a rotation that costs nothing: store a base offset alongside the data and map a logical index `i` to the physical index `(i + base) mod n`. Rotating by k becomes `base = (base + k) mod n` — a single write of one integer, O(1) time, O(1) space, no data moved, no pages touched, and atomic by construction. On 10^9 entries this is not an optimisation, it is a different order of magnitude of cost. A senior candidate reaches for the three-reversal trick; a lead asks whether any bytes need to move. The indirection is not free forever: every reader now pays a modulo on access, sequential scans wrap once in the middle, and the offset becomes a piece of state that has to be replicated, versioned and reasoned about at recovery. Those are real costs, and they are the reason someone will eventually want the physical order normalised anyway — but on a schedule you choose, not in the middle of an incident. ## When bytes genuinely must move Physical rotation earns its keep when the raw byte order is the contract: an external consumer memory-maps the file and reads it front to back without knowing about your offset, a checksum or index is computed over the physical layout, or the file is handed to a system you do not control. Then the choice is between two real strategies. | | in-place (three reversals) | copy rotated, then rename | |---|---|---| | extra space | O(1) | a second full copy of the file | | passes over data | three, all sequential | one sequential read plus one write | | pages dirtied | every page, twice | every page of the new file once | | crash behaviour | file left in a partial state | old file intact until the rename | | retry | needs a persisted phase marker | just start over | | readers during the work | see torn, inconsistent order | see the old order until the swap | The in-place route's O(1) extra space is a genuine advantage only when storage headroom or resident memory is the binding constraint — a fleet where nodes are provisioned near capacity, or a device where a second copy of the file simply does not fit. That constraint is real and common enough to be the reason the technique is worth knowing. What it costs is everything in the bottom half of that table. Rewriting every entry of a memory-mapped 10^9-element region dirties every page, and the resulting writeback pressure competes with whatever else the node is serving; p99 latency for unrelated work moves while the rotation runs. Worse, there is no moment at which the file is consistent: a crash between the second and third reversal leaves data that matches neither the old layout nor the new one, and nothing in the file says which phase was reached. The copy-and-rename route buys atomicity from the filesystem for the price of storage. ## Making the in-place route survivable If headroom forces in place, do not ship the bare three lines. Persist a small durable header recording k and which of the three reversals has completed, updating it between phases; on restart, resume from the recorded phase. This works because each phase is a whole range reversal with known boundaries — but note that a crash *inside* a phase leaves that range partially reversed, so either the phase marker must be finer-grained or the restart must be able to re-derive the range's state. That awkwardness is itself an argument: the recovery design costs more engineering than the copy would have cost in disk. Also resist the temptation to reach for the cleverest rotation available. A cycle-based rotation performs half the writes, but its correctness rests on a cycle-counting argument, and this is code someone will read at three in the morning while the log is half-rotated. Three calls to a reversal primitive is what you want in a runbook. ## How to present the decision Frame it as failure modes, not cleverness. "In place if storage headroom is the constraint we cannot move and we accept building resume logic; copy-and-rename if we want the rotation to be atomic and retryable and we can afford the second copy; neither if we can push the rotation into an offset and touch no bytes at all." Then say which one you would pick given the constraint that actually binds today, and what measurement would change your mind — free storage on the tightest node, the writeback impact on p99 during a rehearsal, and how often this rotation is expected to happen at all. A rotation performed once a year and a rotation performed hourly deserve different answers.