News Column

Researchers Submit Patent Application, "System and Methods for Managing Storage Space Allocation", for Approval

July 1, 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 GOLD, ISRAEL (Haifa, IL); SATRAN, JULIAN (Omer, IL), filed on December 10, 2012, was made available online on June 19, 2014.

The patent's assignee is Infinidat Ltd.

News editors obtained the following quote from the background information supplied by the inventors: "Free-space management of storage-based applications is required for reusing the space freed when objects are deleted, for new objects or for new data of existing objects. Low level volume management involves handling fixed size blocks that compose the volume, which makes space allocation easier to handle. However, free-space management becomes more complicated when the managed storage consists of variable sized objects as usually happens in upper layer storage applications, such as filesystems that manage variable sized files, databases that manage tables and indexes of various sizes and the like.

"Free space is managed using various types of data-structures, some of which are described below.

"A file system is required to keep track of allocated and free blocks within a logical volume that contains objects of the file system. The simplest solution often used is an allocation bitmap that represents allocated and free space, wherein each bit in the bitmap represents a block in the volume and indicates whether the specific block in a volume is allocated or free. When the file system needs to allocate additional blocks, it refers to the bitmap to identify which blocks are available. However, it is extremely inefficient to search through a bitmap to find large contiguous chunks of free space, particularly when large volumes are involved.

"Bitmaps of the whole volume can become quite large for high capacity volumes and need to be saved in the disk and to be read to the cache memory upon allocation change and then be written back to the disk.

"Extent lists are the most common alternative to bitmaps. Extent lists are data structures that organize free space into contiguous regions described by location in storage and length of available blocks. Extent lists are sometimes preferred for compression, representing free space using less memory and storage. However, they can grow to be larger than bitmaps, particularly when storage is heavily utilized by small allocations.

"One of the problems of bitmaps is de-allocation of blocks. Space allocation algorithms can control the locality of allocations, by deciding which area of the volume is currently dedicated for allocation of new data, but there is no control over the locality of frees, as portions of a file that were allocated in different times can be spread all over the volume. As an example of a worst case, removing 4 GB of object data (a million 4K blocks) could require million bitmaps (of 4K bit each) to be read, modified, and written back again."

As a supplement to the background information on this patent application, VerticalNews correspondents also obtained the inventors' summary information for this patent application: "In accordance with certain aspects of the currently presented subject matter, there is provided a method of operating a storage system including a block control layer operatively coupled to one or more physical storage devices constituting a physical storage space represented by storage blocks, the method includes: (i) receiving a request for obtaining a space allocation descriptor indicative of one or more logical blocks free for allocation within a range of logical addresses, the range is included within a logical address space associated with an upper layer application which has issued the request; and (ii) providing the space allocation descriptor by using a data structure included in the block control layer and operative to map between the logical address space and allocated storage blocks within the physical storage space, managed by the block control layer.

"In accordance with further aspects of the currently presented subject matter, the method can further include receiving an allocation request for allocating one or more free storage blocks and for associating the free storage blocks with a second range of logical addresses, included within the logical address space; allocating the free storage blocks; and updating the data structure so as to include a mapping between the second range of logical addresses and the free storage blocks that have been allocated.

"The allocating the free storage blocks is provided merely in a case when the allocation request is related to writing data corresponding to the second range of logical addresses, to the physical storage space.

"In accordance with further aspects of the currently presented subject matter, the method can further include configuring the data structure to include a plurality of entries, each entry indicative of mapping between logical blocks included in the logical address space and respective allocated storage blocks, and wherein each entry corresponds to a range of consecutive logical block addresses.

"In accordance with further aspects of the currently presented subject matter, the method can further include associating at least one entry with an allocation value, wherein the at least one entry is characterized by an identical allocation status of all logical blocks corresponding to the at least one entry and wherein the allocation value indicative of the identical allocation status shared by all the logical blocks of the at least one entry.

"In accordance with further aspects of the currently presented subject matter, the method can further include configuring the data structure to include one or more bitmaps each associated with a respective entry representing logical blocks having different allocation statuses, the bitmap is indicative of the allocation statuses of all logical blocks represented by the respective entry.

