At a stream management service, one or more storage servers of a first repository are assigned to store at least a first partition of a first data stream. At the first repository, records of different partitions are interleaved. In response to determining that a set of data records of the first partition meet a first criterion, a rearranged version of the set in which the data records of the first partition are contiguous is stored at a second repository. Using the rearranged version, one or more records of the first partition are provided to an application which meets a lag criterion.