Gang blocks

• US 7,437,528 B1
• Filed: 08/17/2004
• Issued: 10/14/2008
• Est. Priority Date: 08/17/2004
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Ahrens, Matthew A., Bonwick, Jeffrey S., Moore, William H.
• Primary Examiner(s): Kim; Matt
• Assistant Examiner(s): DUDEK JR, EDWARD J
• Application Number:
  US10/919,878
• Time in Patent Office: 1,519 Days
• Field of Search: 711/170
• US Class Current: 711/170
• CPC Class Codes: G06F 12/02 Addressing or allocation; Relocation program address sequencing G06F9/00; arrangements for selecting an address in a digital store G11C8/00
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0676 Magnetic disk device

Abstract

A method for allocating space on a disk involving receiving a request to allocate space on the disk having a first size, determining whether contiguous space of the first size exists on the disk. If contiguous space of the first size exists on the disk, allocating the contiguous space on the disk to obtain a contiguous space address, and responding to the request to allocate space on disk with a contiguous space pointer. If no contiguous space of the first size exists on the disk, allocating a gang block header, populating the gang block header, and responding to the request to allocate space on the disk with a gang block header pointer.

Claims

1. A method for allocating space on a disk comprising:

receiving a first request to allocate space on the disk having a first size;

allocating, in response to the first request, a first contiguous space having the first size and storing a first indirect block in the first contiguous space;

storing a second indirect block comprising a first block pointer referencing the first indirect block, wherein the first block pointer comprises a first gang block header bit that is not set;

receiving a second request to allocate space on the disk having a second size, wherein no contiguous space of the second size exists on the disk;

allocating, in response to the second request, a gang block header, wherein the gang block header occupies a minimum allocateable portion on the disk;

populating the gang block header; and

responding to the second request to allocate space on the disk by storing a second block pointer in the second indirect block, wherein the second block pointer comprises a second gang block header bit that is set, wherein the second block pointer references the gang block header and comprises a disk virtual address (DVA), a birth, and a checksum field and wherein the DVA comprises the second gang block header bit and a size field,

wherein populating the gang block header comprises;

obtaining a second contiguous space on the disk having a third size, wherein the third size is less than the second size,

storing a third pointer to the second contiguous space in the gang block header,

obtaining a third contiguous space on the disk having a fourth size, wherein the fourth size is less than the second size, and

storing a fourth pointer to the third contiguous space in the gang block header.

2. The method of claim 1, further comprising:

if a total size of the second contiguous space and the third contiguous space are less than the second size then;

obtaining a fourth contiguous space on the disk having a fifth size, wherein the fifth size is less than the second size; and

storing a third pointer to the fourth contiguous space in the gang block header.

3. The method of claim 1, wherein the size field stores a value corresponding to the second size.

4. A method for retrieving a block comprising:

receiving a first request to read a first block, wherein the first request comprises a first block pointer, wherein the first block pointer comprises a gang block header bit that is not set;

retrieving, in response to the first request, an indirect block using the first block pointer, wherein the indirect block comprises a second block pointer referencing the first block;

retrieving the first block using the second block pointer;

receiving a second request to read a second block, wherein the second request comprises a third block pointer, wherein the third block pointer comprises a disk virtual address (DVA), a birth, and a checksum field, wherein the DVA comprises the gang block header bit that is set and a size field;

retrieving a gang block header using the third block pointer, wherein the gang block header occupies a minimum allocateable portion on a disk and comprises a plurality of block pointers, and wherein each of the plurality of block pointers references a non-contiguous sub-block of disk space;

processing the gang block header to obtain at least two sub-blocks, wherein the size of each sub-block is less than the size of the second block; and

combining the at least two sub-blocks to obtain the second block.

5. The method of claim 4, further comprising:

forwarding the second block to a process that sent the request after the block has been obtained.

6. The method of claim 4, wherein processing the gang blocker header comprises:

retrieving a first sub-block using a first one of the plurality of pointers in the gang block header;

retrieving a second sub-block using a second one of the plurality of pointers in the gang block header.

7. The method of claim 6, further comprising:

storing the first sub-block and the second sub-block in a buffer prior to combining the first sub-block and the second sub-block to obtain the second block.

8. A system, comprising:

a storage pool comprising a first sub-data block, a second sub-data block, a first indirect block, a first data block, a gang block header, and a second indirect block,

wherein the first indirect block comprises a first block pointer referencing the first data block, wherein the first data block is allocated as a contiguous block of space;

wherein the gang block header occupies a minimum allocateable portion in the storage pool,

wherein the gang block header comprises a second block pointer to the first sub-data block and a third block pointer to the second sub-data block,

wherein the first sub-data block and the second sub-data block are located in non-contiguous portions of the storage pool,

wherein a combination of the first-sub data block and the second sub-data block make up a second data block,

wherein the second indirect block comprises a pointer to the gang block header, wherein the pointer comprises a disk virtual address (DVA), a birth, and a checksum field, wherein the DVA comprises a gang block header bit that is set and a size field; and

a storage pool allocator configured to store the second data block using the gang block header and the second indirect block in the storage pool.

9. A computer system for allocating space on a disk comprising:

a processor;

a memory;

a storage device; and

software instructions stored in the memory for enabling the computer system under control of the processor, to;

receive a first request to allocate space on the disk having a first size;

allocate, in response to the first request, a first contiguous space having the first size and storing a first indirect block in the first contiguous space;

