1. A method performed by data processing apparatus, the method comprising: receiving a request to initialize a virtual machine, the virtual machine having an associated persistent virtual block device, wherein the persistent virtual block device is realized using a plurality of data files maintained by a file system and a persistent file map comprising a plurality of file map entries, each file map entry associating a respective block of the virtual block device with a respective position within a respective data file maintained by the file system to which the block was written, and wherein each of the blocks is written to the respective data file in association with metadata that identifies the block; and initializing the file map for use by the virtual machine, wherein initializing the file map for use by the virtual machine comprises determining whether the file map is up to date with respect to the file system for each of the blocks of the persistent virtual block device identified in the file map, comprising: determining that the file map indicates that a particular data file of the plurality of data files maintained by the file system has one or more unused positions that are not associated with any virtual blocks; scanning the one or more unused positions in the particular data file; identifying, from the scanning, that a new version of a particular block that is associated with an initial position in the file map has been written to a new position in the one or more unused positions of the particular data file; determining that the particular block was written to the new position subsequent to being written to the initial position indicated by the file map; and updating the position associated with the particular block in the file map to the new position.