Browse Prior Art Database

Space optimized, direct indexed, hierarchical block allocation maps

IP.com Disclosure Number: IPCOM000247121D
Publication Date: 2016-Aug-08
Document File: 3 page(s) / 66K

Publishing Venue

The IP.com Prior Art Database

Related People

Freddy James: INVENTOR [+4]

Abstract

In this method a sparse block map with organization that mimics that of a fully allocated optimal depth block map is used to achieve efficient block map operations. This way we keep all the advantages of a fully allocated block map as well as keep space usage at a minimum. Some novel mechanisms to reduce the overhead of block map allocation in the context of a data block allocation is discussed.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 51% of the total text.

Page 01 of 3

Space optimized, direct indexed, hierarchical block allocation maps

Freddy James

Rachit Chadha

Ajay Salpekar

Brad Boyer

Abstract

In this method a sparse block map with organization that mimics that of a fully allocated optimal depth block map is used to achieve efficient block map operations. This way we keep all the advantages of a fully allocated block map as well as keep space usage at a minimum. Some novel mechanisms to reduce the overhead of block map allocation in the context of a data block allocation is discussed.

Problem Statement

Traditional block map operation is inefficient as we have to do a binary search in the block map at every level to find the index in the next level. Also insertions to block map require shifting of entries with in a map, which is transactionally inefficient. Also some insertion may result in a split operation which can recursively propagate to the root level. There are lot of inefficiencies which are hidden in the details

Publication Description

We need a way to avoid binary search in the block map. Also insertions should not result in adjustments (shifting) of existing bmap entries. One way to do this is by allocating the entire bmap and initializing it with either block information or HOLE entries when there is no allocation at a logical offset. However, this result in excess space usage for block map. This can also increase metadata management cost that include inefficient use of metadata cache, increased file system check time. A solution to this problem is to assume a bmap structure that can be achieved using a fully allocated block map, but without actual allocation in unused parts of block map.

1

© 2016 Veritas Technologies LLC. All rights reserved. Veritas and the Veritas Logo are trademarks or registered trademarks of Veritas Technologies LLC or its affiliates in the U.S. and other countries. Other names may be trademarks of their respective owners.


Page 02 of 3

Description
Consider a file which is fully allocated. Every bmap entry describes a single filesystem block. In this case the block map tree of the file has to be fully populated. This is because the bmap has to keep entries representing each block allocated to the file. Since mapping of the logical offset of a block to logical offset in the bmap is fixed, the index at every level can be arrived without any binary search. However, for a file which is sparse, we don't have to allocate the entire bmap space. However, we can choose to allocate the entire block map, even in the sparse file case and keep the efficiencies associated with a fully allocated bmap. However, instead of allocating the whole bmap, we can use the same indirect framework to later allocate bmap to the file. This way we can keep all the benefits of fully allocated bmap, but at the same time use only as much space as required to keep information about currently allocated blocks.

The term used for a block map block in filesystem is "...