Efficient block-level space allocation for multi-version concurrency control data

• US 9,875,024 B2
• Filed: 11/25/2014
• Issued: 01/23/2018
• Est. Priority Date: 11/25/2014
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP SE
• Inventors: Schreter, Ivan, Eluri, Amarnadh Sai
• Primary Examiner(s): Bertram, Ryan
• Assistant Examiner(s): TA, TRANG KHANH
• Application Number:
  US14/553,680
• Publication Number:
  US 20160147448A1
• Time in Patent Office: 1,155 Days
• Field of Search: None
• CPC Class Codes: G06F 12/00 Accessing, addressing or allocating within memory systems or architectures digital input from, or digital output to record carriers, e.g. to disk storage units, G06F3/06
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 16/2329 using versioning
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 3/0647 Migration mechanisms
• CPC Class Codes: G06F 3/0673 Single storage device

Abstract

Lockless allocation of a block from a page is initiated by computing a needed block size from an original block header value. Thereafter, a currently used block size and a capacity of the page are determined. A new block size is then computed based on the currently used block size and the needed block size and a remaining capacity of the page. A new block header value is subsequently generated that includes the determined new block size and the determined remaining capacity of the page The original block header value is then replaced with the new block header value. Related apparatus, systems, techniques and articles are also described.

Claims

1. A method comprising:

initiating lockless allocation of a block from a page by computing a needed block size from an original value in a page header, the original value comprising a currently used block size of the page and a capacity of the page;

computing a next used block size based on the currently used block size and the needed block size and a remaining capacity of the page after allocation of the block from the page;

generating a new value comprising the next used block size of the page and the remaining capacity of the page; and

replacing the original value in the page header with the new value.

2. The method of claim 1, wherein the replacing uses a compare and swap operation.

3. The method of claim 2, wherein the computing and generating are iteratively implemented until the original value is replaced with the new value in the page header.

4. The method of claim 1 further comprising:

returning a pointer to the block after replacing the original value in the page header with the new value in the page header.

5. The method of claim 4, wherein the pointer points to a location in the page that is computed from the block size from the page header plus the currently used block size.

6. The method of claim 4, wherein the location is part of a block handle.

7. The method of claim 1, wherein the initiating computing, generating, and replacing are implemented by at least one hardware data processor.

8. The method of claim 7, wherein the at least one hardware data processor forms part of an in-memory database.

9. A method comprising:

initiating allocation of a block from a new page in a multi-version concurrency control (MVCC) page chain by obtaining a first current last page number in the MVCC page chain;

acquiring a mutex lock that prevents allocation of pages in the page chain;

obtaining a second current last page number in the MVCC page chain;

attempting to allocate a block from a last page in the MVCC page chain if the first current last page number and the second current last page number differs;

allocating a new MVCC page in the MVCC page chain if the attempt to allocate the block fails or if there is no change in the last page;

allocating a new block with a specified block size from a newly allocated page using lockless block allocation logic that returns a pointer to the block;

appending the allocated new page to the MVCC page chain; and

releasing the mutex lock and returning a block handle holding the allocated new block.

10. The method of claim 9, wherein the method is implemented by at least one hardware data processor.

11. The method of claim 10, wherein the at least one hardware data processor forms part of an in-memory database.

12. A method comprising:

initiating allocation of a block from a last page in a multi-version concurrency control (MVCC) page chain by attempting to return a block from a lockless free list, or, if no block is available, then allocating a block from the last page;

loading a last page of the MVCC page chain;

attempting to allocate the block using lockless block allocation from the last page in the MVCC page chain if the last page is valid;

allocating the block from a new page if the attempt to allocate fails or there are no changes in the pages; and

returning a block handle associated with allocated new block.

13. The method of claim 12, wherein the lockless free list is a free reserved stub list, a free stub list, or free MVCC block list.

14. The method of claim 13, wherein each of the operations are implemented by at least one hardware data processor.

15. The method of claim 14, wherein the at least one hardware data processor forms part of an in-memory database.

16. The method of claim 13, wherein the free list comprises destroyed MVCC blocks and is managed as a lock-less queue.

17. The method of claim 13 further comprising:

returning the block from an MVCC free block list for blocks with header and data sections.

18. The method of claim 13 further comprising:

returning the block from a free reserved stub list or free stub list for stub timestamp blocks;

wherein the block comprises only a header section.

19. The method of claim 13 further comprising:

returning the block from a free stub block list or allocating the block from the pages using a lock-less block allocation algorithm;

wherein the block comprises only a header section.

20. The method of claim 13 further comprising:

attempting to allocate a block from the MVCC pages of the MVCC page chain either from a last page or from a newly allocated page.