CMU数据库15-445/645

发表于 更新于 分类于 ， 阅读次数：

学弟突然对你发出了击剑邀请

建议先大概看一遍CMU 15-445/645 (Spring 2023) Database Systems 通关指北。

搭建好WSL2的ubuntu环境，配置好github的ssh，在WSL中clone该项目，而不是Windows下clone。不要用windows下面的账户去管控、提交WSL的git，会有文件权限变化问题。

Schedule

目标 周一 周二 周三 周四 周五
Project:C++ Primer
Homework:SQL		 1. 课程概述
2. C++ Primer		 1. 关系模型和代数 1. 现代SQL
2. 作业
Project:Buffer Pool Manager
Homework:Storage
 1. 数据库存储
Homework:Indexes & Filters
Project:Database Index
Project:Query Execution
Homework:Query Execution
Homework:Concurrency Control
Project:Concurrency Control
Homework:Distributed Databases

PROJECT

  1. C++ Primer：完成hyperloglog.h、hyperloglog_presto.h
  2. Buffer Pool Manager：
  3. Database Index：
  4. Query Execution：
  5. Concurrency Control：

C++ Primer

HyperLogLog

HyperLogLog是一种概率数据结构，用于统计一个大数据集合的基数，仅使用传统方法所需内存的一小部分。

使用哈希函数将每一个字符串key均匀地映射到二进制上。

HLL

定义几个值：

  • $b$ ： 哈希值的前 $b$ 位作为索引，用于将哈希值的剩余位映射到某个固定的桶，一共 $2^b$ 个桶。
  • $m$ ：桶的个数，记为 $register[m]$， $m = 2^b$。
  • $p$ ：最左侧第一个 $1$ 的位置。

其中 $constant=0.79402,N=m$。

Task #1 MSB

hyperloglog.h中有几个函数需要实现：

  • HyperLogLog(inital_bits): 桶内的前 bits (b) 会被用来计数。
  • GetCardinality(): 返回给定集合的基数值。
  • AddElem(val): 计算并将 $val$ 放入 $register$中。
  • ComputeCardinality(): 根据上述公式计算基数。

还可以再添加几个辅助函数：

  • ComputeBinary(hash_t hash): 计算给定哈希值的二进制值。哈希值应转换为 64 位二进制（否则测试可能失败）。
  • PositionOfLeftmostOne(....): 计算最左侧的1的位置。

要计算哈希值，可以使用给定的函数：

  • CalculateHash(...) ： to calculate hash

请参考 std::bitset 库中的二进制存储方式。当获得十进制数值时，将其转换为小于或等于十进制的最大整数。详情请参考 std::floor。

Task #2 LSB

可以先看下HyperLogLog in Presto这篇文章，当元素较多的时候，由 $sparse$ 转为 $dense$ 模式。

In hyperloglog_presto.h following functions will be used for grading:

  • GetDenseBucket() - 返回密集桶数组
  • GetOverflowBucketOfIdx(..) - 返回给定索引的溢出位集（如果存在）。
  • GetCardinality() - 返回基数值

实现以下功能：

  • HyperLogLogPresto(initial_bits)- HyperLogLogPresto 的构造函数
  • AddElem()- 计算并将值放入寄存器中。
  • ComputeCardinality()- 根据上述公式计算基数。

为了计算哈希值，您可以使用给定的函数：

  • CalculateHash(...)- 计算哈希值

Gradescope注册：How can people not enrolled in the class test their projects?

项目的所有源代码均可在Github上找到。非 CMU 学生可以使用Gradescope提交网站（入口代码： WWWJZ5）。⚠请确保将您的学校设置为“Carnegie Mellon University”。我们将在 CMU 学生的截止日期**之后**在 Gradescope 上为非 CMU 学生提供每项作业的自动评分器。作为向公众开放此功能的交换条件，我们要求您不要在Github 或其他源代码存储库上公开您的项目实现。

6d5e57a4-6787-4563-80e6-f420c4aafe46

注意每年的邀请码不一样。

调试

项目中有用GTest写好的测试程序，将第二个参数的DISABLE_前缀去掉即可运行。

通过本地测试用例后，提交到Gradescope上进行最终的评分。

提交

将src目录下需要打包的文件用zip命令打包。

TODO

看了前3P

课程总体概述

数据库管理系统的设计与实现，并不注重与实践和应用，注重如何去构建和设计。CMU 95-703和CMU 15-415更注重实践。

