Implementing a buffer manager

[nikriek]

Context

For my master's thesis, we looked into extending Hyrise for larger-than-memory workloads using three-tier buffer management. In order to work with larger amounts of data, several approaches have been implemented in Hyrise. First, data compression can be used to reduce the main memory footprint for segments. Second, memory and storage tiering has been successfully applied by Dreseler to place segments on tiers with different characteristics based on a optimization objective and a training algorithm. Buffer managers are still interesting for in-memory databases such as Hyrise, because they enable eviction of binary data to a fast, secondary storage devices such as SSDs without a complicated tiering mechanisms. This discussion should publicly track all our decisions.

What is buffer management

Traditional databases mainly store data on the disk. For query processing, they load one or more pages (smallest storage unit) into main memory buffer pool using a "buffer manager". Pinning avoids their eviction during query processing. When reaching the memory limit of the buffer pool, pages are evicted based on a replacement strategy (e.g. LRU, Clock, Random, MRU …). The actual design of a buffer managers depends on various factors such as the file formats, memory hierarchy, durability guarantees etc.

Potential approaches and why they are unsuitable

In Hyrise, most data structures and segments (vertical partitions of a table) rely on polymorphic vectors (pmr_vector). Classical buffer manager designs are incompatible with this design decision. Classical buffer manager designs would require changing the basic storage assumptions. We also looked into representation-aware containers to support buffer management of vectors. Similarly to Dreseler's work, we evaluated a custom "fancy pointer" with a central hash map or pointer swizzling techniques. However, we found this approach too complex to implement or inefficient.

Another technique to consider is paging with mmap. This was also tested previously with Hyrise. However, mmap for buffer managers has several flaws according to Crotty et al. due performance issues, transactional (un)safety, IO stalls etc. Alternative virtual memory subsystems such as UMap and FastMap are also unsuitable, because they do not allow control over the eviction mechanism according to Leis et al..

Proposed implementation

Recent work by Leis et al. proposes a buffer manager that leverages explicit virtual memory management techniques (I recommend reading it first with a focus on section 3). Their mechanism is easy to implement and flexible. We just need to switch the allocation mechanism as shown in this example:

// Create a ValueSegment. The data is only pinned in the current scope. 
{	
    auto buffer_manager = BufferManager::get();
    auto allocator = PolymorphicAllocator<int>{&buffer_manager};
    auto alloc_guard = AllocatorPinGuard{allocator};
    auto data = pmr_vector<int>(10000, &allocator);
    segment = ValueSegment<int>(std::move(data));
}

