Caching Queues in Memory Buffers

Abstract

Maintaining queues in a small and fast memory cache with large but slow secondary storage is an important problem that occurs in many contexts like DataStream systems \cite{stream,aurora,eddies,gigascope,niagaracq}, Network Router design \cite{sundar,devavrat,george} and Distributed Messaging systems \cite{mqseries}. At any clock-tick any number of tuples may enter the various queues, and a single tuple is consumed from the head of one of the queues. However since the number of unconsumed tuples may exceed the size of the memory buffer, some of the tuples in the queues will have to be written-out to secondary storage and then later read-in back into memory for consumption. The only constraint is that tuples written-out and then read-in should not be written-out again to avoid thrashing. The aim of the algorithm is to minimize the cost of the reads and writes to secondary storage. We provide online competitive algorithms for different cost models for reads and writes. For the cost model in which each read/write has unit cost (as present day disks are modelled) we provide a 2-competitive online algorithm and show a matching lower bound for maintaining a single queue. For n queues when a single read(write) can only access contiguous tuples from a single queue, we provide a 2n-competitive algorithm and prove a $\sqrt n$ lower bound if the heads of different queues are consumed in round-robin. On the other hand for adverserial consumption, we show that it is not possible to even have a o(M) competitive online algorithm, where M the size of the memory is much larger than the number of queues, n. However if the online algorithm is given extra M/2 memory then then we show a 2n-competitive algorithm. For the extended cost model where the cost of the read(write) depends on the number of blocks written out we provide a 4-competitive algorithm. These algorithms will be implemented in the Stanford Stream system