bustub-0

Ludwig Huang

0. Disk Manager

CMU 15-445 Project Review: Disk Manager

In this series, I will show you how to build a disk-oriented DBMS (Database Management System) roughly. This article is about Disk Manager, contains: Disk Manger, Storage Layout and System Catalog.

This article mainly describes: How the DBMS represents the database in files on disk.

N. Logging & Recovery  ^ Up (high level)
4. Concurrency Control |
N. Query Planning      |
3. Operator Execution  |
2. Access Methods      |
1. Buffer Pool Manager |
0. Disk Manager        | Bottom (low level) <- Today

Disk Manager

Disk Manager takes care of the allocation and de-allocation of pages within a database. It performs the reading/writing of pages to/from disk, providing a logical file layer within the context of a DBMS. (Use direct file I/O provided by the Operating System)

In bustub, relationship between disk manager & database file is one-to-one map. It is very easy to figure out what page_id does. If higher level ask for reading/writing page, it will call its disk manager with a unique page_id. Then, disk manger will know where physical address) to read/write => file + offset(page_id * PGSIZE)

Storage Layout

Database file layout:

The database file is organized as a heap file, representing as Page Directory. A file has a header page (page_id = 0) to store meta-data, which contains info of table/index {name, root_id}.

# Header Page: meta-data of table/index
 -----------------------------------------------------------------
| RecordCount (4) | Entry_1 name (32) | Entry_1 root_id (4) | ... |
 -----------------------------------------------------------------

Database page layout:

A table is organized as a doubly-linked list of pages. There is no such like header page of table, everything is unordered in a table. The table pages are representing as slotted pages.

If we need a table named "info", call disk manager to get the first page, and invoke GetRootId(root_id) by "info". Then, get 1st table page by root_id and invoke TableHeap by 1st page.

More specific:

# Slotted page format:
---------------------------------------------------------
| HEADER | ... FREE SPACE ... | ... INSERTED TUPLES ... |
---------------------------------------------------------

# Header format (size in bytes):
-----------------------------------------------------------------------
| PageId (4)| LSN (4)| PrevPageId (4)| NextPageId (4)| FreeSpacePtr(4)|
-----------------------------------------------------------------------
---------------------------------------------------------------
| TupleCount (4)| Tuple_1 offset (4) | Tuple_1 size (4) | ... |
---------------------------------------------------------------

Database tuple layout:

In bustub, we use RID (page_id+offset) to identify a tuple. A tuple is a collection of many attribute values. When write to a table page, we need to serialize the meaningful values to a sequence of bytes. It is natural that when read from, deserialize the bytes to attributes (interpreted by DBMS).

There multiple types of values, I will not cover them here. If you want to know more, please refer to src/include/storage/page. One more thing: for varchar type value, there is always 4 bytes size just before it.

# Tuple format:
------------------------------
| SIZE | Attr1|Attr2|Attr3...|
------------------------------

# Varchar format: (Not inlined column)
-----------------------
| LEN | Varchar Bytes |
-----------------------

System Catalog

A DBMS stores meta-data about databases in its internal catalogs. In bustub, system catalog is a non-persistent catalog, which is designed for use by executors within the DBMS execution engine. ~~It seems like there is no way to persistent a database with a catalog, that is we can only use in-memory database or maintain catalog some where else.~~ In general, system catalog is stored in DBMS instead of the database file. But in bustub, we only got some test databases, whose system catalogs are hard-coded.

The catalog contains table info & index info, i.e., the meta-data of indexes and tables. In table info, there are: name, schema, table heap pointer and oid (Object id in catalog). A schema defines a relation with multiple columns. A column specifies an attribute with type, name and length.

# Schema:
----------------------
| Col1 | Col2 | Col3 |
----------------------

# Column
------------------------
| Name | Type | Length |
------------------------

Summary

In summary, database is organized as a file in bustub, is a collection of tables and indexes. Tables & Indexes are representing as a collection of unordered pages containing tuples. We use disk manager to fetch/push pages from/to disk, i.e., reading/writing the database on disk.

Published by Tech Blog - Huang Blog.