Vectors in ActivePivot

Introduction

A vector in ActivePivot is equivalent to a fixed-size array that has been strongly typed for performance. It comes with read and write capabilities, internal operations related to statistics usage (topKIndices, variance...) and cross-vector operations (plus, minus, scale...).

Vectors are used in ActivePivot as values of a field in the datastore. This can be achieved when building a store with the StoreDescriptionBuilder, using withVectorField(String name, String type).

Storing Design Overview

While this section mentions Off-Heap memory to explain the design choices behind the vector architecture, the design is the same for On-Heap vectors.

In most Java applications, there is a typical distribution for the lifetime of created objects, where the vast majority of objects dies young. Thus, most Garbage Collectors are built around this empirical observation.

However, ActivePivot, and especially ActivePivot's datastore, acts as a database, and thus does not follow this rule: all the data is long-lived. The Garbage Collector must keep track of these objects, and even transfer them when necessary. Off-Heap Memory provides a way to hide these objects from the Garbage Collector, allowing it to focus on objects created and deleted within the application's life cycle.

The Java NIO API gives access to a DirectByteBuffer to read and write from the Off-Heap memory.

However, these buffers do not provide the performance needed for ActivePivot:

  • Instances of DirectByteBuffer are much bigger than standard Java arrays.
  • Java poorly handles millions of such buffers.
  • The creation of each buffer induces a call to the system's malloc, a single-threaded memory allocator that adds another memory overhead for its own tracking system. This goes against ActivePivot's efforts for multi-threading, notably through partitioning

To reduce this performance overhead, ActivePivot allocates several vectors within a single buffer, using an abstraction called blocks (IBlock interface).

This also means that as vectors get deleted within a block, the block itself holds less and less relevant data. To keep ActivePivot's memory usage efficient, blocks come with a compaction mechanism.

Allocation

Each thread has its own IVectorAllocator that can allocate vectors in blocks. Threads that are part of the QFS thread pools each include a vectorAllocator. Calling currentThread.getVectorAllocator().allocateNewVector() allocates a new vector from the current block of the allocator, on the NUMA node (if stored off-heap) the thread is running on.

In the datastore, it is possible to define the size of the vecor and the vector's block for each field. Fields with different vector block sizes will use different vector allocators. However, vectors with the same vector block size will rely on the same allocator, and thus belong to the same blocks, even if they have different vector sizes.

For instance, if field A has vectors of size 10, and field B has vectors of size 5, while both have a block size of 50, a block may, at a given time, contain { 10, 5, 10, 10, 5, 5 }. If the allocator needs to allocate a vector for field A, a new block will be created.

By default, ActivePivot uses off-heap memory allocation, relying on the class ADirectVectorBlock. Off-heap storage can be disabled. In this case, ActivePivot will rely on either arrays or heap-buffers to manage the storage, using the classes AArrayVector and ABufferVectorBlock.

Compaction

ActivePivot relies on a copy Garbage Collection algorithm. Whenever a version is discarded, ActivePivot iterates through all vectors in the datastore and the aggregate store, and checks if they belong to a block that is mostly garbage. If they do, the vectors are transferred to another block.

Configuration

