代做program、代写Java，Python程序

日期：2024-04-23 09:37

PM CrustyDB 1: Page Milestone

1/16

CrustyDB 1: Page Milestone

4/19/2024

0 Points Possible

Add Comment

Details

Due Date: Friday, April 19th, 2024 at 11:59 am (Noon)

Welcome to CrustyDB! CrustyDB is an academic Rust-based relational database management

system built by ChiData at The University of Chicago (https://uchi-db.github.io/chidatasite/) , and

it is the work of many contributors. It is designed to be an academic project that can be used for

teaching and a testbed for research projects. We will use the CrustyDB platform to teach you

about database system internals.

The CrustyDB Project

Our approach to building the database system is going to be bottom-up. We start with the storage

manager, the entity responsible for storing the data on the disk, and then work our way upwards

to the query processing engine.

The project is divided into several milestones, each introducing you to a new concept in database

systems. The milestones are as follows:

Crusty DB 1 - Page (This Milestone): You will build a system to persist data onto fixed-sized

pages that store variable values. This milestone requires you to build out a slotted-page storage

system.

Crusty DB 2 - Heapstore: In the next milestone, you will continue to build the storage engine by

implementing a heap file storage manager called the heapstore. If you are taking the graduate

version of this course, you will also implement a buffer pool manager, which caches pages in

memory and implements a page replacement policy.

Crusty DB 3 - Query Operators: In the third milestone, you will implement a set of query

operators that can be used to execute queries on the data stored in the database.

Crusty DB 4 - Choose your own Adventure (Graduate Students Only): If you are taking the

graduate version of this course, you will additionally be tasked with implementing an additional

feature of CrustyDB of your choosing.

Getting Started

We will use a separate upstream repository to manage the files for CrustyDB. You will need to set

up a private repository using Github Classroom, separate from the homework respository you set

up in HW0.

PM CrustyDB 1: Page Milestone

2/16

Step 1

Open the following URL in a browser tab: https://classroom.github.com/a/SW3F_tWN

(https://classroom.github.com/a/SW3F_tWN)

Then complete the following steps:

You may link your GitHub account to a CNetID if you have not already done so. You may skip

this step if you don  t find your CNetID in the list.

You must click   Accept this assignment  , or your repository will not be created. Do not skip

this step!

You will be taken to a page saying your repository is being prepared. It will usually be ready

within a few seconds, and you can just reload the page to confirm your repository is set up.

Please note that this will sometimes take a few minutes.

If you run into any issues, please ask for help on Ed.

You may receive an email from GitHub that looks like the following:

@github-classroom[bot] has invited you to collaborate on the

uchicago-cmsc23500-spr-2024/crustydb-GITHUB_USERNAME repository.

You can go ahead and click on the   view invitation   button to accept the invitation.

Important: Do NOT follow the repository initialization instructions provided by

GitHub. Follow the instructions provided in the next section instead.

Now, you will finish setting up the repository you just requested. You will only need to do this once

since you will be using the same repository for all the CrustyDB milestones this quarter.

Step 1

Verify that your repository has been created on GitHub. To do so, open a browser tab to this URL:

https://github.com/uchicago-cmsc23500-spr-2024/crustydb-GITHUB_USERNAME

where GITHUB_USERNAME is replaced by your GitHub username. If you are not able to open this URL

successfully, please ask for help.

Step 2

Get the SSH URL of the repository from GitHub. In the browser window that you opened to your

repository, under   Quick setup    if you  ve done this kind of thing before  , make sure the   SSH  

button is selected. Your repository URL should look something like this: git@github.com:uchicago?cmsc23500-spr-2024/crustydb-jrandom.git . (Except jrandom will be your GitHub username). We will

refer to this URL as REPO_URL later on.

Step 3

In a new terminal, run the commands listed below.

PM CrustyDB 1: Page Milestone

3/16

Remember to replace GITHUB_USERNAME with your GitHub username and REPO_URL with the SSH

URL that appears on your repository page on GitHub (as described in Step 2)

Here are the commands:

$ cd

$ mkdir -p cmsc23500-spr-2024/crustydb-GITHUB_USERNAME

$ cd cmsc23500-spr-2024/crustydb-GITHUB_USERNAME

$ git init

$ git remote add origin REPO_URL

$ git remote add upstream git@github.com:uchicago-cmsc23500-spr-2024/crustydb-upstream.git

$ git pull upstream main

$ git branch -M main

$ git push -u origin main

Step 4

Let  s do a few quick checks to make sure everything is properly set up.

You should see a few folders including src , docs and some files in the root of the repository.,

The contents of the README.md file will be the following:

# CrustyDB

This is the repository for the Academic Handout version of the CrustyDB project.

Please see your handout instructions for more information.

## CrustyDB 1 - Page Milestone

Implement the slotted page structure in the files `src/storage/heapstore/page.rs`

and `src/storage/heapstore/heap_page.rs`.

Please see your handout instructions for more information.

Do not modify any other files in the repository.

If not, your repository was not correctly initialized. If you followed GitHub  s instructions for

initializing the repository instead of following our instructions, you will need to request a new

repository. Please post on Ed to request that we remove your repository so you can request a new

one.

Next, the files you see in your repository should also be in your repository on GitHub (to check,

use a browser to view

https://github.com/uchicago-cmsc23500-spr-2024/crustydb-GITHUB_USERNAME

where GITHUB_USERNAME is replaced by your GitHub username.)

Next, run this:

$ git remote -v

It should print the following (it is ok if the lines don  t appear in this exact order, as long as all four

lines appear)::

origin git@github.com:uchicago-cmsc23500-spr-2024/crustydb-GITHUB_USERNAME.git (fetch)

origin git@github.com:uchicago-cmsc23500-spr-2024/crustydb-GITHUB_USERNAME.git (push)

PM CrustyDB 1: Page Milestone

4/16

upstream git@github.com:uchicago-cmsc23500-spr-2024/crustydb-upstream.git (fetch)

upstream git@github.com:uchicago-cmsc23500-spr-2024/crustydb-upstream.git (push)

(where your GitHub username will appear instead of GITHUB_USERNAME )

Note

If you realize you entered the wrong value for either the origin or upstream remote, please

note that you will not be able to update it by running git remote add again (you will get an

error message that says something like: error: remote origin already exists ).

Instead, you must run git remote set-url . For example, suppose your GitHub username

is SampleStudent and you entered the wrong value for the origin remote. You can update it

like this

git remote set-url origin git@github.com:uchicago-cmsc23500-spr-2024/crustydb-SampleStud

ent.git

Finally, if you run:

$ git status .

in your crustydb-GITHUB_USERNAME directory, the result should be:

On branch main

Your branch is up to date with 'origin/main'.

nothing to commit, working tree clean

Source Code Layout

Now that you have obtained a copy of the CrustyDB started code, let  s explore its structure.

CrustyDB is set up as a Rust workspace, and various modules/components of the database are

broken into separate packages/crates. To build a specific crate (for example, the common crate),

you would use the following command cargo build -p common . Note if a package/crate depends

on another crate (e.g. the heapstore crate depends on common crate) those crates will

automatically be built as part of the process.

The crates (currently located in src ) are:

common : shared data structures or logical components needed by everything in CrustyDB.

This includes things like tables, errors, logical query plans, ids, some test utilities, etc.

storage : A module that contains multiple storage managers (SM  s). The storage module is

broken into several crates:

storage/heapstore : a storage manager for storing data in heap files.

Additional crates (which will be added in future milestones) include:

PM CrustyDB 1: Page Milestone

5/16

cli-crusty : a command line interface client binary application that can connect and issue

commands/queries to a running CrustyDB server.

optimizer : a crate for generating the query execution plan and for query optimization

queryexe : responsible for executing queries. This contains the operator implementations as

well as the execution code.

server : the binary crate for running a CrustyDB server. This will glue all modules (outside a

client) together.

txn_manager : a near-empty crate for an optional milestone to implement transactions. the use

of transaction is embedded in many other crates, but can be safely ignored for the given

milestones. There is also the use of a logical timestamp throughout many components. You

can safely ignore this.

utilities : utilities for performance benchmarks that will be used by an optional milestone

Note

For the first milestone, you will only be able to see the files

in heapstore and common crates. The other parts of CrustyDB will be added to the

upstream repository from Milestone 2 onwards.

The CrustyDB Storage Manager

In CrustyDB a storage manager (SM) is responsible for persisting all data (aka writing it to disk).

The storage manager is a generic interface that allows us to create different storage managers for

storage strategies. We will be building an SM that stores data in fixed-sized pages within heap

files, called the heapstore. Here  s some more information about storage managers in CrustyDB:

A SM in Crusty is agnostic to what is being stored, as it takes a request to store a value as

bytes (a Vec<u8> ) in a container .

A container could represent a table, an index, a stored result, or anything else you want to

persist.

For example, CrustyDB will create a container for each table/relation stored, and each record

will be stored as a value .

Note that there is a 1-1 relationship between containers and heapfiles: you can think of

 containers   as wrappers that allow the SM to manage things like heapfile access permissions.

Other components in the CrustyDB system are responsible for converting data into bytes for

the SM and interpreting bytes from the SM.

The SM manages access to all other interfaces related to storage tasks, such

as HeapFile or Page , and acts as the sole interface through which different components can

PM CrustyDB 1: Page Milestone

6/16

persist data or interact with data on disk.

Heapstore Design

The heapstore is a storage manager that manages data stored in heap files. Any value that is to

be stored in the database is first converted to a byte array and then passed into the heapstore to

be stored. You  ll learn much more about heap files and storage managers in the next milestone,

but in brief:

A   heapfile   is a struct that manages a file. You can think of this as a wrapper around a file

that contains additional metadata and methods to help you interact with the file.

The heapfile struct will contain info to help you utilize that file in the context of Crusty, but the

file it  s linked to is just a regular file in your filesystem.

A heapfile organizes data as values stored in fixed-sized pages. Each page is a fixed size

(defined by PAGE_SIZE in common::lib.rs ), and the heapfile will manage the pages in the file.

We will specifically be using Slotted Page architecture to manage the values in a page.

Slotted Page Architecture

A heapfile is made up of a sequence of fixed-sized pages (the size being defined

by PAGE_SIZE in common::lib.rs ) concatenated together into one file. In this milestone, you will

focus on one piece of functionality of the heapstore crate, the page. A page is a fixed-sized data

structure that holds variable-sized values (in our case, records) via slotted storage. In slotted

storage, each record inserted into a page is associated with a slot that points to a contiguous

sequence of bytes on the page. A record/value will never be split across pages. The logic for

managing values in a page is as follows:

PM CrustyDB 1: Page Milestone

7/16

When a value is stored in a page, it is associated with a slot_id that should not change.

The page should always assign the lowest available slot_id to an insertion. Therefore, if the

value associated with a given slot_id is deleted from the page, you should reuse

this slot_id (see more on deletion below).

While the location of the actual bytes of a value in a page can change, the slot_id should not.

Note that this means that slot_id s are not tied to a specific location on the page either.

When storing values in a page, the page should insert the value in the   first   available space in

the page. We quote first as it depends on your implementation what first actually means.

If a value is deleted, that space should be reused by a later insert.

When free space is reclaimed and compacted together is up to you; however if there is enough

free space in the page you should always accept an insertion request  C even if the free space

was previously used or is not contiguous.

A page should provide an iterator to return all of the valid values and their

corresponding slot_id stored in the page.

The bytes that make up a page are broken into:

The header, which holds metadata about the page and the values it stores.

Restrictions on the header  s composition and size are detailed in the next section.

The body, which is where the bytes for values are stored, i.e., the actual records, and

comprise the remaining bytes in the page.

Thus the entire page (i.e the header and body) must be packed into a contiguous byte array of

size PAGE_SIZE . Note that while values can differ in size, CrustyDB can reject any value that is

larger than PAGE_SIZE .

Id and Offset types For this milestone, we will use PageId and SlotId types for each distinct

value that is stored in a page. The data types used for these Ids are also defined in common::ids .

A related type definition in page.rs is the Offset type, defined as follows:

pub type Offset = u16;

The Offset type can be used to store a location within the page (as an offset) using just 2 bytes.

Note that Rust will default most lengths or indexes to a usize which is 8 bytes on most systems

(i.e. u64 ).

While it is usually not safe to downcast a usize to a smaller size type (i.e. Offset ), if you are

careful as to what you are indexing into or checking the size of, you can downcast ( x as Offset ) -

assuming your sizes or indexes do not exceed the Offset size bounds ($2^16$). When casting or

defining variables, you should use the CrustyDB specific type for the purpose and not the original

type, as these type definitions can change (e.g., always use SlotId when referring to a slot

number and not u16 ).

PM CrustyDB 1: Page Milestone

8/16

Page and Header Structure

The header should be designed carefully. We will need enough metadata to manage the slots

efficiently, but we also want to minimize the header size to maximize the space available for

storing records. We also have to make some assumptions about the page structure to provide

useful tests that you can use to verify your implementation.

As you decide on your metadata implementation, Here are some tips to guide you:

You will need to store the PageId of the page in the header. The storage manager must know

which page it is reading/writing on.

You will need to store the number of slots on the page so you know how many slots are in use.

You will need to store the offset of the first free space on the page so you know where to insert

the next record.

For each slot, you will need to know the offset of the record in the body of the page. As we

support variable-length records, you will also need to store the length of each record in the slot

metadata.

Consider how you will handle deleted records. As you complete the Page functionality, you will

need to reuse the space of deleted records.

Suggested Steps

PM CrustyDB 1: Page Milestone

9/16

We will now provide a rough order of suggested steps to complete this milestone. Please note

that this is not an exhaustive list of all required tests for the milestone, and you may want to write

(and possibly contribute) additional tests

Note that this milestone will have more guidance than later, so you will be completing the required

functions for much of this milestone. This milestone includes a series of unit and integration tests

to test your page  s functionality. This module has a moderate amount of comments. Not all

packages in CrustyDB will have the same level of comments. Working on a moderate-sized code

base with limited comments and documentation is typical when working with large systems

projects, and this should serve as an excellent introduction to this highly valued skill.

Read page.rs and heap_page.rs

The heap page is the basic building block of this milestone, so start with

the page.rs and heap_page.rs files. page.rs contains the Page struct, which is a generic page

struct that can essentially store any byte array that is of size PAGE_SIZE . heap_page.rs contains

the HeapPage trait, which defines a specific type of page that implements the slotted page

architecture as described above.

Start by reading through the functions and comments to understand the functionality to be

implemented. You may find it helpful to look at the unit tests in these files to check our

understanding of their expected behavior before you code.

As you read through, think about what data structures/metadata you will need to allow for storing

variable-sized values. You may end up adding new helper/utility functions.

Implement the Page struct in page.rs

First, in page.rs , you should implement the methods for the Page struct. All of the data for a

page should be stored in the single 4096-byte array within the struct called data . The methods to

be implemented for this struct are:

new - Create a new page with the given PageId . This function should initialize the data field

of the struct and serialize PageID into the appropriate location of the data byte array.

get_page_id - Get the PageId of the page from the data field.

from_bytes - Create a new page from a byte array. This function should return a Page struct

with the given byte array.

to_bytes - Return a reference to the page as a byte array.

Tip

Note the inputs of the from_bytes and to_bytes functions. They take/return explicit byte

arrays that are of size PAGE_SIZE . The heapstore storage manager will always

PM CrustyDB 1: Page Milestone

10/16

provide/expect byte arrays of this size. In this case, do we need explicit byte conversions

to serialize/deserialize the page using these methods?

After you complete these functions, you should be able to run and pass

the hs_page_create_basic test. As a reminder, to run a single test, you can use the following

command:

cargo test -p heapstore hs_page_create_basic

You may use the same syntax to run any test mentioned in future sections.

Note

You may see some warnings about unused variables or functions. You can ignore these

warnings for now, as they are expected until you implement the rest of the milestone.

Implement the HeapPage trait in heap_page.rs

Once your basic page handling code is working, we can move on to the more advanced functions

listed in heap_page.rs .

The HeapPage trait is a trait that defines the basic functionality of a page in a heapfile. Your page

should continue implementing the slotted page architecture described in the Slotted Page

Architecture section.

Header Utility Functions

At this point, you should work on your header design. You should add any helper/utility functions

that you think will be useful for managing the header information. You should think about how you

will access and update the header information as well as information per slot. We don  t provide

any explicit designs or tests for this, so you will need to think about what you need to implement

to manage the header information effectively.

To add a helper function, you should add a function signature to the HeapPage trait and implement

it in the implementation block for the Page struct. Do not modify any of the existing function

signatures in the HeapPage trait, this will cause the tests to fail.

Once your header and slot design and associated helper functions are done, a natural starting

point is to implement two utility functions as follows:

get_header_size for getting the current header size when serialized (which will be useful for

figuring out how much free space you really have) and

get_free_space to determine the largest block of data free in the page.

Once these are implemented, you should be able to pass

the hs_page_sizes_header_free_space test.

PM CrustyDB 1: Page Milestone

11/16

Inserting and Retrieving Values

With the header working, move on to add_value . This should enable hs_page_simple_insert to

pass. This test adds some tuples (as bytes) to the page and then checks that (1) the slot ids are

assigned in order and (2) that the largest free space and header size are aligned.

Once add_value is correctly implemented, you can move on to get_value and verify

that hs_page_get_value passes. At this point,

tests hs_page_header_size_small , hs_page_header_size_full , and hs_page_no_space should also

work.

Deleting Values

Next, implement the function delete_value , which should free up the bytes previously used by the

slot_id and make the corresponding slot_id available for the next value that may be inserted. Start

with the test hs_page_simple_delete , which only verifies that deleted values are gone. Once this is

working, you will want to ensure you are reusing the space/slots. Please refer to the sections

below, which explain space and SlotId reclamation as well as the expected compaction logic for

a page. I suggest writing a utility function to find the first free space on a page. Here, you might

want to explore inserting byte vectors of different sizes and see if you can replace/reuse the space

as effectively as possible. You should have hs_page_delete_insert working also at this point.

Space Reclamation Example

The page should use deleted space again, but there is no requirement as to when the page should

be reclaimed. In other words, you should never decline an add_value request when there is

enough free space on the page, even if it is scattered in multiple blocks.

To visualize the free space reclamation, imagine the following scenario: We have a value AA, a

value B, a value CC, and three free spaces (-). The SlotIds of AA, B, and CC are 0,1,2

respectively. The physical layout of the page is as follows:

AABCC---

After we delete B, the page looks like this:

AA-CC---

Now, when inserting item D, we could use the free space ( - ) between A & C (resulting in AADCC--

- ) or use free space - after CCC (resulting AA-CCD-- ). Let  s go with the latter option. Either way,

the slotId of D should be 1 (as we should re-use B  s SlotId ). Now the page looks like this:

AA-CCD--

Now, if we want to insert EE , we only have one viable spot/space. The slotId of EE should be 3 ,

and the page should look like this:

AA-CCDEE

PM CrustyDB 1: Page Milestone

12/16

Inserting FF should be rejected (i.e. return None) as it  s too large. No slotId should be assigned.

Inserting G must be accepted as there is room. The slotId of G should be 4 .

AAGCCDEE

Compaction

If we delete G and EE , we again have the following three spaces free.

AA-CCD--

If the page attempts to insert NNNN , this request should not work as there is not enough space to

hold NNNN (i.e. we should return None ). Conversely, an insert for HHH should work, as we have

three spaces available.

However, since they are not contiguous spaces the page will need to compact the existing values

such that three contigious spaces exist on the page. One of the possible layouts after compaction

is as follows:

AACCD---

Now, the insertion of HHH should result in the following layout:

AACCDHHH

Note that since slot 3 is the lowest available slot ID, HHH should be assigned a slot ID of 3. Note

that when and how you compact data is up to you, but you must compact values if there is

expected free space (accounting for necessary header data).

Page Iterator

The last component of this milestone is writing an iterator to   walk   through all valid values stored

on a page. This consuming iterator will move/take ownership of the page. The [Rust

Documentation on Iterators (https://doc.rust-lang.org/book/ch13-02-iterators.html) will help you

understand the iterator pattern and the traits involved in creating and managing iterators in Rust.

To complete this task, you will have to:

Fill in the struct HeapPageIntoIter to hold the metadata for the iterator,

the next function in the impl Iterator for HeapPageIntoIter trait implementation

and into_iter function in impl IntoIterator for Page trait implementation that creates the

iterator from a page.

With these functions, hs_page_iter should pass. The tests will assume that values are returned by

the iterator in ascending SlotId order.

Final Tests

PM CrustyDB 1: Page Milestone

13/16

After completing the iterator, all required functionality for this milestone should be complete, and

you can run all the tests in the file by running the following command:

cargo test -p heapstore hs_page_

One of these tests, hs_page_stress_test is designed to test your implementation with a large

number of randomized insertions and deletions. If you pass this test consistently, you can be fairly

confident that your implementation is correct.

If not, use the Logging and Debugging tips below to debug your implementation. In the past,

students have successfully fixed their implementations by replicating an exact stress test scenario

by logging the insertions/deletions and verifying that the page state is as expected at each step.

Performance Considerations

This project is designed to be cumulative, and a successful implementation of this milestone is

crucial for the next milestones. If you find that your implementation is slow (e.g., the stress test is

taking a long time to run), you should evaluate your implementation for performance bottlenecks.

Some suggestions for optimizing your implementation are:

Memory Allocation: You should avoid unnecessary memory allocations. For example, you

should not make unnecessary copies of byte arrays.

Inline Functions: You should consider inlining your helper functions that are frequently called,

mainly functions used to manage metadata or access individual Slots or Values in the Page.

You can read more about the inline macro in the Rust Reference (https://doc.rust?lang.org/nightly/reference/attributes/codegen.html) . A function can be inlined in Rust by adding

the following attribute to the function definition:

#[inline(always)]

fn my_function() {

// function body

}

(Optional) Benchmarking: If you have completed the milestone and are looking to optimize

your implementation, you can use the criterion crate to benchmark your code. criterion is

a statistics-driven micro-benchmarking library that can help you identify performance

bottlenecks in your code. You can read more about the criterion crate here

(https://bheisler.github.io/criterion.rs/book/index.html) . We have included an optional

benchmark in the heapstore crate, and you can run the benchmark by running the following

command:

cargo bench -p heapstore

Benchmarking is not required for this milestone, but it will be a requirement in future

milestones. Once you have the correctness of your milestone figured out, benchmarking can

be a valuable tool for optimizing your code and allowing you to make progress towards future

milestones.

PM CrustyDB 1: Page Milestone

14/16

A reference implementation of this milestone running on an M1 Macbook Pro had a mean

runtime of 12 for the page_insert_medium benchmark and roughly 1 for

page_insert_large_recs. Performance can vary widely based on your implementation, so

staying within an order of magnitude to these reference numbers is expected for this project.

Logging and Debugging

Logging

CrustyDB uses the env_logger (https://docs.rs/env_logger/0.8.2/env_logger/) crate for logging. Per

the docs on the log crate:

The basic use of the log crate is through the five logging

macros: error! , warn! , info! , debug! and trace! where error! represents the highest-priority

log messages and trace! represents the lowest. The log messages are filtered by configuring the

log level to exclude messages with a lower priority. Each of these macros accept format strings

similarly to println! .

The logging level is set by an environmental variable, RUST_LOG . The easiest way to set the level is

when running a cargo command you set the logging level in the same command, like so:

RUST_LOG=debug cargo run --bin server

However, when running unit tests logging output is suppressed, and the logger is not initialized. If

you want to use logging for a test, you must:

Make sure the test in question calls init() which is defined in common::testutils that

initializes the logger. It can safely be called multiple times.

Tell cargo not to capture the output during testing, and set the level to debug (note the -

- before --nocapture ):

RUST_LOG=debug cargo test -- --nocapture [opt_test_name]

Debugging

It is highly recommended that you set up your IDE to enable Rust debugging (https://uchi?db.github.io/rust-guide/01_getting_started/03_debugging.html) , as it will allow you to set

breakpoints and step through and inspect your code. In particular, the rust_analyzer extension

for VSCode is highly recommended and should provide a hex dump of the page, allowing you to

inspect the page during crucial points in your code.

In addition, we have implemented the Debug`` trait for the Page struct in page.rs . This will allow

you to print out the contents of a page using the {:?} format specifier or by using

the dbg! macro. For example, after you have implemented the function new() for

the Page struct, you can print the hex representation of the page by using dbg! in your code:

let p = Page::new(1);

dbg!(page);

PM CrustyDB 1: Page Milestone

15/16

The following lines will be printed to the console:

[ 0] 01 . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . .

101 empty lines were hidden

[4080] . . . . . . . . . . . . . . . .

Of course, in this simple example, the page is empty except for the first two bytes, which contains

the PageId . You can use the dbg! macro to print out more complex pages and verify that the

implementation is correct.

Scoring and Requirements

Testing

80% of your score on this milestone is based on correctness. Correctness is demonstrated by

passing all of the provided unit tests in the heapstore crate. A majority of the points will come

from the provided tests.

Quality

15% of your score is based on code quality (following good coding conventions, comments, well?organized functions, etc). In addition to suggestions provided by the rust compiler and clippy, we

will also be looking for the following:

1. Comments: You should have comments for all new helper functions, constants and other

identifiers that you add.

2. Proper Types: You should use suitable custom types. For example, you should

use SlotId instead of u16 when referring to a slot number.

3. Magic Numbers: You should avoid magic numbers in your code. If you have a constant that is

used in multiple places, you should define it as a constant at the top of the file.

We will run cargo fmt --check and cargo clippy on your code; if either fails or reports issues on

your code (only the files you edit/turn in), you will receive 0% on code quality.

You can easily run cargo fmt to format your code in the right   style,   and clippy gives you

warnings about your code, for either performance reasons or code quality.

In addition, we have added a GitHub action (located in .github/workflows/rust.yml ) that will

run cargo fmt --check and cargo clippy on your code every time you push to your repository.

This will help you ensure that your code is formatted correctly and that you are following good

coding practices in Rust. You can see the results of these checks in the   Actions   tab of your

repository. If you want to automatically check your code when you commit locally, you can install

a pre-commit hook that runs these checks.

Write Up

PM CrustyDB 1: Page Milestone

16/16

5% is based on your write-up ( docs/my-pg.txt ). The write-up should contain:

A brief description of your solution, in particular, any design decisions you made and why. This

is only needed for the parts of your solution that involve significant work.

How long did you roughly spend on the milestone, and what did you like/dislike?

If you know you were unable to complete this milestone, write up what parts are not working,

how close you think you are, and what part(s) you got stuck on.