Virtual Block Devices

• US 20130262405A1
• Filed: 03/14/2013
• Published: 10/03/2013
• Est. Priority Date: 03/27/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Kadatch, Andrew, Khorun, Sergey
• Granted Patent: US 9,069,806 B2
• Time in Patent Office: Days
• US Class Current: 707/692
• CPC Class Codes: G06F 16/13 File access structures, e.g. distributed indices arrangements of input from, or output to, record carriers G06F3/06
• CPC Class Codes: G06F 16/1727 Details of free space management performed by the file system saving storage space on storage systems G06F3/0608; management of blocks in storage devices G06F3/064
• CPC Class Codes: G06F 16/188 Virtual file systems
• CPC Class Codes: G06F 16/215 Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 2009/4557 Distribution of virtual machine instances; Migration and load balancing
• CPC Class Codes: G06F 9/45558 Hypervisor-specific management and integration aspects
• CPC Class Codes: G06F 9/5072 Grid computing

Abstract

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for virtual block storage. In one aspect, a method includes receiving a request to initialize a virtual machine, the virtual machine having an associated virtual block device; accessing a file map comprising a plurality of file map entries; determining file map entries corresponding to blocks of data allocated to the virtual block device and one or more files in which the blocks of data allocated to the virtual block device are stored; determining that a particular one of the blocks allocated to the virtual block device has been written to a new position not associated with the particular block in the file map; and updating the position associated with the particular block to the new position.

Claims

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 virtual block device;

accessing a file map comprising a plurality of file map entries, each file map entry associating a respective block of data with a respective position within a respective data file to which the block of data was written, wherein each of the plurality of blocks of data is stored in the respective data file in association with metadata that identifies the block of data and a respective sequence number for a write request that resulted in the block being written to the position;

determining file map entries corresponding to blocks of data allocated to the virtual block device and one or more files in which the blocks of data allocated to the virtual block device are stored;

determining that a particular one of the blocks allocated to the virtual block device has been written to a new position not associated with the particular block in the file map, comprising;

scanning one or more positions within the one or more files to determine that the particular block was written to the new position, the new position not being associated with the particular block in the file map, and

determining, from a sequence number stored in association with the particular block at the new position, that the particular block was written to the new position subsequent to being written to the position indicated by the file map; and

updating the position associated with the particular block to the new position.

2. The method of claim 1, wherein updating the position associated with the particular block to the new position comprises:

generating a new file map entry, the new file map entry associating the particular block of data with the new position; and

updating the file map with the new file map entry.

3. The method of claim 1, further comprising:

receiving a first request from the virtual machine to write a first block of data to the virtual block device;

associating metadata with the first block of data, the metadata identifying the first block of data and a sequence number for the first request;

submitting a request to a file system to write the block of data and the metadata to a first position within a first file; and

generating a first file map entry, the first file map entry associating the first block of data with the first position within the first file.

4. The method of claim 3, further comprising:

receiving a request from the virtual machine to read the first block of data from the virtual block device;

determining, from the first file map entry, that the first block of data was written to the first position within the first file; and

submitting a request to the file system to read the first block of data from the first position within the first file.

5. The method of claim 3, further comprising:

storing the first file map entry in a local memory.

6. The method of claim 5, further comprising:

determining that a predetermined period of time has elapsed subsequent to a previous update of the file map; and

updating the file map with the first file map entry.

7. The method of claim 5, further comprising

determining that a number of file map entries generated subsequent to a previous update of the file map exceeds a predetermined number;

and

updating the first file map with the first file map entry.

8. The method of claim 1, wherein the sequence number assigned to each request to write a block of data to the virtual block device is greater than any sequence number assigned to any previous request to write the block of data to the virtual block device.

9. The method of claim 8, wherein determining, from the sequence number stored in association with the particular block at the new position, that the particular block was written to the new position subsequent to being written to the position indicated by the file map comprises:

determining that the sequence number associated with the particular block at the new position is greater than the sequence number associated with the particular block at the position indicated by the file map.

10. The method of claim 1, wherein scanning the one or more positions in the one or more files to determine that the particular block was written to the new position comprises:

determining that a size of a particular file exceeds a size indicated by metadata associated with the file map for the particular file; and