// Perform a custom scan operation. SharedPinGuard ensures access to the segment and its vectors
auto count_fives(const ValueSegment &segment) {
    auto count = 0;
    // For illustrative purposes, the pin guard is not in the segment_with_iterators func
    auto pin_guard = SharedPinGuard{segment};
    segment_with_iterators(segment, [&count](auto it, auto end) { 
        for (; it != end; ++it) { 
            count += (*it == 5);
        }
    };
    return count;
}

We adapted their implementation for Hyrise and extended it with multiple tiers and explicit variable-sized pages. Additionally, we added support for Mac OS X. The buffer manager is exposed to all components in Hyrise as a polymorphic memory resource singleton. PinGuards are helper objects that ensure valid memory access to a data structure in the current scope using RAII. For the eviction, we use a Second-Chance FIFO queue as implemented by DuckDB, Kùzu. The data migration policy handles the movement decision with several tiers / NUMA nodes.

Open Questions

• How do we deal with std::vector<bool>? Such vector does not conform to the container interface in C++ and does not offer the required data() method. boost::vector<bool> wastes more memory than needed. We could use a custom compact::vector. However, this needs some adaptions.

TBA

Deliverables

Components / Deliverable	Description	Pull Request
PageID and Frame	Adding basic primitives for access and latching	#2618
Persistence Manager	Adding support for manual IO to SSD	#2621
Volatile Region	Supports access to the virtual memory with mmap etc.	#2620
Buffer Pool	Manages the volatile region, SSD region and the replacement	#2622
Buffer Manager (two tiers)	Combines all previous components and offers methods for memory allocation and pinning	-
Stress Tests	Stress test concurrency for Buffer Manager and Frame	-
Pin Guard	Introduces pin guard that can manage pinning with the buffer manager and vectos	-
Simple Integration	Adds Buffer Manager as a global PMR and integrates it at various places	-
Three Tiers	Add mechanism to support more than two tiers using migration policy	-
Complex Allocation	Add support for slab allocation on pages using jemalloc	-

Future Work

The integration of a buffer managers enables several new and interesting features for Hyrise. This includes:

• Asynchronous IO using AIO or io_uring (Linux only)
• Pre-fetching data in operators
• Buffer-manager optimized algorithms (e.g. external sorting, out-of-core aggregation) or data structures (e.g. B+-Trees)
• WAL and recovery on SSDs

[Bouncner]

Is the pin guard in the count_fives() example just for presentation purposes? Can't we have the pin guard in the segment_iterate call?

Concerning the null_vectors I tend to vote for a simple pmr_vector<uint32t> and a few access methods (assuming we really don't do much magic with NULLs) over such a "verbose" third party library.

Another question I have would be: how could we efficiently store and load data from disk? Is it possible to show a little POC that demonstrates how that could be achieved?

[nikriek]

Is the pin guard in the count_fives() example just for presentation purposes? Can't we have the pin guard in the segment_iterate call?

You are right. We are doing this already. I added it to outer scope for illustrative purposes.

Concerning the null_vectors I tend to vote for a simple pmr_vector<uint32t> and a few access methods (assuming we really don't do much magic with NULLs) over such a "verbose" third party library.

would this require a subclassing? I think, this is discouraged in c++

Another question I have would be: how could we efficiently store and load data from disk? Is it possible to show a little POC that demonstrates how that could be achieved?

I can add an example workflow, yes. It is as efficient as standard POSIX IO. Async IO is also possible, but more complex to implement.

[mweisgut]

Another question I have would be: how could we efficiently store and load data from disk? Is it possible to show a little POC that demonstrates how that could be achieved?

To persist the discussion about loading data: The loading of persistent data at the start of Hyrise was not part of the work and is orthogonal to it. However, with the current binary loading, loaded data is buffer-managed when the vectors have been allocated with the buffer manager. After implementing the buffer manager, it would be a potential follow-up project to take care of the persistence of data and to implement a mapping between pages and data structures (e.g., segments) so that persisted pages can be mapped to (and eventually loaded into) to the buffer pool(s) virtual memory region(s). This mapping could, for example, be stored in a defined (meta) page.

[nikriek]

Thank you for the summary. We also need to ensure that the virtual memory region has the same absolute address for recovery. Luckily, this can be specified in the mmap syscall as a hint.

[Bouncner]

@nikriek: Why would the addresses be of relevance?

Something else that came up during the master's project. We cannot "put data into a vector" (e.g., by changing the internal pointer that data()) returns.
Or is this what you meant with the same absolute address, Niklas?

[nikriek]

This is what I meant. I also tried an approach with representation-aware containers which allows the customization of the internal pointer. Too complicated and not portable...

[Bouncner]

One question that continues to bother me is how to integrate persistency here. It's by no means part of your current work, but I still want to understand the steps that we need to take if we decide to go in this direction.

In the master's project we did a simple thing that appeared to work quite well:

• segments are no longer managing their data theirselves
• they are passed the data via "some" pointer and use std::span to "look like" containers to everybody (code changes have been really small)
• the raw data for each segment is stored in files

Now, assume we have a file that stores the dictionary data for a particular segment. Could you explain (again, not asking you to implement that) how to load this data into the buffer and retrieve "the pointer" so that the segment can be instantiated with this pointer?

[nikriek]

Regarding our discussion about string vectors and buffer manager, I found this PR to be really helpful: #2593. The changes would allow us to store multiple variable-sized strings in a contiguous array that we can store on a page.

[Bouncner]

Yes, the project was @klauck 's idea and we found strings to be a major issue in last year's master project (the one that used mmap etc.).

[Bouncner]

And given the performance numbers (I updated the description yesterday), it's also worth it to integrate the new segment type.