The patent's assignee is
News editors obtained the following quote from the background information supplied by the inventors: "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."
As a supplement to the background information on this patent application, VerticalNews correspondents also obtained the inventors' summary information for this patent application: "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."
For additional information on this patent application, see: Kirazci, Ulas; Banachowski, Scott. Consistent, Disk-Backed Arrays. Filed
Keywords for this news article include:
Our reports deliver fact-based news of research and discoveries from around the world. Copyright 2014, NewsRx LLC
Most Popular Stories
- Doctor Who Christmas Episode Begins Production
- HCL America Adding 1,200 IT Jobs
- Medical Mfg. Jobs Coming to Dayton
- Michael Jackson, Freddie Mercury on Previously Unreleased Queen Cut
- Longtime Unemployed to Get Help in Las Vegas
- SpaceX Aims for Predawn Launch on Saturday
- Women Key to Democratic Party: Clinton
- U.S. Chamber Caught Up in Tax Inversion Question
- Feds Won't Say How Many Border Crossers Jailed
- Christie Didn't Order Bridge Shut Down, Feds Say