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

Patent metadata

Field	Value
Publication number	US-9875024-B2
Application number	US-201414553680-A
Country	US
Kind code	B2
Filing date	Nov 25, 2014
Priority date	Nov 25, 2014
Publication date	Jan 23, 2018
Grant date	Jan 23, 2018

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.

First claim

What is claimed is:

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.

Assignees

• Schreter Ivan
• Eluri Amarnadh Sai
• Sap Se

Inventors

• Schreter Ivan
• Eluri Amarnadh Sai

Classifications

• G06F3/0647

  Migration mechanisms · CPC title

• G06F12/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 title

• G06F3/0604 Primary

  Improving or facilitating administration, e.g. storage management · CPC title

• G06F3/0673

  Single storage device · CPC title

• G06F17/30356

  Physics · mapped topic