Allocation of storage for a database

• US 7,421,446 B1
• Filed: 08/25/2004
• Issued: 09/02/2008
• Est. Priority Date: 08/25/2004
• Status: Active Grant

• Current Assignee: Unisys Corporation
• Original Assignee: Unisys Corporation
• Inventors: Bruso, Kelsey L., Plasek, James M.
• Primary Examiner(s): Vo; Tim
• Assistant Examiner(s): Dwivedi; Mahesh H
• Application Number:
  US10/925,531
• Time in Patent Office: 1,469 Days
• Field of Search: 707/102, 707/3, 711/100, 711/168
• US Class Current: 1/1
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

Various approaches for allocating storage for a file are disclosed. In one approach, in response to each call to allocate an available portion of storage, one of a plurality of allocation approaches is selected based on a value of a file attribute associated with the file. If a first one of the allocation approaches is selected, a portion of storage is selected for storage of data using an approach that emphasizes storage of data in sequential physical storage. If a second one of the allocation approaches is selected, a portion of storage using an approach that emphasizes maintaining concurrent access to the file.

Claims

1. A method for allocating storage for a file, comprising:

reserving a quantity of sequential physical storage for the file;

selecting, in response to each call to allocate an available portion of the storage of the file, one of a plurality of allocation approaches based on a value of a file attribute associated with the file;

establishing a plurality of allocation records for the file and assigning initial respective portions of the reserved quantity of storage with the allocation records, wherein for the value of the file attribute specifying a first of the allocation approaches, the initial respective portions increase in quantity from a first of the allocation records to a last of the allocation records, and for the value of the file attribute specifying a second of the allocation approaches, the initial respective portions have equal quantities;

selecting for storage of data, in response to selection of the first allocation approach, a portion of storage of the file from one of the respective portions assigned to one of the allocation records, wherein the selecting under the first approach begins with the first allocation record and proceeds toward the last allocation record in seeking an available portion to allocate wherein physical storage is allocated based on maintaining sequentially allocated portions;

selecting for storage of data, in response to selection of the second allocation approach, a portion of storage of the file from one of the respective portions assigned to one of the allocation records, wherein the selecting under the second approach begins with an allocation record other than the first allocation record in seeking an available portion to allocate wherein physical storage is allocated based on maintaining concurrent access to the file; and

in response to an allocation record having no available portion of storage for the file, reassigning portions from one allocation record to another, wherein reassigning for the file attribute indicating the first approach reassigns portions from a next successive allocation record, and reassigning for the file attribute indicating the second approach balances respective portions assigned to the allocation records.

2. The method of claim 1, further comprising:

wherein the first one of the allocation approaches includes,

selecting as a current portion, a portion at the beginning of the reserved quantity of storage;

attempting to lock the current portion of the reserved quantity of storage;

allocating for storage of data, in response to a lock granted to the current portion, an amount of storage from the current portion;

selecting, in response to denial of the lock of the current portion, a new portion that sequentially follows the current portion, and repeating the steps of attempting, allocating, and selecting using the new portion as the current portion.

3. The method of claim 2, further comprising queuing for a lock on the portion at the beginning of the reserved quantity of storage in response to denial of locks for each other portion of the reserved quantity of storage.

4. The method of claim 1, further comprising:

wherein the second one of the allocation approaches includes,

selecting at random as a current portion, one of a plurality of portions of the reserved quantity of storage;

attempting to lock the current portion of the reserved quantity of storage;

allocating for storage of data, in response to a lock granted to the current portion, an amount of storage from the current portion;

selecting, in response to denial of the lock of the current portion, a new portion that sequentially follows the current portion, and repeating the steps of attempting, allocating, and selecting using the new portion as the current portion.

5. The method of claim 4, further comprising queuing for a lock on the portion of the reserved quantity of storage selected at random in response to denial of locks for each other portion of the reserved quantity of storage.

6. The method of claim 1, further comprising:

wherein the second one of the allocation approaches includes,

selecting a portion of the reserved quantity of storage in response to specification of the portion in an allocation request;

attempting to lock the portion of the reserved quantity of storage;

allocating for storage of data, in response to a lock granted to the portion, an amount of storage from the portion;

queuing for a lock on the portion of the reserved quantity of storage in response to a denial of a lock for the portion of storage.

7. The method of claim 1, further comprising:

associating, in response to de-allocation of a quantity of storage from storage of file data, the de-allocated quantity of storage with one of the allocation records;

for each portion of storage associated with an allocation record, identifying as previously used storage each de-allocated quantity of storage, and identifying as never-used storage each quantity of storage that has not been selected for allocation to the file;

wherein selecting a portion of storage for storage of data, includes selecting a quantity first from previously used storage in an allocation record, and in response to no previously used storage being associated with the allocation record, selecting a quantity from never-used storage of the allocation record.

8. The method of claim 7, further comprising locking an allocation record for exclusive access prior to performing the selecting using the first allocation approach and the selecting using the second allocation approach.

9. The method of claim 8, further comprising:

wherein the allocation records are ordered first to last, and the respective portions of storage associated with the allocation records are sequential ranges of storage addresses, with a range having a beginning address of the reserved storage being associated with the first allocation record and each successively addressed range being associated with a successive one of the allocation records;

wherein the first one of the allocation approaches includes,

