Consistent, disk-backed arrays

• US 10,067,674 B2
• Filed: 08/10/2016
• Issued: 09/04/2018
• Est. Priority Date: 01/16/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Kirazci, Ulas, Banachowski, Scott
• Primary Examiner(s): Tsai, Sheng-Jen
• Application Number:
  US15/233,021
• Publication Number:
  US 20160350001A1
• Time in Patent Office: 755 Days
• Field of Search: 711103
• CPC Class Codes: G06F 11/1004 to protect a block of data words, e.g. CRC or checksum G06F11/1076 takes precedence; security arrangements for protecting computers or computer systems against unauthorized activity G06F21/00
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/0647 Migration mechanisms
• CPC Class Codes: G06F 3/0673 Single storage device

Abstract

Disk-backed array techniques can, in some implementations, help ensure that the arrays contain consistent data. An alert can be provided if it is determined that the data in the array is, or may be, corrupted.

Claims

1. A method of managing changes to an array in non-volatile storage, the method comprising:

storing, in volatile memory of a computing device, the array that is stored in the non-volatile storage;

storing, in the volatile memory of the computing device, information indicative of changes to be made to a portion of the array;

computing a first cyclic redundancy check (CRC) value for the array before the changes are made to the portion of the array;

computing a second CRC value for the portion of the array before the changes are made to the portion of the array;

in response to storing, in the volatile memory of the computing device, the information indicative of the changes to be made to the portion of the array;

computing a third CRC value for the portion of the array with the changes having been made to the portion of the array; and

computing a fourth CRC value for the array with the changes having been made to the portion of the array, based on;

(i) the first CRC value for the array before the changes are made to the portion of the array,

(ii) the second CRC value for the portion of the array before the changes are made to the portion of the array, and

(iii) the third CRC value for the portion of the array with the changes having been made to the portion of the array,

carrying over to the portion of the array in the non-volatile storage the changes indicated by the information stored in the volatile memory;

storing, in the non-volatile storage, the fourth CRC value that was generated based on the first CRC value, the second CRC value, and the third CRC value;

detecting, by the computing device, a power interruption;

in response to detecting the power interruption;

computing a fifth CRC value based on the portion of the array in the non-volatile storage; and

comparing the fourth CRC value that was generated based on the first CRC value, the second CRC value, and the third CRC value to the fifth CRC value; and

based on determining the fourth CRC value matches the fifth CRC value, determining that the array in the non-volatile storage is valid.

2. The method of claim 1 including repeatedly calling a function to write data buffered in the volatile memory to the non-volatile storage so as to synchronize the non-volatile storage with the volatile memory.

3. The method of claim 1 wherein computing the fourth CRC value and storing the fourth CRC value in the non-volatile storage is performed in response to a user request.

4. The method of claim 1 wherein storing information indicative of changes to be made to the portion of the array in volatile memory includes making changes to a bitmap in the volatile memory, but not changing the array in non-volatile storage.

5. The method of claim 4 wherein the bitmap represents portions of an underlying file of the array in the non-volatile storage that are to be modified.

18. The method of claim 1, comprising:

storing, in the volatile memory of the computing device, (i) the first CRC value for the array before the changes are made to the portion of the array, (ii) the second CRC value for the portion of the array before the changes are made to the portion of the array, and (iii) the third CRC value for the portion of the array with the changes having been made to the portion of the array.

6. A method of managing changes to an array in non-volatile storage of a computing device, the method comprising:

storing, in random access memory of the computing device, the array that is stored in the non-volatile storage;

storing, in the random access memory of the computing device, information indicative of changes to be made to a portion of the array;

computing a first cyclic redundancy check (CRC) value for the array before the changes are made to the portion of the array;

computing a second CRC value for the portion of the array before the changes are made to the portion of the array;

in response to storing, in the random access memory of the computing device, the information indicative of the changes to be made to the portion of the array;

computing a third CRC value for the portion of the array with the changes having been made to the portion of the array; and

