k2bd/k2db

My solutions to the projects set in CMU's Intro to Database Systems Course in Rust

k2db

My solutions to the projects set in CMU's Intro to Database Systems Course in Rust. By the nature of the projects it will also be at least a partial clone of some iteration of BusTub, the scaffold database system produced by CMU for that course's project work.

The goal of this repo is for me to learn about database internals and DBMS development by following that CMU course and other resources, and to brush up on Rust development.

Progress

• Project 1
  • Task 1 Clock Replacer
  • Task 2 Buffer Pool Manager
• Project 2
  • Task 1 Hash Table Header Page, Hash Table Block Page
  • Task 2 (WIP)

Resources

The BusTub source repo as of a 2019 commit

An example solution to the whole project in C++

toyDB, a distributed sql database written in Rust

mini-db, a relational database system built in Rust

k2db's Issues

Page unpinning on error results

At the moment error results can leave a bunch of pages pinned :(

Return Result<> in iterators instead of panicking

Hash table header extension pages

At the moment there's a limit to hash table size due to limited header page space to index block pages. A simple extension would be to allocate a byte of memory to the header page for an optional header extension page ID which would be structured like:

| Header page ID (4) | Previous extension page ID or null (4) | Next extension page ID or null (4) | Block page IDs (4084) |

And the header page would then look like:

| LSN (4) | Size (4) | PageId(4) | NextBlockIndex(4) | First extension page ID or null (4) | Block page IDs (4076) |

Make more use of generic types wherever we're initializing concrete implementations

E.g. instead of instantiating a WriteableHashTableBlockPage directly in HashTable I should be instantiating whatever implementation of IHashTableBlockPageWrite our table is using based on a generic. That's why these interfaces exist.

Reduce repetition in readonly/writable versions of structs

At the moment all the read methods are implemented twice manually

Either a redesign to avoid this or a macro that implements these methods would work I think

Clean up unwraps in buffer pool manager etc

And write --> try_write etc

Buffer pool manager helper method for waiting for a page if there are no available buffer slots