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.

FIELD OF THE DISCLOSURE

The present disclosure relates to consistent disk-backed arrays.

BACKGROUND

An array is a data structure consisting of a collection of elements (values or variables), each of which is identified by at least one array index or key. Arrays are sometimes used to implement tables, such as look-up tables. Many software programs use arrays, which also can be used to implement other data structures, such as lists, strings and tries.

In general, it is desirable for an array to be persistent such that the data in the array remains valid even if power is removed from the device storing the array. For this reason, arrays often are stored on disk (e.g., flash memory). However, some arrays are mutable, such that the data structure can be updated, for example, to include additional elements. In such situations, the data in the array between transactions (e.g., between updates) may contain inconsistent states and, therefore, may contain errors.

SUMMARY

The present disclosure describes disk-backed array techniques that 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.

For example, one aspect describes a method of managing changes to an array in non-volatile storage of a computing device. The method includes storing, in random access or other volatile memory of the computing device, information indicative of changes to be made to the array. A pre-specified bit in the non-volatile storage that is associated with the array is set, for example, in response to a user request (e.g., after a batch of changes are made to the array). A request is received in the computing device to carry over to the non-volatile storage the changes indicated by the information stored in the random access or other volatile memory, and a request is received in the computing device to clear the pre-specified bit.

In some implementations, the method includes subsequently checking whether the pre-specified bit has been cleared, and determining, based on results of the checking, whether data in the array in the non-volatile storage is, or may be, corrupted. In some implementations, checking whether the pre-specified bit has been cleared and determining whether data in the array in the non-volatile storage is corrupted is performed after power is restored to the computing device following a power loss. In the event that it is determined that the data is or may be corrupted, an alert can be provided. For example, in some cases, providing an alert includes providing a message in the computing device indicating the presence of possibly corrupted data in the array in the non-volatile storage.

According to another aspect, a method of managing changes to an array in non-volatile storage includes storing, in volatile memory, a mapping of the array that is in non-volatile storage. Requested modifications are made to one or more sections of the array as stored in the volatile memory. Original, unmodified values of the array corresponding to the modified sections may be stored in the volatile memory as well. The method also includes computing a cyclic redundancy check (CRC) value for the entire array as modified, and writing the one or more modified sections of the array and the CRC value to the non-volatile storage.

Some implementations can include subsequently computing a new CRC value for the entire array as stored in the non-volatile storage and comparing the new CRC value to the CRC value previously written to the non-volatile storage. A determination can be made as to whether data in the array in the non-volatile storage is corrupted based on the comparison.

Various techniques can be used to compute a CRC value for the modified array stored in non-volatile memory. For example, the CRC value can be updated incrementally, rather than computing a new CRC for the entire modified array each time. Updating the CRC value incrementally can be based, at least in part, on using the original, unmodified values of the array stored in the volatile memory. In some implementations, 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 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.

The disclosure also describes computing devices, such as mobile phones and the like, that store a mutable array in non-volatile memory and which can be managed using the foregoing techniques.

Performing various processing tasks on data stored in the volatile memory can increase overall processing speed for updating and incorporating changes to the array(s), while also reducing the likelihood of inconsistent data being present in the array(s) in the non-volatile storage.

A particular example of an application for the disclosed techniques is in connection with a mutable trie structure that is composed of multiple arrays. The trie can be used, for example, for searching files locally on a mobile phone or other computing device. The disclosed techniques can help ensure that as the arrays in the trie structure are updated, the data stored in non-volatile memory remains consistent. If the data becomes (or appears to be) corrupted, an alert can be provided. The techniques also can be used in other applications.

Other aspects, features and advantages will be apparent from the following detailed description, the accompanying drawings and the claims.

DETAILED DESCRIPTION

The techniques described here can be used in connection with various arrays. For the purposes of illustration,FIG. 1shows an example of an array20. Array20can be stored, for example, in a non-volatile, or persistent, storage medium102, such as disk or flash memory, on a mobile phone or other computing device100(seeFIG. 2). The non-volatile storage medium102retains data and information stored thereon even if power is removed from the device. Power loss may be intentional (e.g., a device reboot or shutdown) or accidental (e.g., a power failure). The computing device100also may include other components such as volatile memory (e.g., random access memory (RAM))104, read-only memory (ROM)106that stores the device's operating system108and other software instructions, a processor110, a user interface112(including, e.g., input/output keys114, a touch screen116, and a display118), a battery or other power source120and a transceiver122.