store a second indirect block comprising a first block pointer referencing the first indirect block, wherein the first block pointer comprises a first gang block header bit that is not set;

receive a second request to allocate space on the disk having a second size, wherein no contiguous space of the second size exists on the disk;

allocate, in response to the second request, a gang block header, wherein the gang block header occupies a minimum allocateable portion on the disk;

populate the gang block header; and

respond to the second request to allocate space on the disk by storing a second block pointer in the second indirect block, wherein the second block pointer comprises a second gang block header bit that is set, wherein the second block pointer references the gang block header and comprises a disk virtual address (DVA), a birth, and a checksum field and wherein the DVA comprises the second gang block header bit and a size field,

wherein populating the gang block header comprises;

obtaining a second contiguous space on the disk having a third size, wherein the third size is less than the second size,

storing a third pointer to the second contiguous space in the gang block header,

obtaining a third contiguous space on the disk having a fourth size, wherein the fourth size is less than the second size, and

storing a fourth pointer to the third contiguous space in the gang block header.

10. A computer system for retrieving a block comprising:

a processor;

a memory;

a storage device; and

software instructions stored in the memory for enabling the computer system under control of the processor, to;

receive a first request to read a first block, wherein the first request comprises a first block pointer, wherein the first block pointer comprises a gang block header bit that is not set;

retrieve, in response to the first request, an indirect block using the first block pointer, wherein the indirect block comprises a second block pointer referencing the first block;

retrieve the first block using the second block pointer;

receive a second request to read a second block, wherein the second request comprises a third block pointer, wherein the third block pointer comprises a disk virtual address (DVA), a birth, and a checksum field, wherein the DVA comprises the gang block header bit that is set and a size field;

retrieve a gang block header using the third block pointer, wherein the gang block header occupies a minimum allocateable portion on a disk and comprises a plurality of block pointers, and wherein each of the plurality of block pointers references a non-contiguous sub-block of disk space;

process the gang block header to obtain at least two sub-blocks, wherein the size of each sub-block is less than the size of the second block; and

combine the at least two sub-blocks to obtain the second block.

11. A computer readable medium for allocating space on a disk comprising software instructions to:

receive a first request to allocate space on the disk having a first size;

allocate, in response to the first request, a first contiguous space having the first size and storing a first indirect block in the first contiguous space;

store a second indirect block comprising a first block pointer referencing the first indirect block, wherein the first block pointer comprises a first gang block header bit that is not set;

receive a second request to allocate space on the disk having a second size, wherein no contiguous space of the second size exists on the disk;

allocate, in response to the second request, a gang block header, wherein the gang block header occupies a minimum allocateable portion on the disk;

populate the gang block header; and

respond to the second request to allocate space on the disk by storing a second block pointer in the second indirect block, wherein the second block pointer comprises a second gang block header bit that is set, wherein the second block pointer references the gang block header and comprises a disk virtual address (DVA), a birth, and a checksum field and wherein the DVA comprises the second gang block header bit and a size field,

wherein populating the gang block header comprises;

obtaining a second contiguous space on the disk having a third size, wherein the third size is less than the second size,

storing a third pointer to the second contiguous space in the gang block header,

obtaining a third contiguous space on the disk having a fourth size, wherein the fourth size is less than the second size, and

storing a fourth pointer to the third contiguous space in the gang block header.

12. A computer readable medium for retrieving a block comprising software instructions to:

receive a first request to read a first block, wherein the first request comprises a first block pointer, wherein the first block pointer comprises a gang block header bit that is not set;

retrieve, in response to the first request, an indirect block using the first block pointer, wherein the indirect block comprises a second block pointer referencing the first block;

retrieve the first block using the second block pointer;

receive a second request to read a second block, wherein the second request comprises a third block pointer, wherein the third block pointer comprises a disk virtual address (DVA), a birth, and a checksum field, wherein the DVA comprises the gang block header bit that is set and a size field;

retrieve a gang block header using the third block pointer, wherein the gang block header occupies a minimum allocateable portion on a disk and comprises a plurality of block pointers, and wherein each of the plurality of block pointers references a non-contiguous sub-block of disk space;

process the gang block header to obtain at least two sub-blocks, wherein the size of each sub-block is less than the size of the second block; and

combine the at least two sub-blocks to obtain the second block.

13. A network system having a plurality of nodes, comprising:

a storage pool comprising a first sub-data block, a second sub-data block, a first indirect block, a first data block, a gang block header, and a second indirect block,

wherein the first indirect block comprises a first block pointer referencing the first data block, wherein the first data block is allocated as a contiguous block of space;

wherein the gang block header occupies a minimum allocateable portion in the storage pool,

wherein the gang block header comprises a second block pointer to the first sub-data block and a third block pointer to the second sub-data block,

wherein the first sub-data block and the second sub-data block are located in non-contiguous portions of the storage pool,

wherein a combination of the first-sub data block and the second sub-data block make up a second data block,

wherein the second indirect block comprises a pointer to the gang block header, wherein the pointer comprises a disk virtual address (DVA), a birth, and a checksum field, wherein the DVA comprises a gang block header bit that is set and a size field; and

a storage pool allocator configured to store the second data block using the gang block header and the second indirect block in the storage pool,

wherein the storage pool resides on any one of the plurality of nodes, and

wherein the storage pool allocator resides on any one of the plurality of nodes.