Course Type: 

Link to online course catalogue

Semester:

Fall 2025

Instructor:

Angelos Bilas

Week

Y2025-26

Topic

Tasks

1a

Mon 29-Sep

Administration & Workloads

Intro to course topics and logistics 

Intro to assignment 1 

Lecture: Intro to modern storage systems, requirements, and workload characterization

- Storage Eras: device, parallel, network, cloud, granularity

- Requirements: YCSB, Facebook workloads, Twitter workloads

- Characterization: Role of key distribution, operation distribution, size distribution, updates

Reading: Lecture slides

1b

Wed 1-Oct

Workloads

Lecture (1/2): Intro to modern storage systems, requirements, and workload characterization

- Storage Eras: device, parallel, network, cloud, granularity

- Requirements: YCSB, Facebook workloads, Twitter workloads

- Characterization: Role of key distribution, operation distribution, size distribution, updates

Reading: 

- Lecture slides

- Benchmarking cloud serving systems with YCSB. Brian F. Cooper, Adam Silberstein, Erwin Tam, Raghu Ramakrishnan, and Russell Sears. 2010. In SoCC '10. https://dl.acm.org/doi/pdf/10.1145/1807128.1807152

2a

Fri 3-Oct

Workloads

Lecture (2/2): Intro to modern storage systems, requirements, and workload characterization

- Storage Eras: device, parallel, network, cloud, granularity

- Requirements: YCSB, Facebook workloads, Twitter workloads

- Characterization: Role of key distribution, operation distribution, size distribution, updates

Reading:

- Lecture slides

- Benchmarking cloud serving systems with YCSB. Brian F. Cooper, Adam Silberstein, Erwin Tam, Raghu Ramakrishnan, and Russell Sears. 2010. In SoCC '10. https://dl.acm.org/doi/pdf/10.1145/1807128.1807152

2b

Mon 6-Oct

Device Trends

Paper discussion:

- Characterizing, Modeling, and Benchmarking RocksDB Key-Value Workloads at Facebook. Z. Cao and S. Dong et al. 2020. In USENIX FAST’20. https://www.usenix.org/system/files/fast20-cao_zhichao.pdf

3a

Wed 8-Oct

Device Trends

Lecture (1/3): Device technologies and I/O caches: HDDs – FLASH SSDs - NVMe – NVM 

Reading:

- Lecture slides