scanning a tail of the particular file to identify blocks allocated to the virtual block device stored in the tail, wherein the tail of the particular file is the portion of the particular file that exceeds the size indicated by the metadata.

11. The method of claim 1, wherein scanning the one or more positions in the one or more files to determine that the particular block was written to the new position comprises:

scanning one or more positions in the particular file not associated with any block of data in the file map, the one or more positions including the new position; and

determining that the particular block of data is stored at the new position in the particular file.

12. The method of claim 1, further comprising:

determining that a size of a particular file exceeds a threshold size; and

refraining from writing any blocks of data to the particular file.

13. The method of claim 12, further comprising:

determining, from the sequence numbers associated with blocks of data stored in the particular file, that each of the blocks of data stored in the particular file has been subsequently written to a respective different file; and

marking the particular file for deletion.

14. A storage medium encoded with instructions which, when executed by data processing apparatus, cause the data processing apparatus to perform operations comprising:

receiving a request to initialize a virtual machine, the virtual machine having an associated virtual block device;

accessing a file map comprising a plurality of file map entries, each file map entry associating a respective block of data with a respective position within a respective data file to which the block of data was written, wherein each of the plurality of blocks of data is stored in the respective data file in association with metadata that identifies the block of data and a respective sequence number for a write request that resulted in the block being written to the position;

determining file map entries corresponding to blocks of data allocated to the virtual block device and one or more files in which the blocks of data allocated to the virtual block device are stored;

determining that a particular one of the blocks allocated to the virtual block device has been written to a new position not associated with the particular block in the file map, comprising;

scanning one or more positions within the one or more files to determine that the particular block was written to the new position, the new position not being associated with the particular block in the file map, and

determining, from a sequence number stored in association with the particular block at the new position, that the particular block was written to the new position subsequent to being written to the position indicated by the file map; and

updating the position associated with the particular block to the new position.

15. The storage medium of claim 14, wherein updating the position associated with the particular block to the new position comprises:

generating a new file map entry, the new file map entry associating the particular block of data with the new position; and

updating the file map with the new file map entry.

16. The storage medium of claim 14, the operations further comprising:

receiving a first request from the virtual machine to write a first block of data to the virtual block device;

associating metadata with the first block of data, the metadata identifying the first block of data and a sequence number for the first request;

submitting a request to a file system to write the block of data and the metadata to a first position within a first file; and

generating a first file map entry, the first file map entry associating the first block of data with the first position within the first file.

17. The storage medium of claim 16, the operations further comprising:

receiving a request from the virtual machine to read the first block of data from the virtual block device;

determining, from the first file map entry, that the first block of data was written to the first position within the first file; and

submitting a request to the file system to read the first block of data from the first position within the first file.

18. The storage medium of claim 16, the operations further comprising:

storing the first file map entry in a local memory.

19. The storage medium of claim 18, the operations further comprising:

determining that a predetermined period of time has elapsed subsequent to a previous update of the file map; and

updating the file map with the first file map entry.

20. The storage medium of claim 18, the operations further comprising

determining that a number of file map entries generated subsequent to a previous update of the file map exceeds a predetermined number;

and

updating the first file map with the first file map entry.

21. The storage medium of claim 14, wherein the sequence number assigned to each request to write a block of data to the virtual block device is greater than any sequence number assigned to any previous request to write the block of data to the virtual block device.

22. The storage medium of claim 21, wherein determining, from the sequence number stored in association with the particular block at the new position, that the particular block was written to the new position subsequent to being written to the position indicated by the file map comprises:

determining that the sequence number associated with the particular block at the new position is greater than the sequence number associated with the particular block at the position indicated by the file map.

23. The storage medium of claim 14, wherein scanning the one or more positions in the one or more files to determine that the particular block was written to the new position comprises:

determining that a size of a particular file exceeds a size indicated by metadata associated with the file map for the particular file; and

scanning a tail of the particular file to identify blocks allocated to the virtual block device stored in the tail, wherein the tail of the particular file is the portion of the particular file that exceeds the size indicated by the metadata.

24. The storage medium of claim 14, wherein scanning the one or more positions in the one or more files to determine that the particular block was written to the new position comprises:

scanning one or more positions in the particular file not associated with any block of data in the file map, the one or more positions including the new position; and

