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.

Description:
CROSS-REFERENCE TO RELATED APPLICATION(S) 
     This application claims the benefit of U.S. Provisional Application No. 61/753,159, filed on Jan. 16, 2013, which is incorporated by reference. 
    
    
     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. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  illustrates an example of an array. 
         FIG. 2  is a block diagram of an example of a computing device that stores the array. 
         FIG. 3  illustrates a first implementation of how changes to an array are managed. 
         FIG. 4  is a flow chart illustrating a first method of managing changes to the array. 
         FIG. 5  illustrates a second implementation of how changes to an array are managed. 
         FIG. 6  is a flow chart illustrating a second method of managing changes to the array. 
         FIG. 7  is a flow chart illustrating a method of reading data from the array. 
     
    
    
     DETAILED DESCRIPTION 
     The techniques described here can be used in connection with various arrays. For the purposes of illustration,  FIG. 1  shows an example of an array  20 . Array  20  can be stored, for example, in a non-volatile, or persistent, storage medium  102 , such as disk or flash memory, on a mobile phone or other computing device  100  (see  FIG. 2 ). The non-volatile storage medium  102  retains 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 device  100  also may include other components such as volatile memory (e.g., random access memory (RAM))  104 , read-only memory (ROM)  106  that stores the device&#39;s operating system  108  and other software instructions, a processor  110 , a user interface  112  (including, e.g., input/output keys  114 , a touch screen  116 , and a display  118 ), a battery or other power source  120  and a transceiver  122 . 
     As illustrated in  FIG. 1 , array  20  contains multiple elements  22 . In some implementations, array  20  can be part of a data structure that can be searched. Array  20  can be used, for example, in connection with a key value look-up table on a computing device. In some implementations, array  20  can be updated dynamically to incorporate new elements  22  or to change the contents of existing elements. 
     This and the following paragraphs describe a first technique for storing changes to array  20 . 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 array  20  that is being modified (see  FIG. 3 ). The bitmap is stored in RAM  104 , and when an attempt is made to write to the array  20 , changes are made to the bitmap in RAM  104 , rather than to the array stored in disk  102  ( FIG. 4 , block  202 ). In some implementations, 4-kbyte sections of the array  20  are stored in RAM  104  corresponding to the section(s) of the array being modified. 
     After modifications to array  20  are made and stored by the bitmap in RAM  104 , a user can call a Flush function with respect to the array (block  204 ). Calling the Flush function causes the processor  110  to set a special bit  124  that is stored in disk  102  and that is associated with the particular array  20  being modified (block  206 ). The special bit  124  may 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&#39;s Sync to Disk function is called (block  208 ). Changes that were made with respect to the bitmap in RAM  104  then are carried over to array  20  that is stored on disk  102  (see  FIG. 3 , and block  210  of  FIG. 4 ), and the kernel&#39;s Sync to Disk function is called again (block  212 ). In particular, the Sync to Disk function writes any data buffered in memory  104  to disk  102  and synchronizes disk  102 . 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 disk  102 , the kernel clears the “corrupt data indicator” bit  124  and synchronizes disk  102  (block  214 ), and the kernel&#39;s Sync to Disk function is called again (block  216 ). In addition, the kernel discards the bitmap previously stored in RAM  104  (block  218 ). A new bitmap then can be initiated in RAM  104  so as to track any additional changes to the array. 
     By using the foregoing technique, in the event that the program executed by processor  110  is interrupted, for example, as the result of a power loss to the device  100  or 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 array  20  on disk  102  can be considered valid up until the last time the Flush function was called. In other words, since changes to the array  20  initially are made only in RAM  104 , 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 array  20  on disk  102  may be corrupted and is not necessarily valid. Nevertheless, the status of the “corrupt data indicator” bit  124  can be used to determine whether the changes to the array were successfully carried over to disk  102 . In particular, if the “corrupt data indicator” bit  124  associated with the file for the particular array is still set when power is restored to device  100 , the bit  124  would 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 disk  102 . On the other hand, if the “corrupt data indicator” bit  124  is clear when power is restored to the device, the bit&#39;s status would indicate that the data was successfully written to the array on disk  102 . 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 array  20  that is being modified is stored in a shared mode, in which it is assumed that changes made in RAM  104  will be reflected in the file on disk  101 . However, the timing of carrying over the changes to disk  102  is handled by the operating system  108  at 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 array  20  is modified, the changes are reflected immediately in the kernel buffers in RAM  104 . In particular, as shown in  FIG. 5 , the kernel can store in RAM  104  a mapping  302  of the underlying file for the array (including any changes that are made to the array), and also can store the original values  304  of the modified sections of the array (i.e., prior to the modifications) (see also  FIG. 6 , block  402 ). Preferably, the original values of the array are maintained in RAM  104  only 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 (block  404 ). The Checkpoint function computes a cyclic redundancy check (CRC) value for the array as modified (block  406 ), and stores the computed CRC value  306  is stored in RAM  104  (block  408 ). 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 RAM  104 . Changes to array  20  and to the CRC value are carried over to disk  102  based on the memory mapping (block  410 ). As mentioned above, operating system  108  can carry over the information to disk  20  at 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 disk  102 . 
     As illustrated in  FIG. 7 , when the program executed by processor  110  returns and reads data from the array  20  on disk  102 , 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 disk  102  (bock  414 ). If the newly computed value equals the CRC value stored in the file on disk  102 , then the data stored in the array on disk  102  is valid (block  416 ). On the other hand, if the newly computed value does not equal the CRC value stored in the file on disk  102 , then the data stored in the array on disk  102  is not valid and may be corrupted (block  418 ). In some implementations, a message can be provided automatically as an alert regarding the presence of possibly corrupted data in the particular file on disk  102 . 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 RAM  104  (in block  404  of  FIG. 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 array  20  has 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 N 2 . 
     An alternative approach makes use of the original values  304  of the array stored in RAM  104  and 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), CRC u (M′) of information M′=AB′C may be computed from known CRC u (M). In particular:
 
 CRC   u ( M ′( x ),  v ( x ))= CRC   u ( M ( x ),  v ( x ))+Δ
 