As illustrated inFIG. 1, array20contains multiple elements22. In some implementations, array20can be part of a data structure that can be searched. Array20can be used, for example, in connection with a key value look-up table on a computing device. In some implementations, array20can be updated dynamically to incorporate new elements22or to change the contents of existing elements.

This and the following paragraphs describe a first technique for storing changes to array20. In this first technique, the device operates according to a private mode, in which the kernel (i.e., the operating system) obtains a bitmap of the portions(s) of the underlying file of array20that is being modified (seeFIG. 3). The bitmap is stored in RAM104, and when an attempt is made to write to the array20, changes are made to the bitmap in RAM104, rather than to the array stored in disk102(FIG. 4, block202). In some implementations, 4-kbyte sections of the array20are stored in RAM104corresponding to the section(s) of the array being modified.

After modifications to array20are made and stored by the bitmap in RAM104, a user can call a Flush function with respect to the array (block204). Calling the Flush function causes the processor110to set a special bit124that is stored in disk102and that is associated with the particular array20being modified (block206). The special bit124may be referred to as a “corrupt data indicator” bit, for reasons that will become evident below, and can be located, for example, at the end of the disk space. Next, the kernel's Sync to Disk function is called (block208). Changes that were made with respect to the bitmap in RAM104then are carried over to array20that is stored on disk102(seeFIG. 3, and block210ofFIG. 4), and the kernel's Sync to Disk function is called again (block212). In particular, the Sync to Disk function writes any data buffered in memory104to disk102and synchronizes disk102. The kernel can receive confirmation when the Sync to Disk function is returned. Once the changes to the array are written to the file stored in disk102, the kernel clears the “corrupt data indicator” bit124and synchronizes disk102(block214), and the kernel's Sync to Disk function is called again (block216). In addition, the kernel discards the bitmap previously stored in RAM104(block218). A new bitmap then can be initiated in RAM104so as to track any additional changes to the array.

By using the foregoing technique, in the event that the program executed by processor110is interrupted, for example, as the result of a power loss to the device100or a crash (i.e., a condition where a processor or a program, either an application or part of the operating system, ceases to function properly), the data stored in the array20on disk102can be considered valid up until the last time the Flush function was called. In other words, since changes to the array20initially are made only in RAM104, data stored in the array can be considered valid up until the last time the Flush function was called.

An exception can occur if the program is interrupted during execution of the Flush function. In such a situation, it is possible that data stored in the array20on disk102may be corrupted and is not necessarily valid. Nevertheless, the status of the “corrupt data indicator” bit124can be used to determine whether the changes to the array were successfully carried over to disk102. In particular, if the “corrupt data indicator” bit124associated with the file for the particular array is still set when power is restored to device100, the bit124would thus indicate that the file may be corrupted. In some implementations, a message can be provided automatically as an alert regarding the presence of possibly corrupted data in the particular file on disk102. On the other hand, if the “corrupt data indicator” bit124is clear when power is restored to the device, the bit's status would indicate that the data was successfully written to the array on disk102. One advantage to the foregoing technique for storing a mutable array is that, other than during the Flush sequence, the data in the array is more reliably secure.

Whereas the foregoing first technique employs explicit disk synchronization, the second technique, described in this and the following paragraphs uses check pointing, without disk synchronization. The file storing the array20that is being modified is stored in a shared mode, in which it is assumed that changes made in RAM104will be reflected in the file on disk101. However, the timing of carrying over the changes to disk102is handled by the operating system108at a time of its own choosing and can be optimized, for example, in accordance with other system operations.

