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).
@cite_9: Dynamic memory allocation has been a fundamental part of most computer systems since roughly 1960, and memory allocation is widely considered to be either a solved problem or an insoluble one. In this survey, we describe a variety of memory allocator designs and point out issues relevant to their design and evaluation. We then chronologically survey most of the literature on allocators between 1961 and 1995. (Scores of papers are discussed, in varying detail, and over 150 references are given.)
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.