Abstract
This thesis investigates the efficiency of extent-based allocator
design to satisfy file allocation requests in a CDN proxy cache. The
allocator is based on the method inspired by the memory allocators,
where free space is managed in chunks of varying size, or extents. The
design is tested in a simulation, where a trace of allocation and
deallocation events from a content server was submitted to the
allocator. Content serves of this type experience high demands on
throughput, so their file system must store files in the most
efficient way possible. The bottleneck for content retrieval often
lies on data transfer rates of the hard disks used in the server. To
facilitate fastest possible transfer of a file, it must be read
sequentially, in one operation. At the same time, given the large
quantity of file, which are present on such servers, space wastage due
to incomplete utilisation of large allocation units is not
desirable. Our allocator design tries to achieve both, to a certain
extent, mutually exclusive goals. The design was implemented and the
results we obtained in the course of simulation, show that we managed
to achieve these goals, creating an allocator that displays
properties, favourable for contiguous file placement, while keeping
space wastage at its minimum. Additionally, the allocator is
memory-efficient and has small bookkeeping and computational
overhead. The use of our allocator in a CDN proxy file system will
allow to keep the data transfer throughput at maximum speed, while
utilising the storage space in an efficient manner. The reader of this
thesis will learn about the allocator semantics and have a detailed
introduction into a specific allocation algorithm, QuickFit. This
study outlines several venues of improvement and opens for a further
empirical study of complete system, based on the allocator presented
in this thesis.