computing a fourth CRC value for the array with the changes having been made to the portion of the array, based on;

(i) the first CRC value for the array before the changes are made to the portion of the array,

(ii) the second CRC value for the portion of the array before the changes are made to the portion of the array, and

(iii) the third CRC value for the portion of the array with the changes having been made to the portion of the array

storing, in the non-volatile storage, the fourth CRC value that was generated based on the first CRC value, the second CRC value, and the third CRC value;

receiving a request in the computing device to carry over to the portion of the array in the non-volatile storage the changes indicated by the information stored in the random access memory;

detecting, by the computing device, a power interruption;

in response to detecting the power interruption;

computing a fifth CRC value based on the portion of the array in the non-volatile storage; and

comparing the fourth CRC value that was generated based on the first CRC value, the second CRC value, and the third CRC value to the fifth CRC value; and

determining, based on determining that the fourth CRC value does not match the fifth CRC value, that data in the array in the non-volatile storage is likely corrupted.

7. The method of claim 6 further including providing an alert to indicate that the data in the array is likely corrupted.

8. The method of claim 7 wherein providing an alert includes providing a message in the computing device indicating the presence of likely corrupted data in the array in the non-volatile storage.

9. The method of claim 6 including repeatedly calling a function to write data buffered in the random access volatile memory to the non-volatile storage so as to synchronize the non-volatile storage with the volatile memory.

10. A computing device comprising:

a non-transitory machine-readable medium storing instructions;

a processor operable to execute the instructions;

non-volatile storage storing an array; and

volatile memory,

wherein the processor is configured to execute the following operations based on the instructions;

store, in the volatile memory of a computing device, the array that is stored in the non-volatile storage;

store, in the volatile memory, information indicative of changes to be made to a portion of the array;

compute a first cyclic redundancy check (CRC) value for the array before the changes are made to the portion of the array;

compute a second CRC value for the portion of the array before the changes are made to the portion of the array;

in response to storing, in the volatile memory, the information indicative of the changes to be made to the portion of the array;

compute a third CRC value for the portion of the array with the changes having been made to the portion of the array;

compute a fourth CRC value for the array with the changes having been made to the portion of the array, based on;

(i) the first CRC value for the array before the changes are made to the portion of the array,

(ii) the second CRC value for the portion of the array before the changes are made to the portion of the array, and

(iii) the third CRC value for the portion of the array with the changes having been made to the portion of the array,

carry over to the portion of the array in the non-volatile storage the changes indicated by the information stored in the volatile memory;

store, in the non-volatile storage, the fourth CRC value that was generated based on the first CRC value, the second CRC value, and the third CRC value;

detect, by the computing device, a power interruption;

in response to detecting the power interruption;

compute a fifth CRC value based on the portion of the array in the non-volatile storage; and

compare the fourth CRC value that was generated based on the first CRC value, the second CRC value, and the third CRC value to the fifth CRC value; and

based on comparing the fourth CRC value to the fifth CRC value, determine that the array in the non-volatile storage is valid or likely corrupted.

11. The computing device of claim 10 wherein the volatile memory is composed of random access memory.

12. The computing device of claim 10 wherein the non-volatile storage is composed of disk storage.

13. The computing device of claim 10 wherein the non-volatile storage is composed of flash memory.

14. The computing device of claim 10 wherein the processor computes the fourth CRC value and stores the fourth CRC value in the non-volatile storage in response to user request.

15. The computing device of claim 10 wherein the operation by the processor of storing information indicative of changes to be made to the portion of the array in volatile memory includes making changes to a bitmap in the volatile memory, but not changing the array in non-volatile storage.

16. The computing device of claim 10 wherein the bitmap represents portions of an underlying file of the array in the non-volatile storage that are to be modified.

17. The computing device of claim 10 wherein the processor is operable to cause a user-recognizable alert to be provided to indicate that the data in the array is likely corrupted.