News Column

Researchers Submit Patent Application, "Method and System for Reducing Mapping Table Size in a Storage Device", for Approval

July 15, 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 inventor Thomas, Nicholas James (Dundee, GB), filed on February 22, 2013, was made available online on July 3, 2014.

No assignee for this patent application has been made.

News editors obtained the following quote from the background information supplied by the inventors: "Non-volatile memory systems, such as flash memory, are used in digital computing systems as a means to store data and have been widely adopted for use in consumer products. Flash memory may be found in different forms, for example in the form of a portable memory card that can be carried between host devices or as a solid state disk (SSD) embedded in a host device. These memory systems typically work with data units called 'pages' that can be written, and groups of pages called 'blocks' that can be read and erased, by a storage manager often residing in the memory system.

"In a SSD there is a mapping table or other data structure that typically stores a map of all logical addresses to physical addresses in the SSD. When data is written to a flash memory, the mapping table or other data structure that tracks the location of data in the flash memory must be updated. The time involved in updating data structures for file systems to reflect changes to files and directories, and accessing these data structures, may affect the performance of the storage device. Typically, runs of logical addresses exist which are written at the same time to contiguous runs of physical addresses, but the memory system should to be able to handle worst case scenarios where no contiguous runs exist and each logical address is mapped to randomly to different physical addresses.

"Thus, in SSDs or other flash storage devices, a fine granularity mapping table is required to allow best write performance. This table can typically be very large. The full table or subparts of it are generally required to perform read and write tasks so it is desirable to store a working copy in dynamic random access memory (DRAM) to ease random read and write overhead. It may not be economically feasible or technologically viable to use a DRAM sufficiently large to hold the entire table. However, if the entire mapping table is not held in DRAM then read and write performance may slow down and write wear may increase in any flash memory that is used to hold portions of the mapping table that is not held in the DRAM."

As a supplement to the background information on this patent application, VerticalNews correspondents also obtained the inventor's summary information for this patent application: "In order to address the problems and challenges noted above, a system and method for handling logical-to-physical mapping in a flash memory system is disclosed.

"According to a first aspect, method is disclosed where, in a memory device having a non-volatile memory, a volatile memory and a controller in communication with the non-volatile memory and the volatile memory, the controller maintains an index table in the volatile memory. The index table is configured to store a predetermined number of index entries where each of the predetermined number of index entries is associated with a cluster group, each cluster group having a fixed plurality of clusters, where each cluster group comprises a predetermined number of logically contiguous clusters and each of the predetermined number of index entries is configured to contain physical address information for only one cluster of the cluster group associated with that index entry. The method includes receiving data associated with a cluster in a data write command and determining a physical location in the non-volatile memory for storing the cluster. The method includes then identifying in the index table an index entry associated with the cluster and storing in the volatile memory an address of the physical location for the cluster in the identified index entry. Further, the method includes storing in the physical location in the non-volatile memory the received data for the cluster and storing, in a header of the received data stored at the physical location, location information of each of a remainder of the clusters in the cluster group associated with the identified index entry. In this manner, the index entry in the volatile memory contains the address of the physical location of only one of the clusters in the cluster group, and the header of the data at the physical location contains location information for the remainder of the clusters in the cluster group associated with the index entry.

"According to another aspect, a storage device is disclosed. The storage device includes a non-volatile memory, a volatile memory; and a controller in communication with the non-volatile memory and the volatile memory. The controller is configured to maintain an index table in the volatile memory, the index table sized to store a predetermined number of index entries where each of the predetermined number of index entries is associated with a cluster group, each cluster group having a predetermined number of logically contiguous clusters and each of the predetermined number of index entries is configured to contain physical address information for only one cluster of the cluster group associated with that index entry. The controller is further configured to receive data associated with a cluster in a data write command, determine a physical location in the non-volatile memory for storing the cluster and identify in the index table an index entry associated with the cluster. The controller is further configured to store in the volatile memory an address of the physical location for the cluster in the identified index entry, store in the physical location in the non-volatile memory the received data for the cluster, and store, in a header of the received data stored at the physical location, location information of each of a remainder of the clusters in the cluster groups associated with the identified index entry.

"In other aspects, the method and system may determine if the index table has empty entries, for example by using spare bits in entries of the index table to indicate whether clusters in a cluster group contain valid data, and then use the empty index entries for storing physical location information for a non-primary cluster of a different cluster group.

"Other embodiments are disclosed, and each of the embodiments can be used alone or together in combination. The embodiments will now be described with reference to the attached drawings.

BRIEF DESCRIPTION OF THE DRAWINGS

"FIG. 1 illustrates a block diagram of host and storage device according to one embodiment.

"FIG. 2 illustrates an example physical memory organization of the memory in the storage device of FIG. 1.

"FIG. 3 shows an expanded view of a portion of the physical memory of FIG. 2.

"FIG. 4 illustrates an embodiment of a storage device having a selected portion of a mapping table stored in DRAM.

"FIG. 5 illustrates one primary logical to physical mapping table layout usable in the primary mapping table of FIG. 4.

"FIG. 6 illustrates an example of a storage device having a primary mapping table sized to fit in DRAM of the storage device and distributed mapping data in headers of data in NAND of the storage device.

"FIG. 7 illustrates one primary logical to physical mapping table layout usable in the primary mapping table of FIG. 6.

"FIG. 8 is a flow diagram of a method for managing logical to physical mapping during write operations in a storage device such as illustrated in FIG. 6.

"FIG. 9 is an embodiment of the structure of a primary mapping table.

"FIG. 10 is an embodiment of the structure of a non-volatile memory associated with the primary mapping table of FIG. 9.

"FIG. 11 is a flow diagram of a method for managing logical to physical mapping during read operations in a storage device such as illustrated in FIG. 6."

For additional information on this patent application, see: Thomas, Nicholas James. Method and System for Reducing Mapping Table Size in a Storage Device. Filed February 22, 2013 and posted July 3, 2014. Patent URL: http://appft.uspto.gov/netacgi/nph-Parser?Sect1=PTO2&Sect2=HITOFF&u=%2Fnetahtml%2FPTO%2Fsearch-adv.html&r=667&p=14&f=G&l=50&d=PG01&S1=20140626.PD.&OS=PD/20140626&RS=PD/20140626

Keywords for this news article include: Patents, 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