Eureka! Institutional Repository

Dynamic storage allocators are a critical component of database systems since they largely affect their performance and safety. Persistent storage allocators used by these systems are different from main memory allocators. Additional requirements such as crash resilience, concurrency control and minimized disk accesses must be satisfied. This creates a demand for efficient, fast and safe allocation of storage space in such environments. This thesis presents a theoretical design of a dynamic storage allocator for a new concurrently readable memory mapped key value database system. We initially introduce and analyze the internals of the database specifying the requirements of the allocator. Then, we perform a literature survey on dynamic memory allocation concepts, techniques and low-level mechanisms. Finally, we introduce our design proposal. Both in-memory and on-disk structures are presented along with the mechanisms that make the allocator fast, safe and resilient to system crashes