Each vector field can configure its own size and block size. Default block size can be set using the ActiveViam Property qfs.vectors.defaultBlockSize, which defaults to the default size of a chunk (which depends on the server's size).

The ActiveViam Property qfs.vectors.garbageCollectionFactor (value between 0 and 1) controls how soon a block is considered needing compaction. It represents a trade-off between transaction performance and memory footprint.

Selecting the size of the vector blocks is considered an advanced feature. The size is set automatically, depending on the amount of memory available to the JVM, and the size of the vectors.

Selecting a vector block size for a field is an operation that requires great care: in order to:

  • minimize external memory loss (have the block size as close as possible to a multiple of the page cache size)
  • minimize internal memory loss (not wasting memory in the last block to store the last vectors of the chunk)
  • keep a high enough number of blocks to ensure good compaction
  • keep their number low enough to minimize the number of allocations (those system calls are very expensive, especially in a multi-threaded environment).

Swapping

This storing design allows you to seamlessly add efficient vectors swap capabilities in ActivePivot.

The Operating System uses a cache where it stores the most frequently accessed portions of files in memory: the page cache. When requesting some data within a file, the OS first checks the cache: if the data is found, a copy is given to the user. Otherwise, the file is loaded into the cache, and a copy of the data is given to the user.

Copying takes CPU time, hurts CPU caches, and wastes RAM with duplicated data. To minimize copies, ActivePivot relies on MappedByteBuffer (from Java NIO API as well). This class relies internally on the mmap system call to grant access to the page cache.

When swapping vectors, blocks are stored in MappedByteBuffers, and ActivePivot delegates the responsibility of writing the underlying file to the OS.

By default, files are written into the default OS temporary directory. Because of its limited size, it is best to provide a swap directory when defining a swapped vector field.

Swapping Advanced tuning considerations

As the amount of swapped data increases, the default settings might not provide sufficient performance. For advanced tuning, it is recommended to read on how the page cache works on Linux, to learn about vm.swapiness, vm.dirty_background_bytes and vm.dirty_bytes.

ActivePivot suggests these three properties to be respectively set to 0, a low value, and a high value.

The ActiveViam Property qfs.vectors.swap.directory.numberFiles, set by default to 10k, controls the maximum number of swap files created in one directory.

On Linux, the default number of available mappings, set through vm.max_map_count, is 2^16. This limit is very likely hit on big projects, which will result in an OutOfMemoryError("Map failed"). This can be avoided by changing this kernel property or by increasing block size.

The JVM might core dump if disk space is full, or if the swap directory is full, instead of throwing an OOM Error.

Transparent Huge Pages, which acts as an adapter for simple use of Huge Pages, MUST be disabled, as the default allocator (SLAB) in ActivePivot natively supports Huge Pages.

Cleaning swapped vectors

ActivePivot does not collect old unused blocks from the disk, meaning that the disk usage can grow indefinitely. Thanks to the way memory-mapped files work, this is easily fixable: these files can be deleted without impacting ActivePivot, as the OS only permanently removes these files when the last reference to the file is deleted. This means that one can call rm on a swapped file, and it will be effectively deleted once the last vector in the corresponding block is marked as garbage.

Working with vector fields

With Copper

Working with vectors within Copper is a seamless experience. Standard operators between vectors, or between scalars and vectors, behave naturally. One can also access IVector-specific API using the map function and casting the argument, like so: 

Copper.sum("VectorField")
        .map((IVector v) -> v.quantileDouble(0.95))
        .withFormatter("DOUBLE[#,###.##]")
        .withName("95th Percentile");

With Post Processors

Within ActivePivot, custom aggregation functions can be written by extending the dedicated AVectorAggregationFunction. ActivePivot does not provide specialized Post-Processors to handle vectors. Creating one's own Post-Processors should prove easy. For instance, one can calculate the 5% expected shortfall (the value that is lost on average with a 5% probability) using:

@Override
public Object evaluate(ILocation location, Object[] underlyingMeasures) {
    final IVector v = (IVector) underlyingMeasures[0];
    if (v == null) {
        return null;
    }
    return v.topK((5 * v.size()) / 100).getUnderlyingArray().average();
}

Warning: Note that this Post Processor does not copy the vector before using it. One must pay attention to the operation's impact on the vectors given as arguments. In the following example, it is necessary to copy the vector before applying the operation, as the plus operation modifies the vector in place.

/**
 * This PostProcessor takes the sum of the vectorField.SUM and vectorField.AVG
 */
@Override
public Object evaluate(ILocation location, Object[] underlyingMeasures) {
    final IVector sumVector = (IVector) underlyingMeasures[0];
    final IVector avgVector = (IVector) underlyingMeasures[1];
    if (sumVector == null || avgVector == null) {
        return null;
    }
    IVector result = sumVector.cloneOnHeap();
    // plus overrides the vector which calls it (but only reads in the argument vector)
    result.plus(avgVector);
    return result;
}

Indeed, this can be calculated as the average of the biggest values of a vector, where the 'biggest' values are those that fall within the top 5%.

When implementing a post-processor that returns vectors as evaluation results, one should always use IVector as output type class parameter.

Advanced users may want to use the class AGenericVectorAggregationFunction for more complex aggregations, and write their own aggregation bindings using AVectorAggregationBinding.