Buddy system space allocation management

• US 6,032,160 A
• Filed: 06/05/1997
• Issued: 02/29/2000
• Est. Priority Date: 02/10/1995
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Lehman, Tobin Jon
• Primary Examiner(s): Lintz, Paul R.
• Application Number:
  US08/869,585
• Time in Patent Office: 999 Days
• Field of Search: 707/205, 707/200, 711/170, 711/211
• US Class Current: 1/1
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 16/2219 Large Object storage; Management thereof
• CPC Class Codes: Y10S 707/99956 File allocation

Abstract

A relational data base management system that stores and retrieves large data objects (LOBs) from data base storage includes a data manager that maintains LOB data space allocation according to the buddy system with two types of allocation pages, called regular buddy space (RBS) pages and super buddy space (SBS) pages. The RBS pages control buddy spaces comprising equal-size areas of the LOB data space in which LOB buddy segments are stored. The SBS pages control the RBS pages. The RBS pages include a pointer array that contains the forward-most location of where searching for a free storage space should begin and a counter array that indicates the number of free buddy segments in a buddy space for a particular buddy segment size. The SBS pages include analogous pointer and counter arrays that refer to the RBS pages and indicate the location and extent of free storage space, and also include a divided-space array and an SBS page directory.

Claims

1. A space management system for use in managing storage allocation for the storage of data values of a data type corresponding to large data objects (LOBs) stored in storage locations of a data base of a computer system having a central processor, a memory unit, and a storage subsystem containing a LOB data space in which the LOB data values are stored, the space management system comprising:

a plurality of regular-tier allocation page data structures that indicate, for a predetermined number of LOB data space storage locations comprising a regular-tier buddy space, whether the storage locations are free or allocated such that each regular-tier allocation page identifies free regular-tier buddy spaces of the LOB data space in which to store the LOB data value and thereby control data access to the regular-tier buddy spaces;

a plurality of super-tier allocation page data structures of the LOB data space that indicate, for a predetermined number of regular-tier pages comprising a super-tier buddy space, whether the regular-tier pages are free or allocated, to identify one or more free super-tier buddy spaces in which to store the LOB data value, where the LOB data value has a size such that it cannot be stored in less than one super-tier buddy space, and thereby control data access to the super-tier buddy spaces, such that at least one super-tier allocation page identifies free super-tier buddy spaces over the entire LOB data space; and

a data manager controller that manages the regular-tier and the super-tier allocation pages by receiving requests from users of the computer system for access to LOB data values and allocating storage locations in the LOB data space identified by the super-tier allocation pages and regular-tier allocation pages, respectively, as free for the storage of LOB data values and freeing selected LOB data space storage locations that are no longer needed for the storage of LOB data values.

2. A space management system as defined in claim 1, wherein each regular-tier allocation page controls a predetermined number of LOB data space storage locations comprising a storage page of the relational data base.

3. A space management system as defined in claim 2, wherein the data manager controller allocates blocks of storage pages according to an increasing binary sequence of block sizes.

4. A space management system as defined in claim 3, wherein the regular-tier allocation pages control storage pages that comprise 1 kilobyte blocks of LOB data space storage locations and the binary sequence of regular-tier page block sizes includes a smallest block comprising a single storage page.

5. A space management system as defined in claim 3, wherein each regular-tier allocation page includes:

a pointer array data structure that points to a free block of each regular-tier allocation page size; and

a count array data structure that identifies the number of storage location blocks that are allocated for storing data for each size of the binary sequence.

6. A space management system as defined in claim 5, wherein the data manager controller allocates blocks of LOB data space storage pages in units of regular-tier buddy space storage pages according to an increasing binary sequence of regular-tier allocation page block sizes.

7. A space management system as defined in claim 6, wherein each super-tier allocation page includes:

a pointer array data structure that points to a free regular-tier allocation page; and

a count array data structure that identifies, for each size of regular-tier allocation page block in the binary sequence, the number of regular-tier allocation pages that are free.

8. A space management system as defined in claim 7, wherein a first super-tier allocation page indicates a starting point for searching for a free regular-tier allocation page.

9. A space management system as defined in claim 8, further including a divided page array data structure in which the data manager controller indicates, for each super-tier allocation page, whether that page controls super-tier buddy spaces that have been subdivided so as to include allocated blocks of regular-tier buddy spaces smaller than one super-tier buddy space in size.

10. A space management system as defined in claim 2, wherein the regular-tier allocation pages and the super-tier allocation pages are stored in the LOB data space.

11. A space management system as defined in claim 1, wherein the data base in which the data values are stored is a relational data base.