selecting the first allocation record as a current allocation record;

attempting to lock the current allocation record;

allocating for storage of data, in response to a lock granted to the current allocation record, an amount of storage from the current allocation record;

selecting, in response to denial of the lock of the current allocation record, a succeeding allocation record of the current allocation record, and repeating the steps of attempting, allocating, and selecting using the succeeding allocation record as the current allocation record.

10. The method of claim 9, further comprising queuing for a lock on the first allocation record in response to denial of locks for each other allocation record.

11. The method of claim 8, further comprising:

wherein the allocation records are ordered first to last, and the respective portions of storage associated with the allocation records are sequential ranges of storage addresses, with a range having a beginning address of the reserved storage being associated with the first allocation record and each successively addressed range being associated with a successive one of the allocation records;

wherein the second one of the allocation approaches includes,

selecting at random an initial one of the plurality of allocation records as a current allocation record;

attempting to lock the current allocation record;

allocating for storage of data, in response to a lock granted to the current allocation record, an amount of storage associated with the current allocation record;

selecting, in response to denial of the lock of the current allocation record, a succeeding allocation record of the current allocation record, and repeating the steps of attempting, allocating, and selecting using the succeeding allocation record as the current allocation record.

12. The method of claim 11, further comprising queuing for a lock on the initial one of the allocation records in response to denial of locks for each other allocation record.

13. The method of claim 8, further comprising:

wherein the allocation records are ordered first to last, and the respective portions of storage associated with the allocation records are sequential ranges of storage addresses, with a range having a beginning address of the reserved storage being associated with the first allocation record and each successively addressed range being associated with a successive one of the allocation records;

wherein the second one of the allocation approaches includes,

selecting an allocation record in response to specification of the allocation record in an allocation request;

attempting to lock the allocation record;

allocating for storage of data, in response to a lock granted to the allocation record, an amount of storage associated with the allocation record;

queuing for a lock on the allocation record in response to a denial of a lock for the allocation record.

14. An apparatus for allocating storage for a file, comprising:

means for reserving a quantity of sequential physical storage for the file;

means for selecting, in response to each call to allocate an available portion of the storage of the file, one of a plurality of allocation approaches based on a value of a file attribute associated with the file;

means for establishing a plurality of allocation records for the file and for assigning initial respective portions of the reserved quantity of storage with the allocation records, wherein for the value of the file attribute specifying a first of the allocation approaches, the initial respective portions increase in quantity from a first of the allocation records to a last of the allocation records, and for the value of the file attribute specifying a second of the allocation approaches, the initial respective portions have equal quantities;

means for selecting for storage of data, responsive to selection of the first allocation approach, a portion of storage of the file from one of the respective portions assigned to one of the allocation records, wherein the selecting under the first approach begins with the first allocation record and proceeds toward the last allocation record in seeking an available portion to allocate wherein physical storage is allocated based on maintaining sequentially allocated portions;

means for selecting for storage of data, responsive to selection of the second allocation approach, a portion of storage of the file from one of the respective portions assigned to one of the allocation records, wherein the selecting under the second approach begins with an allocation record other than the first allocation record in seeking an available portion to allocate wherein physical storage is allocated based on maintaining concurrent access to the file and

means, responsive to an allocation record having no available portion of storage for the file, for reassigning portions from one allocation record to another, wherein reassigning for the file attribute indicating the first approach reassigns portions from a next successive allocation record, and reassigning for the file attribute indicating the second approach balances respective portions assigned to the allocation records.

15. A system for allocating storage for a database file, comprising:

a data processing system;

a quantity of retentive storage reserved for allocation to a database file and coupled to the data processing system, wherein the quantity occupies sequential physical locations;

a file attribute associated with the database file, wherein the value of the file attribute indicates one of a plurality of allocation approaches for allocating storage from the reserved storage to the file;

a plurality of allocation records associated with respective portions of the reserved quantity of storage, wherein initially respective portions of the reserved quantity of storage are assigned to the allocation records, for the value of the file attribute specifying a first of the allocation approaches, the initial respective portions increase in quantity from a first of the allocation records to a last of the allocation records, and for the value of the file attribute specifying a second of the allocation approaches, the initial respective portions have equal quantities; and

a database management system (DBMS) hosted by the data processing system and coupled to the quantity of retentive storage and to the allocation records, the DBMS configured to;

select, in response to each call to allocate an available portion of reserved storage, one of the plurality of allocation approaches based on the a value of the file attribute,

select for storage of data, in response to selection of the first allocation approach, a portion of reserved storage of the file from one of the respective portions assigned to one of the allocation records, wherein the selecting under the first approach begins with the first allocation record and proceeds toward the last allocation record in seeking an available portion to allocate and is based on attempting to store the data in sequential physical storage, and

select for storage of data, in response to selection of the second allocation approach, a portion of reserved storage of the file from one of the respective portions assigned to one of the allocation records, wherein the selecting under the second approach begins with an allocation record other than the first allocation record in seeking an available portion to allocate and is based on attempting to maintain concurrent access to the database file

reassign, in response to an allocation record having no available portion of storage for the file, portions from one allocation record to another, wherein reassigning for the file attribute indicating the first approach reassigns portions from a next successive allocation record, and reassigning for the file attribute indicating the second approach balances respective portions assigned to the allocation records.