News Column

Researchers Submit Patent Application, "Consistent, Disk-Backed Arrays", for Approval

August 5, 2014



By a News Reporter-Staff News Editor at Information Technology Newsweekly -- From Washington, D.C., VerticalNews journalists report that a patent application by the inventors Kirazci, Ulas (Mountain View, CA); Banachowski, Scott (Mountain View, CA), filed on August 19, 2013, was made available online on July 24, 2014.

The patent's assignee is Google Inc.

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 August 19, 2013 and posted July 24, 2014. Patent URL: http://appft.uspto.gov/netacgi/nph-Parser?Sect1=PTO2&Sect2=HITOFF&u=%2Fnetahtml%2FPTO%2Fsearch-adv.html&r=450&p=9&f=G&l=50&d=PG01&S1=20140717.PD.&OS=PD/20140717&RS=PD/20140717

Keywords for this news article include: Google Inc., Information Technology, Information and Data Architecture.

Our reports deliver fact-based news of research and discoveries from around the world. Copyright 2014, NewsRx LLC


For more stories covering the world of technology, please see HispanicBusiness' Tech Channel



Source: Information Technology Newsweekly


Story Tools






HispanicBusiness.com Facebook Linkedin Twitter RSS Feed Email Alerts & Newsletters