Layout-Aware Data Organization for Heterogeneous Hierarchies Vinay Banakar Department of Computer Sciences University of Wisconsin-Madison

Abstract:

Modern operating systems manage memory at page granularity, but applications access data at the granularity of objects and fields. This mismatch has always produced inefficiency, but two shifts in the memory hierarchy are making it impossible to ignore: byte-addressable storage devices that sit between DRAM and block storage, and memory tiering systems that migrate pages across capacity tiers to reduce DRAM provisioning. On byte-addressable storage, page-level data movement wastes bandwidth by transferring cold bytes alongside hot ones. Under memory tiering, a single hot object on a page traps its cold neighbors in expensive DRAM. This dissertation argues that efficient use of modern memory hierarchies requires layout-aware organization, and identifies two regimes: static layout when application semantics reveal which data will be hot and which will be cold, and dynamic layout when access patterns depend on workload behavior and must be discovered through observation.

For the static regime, we study external sorting on byte-addressable storage. We introduce the BRAID model, which characterizes five properties of these devices that invalidate the assumptions of conventional storage algorithms: byte addressability, high random-read performance, asymmetric read-write costs, read-write interference, and device-constrained concurrency. We present WiscSort, a sorting system that exploits the semantic structure of sorting by separating keys from values and deferring value retrieval until sorted order is known. Combined with interference-aware scheduling and thread-pool sizing tuned to device characteristics, WiscSort achieves 2 to 7 times the throughput of competing approaches on industry-standard benchmarks.

When application semantics do not reveal access structure, static layout is insufficient. We quantify this limitation by measuring hotness fragmentation in production workloads at Google, Meta, and Twitter. The fragmentation is pervasive: across six Google workloads, up to 97% of bytes in active pages are cold data trapped by hot neighbors, and production traces confirm that object hotness shifts continuously over time. Because neither the application nor the OS can predict which objects will be hot, dynamic reorganization is necessary.

To address hotness fragmentation, we propose address-space engineering: dynamically reorganizing the virtual address space so that objects of similar access intensity reside together. We present OBASE, a compiler-runtime system for unmanaged languages that serves as an object-aware frontend for page-aware OS backends. OBASE introduces a guide abstraction that enables object relocation in C++, tracks accesses via lightweight pointer instrumentation, and migrates objects between hot and cold heaps using a lock-free protocol that is safe under concurrency. By reorganizing the address space, OBASE enables unmodified backends to tier memory effectively without understanding object boundaries. Across ten concurrent data structures, six tiering backends, and production traces from Meta and Twitter, OBASE improves page utilization by 2 to 4 times and reduces memory footprint by up to 70%, with only 2 to 5% performance overhead.

Together, WiscSort and OBASE demonstrate that layout-aware data organization, whether guided by application semantics or inferred from observed access patterns, enables modern memory hierarchies to achieve their potential by aligning page boundaries with access intensity.

Full Paper: PDF   BibTeX   Slides

Publications