Consistent, disk-backed arrays

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

storing, in volatile memory, a memory mapping of an array that is in non-volatile storage;

modifying one or more sections of the array as stored in the volatile memory;

determining that modifications to the array as stored in the volatile memory are to be carried over to the non-volatile memory;

in response to determining that modifications to the array as stored in the volatile memory are to be carried over to the non-volatile memory, computing a cyclic redundancy check (CRC) value for the entire array as modified and as stored in volatile memory;

storing, in the volatile memory, (i) original, unmodified values of the array corresponding to the modified sections, (ii) the one or more modified sections of the array, and (iii) the CRC value;

after storing the one or more modified sections of the array and the CRC value in the volatile storage, storing, in the non-volatile storage, the array as modified and the CRC value;

computing a new CRC value for the entire array as stored in the non-volatile storage;

comparing the new CRC value to the CRC value previously stored in the non-volatile storage; and

determining whether data in the array in the non-volatile storage is corrupted based on the comparison of the new CRC value to the CRC value previously stored in the non-volatile storage.

2. The method of claim 1 wherein computing a CRC value for the entire array as modified includes updating the CRC value incrementally.

3. The method of claim 2 wherein updating the CRC value incrementally is based, at least in part, on using the original, unmodified values of the array stored in the volatile memory.

4. The method of claim 3 wherein the original, unmodified values of the array are maintained in the volatile memory only up to a predetermined constant fraction of the array size, and wherein the CRC value is updated incrementally only if a changed area of the array is less than the predetermined constant fraction of the array size.

5. The method of claim 1 further including providing an alert to indicate that the data in the array written to the non-volatile memory is or may be corrupted.

6. The method of claim 5 wherein providing an alert includes providing a message indicating the presence of possibly corrupted data in the array in the non-volatile storage.

7. A computing device comprising:

a machine-readable medium storing instructions;

a processor operable to execute the instructions;

non-volatile storage storing a mutable array;

volatile memory;

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

store, in the volatile memory, a copy of the array that is in the non-volatile storage;

modify one or more sections of the array as stored in the volatile memory;

determine that modifications to the array as stored in the volatile memory are to be carried over to the non-volatile memory;

in response to determining that modifications to the array as stored in the volatile memory are to be carried over to the non-volatile memory, compute a cyclic redundancy check (CRC) value for the entire array as modified and as stored in volatile memory;

store, in the volatile memory, (i) original, unmodified values of the array that correspond to the modified sections, (ii) the one or more modified sections of the array, and (iii) the CRC value;

store, in the non-volatile storage, the array as modified and the CRC value after storing the one or more modified sections of the array and the CRC value in the volatile memory;

compute a new CRC value for the entire array as stored in the non-volatile storage;

compare the new CRC value to the CRC value previously stored in the non-volatile storage; and

determine whether data in the array in the non-volatile storage is corrupted based on the comparison of the new CRC value to the CRC value previously stored in the non-volatile storage.

8. The computing device of claim 7 wherein the processor computes a CRC value for the entire array as modified by updating the CRC value incrementally.

9. The computing device of claim 8 wherein the processor updates the CRC value incrementally based, at least in part, on using the original, unmodified values of the array stored in the volatile memory.

10. The computing device of claim 9 wherein the original, unmodified values of the array are maintained in the volatile memory only up to a predetermined constant fraction of the array size, and wherein the processor updates the CRC value incrementally only if a changed area of the array is less than the predetermined constant fraction of the array size.

11. A non-transitory computer-readable medium storing software comprising instructions executable by one or more computers which, upon such execution, cause the one or more computers to perform operations comprising:

storing, in volatile memory, a memory mapping of an array that is in non-volatile storage;

modifying one or more sections of the array as stored in the volatile memory;

determining that modifications to the array as stored in the volatile memory are to be carried over to the non-volatile memory;

in response to determining that modifications to the array as stored in the volatile memory are to be carried over to the non-volatile memory, computing a cyclic redundancy check (CRC) value for the entire array as modified;

storing, in the volatile memory, (i) original, unmodified values of the array that correspond to the modified sections, (ii) the one or more modified sections of the array, (iii) and the CRC value;

after storing the one or more modified sections of the array and the CRC value in the volatile memory, storing, in the non-volatile storage, the array as modified and the CRC value;

computing a new CRC value for the entire array as stored in the non-volatile storage;

comparing the new CRC value to the CRC value previously stored in the non-volatile storage; and

determining whether data in the array in the non-volatile storage is corrupted based on the comparison of the new CRC value to the CRC value previously stored in the non-volatile storage.

12. The medium of claim 11 , wherein computing a CRC value for the entire array as modified includes updating the CRC value incrementally.

13. The medium of claim 12 , wherein updating the CRC value incrementally is based, at least in part, on using the original, unmodified values of the array stored in the volatile memory.

14. The medium of claim 13 , wherein the original, unmodified values of the array are maintained in the volatile memory only up to a predetermined constant fraction of the array size, and wherein the CRC value is updated incrementally only if a changed area of the array is less than the predetermined constant fraction of the array size.

15. The medium of claim 11 , further including providing an alert to indicate that the data in the array written to the non-volatile memory is or may be corrupted.

16. The medium of claim 15 , wherein providing an alert includes providing a message indicating the presence of possibly corrupted data in the array in the non-volatile storage.