MEMORY ALLOCATION BUFFER FOR REDUCTION OF HEAP FRAGMENTATION

• US 20130185337A1
• Filed: 01/18/2013
• Published: 07/18/2013
• Est. Priority Date: 01/18/2012
• Status: Active Grant

• Current Assignee: Cloudera Incorporated
• Original Assignee: Cloudera Incorporated
• Inventors: Lipcon, Todd
• Granted Patent: US 9,128,949 B2
• Time in Patent Office: Days
• US Class Current: 707/813
• CPC Class Codes: G06F 12/0808 with cache invalidating means G06F12/0815 takes precedence
• CPC Class Codes: G06F 12/12 Replacement control
• CPC Class Codes: G06F 12/128 adapted to multidimensional cache systems, e.g. set-associative, multicache, multiset or multilevel
• CPC Class Codes: G06F 16/1727 Details of free space management performed by the file system saving storage space on storage systems G06F3/0608; management of blocks in storage devices G06F3/064
• CPC Class Codes: G06F 2212/1044 Space efficiency improvement
• CPC Class Codes: G06F 3/0611 in relation to response time
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 3/0683 Plurality of storage devices
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

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.

Claims

1. A method of allocating objects for reducing memory fragmentation in a distributed database system, comprising:

receiving an object for insertion into a target region;

structuring a memory arena dedicated to the target region; and

allocating space for the object from the memory arena.

2. The method of claim 1, further comprising:

storing the object at a location specified by an offset pointer in the allocated space; and

incrementing the offset pointer by the length of the object stored.

3. The method of claim 2, wherein reservation of storage in the allocated space proceeds without the use of mutual exclusion locks.

4. The method of claim 2, wherein an atomic compare-and-swap (CAS) instruction increments the offset pointer without other coordination between processors.

5. The method of claim 2, wherein the distributed database system is a HBase cluster.

6. The method of claim 5, wherein the target region is one of a plurality of regions hosted on a region server in the HBase cluster.

7. The method of claim 6, wherein a memory arena for each of the plurality of regions including the target region is periodically flushed when usage of the memory arena exceeds or reaches a threshold.

8. The method of claim 7, wherein when the memory arena is flushed, memory fragmentation is reduced.

9. The method of claim 1, wherein the structuring is performed by a local allocation buffer to keep objects from a plurality of regions including the target region from intermingling in memory.

10. The method of claim 2, further comprising:

receiving a new object for insertion into the target region;

determining that there is insufficient or no free space in the memory arena;

structuring a new memory arena dedicated to the target region;

allocating space for the new object from the new memory arena;

storing the new object at a location specified by an offset pointer that is set to zero in the allocated space; and

incrementing the offset pointer by the length of the new object.

11. The method of claim 10, wherein each memory arena has a size of or near 0.5 MB, 1 MB, 2 MB, 4 MB, or 8 MB.

12. A distributed database system, comprising:

a region server configured to receive write requests targeted to a plurality of regions hosted in the region server;

a virtual machine for executing one or more applications; and

local allocation buffers for use by the virtual machine to allocate chunks of heap for MemStores corresponding to the plurality of regions,

wherein data from the write requests are inserted into chunks of heap allocated for MemStores corresponding to the targeted plurality of regions.

13. The system of claim 12, wherein the data from the MemStores are not intermingled in the heap.

14. The system of claim 12, wherein the distributed database system is HBase.

15. The system of claim 13, wherein when one of the MemStores is flushed, one or more chunks of heap corresponding to the flushed MemStore are freed up.

16. The system of claim 15, wherein creation of the one or more free chunks reduces heap fragmentation and reduces garbage collection pause.

17. The system of claim 12, wherein when a chunk of heap for a MemStore from the MemStores is filled up, a new chunk of heap is allocated for the MemStore.

18. The system of claim 12, wherein the region server is further configured to receive read requests that are processed by targeting each MemStore and searching or sorting through data collected in one or more chunks of heap allocated for the MemStore.

19. The system of claim 12, wherein each chunk of heap has a chunk size and a pointer that is incremented by the length of data inserted in the chunk.

20. The system of claim 19, wherein the chunk size is a tunable parameter that is tuned to reduce unused memory in the local allocation buffers.

21. A machine-readable storage medium including executable instructions, which when executed by a processor, causes a processor to:

receive write requests targeted to a plurality of regions hosted in a region server;

create local allocation buffers to allocate chunks of heap for MemStores corresponding to the plurality of regions; and

insert data from the write requests into chunks of heap allocated for MemStores corresponding to the targeted plurality of regions.

22. The medium of claim 21, wherein the region server is one of a plurality of server in a distributed HBase cluster.