Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for merging media stream indexes of a media stream are described in this specification. In one aspect, a method includes receiving a first media stream index at a first server system, including a first list of sequentially arranged fragment identifiers corresponding to at least a portion of multiple sequentially arranged fragments. Fragment identifiers that are potentially missing from the first index can be identified. A second media stream index including a second list of sequentially arranged fragment identifiers corresponding to at least a portion of the multiple sequentially arranged fragments can be requested from a second server system. The first and second list of the sequentially arranged fragment identifiers can be compared and the first list of sequentially arranged fragment identifiers can be reconstructed based on the comparison.