12. A method of managing storage allocation for storage of data values in a data base wherein system users request access to data values of a data type corresponding to large data objects (LOBS) stored in storage locations of a LOB data space of a data base of a computer system having a central processor, a memory unit, and a storage subsystem containing the LOB data space so as to allocate free storage locations of the LOB data space for the storage of new LOB data values and to free selected storage locations that are no longer needed for the storage of past LOB data values, the method comprising the steps of:

receiving a user request for access to the LOB data space for storage of a LOB data value having a size comprising a predetermined number of storage locations necessary for storage of the LOB data value in the LOB data space;

examining a super-tier allocation page data structure of the LOB data space with a data manager controller, wherein the super-tier allocation page indicates, for a higher-tier block of LOB data space storage locations comprising a predetermined number of storage locations, whether super-tier blocks over the entire LOB data space are free or allocated, to identify one or more free super-tier blocks in which to store the LOB data value where the LOB data value has a size such that it cannot be stored in less than one super-tier block;

allocating the tree block of storage locations identified in the step of examining, using the data manager controller, for storage of the LOB data value where the LOB data value has a size such that it cannot be stored in less than one super-tier block;

examining a regular-tier allocation page data structure of the LOB data space with the data manger controller, wherein the regular-tier allocation page data structure indicates, for a regular-tier of LOB data space storage locations comprising a predetermined number of storage locations, whether regular-tier blocks over a predetermined number of storage locations equal to a smallest super-tier block, are free or allocated, to identify one or more free regular-tier blocks in which to store the LOB data value;

allocating the identified free regular-tier blocks for storage of the LOB data value if it was not allocated previously by the data manger controller; and

updating data structures of the super-tier allocation pages and regular-tier allocation pages to indicate the identified storage locations as being allocated.

13. A method of managing storage allocation as defined in claim 12, wherein the step of allocating identified regular-tier blocks of storage comprises allocating blocks of storage pages according to an increasing binary sequence of block sizes.

14. A method of managing storage allocation as defined in claim 13, wherein the step of allocating regular-tier blocks comprises allocating storage pages in 1 kilobyte blocks of LOB data space storage locations and the binary sequence of regular-tier page block sizes includes a smallest block comprising a single storage page.

15. A method of managing storage allocation as defined in claim 14, wherein the step of updating data structures includes:

updating a pointer array data structure of each regular-tier allocation page that points to a free block of each regular-tier allocation page size; and

updating a count array data structure that identifies the number of storage location blocks that are allocated for storing data for each size of the binary sequence.

16. A method of managing storage allocation as defined in claim 15, wherein the step of allocating free super-tier blocks comprises allocating blocks of LOB data space storage pages in units of regular-tier buddy space storage pages according to an increasing binary sequence of regular-tier allocation page block sizes.

17. A method of managing storage allocation as defined in claim 16, wherein the step of updating includes:

updating a pointer array data structure of each super-tier allocation page that points to a free regular-tier allocation page of each super-tier allocation page size; and

updating a count array data structure of each super-tier allocation page that identifies, for each size of super-tier allocation page in the binary sequence, the number of super-tier allocation pages that are free.

18. A computer system comprising:

a central processor unit;

a memory unit;

at least one storage device for the storage of data values of a data type corresponding to large data objects (LOBs), the storage device containing a LOB data space having LOB data values of a data base;

a data base management system that permits a computer system user to generate requests for access to LOBs of a data base, the data base management system including;

a plurality of regular-tier allocation page data structures that indicate, for a predetermined number of LOB data space storage locations comprising a regular-tier buddy space, whether the storage locations are free or allocated such that each regular-tier allocation page identifies free regular-tier buddy spaces of the LOB data space in which to store the LOB data value and thereby control data access to the regular-tier buddy spaces;

a plurality of super-tier allocation page data structures of the LOB data space that indicate, for a predetermined number of regular-tier pages comprising a super-tier buddy space, whether the regular-tier pages are free or allocated, to identify one or more free super-tier buddy spaces in which to store the LOB data value, where the LOB data value has a size such that it cannot be stored in less than one super-tier buddy space, and thereby control data access to the super-tier buddy spaces, such that at least one super-tier allocation page identifies free super-tier buddy spaces over the entire LOB data space; and

a data manager controller that manages the regular-tier and the super-tier allocation pages by receiving requests from users of the computer system for access to LOB data values and allocating storage locations in the LOB data space identified by the super-tier allocation pages and regular-tier allocation pages, respectively, as free for the storage of LOB data values and freeing selected LOB data space storage locations that are no longer needed for the storage of LOB data values.

19. A computer system as defined in claim 18, wherein each regular-tier allocation page controls a predetermined number of LOB data space storage locations comprising a storage page of the data base.

20. A computer system as defined in claim 19, wherein the data manager controller allocates blocks of storage pages according to an increasing binary sequence of block sizes.