where
 
Δ={ CRC   u ( B ′( x ),  v ( x ))−( CRC   u ( B ( x ),  v ( x ))} x   |C| mod| P ( x ).
 
     In some implementations, the CRC value is computed (in block  404 ) 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 n 2 . 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, array  20  may 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)=M 1 (x)·xM |2| +M 2 (x) is a concatenation of M 1  and M 2 , and CRCs of M 1 , M 2  (computed with some initial values v 1 (x), v 2 (x) respectively) are known, then CRC u (M(x); v(x)) can be computed without touching contents of the M. For example, the value of v′ 1 =CRC u (M 1 ; v) can be computed from the known CRC u (M 1 ; v 1 ) without touching the contents of M 1  using the following formula:
 
 CRC   u ( M; v ′)= CRC   u ( M; v )+|{( v′−v ) x   |M| }mod  P.  
 
     Then, v′ 2 =CRC u (M 2 ; v′ 1 ) can be computed from known CRCu(M 2 ; v 2 ) without touching the contents of M2. Finally, CRC u (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. 
     Various aspects of the subject matter and the functional operations described in this specification can be implemented in digital electronic circuitry, or in computer software, firmware, or hardware, including the structures disclosed in this specification and their structural equivalents, or in combinations of one or more of them. Embodiments of the subject matter described in this specification can be implemented as one or more computer program products, i.e., one or more modules of computer program instructions encoded on a computer readable medium for execution by, or to control the operation of, data processing apparatus. The computer readable medium can be a machine-readable storage device, a machine-readable storage substrate, a memory device, a composition of matter effecting a machine-readable propagated signal, or a combination of one or more of them. The terms “data processing apparatus” and “computer” encompasses all apparatus, devices, and machines for processing data, including by way of example a programmable processor, a computer, or multiple processors or computers. The apparatus can include, in addition to hardware, code that creates an execution environment for the computer program in question, e.g., code that constitutes processor firmware, a protocol stack, a database management system, an operating system, or a combination of one or more of them. 
     A computer program (also known as a program, software, software application, script, or code) can be written in any form of programming language, including compiled or interpreted languages, and it can be deployed in any form, including as a stand alone program or as a module, component, subroutine, or other unit suitable for use in a computing environment. A computer program does not necessarily correspond to a file in a file system. A program can be stored in a portion of a file that holds other programs or data (e.g., one or more scripts stored in a markup language document), in a single file dedicated to the program in question, or in multiple coordinated files (e.g., files that store one or more modules, sub programs, or portions of code). A computer program can be deployed to be executed on one computer or on multiple computers that are located at one site or distributed across multiple sites and interconnected by a communication network. 
     The processes and logic flows described in this specification can be performed by one or more programmable processors executing one or more computer programs to perform functions by operating on input data and generating output. The processes and logic flows can also be performed by, and apparatus can also be implemented as, special purpose logic circuitry, e.g., an FPGA (field programmable gate array) or an ASIC (application specific integrated circuit). 
     Processors suitable for the execution of a computer program include, by way of example, both general and special purpose microprocessors, and any one or more processors of any kind of digital computer. Generally, a processor will receive instructions and data from a read only memory or a random access memory or both. The essential elements of a computer are a processor for performing instructions and one or more memory devices for storing instructions and data. Generally, a computer will also include, or be operatively coupled to receive data from or transfer data to, or both, one or more mass storage devices for storing data, e.g., magnetic, magneto optical disks, or optical disks. However, a computer need not have such devices. Moreover, a computer can be embedded in another device, e.g., a mobile telephone or other computing device. Computer readable media suitable for storing computer program instructions and data include all forms of non-volatile memory, media and memory devices, including by way of example semiconductor memory devices, e.g., EPROM, EEPROM, and flash memory devices; magnetic disks, e.g., internal hard disks or removable disks; magneto optical disks; and CD ROM and DVD-ROM disks. The processor and the memory can be supplemented by, or incorporated in, special purpose logic circuitry. 
     To provide for interaction with a user, embodiments of the subject matter described in this specification can be implemented on a computer having a display device, e.g., a CRT (cathode ray tube) or LCD (liquid crystal display) monitor, for displaying information to the user and a keyboard and a pointing device, e.g., a mouse or a trackball, by which the user can provide input to the computer. Other kinds of devices can be used to provide for interaction with a user as well; for example, feedback provided to the user can be any form of sensory feedback, e.g., visual feedback, auditory feedback, or tactile feedback; and input from the user can be received in any form, including acoustic, speech, or tactile input. 
     While operations are depicted in the drawings in a particular order, this should not be understood as requiring that such operations be performed in the particular order shown or in sequential order, or that all illustrated operations be performed, to achieve desirable results. In certain circumstances, multitasking and parallel processing may be advantageous. Moreover, the separation of various system components in the embodiments described above should not be understood as requiring such separation in all embodiments, and it should be understood that the described program components and systems can generally be integrated together in a single software product or packaged into multiple software products. 
     A number of implementations have been described. Nevertheless, it will be understood that various modifications may be made without departing from the spirit and scope of the invention. Accordingly, other implementations are within the scope of the claims.