Data Temperature and the Cost of Cleaning Mixed Segments

A segment is a container for whatever happened to be written at the same time. That coincidence is not neutral. If a segment receives both data that will be rewritten within seconds and data that will never be rewritten, then by the time the hot half has died, the cold half is still live, and the collector cannot free the segment without copying the cold half to a new location. The copy frees space in proportion to the dead fraction but costs in proportion to the live fraction, and the ratio is what determines whether cleaning is worth doing at all.

Segregation is the defense: route writes to different segments according to how long the data is expected to live. The idea is simple and the implementation is not, because the filesystem must estimate a lifetime at write time, before it has any evidence about the data’s future.

The arithmetic of a mixed segment

Consider a segment holding two kinds of data in equal measure. Kind A is rewritten every few seconds; kind B is written once and never modified. At the moment the segment is created, both halves are live. After a minute, the A blocks have all been superseded, so the segment’s live fraction is 0.5 and all of it is B. Cleaning the segment writes 0.5·S bytes of B and frees 0.5·S bytes, a cost of one byte copied per byte freed. That is not catastrophic in isolation, but note what the copy achieves: it moves B into a new segment, where B is again surrounded by fresh data. If that new segment also mixes A and B, the cycle repeats, and B is copied once per cycle forever.

Now consider the segregated case. The A data occupies its own segments and the B data occupies its own. After a minute, the A segments are nearly fully dead, with a live fraction near zero, and cleaning them costs almost nothing per byte freed. The B segments are fully live, so the collector never selects them, because their score is terrible and there is always an A segment available. B is written once and never moved.

The difference in total write traffic is unbounded, not a constant factor. The mixed layout imposes a copy of the cold data on every cleaning cycle; the segregated layout imposes none. That is the sense in which placement matters more than selection policy: no scoring function can recover from a segment that contains data with incompatible lifetimes, because the information needed to clean it cheaply is not present in the segment.

Estimating lifetime at write time

The filesystem cannot know how long a block will live. It can, however, observe several things at the moment of the write that correlate strongly with lifetime.

The first is the object’s history. A block that is being rewritten for the tenth time belongs to a file that is being modified repeatedly, and the odds are good that it will be modified again. A block being written for the first time in a file that has been idle belongs to data with no demonstrated churn. An inode’s modification count and the file’s recent write rate are both available in memory and are the strongest single signal.

The second is the kind of object. Directory blocks and inode blocks for files in active directories are modified frequently; file data appended to a log file is modified once. The type of the block is known at write time from the caller, and routing inode and directory writes to one stream and file data to another captures a large part of the distinction with no estimation at all.

The third is the file’s size and access pattern. A file being written sequentially from beginning to end is likely to be written once and read later; a file being overwritten at scattered offsets is likely to be modified again. The filesystem sees the offsets, so it can classify on the shape of the access pattern rather than on any explicit hint.

/* Two-tier classifier: metadata is hot, sequential file data is cold,
 * everything else lands in the middle stream. */
static enum stream classify(struct inode *ip, uint64_t off, uint32_t len)
{
    if (ip->type != REG)
        return STREAM_META;                 /* inodes, dirs, indirect blocks */

    if (off >= ip->size && off - ip->size <= len)
        return STREAM_COLD;                 /* pure append: written once */

    if (ip->nwrites > HOT_THRESHOLD)
        return STREAM_HOT;                  /* repeatedly rewritten */
    return STREAM_WARM;
}

Each stream has its own partial segment, and the number of streams is deliberately small. More streams give finer segregation but waste more space at segment boundaries, since each open stream holds a partially filled segment that cannot be closed until it fills or times out. Three to five streams is the usual range; beyond that the slack cost exceeds the segregation benefit.

The problem with promotion and demotion

Classification at write time is a prediction, and predictions are wrong in both directions.

A block classified cold may turn out to be hot: a file appended once and then rewritten repeatedly. Its blocks sit in a cold segment that the collector declines to clean, and the file’s churn goes into that segment’s successors. The result is a cold segment that is actually half dead and that the collector never selects because its score is dominated by the genuinely cold blocks around it. The dead hot data is trapped.