In the shared mode, when a section of array20is modified, the changes are reflected immediately in the kernel buffers in RAM104. In particular, as shown inFIG. 5, the kernel can store in RAM104a mapping302of the underlying file for the array (including any changes that are made to the array), and also can store the original values304of the modified sections of the array (i.e., prior to the modifications) (see alsoFIG. 6, block402). Preferably, the original values of the array are maintained in RAM104only up to a predetermined constant fraction “k” (e.g., 20%) of the array size . When a batch of changes is completed with respect to the array, the user can call a Checkpoint function (block404). The Checkpoint function computes a cyclic redundancy check (CRC) value for the array as modified (block406), and stores the computed CRC value306is stored in RAM104(block408). The CRC value can be computed as discussed in greater detail below, which also describes an advantage of maintaining the original values of the array in RAM104. Changes to array20and to the CRC value are carried over to disk102based on the memory mapping (block410). As mentioned above, operating system108can carry over the information to disk20at a time selected, for example, to optimize overall system performance. The CRC value can be written and stored, for example, in four bytes at the end of the array file on disk102.

As illustrated inFIG. 7, when the program executed by processor110returns and reads data from the array20on disk102, the program computes a CRC value for the entire array as stored on the disk, and compares the newly computed CRC value to the CRC value previously-stored in disk102(bock414). If the newly computed value equals the CRC value stored in the file on disk102, then the data stored in the array on disk102is valid (block416). On the other hand, if the newly computed value does not equal the CRC value stored in the file on disk102, then the data stored in the array on disk102is not valid and may be corrupted (block418). In some implementations, a message can be provided automatically as an alert regarding the presence of possibly corrupted data in the particular file on disk102. One advantage to the foregoing technique for storing a mutable array is that fewer disk sync operations need to be performed.

One approach to calculating the CRC value for the array data stored in RAM104(in block404ofFIG. 6) is to recalculate the CRC value for the entire array each time the Checkpoint function is called. Although such an approach can be used, it can be very time consuming. For example, if array20has size N and the Checkpoint function is called N/K times in fixed chunks of size K, then the total number of operations required to execute the CRCs is on the order of N2.

An alternative approach makes use of the original values304of the array stored in RAM104and allows the CRC value to be updated incrementally, rather than re-computing a new CRC value for the entire array every time. The following technique can be used to replace a part of information M(x) in-place, and to re-compute the CRC value of modified information M(x) efficiently. If information M =ABC is a concatenation of parts A, B, and C, and B′(x) is a new part of the same length as B(x), CRCu(M′) of information M′=AB′C may be computed from known CRCu(M). In particular:
CRCu(M′(x),v(x))=CRCu(M(x),v(x))+Δ
where
Δ={CRCu(B′(x),v(x))−(CRCu(B(x),v(x))}x|C|mod|P(x).

In some implementations, the CRC value is computed (in block404) using the foregoing incremental updating technique if the changed area of the array is less than the predetermined constant fraction of the array size “k” (e.g., 20%). An advantage to this approach is that it can be less time consuming because the number of operations required is on the order of [n*log(n)], rather than n2. In the event that the changed area of the array is equal to or greater than the predetermined constant fraction of the array size “k” (e.g., 20%), then the program simply re-computes the CRC for the entire array.

In some scenarios, array20may be modified by appending new data to the array rather than changing existing elements in the array. In such a case, there is no original CRC value with respect to the newly appended data. Nevertheless, an updated CRC value for the array as modified can be computed by obtaining a CRC value for the newly added elements in the array, and then adding this CRC value to the CRC value previously obtained for the array prior to its modification.

For example, if information M(x)=M1(x)·xM|2|+M2(x) is a concatenation of M1and M2, and CRCs of M1, M2(computed with some initial values v1(x), v2(x) respectively) are known, then CRCu(M(x); v(x)) can be computed without touching contents of the M. For example, the value of v′1=CRCu(M1; v) can be computed from the known CRCu(M1; v1) without touching the contents of M1using the following formula:
CRCu(M; v′)=CRCu(M; v)+|{(v′−v)x|M|}modP.

Then, v′2=CRCu(M2; v′1) can be computed from known CRCu(M2; v2) without touching the contents of M2. Finally, CRCu(M; v)=v′2. When using the foregoing technique to compute the CRC value, a pointer can be used to point to the last byte in the array touched by the user.

As indicated above, the foregoing techniques can be implemented, for example, on various types of handheld computing devices, such as mobile phones, tablets, personal digital assistants (PDAs), as well as desk top personal computers, laptop computers, and other computing devices.