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_0: Full-text information retrieval systems have traditionally been designed for archival environments. They often provide little or no support for adding new documents to an existing document collection, requiring instead that the entire collection be re-indexed. Modern applications, such as information filtering, operate in dynamic environments that require frequent additions to document collections. We provide this ability using a traditional inverted file index built on top of a persistent object store. The data management facilities of the persistent object store are used to produce efficient incremental update of the inverted lists. We describe our system and present experimental results showing superior incremental indexing and competitive query processing performance.
Finally, a few notes about our strategy for allocating postings slices from fixed-size pools: there are some similarities we can point to in previous work, but some important differences as well. With the in-place update strategy where extra space for postings is pre-allocated, it is not much of a stretch to implement fixed block sizes that are powers of two. @cite_0 allocate space for on-disk postings in sizes of 16, 32, 64, 128, @math 8192. However, a few important differences (beyond in-memory vs. on-disk): copy postings each time a new block is allocated to preserve contiguity, whereas we don't. In addition, the paper leaves open the method by which those blocks are allocated---whereas we describe a specific implementation based on fixed slice sizes in large pools (supporting efficient memory allocation, compact pointer addressing, etc.).