-  Design tradeoffs for SSD performance. Nitin Agrawal, Vijayan Prabhakaran, Ted Wobber, John D. Davis, Mark Manasse, and Rina Panigrahy. 2008. In USENIX 2008 Annual Technical Conference (ATC'08). USENIX Association, USA, 57–70. https://www.usenix.org/legacy/events/usenix08/tech/full_papers/agrawal/agrawal.pdf 

3b

Fri 10-Oct

Device Trends

Lecture (2/3): Device technologies and  I/O caches: HDDs – FLASH SSDs - NVMe – NVM 

Reading:

- Lecture slides

-  Design tradeoffs for SSD performance. Nitin Agrawal, Vijayan Prabhakaran, Ted Wobber, John D. Davis, Mark Manasse, and Rina Panigrahy. 2008. In USENIX 2008 Annual Technical Conference (ATC'08). USENIX Association, USA, 57–70. https://www.usenix.org/legacy/events/usenix08/tech/full_papers/agrawal/agrawal.pdf 

4a

Mon 13-Oct

Device Trends

Assignment 1 due

Intro to assignment 2

Lecture (3/3): Device technologies and device caches: HDDs – FLASH SSDs - NVMe – NVM 

Reading:

- Lecture slides

-  Design tradeoffs for SSD performance. Nitin Agrawal, Vijayan Prabhakaran, Ted Wobber, John D. Davis, Mark Manasse, and Rina Panigrahy. 2008. In USENIX 2008 Annual Technical Conference (ATC'08). USENIX Association, USA, 57–70. https://www.usenix.org/legacy/events/usenix08/tech/full_papers/agrawal/agrawal.pdf 

4b

Fri 17-Oct

Device Trends

Paper discussion:

-  Design tradeoffs for SSD performance. Nitin Agrawal, Vijayan Prabhakaran, Ted Wobber, John D. Davis, Mark Manasse, and Rina Panigrahy. 2008. In USENIX 2008 Annual Technical Conference (ATC'08). USENIX Association, USA, 57–70. https://www.usenix.org/legacy/events/usenix08/tech/full_papers/agrawal/agrawal.pdf 

(if time allows)

-  Using transparent compression to improve SSD-based I/O caches. Thanos Makatos, Yannis Klonatos, Manolis Marazakis, Michail D. Flouris, and Angelos Bilas. 2010. In Proc. of the 5th European conference on Computer systems (EuroSys '10). ACM, New York, NY, USA, 1–14. DOI: https://doi.org/10.1145/1755913.1755915

5a

Mon 20-Oct

LSM

Lecture (1/2): Multi-level key-value stores: LSM 

            ·       Introduction

            ·       What is LSM: concept, prototype implementation, benefits

            ·       Discussion (KVS, FS, Parallel FS, Distributed Volumes, Object stores)

Reading: 

- Lecture slides  

Paper discussion:

Sections 1,2,4,5 of:  The log-structured merge-tree (LSM-tree). Patrick O'Neil, Edward Cheng, Dieter Gawlick, and Elizabeth O'Neil. 1996. Acta Inf. 33, 4 (1996), 351–385. https://link.springer.com/content/pdf/10.1007/s002360050048.pdf 

5b

Wed 22-Oct

LSM

Lecture (2/2): Multi-level key-value stores: LSM 

            ·       Introduction

            ·       What is LSM: concept, prototype implementation, benefits

            ·       Discussion (KVS, FS, Parallel FS, Distributed Volumes, Object stores)

Reading: 

·        Lecture slides  

·        Sections 1,2,4,5 of:  The log-structured merge-tree (LSM-tree). Patrick O'Neil, Edward Cheng, Dieter Gawlick, and Elizabeth O'Neil. 1996. Acta Inf. 33, 4 (1996), 351–385. https://link.springer.com/content/pdf/10.1007/s002360050048.pdf 

6a

Mon 27-Oct

LSM

Assignment 2 due 

Intro to assignment 3

Paper discussion:

Russell Sears and Raghu Ramakrishnan. 2012. bLSM: a general purpose log structured merge tree. In Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data (SIGMOD '12). Association for Computing Machinery, New York, NY, USA, 217–228. https://dl.acm.org/doi/pdf/10.1145/2213836.2213862

6b

Wed 29-Oct

 LSM

Paper discussion:

Russell Sears and Raghu Ramakrishnan. 2012. bLSM: a general purpose log structured merge tree. In Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data (SIGMOD '12). Association for Computing Machinery, New York, NY, USA, 217–228. https://dl.acm.org/doi/pdf/10.1145/2213836.2213862

7a

Mon 3-Nov

Indexing

Lecture (1/2): LSM Indexing

·       In-memory indexes vs. persistent indexes, briefly

·       In-memory L0, iIn-memory guards

·       Li B+-Tree index organization, leaf organization

·       Concurrency, caching, boom filters

·       Examples

o   RocksDB B-Tree-like index

o   Kreon Memory-Mapped B+-Tree

o   Btrfs Copy-on-Write B+-Tree

Reading:

·        Lecture slides

·        Anastasios Papagiannis, Giorgos Saloustros, Giorgos Xanthakis, Giorgos Kalaentzis, Pilar Gonzalez-Ferez, and Angelos Bilas. 2021. Kreon: An Efficient Memory-Mapped Key-Value Store for Flash Storage. ACM Trans. Storage 17, 1, Article 7 (February 2021), 32 pages. https://doi.org/10.1145/3418414 

·        Sections 3,5: Ohad Rodeh, Josef Bacik, and Chris Mason. 2013. BTRFS: The Linux B-Tree Filesystem. ACM Trans. Storage 9, 3, Article 9 (August 2013), https://dl.acm.org/doi/pdf/10.1145/2501620.2501623

7b

Wed 5-Nov

Indexing

Lecture (2/2): LSM Indexing

·       In-memory indexes vs. persistent indexes, briefly

·       In-memory L0, iIn-memory guards

·       Li B+-Tree index organization, leaf organization

·       Concurrency, caching, boom filters

·       Examples

o   RocksDB B-Tree-like index

o   Kreon Memory-Mapped B+-Tree

o   Btrfs Copy-on-Write B+-Tree

·       Bε-Tree (Global vs. per-level indexes, Incremental compaction vs. level buffers, Buffer size and updates)

Reading:

·        Lecture slides           

·        Lecture slides (Bε-Tree)

·        Anastasios Papagiannis, Giorgos Saloustros, Pilar González-Férez, and Angelos Bilas. 2016. Tucana: design and implementation of a fast and efficient scale-up key-value store. In Proceedings of the 2016 USENIX Conference on Usenix Annual Technical Conference (USENIX ATC '16). USENIX Association, USA, 537–550. https://www.usenix.org/system/files/conference/atc16/atc16_paper-papagiannis.pdf

Paper discussion:

SplinterDB: Closing the Bandwidth Gap for NVMe Key-Value Stores. Alex Conway, Abhishek Gupta, Vijay Chidambaram, Martin Farach-Colton, Richard Spillane, Amy Tai, Rob Johnson. ATC 2020. https://www.usenix.org/system/files/atc20-conway.pdf

8a

Mon 10-Nov

Compaction

Assignment 3 due 

Intro to assignment 4

Lecture: LSM compaction

·       Levelling – Tiering - KV separation 

·       Adaptive levelling – tiering 

·       Incremental compaction (blsm, rocksdb)

·       Date-tiered and Time-window Compaction

Reading:

-        Lecture slides

-        Giorgos Xanthakis, Giorgos Saloustros, Nikos Batsaras, Anastasios Papagiannis, and Angelos Bilas. 2021. Parallax: Hybrid Key-Value Placement in LSM-based Key-Value Stores. In Proceedings of the ACM Symposium on Cloud Computing (SoCC’21). Association for Computing Machinery, New York, NY, USA, 305–318. DOI: https://doi.org/10.1145/3472883.3487012 

8b

Wed 12-Nov 

Compaction

Lecture: LSM compaction

·       Levelling – Tiering - KV separation 

·       Adaptive levelling – tiering 

·       Incremental compaction (blsm, rocksdb)

·       Date-tiered and Time-window Compaction

Reading:

-        Lecture slides

-        Giorgos Xanthakis, Giorgos Saloustros, Nikos Batsaras, Anastasios Papagiannis, and Angelos Bilas. 2021. Parallax: Hybrid Key-Value Placement in LSM-based Key-Value Stores. In Proceedings of the ACM Symposium on Cloud Computing (SoCC’21). Association for Computing Machinery, New York, NY, USA, 305–318. DOI: https://doi.org/10.1145/3472883.3487012 

9a 

Mon 17-Nov 

Compaction

Paper Discussion:

Pandian Raju, Rohan Kadekodi, Vijay Chidambaram, and Ittai Abraham. 2017. PebblesDB: Building Key-Value Stores using Fragmented Log-Structured Merge Trees. In Proceedings of the 26th Symposium on Operating Systems Principles (SOSP '17). Association for Computing Machinery, New York, NY, USA, 497–514. https://doi.org/10.1145/3132747.3132765

9b

Wed 19-Nov 

Modelling & Tradeoffs

Lecture: Understanding tradeoffs with key-value store data organization 

·        # levels, growth factors

·        types of amplification

·        sizes in memory and on device

·        updates

Reading: 

·        Lecture slides

·        VAT: Asymptotic Cost Analysis for Multi-Level Key-Value Stores. Nikos Batsaras, Giorgos Saloustros, Anastasios Papagiannis, Panagiota Fatourou, and Angelos Bilas.  February 2020. arXIV 2003.00103. arxiv.org/abs/2003.00103v1  

·        Sections 1,2,3 of: Michael A. Bender, Alex Conway, Martín Farach-Colton, William Jannen, Yizheng Jiao, Rob Johnson, Eric Knorr, Sara Mcallister, Nirjhar Mukherjee, Prashant Pandey, Donald E. Porter, Jun Yuan, and Yang Zhan. 2021. External-memory Dictionaries in the Affine and PDAM Models. ACM Trans. Parallel Comput. 8, 3, Article 15 (September 2021), 20 pages. DOI: https://doi.org/10.1145/3470635

10a

Mon 24-Nov  

Recovery

Assignment 4 due

Start thinking about your projects

Project proposals due. After ack from instructor, start working on your projects.

Lecture: Fault tolerance and Recovery: Write-Ahead Log (WAL), intro to CoW

·       In-place (logs) vs. re-map/shadowing (CoW)

·       Group commit, random in-place vs. seq CoW updates

Reading:

-        Lecture slides           

10b

Wed 26-Nov  

Recovery

Lecture: Fault tolerance and Recovery: Write-Ahead Log (WAL), intro to CoW

·       In-place (logs) vs. re-map/shadowing (CoW)

·       Group commit, random in-place vs. seq CoW updates

Reading:

-        Lecture slides

11a

Mon 1-Dec 

Recovery

Project proposals due, start working on your projects

Paper discussion:

SpanDB: A Fast, Cost-Effective LSM-tree Based KV Store on Hybrid Storage. Hao Chen, Chaoyi Ruan, Cheng Li, Xiaosong Ma, Yinlong Xu.  In Proceedings of FAST'21: 19th USENIX Conference on File and Storage Technologies (FAST'21). https://www.usenix.org/system/files/fast21-chen-hao.pdf

11b

Wed 3-Dec  

OS kernel I/O path

Network & RDMA

Lecture: Network access – RDMA

·        RDMA concepts

·        Connections

·        Messages

·        Buffer management

·        Message reception

·        RDMA scaling (connections, buffer management, message reception)

Reading: 

-        Lecture slides 

12a

Mon 8-Dec  

Network & RDMA

Paper discussion:

·       Shin-Yeh Tsai and Yiying Zhang. 2017. LITE Kernel RDMA Support for Datacenter Applications. In Proceedings of the 26th Symposium on Operating Systems Principles (SOSP '17). Association for Computing Machinery, New York, NY, USA, 306–324. DOI: https://doi.org/10.1145/3132747.3132762  

·       (if time allows) Michalis Vardoulakis, Giorgos Saloustros, Pilar González-Férez, and Angelos Bilas. 2022. Tebis: index shipping for efficient replication in LSM key-value stores. In Proceedings of the Seventeenth European Conference on Computer Systems (EuroSys '22). Association for Computing Machinery, New York, NY, USA, 85–98. DOI: https://doi.org/10.1145/3492321.3519572

12b

Wed 10-Dec  

Persistent Memory

Lecture: I/O path from memory to device: Buffered and direct I/O, Syscalls, mmio, U-ring, SPDK

Reading

- Lecture slides

- Optimizing Memory-mapped I/O for Fast Storage Devices. Anastasios Papagiannis, Giorgos Xanthakis, Giorgos Saloustros, Manolis Marazakis, and Angelos Bilas. In proceedings of the 2020 USENIX Annual Technical Conference (USENIX ATC'20). July 2020, Boston, MA, USA. https://www.usenix.org/system/files/atc20-papagiannis.pdf 

Lecture: Persistent memory vs. I/O

·       Byte-addressable I/O (anonymous mmio, ld/st)  

·       Block-based I/O (mmio with named files, read/write)

Reading: 

-        Lecture slides 

Paper discussion:

Stan Park, Terence Kelly, and Kai Shen. 2013. Failure-atomic msync(): a simple and efficient mechanism for preserving the integrity of durable data. In Proceedings of the 8th ACM European Conference on Computer Systems (EuroSys '13). Association for Computing Machinery, New York, NY, USA, 225–238. DOI: https://doi.org/10.1145/2465351.2465374

13a

Mon 15-Dec  

Persistent Memory

The evolving memory hierarchy

·       Memory is fast, storage is persistent. Is NVM about fast storage or persistent memory?

·       Can storage and memory converge to a single abstraction?

·       Discussion

13b

Wed, 17-Dec

Project Presentations

Projects due: Presentations, 15 mins/project. 

End of HY647