Techniques for efficiently allocating persistent storage

Abstract

Efficient disk storage is a crucial component for many applications. The commonly used method of storing data on disk using file systems or databases incurs significant overhead which can be a problem for applications which need to frequently access and update a large number of objects. This paper presents efficient algorithms for managing persistent storage which usually only require a single seek for allocations and deallocations and allow the state of the system to be fully recoverable in the event of a failure. We have developed a portable implementation of our algorithms in Java. Results in this paper demonstrate the superiority of our approach over file systems and databases for Web-related workloads. Our system has been a crucial component for persistently storing data at a number of highly accessed Web sites. We describe our experiences from a large real deployment of our system. © 2002 Elsevier Inc. All rights reserved.