We explore a real-time Twitter search application where tweets are arriving at a rate of several thousands per second. Real-time search demands that they be indexed and searchable immediately, which leads to a number of implementation challenges. In this paper, we focus on one aspect: dynamic postings allocation policies for index structures that are completely held in main memory. The core issue can be characterized as a "Goldilocks Problem". Because memory remains today a scare resource, an allocation policy that is too aggressive leads to inefficient utilization, while a policy that is too conservative is slow and leads to fragmented postings lists. We present a dynamic postings allocation policy that allocates memory in increasingly-larger "slices" from a small number of large, fixed pools of memory. Through analytical models and experiments, we explore different settings that balance time (query evaluation speed) and space (memory utilization).
Tracing the lineage of various storage allocation mechanisms further back in time, we would arrive at a rich literature on general-purposes memory allocation for heap-based languages (e.g., malloc in C). According to the taxonomy of @cite_9 , Earlybird's allocation strategy would be an example of segregated free lists, an approach that dates back to the 1960s. Of course, since we're allocating memory for the very specific purpose of storing postings, we can accomplish the task much more efficiently since there are much tighter constraints, e.g., no memory fragmentation, fixed sizes, etc. Nevertheless, it would be fair to think of our work as a highly-specialized variant of general purpose memory allocators for heap-based languages.
@cite_9
1966822983
Memory management system performance is of increasing importance in today's managed languages. Two lingering sources of overhead are the direct costs of memory allocations and write barriers. This paper introduces it allocation folding, an optimization technique where the virtual machine automatically folds multiple memory allocation operations in optimized code together into a single, larger it allocation group. An allocation group comprises multiple objects and requires just a single bounds check in a bump-pointer style allocation, rather than a check for each individual object. More importantly, all objects allocated in a single allocation group are guaranteed to be contiguous after allocation and thus exist in the same generation, which makes it possible to statically remove write barriers for reference stores involving objects in the same allocation group. Unlike object inlining, object fusing, and object colocation, allocation folding requires no special connectivity or ownership relation between the objects in an allocation group. We present our analysis algorithm to determine when it is safe to fold allocations together and discuss our implementation in V8, an open-source, production JavaScript virtual machine. We present performance results for the Octane and Kraken benchmark suites and show that allocation folding is a strong performance improvement, even in the presence of some heap fragmentation. Additionally, we use four hand-selected benchmarks JPEGEncoder, NBody, Soft3D, and Textwriter where allocation folding has a large impact.