A block classified hot may turn out to be cold: a file written in a burst and then never touched. Its blocks sit in a hot segment that the collector cleans almost immediately, and the copy moves the data into another hot segment, where it is copied again. This is the opposite failure and it is more expensive, because it costs a copy per cycle rather than merely delaying reclamation.

The remedy is to allow reclassification based on observed survival. A block that survives several cleaning cycles without being superseded is evidence of coldness, and the collector can route its copy to a colder stream than the one it came from. That is a promotion toward permanence, and it converges: each cycle, the surviving blocks move one tier colder, and the collector eventually stops touching them. The cost is a bounded number of copies, after which the data is effectively pinned.

Demotion, treating a cold-classified block as hot after it is rewritten, is harder, because the filesystem has already paid the cost of leaving it in a cold segment. It can be handled at the individual block level rather than at the segment level: when a cold-classified file is rewritten, the new blocks go to a hot stream and the old blocks in the cold segment are dead. The cold segment’s live fraction drops, and if enough of its contents are rewritten, it becomes a good candidate after all. So demotion is self-correcting as long as the collector’s scoring uses current liveness rather than classification, which is why the accounting in Segment Liveness Accounting must be exact.

Why the original design needed many streams

The insight in the original log-structured design was not merely that segregation helps but that the number of streams should be chosen to match the number of distinct lifetime classes in the workload, and that the classes are visible from the object type and the file’s recent behavior. The design used several streams, each with its own open segment, and the collector treated all segments uniformly once they were closed. Segregation happened entirely on the write path; the clean path needed no knowledge of temperature because the segments it saw were already homogeneous.

That division of responsibility is the load-bearing idea. The write path classifies, the clean path measures. If the classification is imperfect, the measurement catches it: a misclassified segment shows a live fraction that is neither near zero nor near one, and the collector handles it as an ordinary intermediate case. If the classification were absent, every segment would be an intermediate case, and the collector would have no good candidates at all.

The number of streams has a cost that is easy to underestimate. Each open stream holds a partially filled segment, and a partially filled segment is space that cannot be reclaimed and cannot be written to by another stream. With 1 MiB segments and four streams, up to 4 MiB is held in partial segments, which is trivial on a large volume and significant on a small one. The waste is bounded by the number of streams times the segment size, which is the reason small volumes use smaller segments rather than fewer streams.

Segments that cannot be segregated

Not all data can be routed. Some writes are inherently mixed: a large file’s metadata and its data are created by the same operation, and splitting them into different streams means the metadata is written far from the data it describes, which hurts the read path’s locality. A directory’s entries and its inode have the same problem.

The usual resolution is to accept that a small fraction of segments will be mixed and to make them small. If a mixed segment holds only a few hundred kilobytes, the cost of cleaning it is bounded by its size, and the collector can afford to clean it occasionally even at a mediocre live fraction. The alternative, placing metadata with the data it describes so that reads are sequential, is often the better trade, because read locality is a per-access benefit while the cleaning cost is amortized.

This is the same tension that appears in every log-structured design between placement for writing and placement for reading. The log’s order is the order of writes; a reader that follows a different order pays for it. Segregation by temperature optimizes for the collector, and the collector is not the reader.

The limit of the approach

Segregation reduces the cleaning cost when lifetimes are separable. It does nothing when the workload’s data genuinely has a single lifetime, whether a volume of immutable data or one of pure churn, because there is nothing to separate. And it can only be as good as the classifier’s information, which is derived from the past and applied to the future.

The deeper limit is that temperature is a property of the workload, not of the data, and workloads change. A file that was cold for a year can become hot when an application starts rewriting it, and the filesystem’s accumulated placement decisions are then wrong in a way it cannot undo without copying. The collector’s response is to notice the segment’s liveness dropping and clean it, which is correct but late. Systems that care about this case track temperature per file and reclassify on the write path rather than per block, so that a change in a file’s behavior moves all of its future writes at once.

The interference cost of all this activity, the collector competing with the foreground for the same device queue, is the remaining piece of the picture, taken up in Cleaner Interference and Foreground Latency.