determining that the particular block of data is stored at the new position in the particular file.

25. The storage medium of claim 14, the operations further comprising:

determining that a size of a particular file exceeds a threshold size; and

refraining from writing any blocks of data to the particular file.

26. The storage medium of claim 25, the operations further comprising:

determining, from the sequence numbers associated with blocks of data stored in the particular file, that each of the blocks of data stored in the particular file has been subsequently written to a respective different file; and

marking the particular file for deletion.

27. A system comprising:

a storage medium encoded with instructions;

data processing apparatus operable to execute the instructions to perform operations comprising;

receiving a request to initialize a virtual machine, the virtual machine having an associated virtual block device;

accessing a file map comprising a plurality of file map entries, each file map entry associating a respective block of data with a respective position within a respective data file to which the block of data was written, wherein each of the plurality of blocks of data is stored in the respective data file in association with metadata that identifies the block of data and a respective sequence number for a write request that resulted in the block being written to the position;

determining file map entries corresponding to blocks of data allocated to the virtual block device and one or more files in which the blocks of data allocated to the virtual block device are stored;

determining that a particular one of the blocks allocated to the virtual block device has been written to a new position not associated with the particular block in the file map, comprising;

scanning one or more positions within the one or more files to determine that the particular block was written to the new position, the new position not being associated with the particular block in the file map, and

determining, from a sequence number stored in association with the particular block at the new position, that the particular block was written to the new position subsequent to being written to the position indicated by the file map; and

updating the position associated with the particular block to the new position.

28. The system of claim 27, wherein updating the position associated with the particular block to the new position comprises:

generating a new file map entry, the new file map entry associating the particular block of data with the new position; and

updating the file map with the new file map entry.

29. The system of claim 27, the operations further comprising:

receiving a first request from the virtual machine to write a first block of data to the virtual block device;

associating metadata with the first block of data, the metadata identifying the first block of data and a sequence number for the first request;

submitting a request to a file system to write the block of data and the metadata to a first position within a first file; and

generating a first file map entry, the first file map entry associating the first block of data with the first position within the first file.

30. The system of claim 29, the operations further comprising:

receiving a request from the virtual machine to read the first block of data from the virtual block device;

determining, from the first file map entry, that the first block of data was written to the first position within the first file; and

submitting a request to the file system to read the first block of data from the first position within the first file.

31. The system of claim 29, the operations further comprising:

storing the first file map entry in a local memory.

32. The system of claim 31, the operations further comprising:

determining that a predetermined period of time has elapsed subsequent to a previous update of the file map; and

updating the file map with the first file map entry.

33. The system of claim 31, the operations further comprising

determining that a number of file map entries generated subsequent to a previous update of the file map exceeds a predetermined number;

and

updating the first file map with the first file map entry.

34. The system of claim 27, wherein the sequence number assigned to each request to write a block of data to the virtual block device is greater than any sequence number assigned to any previous request to write the block of data to the virtual block device.

35. The system of claim 34, wherein determining, from the sequence number stored in association with the particular block at the new position, that the particular block was written to the new position subsequent to being written to the position indicated by the file map comprises:

determining that the sequence number associated with the particular block at the new position is greater than the sequence number associated with the particular block at the position indicated by the file map.

36. The system of claim 27, wherein scanning the one or more positions in the one or more files to determine that the particular block was written to the new position comprises:

determining that a size of a particular file exceeds a size indicated by metadata associated with the file map for the particular file; and

scanning a tail of the particular file to identify blocks allocated to the virtual block device stored in the tail, wherein the tail of the particular file is the portion of the particular file that exceeds the size indicated by the metadata.

37. The system of claim 27, wherein scanning the one or more positions in the one or more files to determine that the particular block was written to the new position comprises:

scanning one or more positions in the particular file not associated with any block of data in the file map, the one or more positions including the new position; and

determining that the particular block of data is stored at the new position in the particular file.

38. The system of claim 27, the operations further comprising:

determining that a size of a particular file exceeds a threshold size; and

refraining from writing any blocks of data to the particular file.

39. The system of claim 38, the operations further comprising:

determining, from the sequence numbers associated with blocks of data stored in the particular file, that each of the blocks of data stored in the particular file has been subsequently written to a respective different file; and

marking the particular file for deletion.