Skip to content

Memory Allocator

Jump to bottom Edit New page
Paul Rogers edited this page Apr 10, 2017 · 4 revisions

Components

The major components of Drill's memory allocator are:

  • The value vector, which is backed by
  • The DrillBuf, which represents a single logical buffer, backed by
  • The UDLE (unsigned, direct, little-endian) buffer, sliced and shared by multiple DrillBufs
  • The Drill memory allocator, which manages the UDLEs and creates DrillBufs
  • The Netty memory allocator, which handles UDLE allocation from its own internal pool or from
  • Unsafe, the access to the system direct memory pool.

The purpose of this discussion is to describe how these pieces fit together.

DrillBuf

The Drillbuf is Drill's extension to Netty's ByteBuf extension of the JDK NIO's ByteBuffer abstraction. To the rest of Drill, a DrillBuf presents a single buffer of data, of some length. The DrillBuf is the top of a stack of abstractions:

  • DrillBuf provides the API to the memory
  • UnsafeDirectLittleEndian is the Drill-specific wrapper around the memory
  • PooledUnsafeDirectByteBuf is the Netty holder of the memory
  • Unsafe is the actual interface to the system malloc area

Drill Memory Allocator

Drill has a very elaborate memory manager that forms the "first line support" for managing memory. Major classes:

  • BufferAllocator: the allocation interface within Drill. Provides an API to allocate DrillBufs.
  • BaseAllocator: The concrete implementation of BufferAllocator.
  • RootAllocator: The top-most BaseAllocator.
  • ChildAllocator: Allocators form a tree that parallels the operator tree. This class is a form of BaseAllocator for non-root allocators.

Allocators have two primary tasks:

  • Provide an accounting of the number of bytes used by the client of the allocator.
  • Perform actual memory allocations and releases.

Allocators are given two parameters: the initial and maximum allocations. Chile allocators keep track of the actual allocation. When the client wishes to allocate more memory than is held locally by the child, the child asks its parent for the extra memory, and so on up the allocator tree. Note that this memory is simply an accounting for memory: not actual memory.

Actual memory is allocated when needed. In general, the amount of memory actually allocated by an allocator is less than or equal to the amount assigned to the allocator. (Accounting amount may exceed physical amount.)

Memory Allocation

Memory allocation is performed by the AllocationManager class. This class holds onto something called the "UDLE" (UnsafeDirectLittleEndian) which is a reference to a block of direct memory provided by Unsafe via Netty.

Now, if Drill had a 1:1 correspondence between Drillbuf and UDLE, things would be simple. But, in fact, a single UDLE can be referenced by one, two or more DrillBuf objects. Each DrillBuf owns a distinct "slice" of the UDLE (with possibly some of the UDLE not allocated to any Drillbuf.)

Given this m:1 relationship between Drillbuf and UDLE, we need a separate mechanism to manage the UDLE. The AllocationManager is that mechanism. The BufferLedger forms the link between Drillbuf and UDLE: it specifies the offset and length of the UDLE assigned to the Drillbuf.

All of this provides the following structure:

  • The BufferAllocator allocates a DrillBuf by first creating a AllocationManager to hold the UDLE.
  • The AllocationManager asks for the UDLE from the Drill PooledByteBufAllocatorL class.
  • The AllocationManager creates a BufferLedger to track the portion of the UDLE to assign to the DrillBuf. Since this is an initial allocation, the ledger owns the entire UDLE.
  • The BufferLedger creates the DrillBuf that is the application interface to the (slice of the) UDLE.

Extensive reference count keeps all the various pieces in sync as Drill creates and releases slices.

Drill Pooled Allocator

The above is fine as far as it goes, but how does the AllocationManager obtain the UDLE? The AllocationManager class holds a static reference to the (global) Drill PooledByteBufAllocatorL class.

The pooled allocator works in conjunction with the Drill UnsafeDirectLittleEndian class. As the comments explain, "Is used underneath DrillBufs to abstract away the Netty classes and underlying Netty memory management."

The pooled allocator has two main parts: the PooledByteBufAllocatorL which is the API, and the inner InnerAllocator which implements the allocator.

The implementation provides a block pool (separate from the pools which Netty maintains.) The allocator allocates a block in a way that depends on the "chunk" size: the size of the largest managed Netty allocation.

If the request is larger than the chunk size:

  • Use the Netty UnpooledByteBufAllocator class to allocate a buffer.
  • UnpooledByteBufAllocator allocates a UnpooledUnsafeDirectByteBuf to hold the allocation from Unsafe, returning it as a ByteBuf.
  • Drill wraps the returned buffer in a LargeBuffer.
  • Drill then wraps that again in the Drill UnsafeDirectLittleEndian class.
  • Further up the call chain, the above is wrapped in a DrillBuf.

If the request is of the chunk size or smaller:

  • Allocate the buffer from the Netty PoolArena<ByteBuffer> associated with the allocator.
  • The pool arena maintains a set of free chunks (AKA "slabs"). It will either return a full chunk, or slice a chunk into a binary fraction (1/2, 1/4, 1/8, etc.) to obtain the desired size.
  • Wrap the returned buffer in the Drill UnsafeDirectLittleEndian class.
  • Further up the call chain, the above is wrapped in a DrillBuf.

The Drill InnerAllocator class extends the Netty PooledByteBufAllocator class. Drill does not use PooledByteBufAllocator directly; instead it uses introspection to extract the PoolArena<ByteBuffer>[] field. (Doing so presumably ties Drill to specific Netty versions since Drill depends on Netty implementation, not just API.)

The Netty allocator is an implementation of "jemalloc". From the Netty documentation:

Layers

The allocator is complex. A diagram helps us understand how the components fit together.

Drill Application
DrillBuf | Memory Allocator
Drill Allocator
Netty Allocator
Unsafe
System malloc
  • DrillBuf - Application API to a buffer and implementation of that API
  • Drill Allocator - Machinery for creating, releasing buffers
  • Netty Allocator - Java implementation of jemalloc
  • Unsafe - Java API to the system direct memory pool
  • Linux malloc - Services the allocations made via Unsafe
Add a custom footer
Add a custom sidebar
Clone this wiki locally