News Column

"Avoiding Physical Fragmentation in a Virtualized Storage Environment" in Patent Application Approval Process

August 14, 2014



By a News Reporter-Staff News Editor at Computer Weekly News -- A patent application by the inventors SHAIKH, Faraz (Sunnyvale, CA); VILAYANNUR, Murali (San Jose, CA), filed on March 20, 2014, was made available online on July 31, 2014, according to news reporting originating from Washington, D.C., by VerticalNews correspondents.

This patent application is assigned to Vmware, Inc.

The following quote was obtained by the news editors from the background information supplied by the inventors: "Computer virtualization is a technique that involves encapsulating a physical computing machine platform into a virtual machine that is executed under the control of virtualization software on a hardware computing platform, or 'host.' A virtual machine has both virtual system hardware and guest operating system software. Virtual system hardware typically includes at least one 'virtual disk,' a single file or a set of files that appear as a typical storage drive to the guest operating system. The virtual disk may be stored on the host platform or on a remote storage device. Typically, a virtual machine (VM) uses the virtual disk to store the guest operating system, application programs, and application data.

"In a virtualized environment, application programs executing on the VM access the physical disk space via a virtualization stack. The virtualization stack includes multiple software layers (referred to herein as the 'logical layers') above the ultimate physical storage layer, the physical disk. Logical layers of the virtualization stack include the guest operating system, the hypervisor and the virtual machine file system (VMFS) driver. Each logical layer is associated with a data block layer that maintains and tracks the allocation of logical data blocks in response to requests received from the applications executing on the VM. Translation mechanisms in each logical layer allow for managing the relationships between data blocks across different data block layers.

"Storage access requests from applications executing on the VM are transmitted to the top-most layer of the virtualization stack, which identifies the logical data blocks in the associated data block layer that correspond to the request. The top layer then transmits the request to the next layer of the virtual storage stack, which in turn identifies the logical data blocks in the associated data block layer that correspond to the request. In such a manner, the request traverses the virtual storage stack until the request reaches the physical layer, where the request is serviced.

"In response to write requests received from applications executing on the VM, data blocks in each data block layer associated with a logical layer are allocated for servicing the request. Ultimately, once the logical layers are traversed, disk space in the physical storage layer is allocated for storing the data associated with the write request. In operation, storage virtualization has over-commit goals that lead to sparse allocation of storage blocks in the physical storage layer. More specifically, at each logical layer, storage block allocation is sequenced in order of first writes such that, after a region has been provisioned, block allocation and the underlying physical storage allocation is delayed until a first write occurs in the provisioned region. Such delayed allocation may not preserve spatial locality at the physical storage layer, which may have served other allocation requests in between the receipt of the provisioning request and the allocation request from the particular logical layer. Such a phenomenon leads to fragmentation at the physical storage layer, where storage blocks that should be stored contiguously from a logical point of view are not physically laid out contiguously. Physical fragmentation is highly undesirable because physical co-location of data blocks that are to be accessed sequentially allows for significantly faster access than if those data blocks are not physically co-located.

"One solution to reduce fragmentation at the physical storage layer is to increase the size of data blocks in the data block layers associated with the physical layers. With such an approach, a single write request from the application results in allocating enough of extra contiguous physical storage to accommodate physical co-locality of future writes. Such an approach, however, has limitations. More specifically, future writes may never occur and, thus, the allocated space may never be used. Further, large storage block sizes may have an adverse impact on the storage services that a virtualized environment can provide. For example, a large block size is undesirable for de-duplication where probability of finding duplicates depends on blocks sizes being small. Storage related services, like snapshotting, that use copy on write are also adversely affected if the blocks size is too large as larger blocks are to be read before doing a copy on write and eliminating copy on write overheads in cases of full overwrites are reduced. As the foregoing illustrates, there remains a need in the art for an effective storage block allocation technique that reduces the amount of fragmentation."

In addition to the background information obtained for this patent application, VerticalNews journalists also obtained the inventors' summary information for this patent application: "One or more embodiments of the present invention provide techniques for allocating data blocks in response to write requests in a manner that reduces the final physical fragmentation.

"A method for identifying storage blocks for storing data associated with a write request, according to an embodiment of the present invention, includes the step of reading metadata associated with a set of free storage blocks that were previously written, where the metadata includes a tag for each storage block in the set of storage blocks, and storage blocks in the set of storage blocks that were initially written in response to a single write request share the same tag, thereby indicating a likelihood that physical storage locations that back the storage blocks having the same tag are proximately located. The method also includes the step of identifying one or more storage blocks in the set of free storage blocks for storing data associated with the write request based on the tags of the storage blocks in order to increase a likelihood that the data associated with the write request will be stored in a first set of physical storage locations that are proximately located.

"A method for defragmenting physical storage that is accessed through a set of layers of a storage stack, according to one embodiment of the invention, includes the steps of receiving a first defragmentation request at a lower layer from an upper layer, the first defragmentation request indicating a plurality of storage blocks for defragmentation, determining, at the lower layer, a set of storage blocks that correspond to the plurality of storage blocks, and transmitting by the lower layer a second defragmentation request to a layer that is below thereto, the second defragmentation request indicating the set of storage blocks for defragmentation.

"Embodiments of the present invention further include a non-transitory computer-readable storage medium storing instructions that when executed by a computer system cause the computer system to perform one or more of the methods set forth above, and a computer system that is configured to carry out one or more of the methods set forth above.

BRIEF DESCRIPTION OF THE DRAWINGS

"FIG. 1 is a block diagram that shows a virtualized computer architecture including servers and storage arrays that are configured according to one or more embodiments.

"FIG. 2A depicts a block diagram representative of a server in the virtualized computer architecture of FIG. 1.

"FIG. 2B depicts a block diagram representative of a storage array in the virtualized computer architecture of FIG. 1.

"FIG. 3 is a block diagram representative of a storage stack implemented by the server and the storage array of FIGS. 2A and 2B.

"FIG. 4 illustrates a detailed block diagram of a block allocation unit implemented at various layers of the storage stack illustrated in FIG. 3.

"FIG. 5 illustrates a detailed block diagram of block metadata maintained by the block allocation unit of FIG. 4.

"FIG. 6 is a flow diagram that illustrates a method of allocating one or more blocks to a write request received from a client, according to one or more embodiments.

"FIG. 7 is a flow diagram that illustrates a method of computing a weighted score for a particular block allocation that may be written in response to a write request, according to one or more embodiments.

"FIG. 8 is a flow diagram that illustrates a method of defragmenting data blocks, according to one or more embodiments."

URL and more information on this patent application, see: SHAIKH, Faraz; VILAYANNUR, Murali. Avoiding Physical Fragmentation in a Virtualized Storage Environment. Filed March 20, 2014 and posted July 31, 2014. Patent URL: http://appft.uspto.gov/netacgi/nph-Parser?Sect1=PTO2&Sect2=HITOFF&u=%2Fnetahtml%2FPTO%2Fsearch-adv.html&r=154&p=4&f=G&l=50&d=PG01&S1=20140724.PD.&OS=PD/20140724&RS=PD/20140724

Keywords for this news article include: Software, Vmware Inc.

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: Computer Weekly News


Story Tools






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