在这门课中需要自己构建数据库存储管理器，注意这里并不是完整的数据库系统。

面向disk的数据库管理系统，支持Volcano风格查询处理，支持插拔式API，这样可以替换系统中算法，使用不同索引数据结构或者日志格式和控制方案。

有五个作业：

  1. SQLlite数据库查询

HOW TO CHECK

CLion+WSL环境配置

https://www.jetbrains.com/help/clion/how-to-use-wsl-development-environment-in-product.html#wsl-tooclhain

https://blog.csdn.net/jiexijihe945/article/details/131894202

1. 将CLion官方提供shell脚本放在WSL的ubuntu系统下执行

直接执行

1
wget https://raw.githubusercontent.com/JetBrains/clion-wsl/master/ubuntu_setup_env.sh && bash ubuntu_setup_env.sh

或者将shell拷贝到WSL中执行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#!/bin/bash
set -e

SSHD_LISTEN_ADDRESS=127.0.0.1

SSHD_PORT=2222
SSHD_FILE=/etc/ssh/sshd_config
SUDOERS_FILE=/etc/sudoers
  
# 0. update package lists
sudo apt-get update

# 0.1. reinstall sshd (workaround for initial version of WSL)
sudo apt remove -y --purge openssh-server
sudo apt install -y openssh-server

# 0.2. install basic dependencies
sudo apt install -y cmake ninja-build gcc clang gdb valgrind build-essential

# 1.1. configure sshd
sudo cp $SSHD_FILE ${SSHD_FILE}.`date '+%Y-%m-%d_%H-%M-%S'`.back
sudo sed -i '/^Port/ d' $SSHD_FILE
sudo sed -i '/^ListenAddress/ d' $SSHD_FILE
sudo sed -i '/^UsePrivilegeSeparation/ d' $SSHD_FILE
sudo sed -i '/^PasswordAuthentication/ d' $SSHD_FILE
echo "# configured by CLion"      | sudo tee -a $SSHD_FILE
echo "ListenAddress ${SSHD_LISTEN_ADDRESS}"    | sudo tee -a $SSHD_FILE
echo "Port ${SSHD_PORT}"          | sudo tee -a $SSHD_FILE
echo "UsePrivilegeSeparation no"  | sudo tee -a $SSHD_FILE
echo "PasswordAuthentication yes" | sudo tee -a $SSHD_FILE
# 1.2. apply new settings
sudo service ssh --full-restart
  
# 2. autostart: run sshd 
sed -i '/^sudo service ssh --full-restart/ d' ~/.bashrc
echo "%sudo ALL=(ALL) NOPASSWD: /usr/sbin/service ssh --full-restart" | sudo tee -a $SUDOERS_FILE
cat << 'EOF' >> ~/.bashrc
sshd_status=$(service ssh status)
if [[ $sshd_status = *"is not running"* ]]; then
  sudo service ssh --full-restart
fi
EOF
  

# summary: SSHD config info
echo 
echo "SSH server parameters ($SSHD_FILE):"
echo "ListenAddress ${SSHD_LISTEN_ADDRESS}"
echo "Port ${SSHD_PORT}"
echo "UsePrivilegeSeparation no"
echo "PasswordAuthentication yes"

配置CLion toolchain

在工具链中新增一个WSL。

CMake中新建一个Debug-WSL.

配置CLion Deployment

设置根目录为

1
/home/yankf/prj

img

如果勾选rsync，需要另外配置，后续再说。

配置

img

CLion编译运行

1
2
sudo apt-get install clang-format
sudo apt-get install clang-tidy

安装后再执行

1
2
3
4
5
rm -rf build
mkdir build && cd build
cmake ..
make format
make check-clang-tidy-p0

没看到报error大概就是OK的。

已过时的内容

参考材料

教材是数据库系统概念第七版。

CMU 15-445: Database Systems中文简介

日程表

BusTub

[中文讲解] CMU-15445 数据库内核-Moody-老师

【双语字幕机翻+资料下载】CMU 14-455 | 数据库系统导论(2019·完整版)

【卡内基梅隆大学】CMU-15-445/645 Database Systems | 感觉是机翻 (Fall 2021)

https://www.bilibili.com/video/BV1rN411f7Ef

很全的公开课笔记Fall 2019

1. 关系模型

  1. 关系结构：可以理解为数据表table
  2. 数据完整性：
  3. 操纵和访问：