"In accordance with further aspects of the currently presented subject matter, the method can further include, responsive to a de-allocation request related to all logical blocks represented by the at least one entry, setting the allocation value associated with the entry to indicate a free status of the entire entry.

"In accordance with further aspects of the currently presented subject matter, the method can further include, responsive to a de-allocation request related to a part of logical blocks in a certain entry, associating the certain entry with a bitmap and using the bitmap to indicate an allocation status of each logical block represented by the certain entry.

"In accordance with further aspects of the currently presented subject matter, the method can further include: responsive to the request for receiving the space allocation descriptor, identifying in the data structure all entries indicative of mapping at least one logical address within the range of logical addresses; for each identified entry, generating an entry allocation descriptor indicative of an allocation status of all logical blocks corresponding to the entry; wherein if a certain identified entry is characterized by an identical allocation status of all logical blocks corresponding to the entry, the entry allocation descriptor is configured to include data indicative of the range of the at least one logical address and an allocation value indicative of an allocation status of the entire entry; and wherein if the certain identified entry represents logical blocks having different allocation statuses, the entry allocation descriptor is configured to include a bitmap associated with the certain identified entry; and generating the space allocation descriptor using the entry allocation descriptors of the identified entries.

"The logical blocks represented by each entry can be organized in one or more allocation units of a predefined size, and wherein the allocation units are the smallest data portions handled by the block control layer and by the data structure.

"The data structure can be handled in a cache memory included in the block control layer and the step of providing includes accessing the data structure in the cache memory.

"In accordance with other aspects of the currently presented subject matter, there is provided a non-transitory computer readable storage medium, that stores program instructions for: (i) receiving a request for obtaining a space allocation descriptor indicative of one or more logical blocks free for allocation within a range of logical addresses, the range included within a logical address space related to an upper layer application which has issued the request; and (ii) providing the space allocation descriptor by using a data structure included in the block control layer and operative to map between the logical address space and allocated storage blocks within the physical storage space, managed by the block control layer.

"In accordance with other aspects of the currently presented subject matter, there is provided a storage system including a block control layer operatively coupled to one or more physical storage devices constituting a physical storage space represented by storage blocks; wherein the block control layer is configured to: (i) receive, from an upper layer application, a request for obtaining a space allocation descriptor indicative of one or more logical blocks free for allocation within a range of logical addresses, the range included within a logical address space related to the at least one upper layer application; and (ii) provide the space allocation descriptor by using a data structure included in the block control layer and operative to map between the logical address space and allocated storage blocks within the physical storage space, managed by the block control layer.

BRIEF DESCRIPTION OF THE DRAWINGS

"In order to understand the presently disclosed subject matter and to see how it may be carried out in practice, the subject matter will now be described, by way of non-limiting examples only, with reference to the accompanying drawings, in which:

"FIG. 1 is a functional block diagram schematically illustrating an embodiment of a block based storage system for providing space mapping services for upper layer applications, according to embodiments of the presently disclosed subject matter;

"FIG. 2 is a schematic diagram of a mapping data structure, according to embodiments of the presently disclosed subject matter;

"FIG. 3 is a flowchart illustrating a method for providing volume mapping services by a block based storage system to an upper layer application, according to embodiments of the presently disclosed subject matter;

"FIG. 4 is a flowchart illustrating method steps for configuring a mapping data structure, according to embodiments of the presently disclosed subject matter;

"FIG. 5 is a flowchart illustrating method steps for performing mapping, according to embodiments of the presently disclosed subject matter; and

"FIG. 6 is a flowchart illustrating method steps for performing unmapping, according to embodiments of the presently disclosed subject matter."

For additional information on this patent application, see: GOLD, ISRAEL; SATRAN, JULIAN. System and Methods for Managing Storage Space Allocation. Filed December 10, 2012 and posted June 19, 2014. Patent URL: http://appft.uspto.gov/netacgi/nph-Parser?Sect1=PTO2&Sect2=HITOFF&u=%2Fnetahtml%2FPTO%2Fsearch-adv.html&r=521&p=11&f=G&l=50&d=PG01&S1=20140612.PD.&OS=PD/20140612&RS=PD/20140612

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