202406271727
Status: #idea
Tags: e6data

Umbra

• Modify LeanStore (the buffer manager) to support variable size pages
• Page sizes start at 64KiB and double. No upper bound
• Buffer pool is allowed to use upto half of total system memory
• No need to specify the amount of memory for each page size

2.1 - Buffer Pool Memory Management

• mmap to create a mapping which reserves a contiguous chunk of virtual memory. No physical memory is consumed
• These regions are partitioned into page-sized chunks. Ref. Figure 1
• When buffer frame is active, pread is used to read data from disk to memory
• When buffer becomes inactive, we write changes using pwrite and allows kernel to immediately reuse the memory
• Cooling pages are placed in a FIFO queue, and evicted when they they reach the end

2.2 - Pointer Swizzling

• Since references to pages are now decentralised, page eviction is more complicated
• Uses a $B^{+}$-tree to store swip hierarchy

2.3 - Versioned Latches

• RW lock and R-lock (allows multiple readers)
• Uses optimistic latching, i.e. every thread makes changes, and rolls back if lock is unavailable

2.4 - Buffer Managed Relations

• Relations are stored in $B^{+}$-trees, with synthetic 8-byte tuple identifiers as keys
• Insertions
  • Tuple ID’s increase monotonically to avoid splitting the nodes during insertions
    • As a consequence, arbitrary insert patterns are handled equally well
  • Smallest page size that can fit the tuple is chosen
• Tuples in a leaf page are column-major
  • Fixed size attributes are stored at the stage of the page
  • Variable size attributes are stored densely at the end of the page
  • This data layout is not optimal for disk.
    • Future work is to integrate alternative storage layouts (like DataBlocks) for cold parts of the data
• Each page has one owning swip
  • In order to prevent full traversals of the three, an optimistic latch is maintained on the parent of the current leaf node during current table scans

Conclusion

• Looks the buffer manager seems to be great. Has a good number of optimisations, which refer to other papers.
• Look into LeanStore for more details about buffer manager. Look into DataBlocks for on-disk storage format.
• Test is run on a single SSD. However, this is more relevant, especially if we plan to use a burst buffer for spills.

References