Memory allocation buffer for reduction of heap fragmentation
Inventors
Assignees
Publication Number
US-11899937-B2
Publication Date
2024-02-13
Expiration Date
2033-01-18
Interested in licensing this patent?
MTEC can help explore whether this patent might be available for licensing for your application.
Abstract
Systems and methods of a memory allocation buffer to reduce heap fragmentation. In one embodiment, the memory allocation buffer structures a memory arena dedicated to a target region that is one of a plurality of regions in a server in a database cluster such as an HBase cluster. The memory area has a chunk size (e.g., 2 MB) and an offset pointer. Data objects in write requests targeted to the region are received and inserted to the memory arena at a location specified by the offset pointer. When the memory arena is filled, a new one is allocated. When a MemStore of the target region is flushed, the entire memory arenas for the target region are freed up. This reduces heap fragmentation that is responsible for long and/or frequent garbage collection pauses.
Core Innovation
The invention provides systems and methods of a memory allocation buffer designed to reduce heap fragmentation in distributed databases such as HBase. The disclosed memory allocation buffer structures a memory arena dedicated to a target region within a server that hosts multiple regions. In essence, this memory arena uses a chunk-size and an offset pointer to allocate space for data objects in write requests targeted to the designated region. As data is received, it is inserted at locations specified by the offset pointer within the memory arena. When the current arena is full, a new chunked memory arena is allocated. Upon flushing a MemStore of the target region, the entire set of memory arenas allocated for that region is freed in one contiguous block, thereby significantly reducing fragmentation.
The underlying problem addressed by this invention is the growing issue of long and/or frequent garbage collection pauses in Java-based distributed databases as heap sizes increase. These pauses are caused primarily by heap fragmentation in the old generation memory area, where traditional Java garbage collectors like Concurrent Mark-Sweep (CMS) fail to compact free space efficiently. Fragmentation occurs because data allocated for different MemStores of various regions becomes intermixed in the heap over time, leading to scattered free space insufficient for larger memory allocations and triggering expensive stop-the-world full garbage collections. Furthermore, existing Java Thread-Local Allocation Buffers (TLABs) do not resolve this issue as data for different regions remains mixed since a single thread processes requests for multiple regions.
The memory allocation buffer (referred to as MemStore-Local Allocation Buffer or MSLAB) solves this problem by allocating dedicated contiguous memory arenas per region in the heap for buffering write data. This dedicated allocation keeps data for each region consolidated, improves CPU cache locality for reads, and upon MemStore flush, allows freeing a large contiguous free memory chunk. This approach reduces heap fragmentation, lowers the frequency and duration of garbage collection pauses, and thus improves latency and stability in database clusters managing large heaps.
Claims Coverage
The patent includes three independent claims covering a method, a server system, and a non-transitory machine-readable storage medium implementing the memory allocation technique. These independent claims share common inventive features focused on managing memory arenas dedicated to individual regions in a distributed computing system and operations for tracking and flushing data to reduce fragmentation.
Tracking usage of a dedicated memory arena with an offset pointer
The system tracks usage of a memory arena in the heap dedicated to a target region, utilizing an offset pointer that tracks the previous end location of written data so that subsequent writes continue from this location. The offset pointer resets when allocating a new chunk for that region.
Determining a usage threshold to trigger data flushing
Based on usage tracking, the system determines when the memory arena reaches a usage threshold, which may be based on percentage of used space or quantity of stored data, triggering flushing of data from the memory arena to a storage system.
Allocating write data contiguously within the dedicated memory arena
Write requests received for a target region have their data objects stored in contiguous space from the dedicated memory arena at positions continued from the previous end, and the offset pointer is incremented accordingly.
Allocating a new memory arena chunk when insufficient space
If the current memory arena lacks sufficient free space for a new data object, a new contiguous memory arena chunk is allocated for the target region to continue allocations.
Flushing data from the memory arena and freeing contiguous space
When flushing the MemStore data, the data in the dedicated contiguous memory arena is flushed to storage, and because the arena is contiguous, the freed space in the heap is also contiguous, effectively reducing fragmentation.
Supporting multiple regions with distinct memory arenas
The method and server maintain multiple distinct memory arenas in the heap, one per hosted region, each tracked and flushed individually, improving memory management across a server hosting many regions.
Applying to a distributed, non-relational database system
The invention is specifically applicable to distributed computing systems such as HBase clusters, where multiple regions are hosted per server.
The claims cover a comprehensive system and method for region-specific memory arena allocation in a distributed database server, managing continuous allocation, tracking via offset pointers, usage threshold detection, chunked arena allocation, and flushing to maintain contiguous free memory and thus reduce heap fragmentation effectively.
Stated Advantages
Reduces heap fragmentation by allocating data for each region from dedicated contiguous memory arenas.
Decreases the length and frequency of stop-the-world garbage collection pauses, improving latency.
Creates large contiguous free chunks upon MemStore flush, facilitating efficient memory reuse.
Improves CPU cache locality by grouping data allocations per MemStore region.
Enhances stability and performance of distributed databases with large heaps under heavy write loads.
Documented Applications
Optimizing memory allocation and garbage collection in distributed non-relational databases, such as HBase clusters.
Managing memory in region servers of distributed databases that host multiple regions, to reduce garbage collection latency during write-intensive workloads.
Interested in licensing this patent?