21. A computer system as defined in claim 19, wherein the regular-tier allocation pages control storage pages that comprise 1 kilobyte blocks of LOB data space storage locations and the binary sequence of regular-tier page block sizes includes a smallest block comprising a single storage page.

22. A computer system as defined in claim 19, wherein each regular-tier allocation page includes:

a pointer array data structure that points to a free block of each regular-tier allocation page size; and

a count array data structure that identifies the number of storage location blocks that are allocated for storing data for each size of the binary sequence.

23. A computer system as defined in claim 22, wherein the data manager controller allocates blocks of LOB data space storage pages in units of regular-tier buddy space storage pages according to an increasing binary sequence of regular-tier allocation page block sizes.

24. A computer system as defined in claim 23, wherein each super-tier allocation page includes:

a pointer array data structure that points to a free regular-tier allocation page; and

a count array data structure that identifies, for each size of regular-tier allocation page block in the binary sequence, the number of regular-tier allocation pages that are free.

25. A computer system as defined in claim 24, wherein a first super-tier allocation page indicates a starting point for searching for a free regular-tier allocation page.

26. A computer system as defined in claim 25, further including a divided page array data structure in which the data manager controller indicates, for each super-tier allocation page, whether that page controls super-tier buddy spaces that have been subdivided so as to include allocated blocks of regular-tier buddy spaces smaller than one super-tier buddy space in size.

27. A computer system as defined in claim 18, wherein the regular-tier allocation pages and the super-tier allocation pages are stored in the LOB data space.

28. A computer system as defined in claim 18, wherein the data base in which the LOB data values are stored is a relational data base.

29. A program storage device readable by a processor machine, tangibly embodying a program of instructions executable by the processor machine to perform method steps for managing storage allocation for storage of data values in a relational data base wherein system users request access to data values of a data type corresponding to large data objects (LOBs) stored in storage locations of a LOB data space of a relational data base of a computer system having a central processor, a memory unit, and a storage subsystem containing the LOB data space so as to allocate free storage locations of the LOB data space for the storage of new LOB data values and to free selected storage locations that are no longer needed for the storage of past LOB data values, the method steps performed by the processor machine comprising the steps of:

receiving a user request for access to the LOB data space for storage of a LOB data value having a size comprising a predetermined number of storage locations necessary for storage of the LOB data value in the LOB data space;

examining a super-tier allocation page data structure of the LOB data space with a data manager controller, wherein the super-tier allocation page data structure indicates, for a higher-tier block of LOB data space storage locations comprising a predetermined number of storage locations, whether super-tier blocks over the entire LOB data space are free or allocated, to identify one or more free super-tier blocks in which to store the LOB data value where the LOB data value has a size such that it cannot be stored in less than one super-tier block;

allocating the free block of storage locations identified in the step of examining, using the data manager controller, for storage of the LOB data value where the LOB data value has a size such that it cannot be stored in less than one super-tier block;

examining a regular-tier allocation page data structure of the LOB data space with the data manager controller, wherein the regular-tier allocation page data structure indicates, for a regular-tier of LOB data space storage locations comprising a predetermined number of storage locations, whether regular-tier blocks over a predetermined number of storage locations equal to a smallest super-tier block, are free or allocated, to identify one or more free regular-tier blocks in which to store the LOB data value;

allocating the identified free regular-tier blocks for storage of the LOB data value if it was not allocated previously by the data manager controller; and

updating data structures of the super-tier allocation pages and regular-tier allocation pages to indicate the identified storage locations as being allocated.

30. A program storage device as defined in claim 29, wherein the step of allocating identified regular-tier blocks of storage comprises allocating blocks of storage pages according to an increasing binary sequence of block sizes.

31. A program storage device as defined in claim 30, wherein the step of allocating regular-tier blocks comprises allocating storage pages in 1 kilobyte blocks of LOB data space storage locations and the binary sequence of regular-tier page block sizes includes a smallest block comprising a single storage page.

32. A program storage device as defined in claim 31, wherein the step of updating data structures includes:

updating a pointer array data structure of each regular-tier allocation page that points to a free block of each regular-tier allocation page size; and

updating a count array data structure that identifies the number of storage location blocks that are allocated for storing data for each size of the binary sequence.

33. A program storage device as defined in claim 32, wherein the step of allocating free super-tier blocks comprises allocating blocks of LOB data space storage pages in units of regular-tier buddy space storage pages according to an increasing binary sequence of regular-tier allocation page block sizes.

34. A program storage device as defined in claim 33, wherein the step of updating includes:

updating a pointer array data structure of each super-tier allocation page that points to a free regular-tier allocation page of each super-tier allocation page size; and

updating a count array data structure of each super-tier allocation page that identifies, for each size of super-tier allocation page in the binary sequence, the number of super-tier allocation pages that are free.