從零寫個數據庫系統：磁盤的基本原理和數據庫底層文件系統實現
我做過操作系統，完成過tcpip協議棧，同時也完成過一個具體而微的編譯器，接下來就剩下數據庫了。事實上數據庫的難度系數要大于編譯器，復雜度跟操作系統差不多，因此我一直感覺不好下手。隨著一段時間的積累，我感覺似乎有了入手的方向，因此想試試看，看能不能也從0到1完成一個具有基本功能，能執行一部分sql語言的數據庫系統。由于數據庫系統的難度頗大，我也不確定能完成到哪一步，那么就腳踩香蕉皮，滑到哪算哪吧。
目前數據庫分為兩大類，一類就是Mysql這種，基于文件系統，另一類是redis，完全基于內存。前者的設計比后者要復雜得多，原因在于前者需要將大量數據存放在磁盤上，而磁盤相比于內存，其讀寫速度要慢上好幾個數量級，因此如何組織數據在磁盤上存放，如何通過操控磁盤盡可能減少讀寫延遲，這就需要設計精妙而又復雜的算法。首先我們先看看為何基于文件的數據庫系統要充分考慮并且利用磁盤的特性。
一個磁盤通常包含多個可以旋轉的磁片，磁片上有很多個同心圓，也稱為”軌道“，這些軌道是磁盤用于存儲數據的磁性物質。而軌道也不是全部都能用于存儲數據，它自身還分成了多個組成部分，我們稱為扇區，扇區才是用于存儲數據的地方。扇區之間存在縫隙，這些縫隙無法存儲數據，因此磁頭在將數據寫入連續多個扇區時，需要避開這些縫隙。磁片有上下兩面，因此一個磁片會被兩個磁頭夾住，當要讀取某個軌道上的數據時，磁頭會移動到對應軌道上方，然后等盤片將給定扇區旋轉到磁頭正下方時才能讀取數據，盤片的結構如下：
一個磁盤會有多個盤片以及對應的磁頭組成，其基本結構如下：
從上圖看到，每個盤片都被兩個磁頭夾住，這里需要注意的是，所有磁頭在移動時都必須同時運動，也就是當某個磁頭想要讀取某個軌道時，所有磁頭都必須同時移動到給定軌道，不能是一個磁頭移動到第10軌道，然后另一個磁頭挪到第8軌道，同時在同一時刻只能有一個磁頭進行讀寫，基于這些特點使得磁片的讀寫速度非常慢。
有四個因素會影響影響磁盤讀寫速度，分別為容量，旋轉速度，傳輸速度和磁頭挪動時間。容量就是整個磁盤所能存儲的數據量，現在一個盤片的數據容量能達到40G以上。旋轉速度是指磁盤旋轉一周所需時間，通常情況下磁盤一分鐘能旋轉5400到15000轉。傳輸速率就是數據被磁頭最后輸送到內存的時間。磁頭挪動時間是指磁頭從當前軌道挪動到目標軌道所需要的時間，這個時間最長就是當磁頭從最內部軌道移動到最外部軌道所需時間，為了后面方便推導，我們磁頭挪動的平均時間設置為5ms。
假設我們有一個2個盤片的磁盤，其一分鐘能轉10000圈，磁盤移動的平均時間是5ms，每個盤面包含10000個軌道，每個軌道包含500000字節，于是我們能得到以下數據
首先是磁盤容量，它的計算為 500,000字節 10000 個軌道 4個盤面 = 20,000,000,000字節，大概是20G
我們看看傳輸率，一分鐘能轉10000圈，于是一秒能轉10000 / 60 = 166圈，一個軌道含有500000字節，于是一秒能讀取 166 * 500000 這么多字節，約等于83M。
接下來我們計算一下磁盤的讀寫速度，這個對數據庫的運行效率影響很大。我們要計算的第一個數據叫旋轉延遲，它的意思是當磁頭挪到給定軌道后，等待磁盤將數據起始出旋轉到磁頭正下方的時間，顯然我們并不知道要讀取的數據在軌道哪個確切位置，因此我們認為平均旋轉0.5圈能達到給定位置，由于1秒轉166圈，那么轉一圈的時間是 (1 / 166)秒，那么轉半圈的時間就是(1 / 166) * 0.5 約等于 3ms。
我們看傳輸1個字節所需時間，前面我們看到1秒讀取大概83MB的數據，也就是1秒讀取83,000,000字節，于是讀取一個字節的時間是 (1 / 83,000,000) 大概是0.000012ms。于是傳輸1000字節也就是1MB的時間是0.000012 * 1000 也就是0.012毫秒.
我們看將磁盤上1個字節讀入內存的時間。首先是磁頭挪到給定字節所在的軌道，也就是5毫秒，然后等待給定1字節所在位置旋轉到磁頭下方，也就是3毫秒，然后這個字節傳輸到內存，也就是上面計算的0.000012毫秒，于是總共需要時間大概是8.000012毫秒。
同理將1000字節從磁盤讀入內存或從內存寫入磁盤所需時間就是5 + 3 + 0.012 = 8.012毫秒。這里是一個關鍵，我們看到讀取1000個字節所需時間跟讀取1個字節所需時間幾乎相同，因此要加快讀寫效率，一個方法就是依次讀寫大塊數據。前面我們提到過一個軌道由多個扇區組成，磁盤在讀寫時，一次讀寫的最小數據量就是一個扇區的大小，通常情況下是512字節。
由于磁盤讀寫速度在毫秒級，而內存讀寫速度在納秒級，因此磁盤讀寫相等慢，這就有必要使用某些方法改進讀寫效率。一種方法是緩存，磁盤往往會有一個特定的緩沖器，它一次會將大塊數據讀入緩存，等下次程序讀取磁盤時，它先在緩存里查看數據是否已經存在，存在則立即返回數據，要不然再從磁盤讀取。這個特性對數據庫系統來說作用不大，因此后者必然會有自己的緩存。磁盤緩存的一個作用在于預獲取，當程序要讀取給定軌道的第1個扇區，那么磁盤會把整個軌道的數據都讀入緩存，比較讀取整個軌道所用時間并不比讀取1個扇區多多少。
我們前面提到過，當磁頭移動時，是所有磁頭同時移動到給定軌道，這個特性就有了優化效率的機會，如果我們把同一個文件的的數據都寫入到不同盤面上的同一個軌道，那么讀取文件數據時，我們只需要挪到磁頭一次即可，這種不同盤面的同一個軌道所形成的集合叫柱面。如果文件內容太大，所有盤面上同一個軌道都存放不下，那么另一個策略就是將數據存放到相鄰軌道，這樣磁頭挪動的距離就會短。
另一種改進就是使用多個磁盤，我們把一個文件的部分數據存儲在第一個磁盤，另一部分數據存儲在其他磁盤，由于磁盤數據的讀取能同步進行，于是時間就能同步提升。通常情況下，”民用“級別的數據庫系統不需要考慮磁盤結構，這些是操作系統控制的范疇，最常用的MySQL數據庫，它對磁盤的讀寫也必須依賴于操作系統，因此我們自己實現數據庫時，也必然要依賴于系統。因此在實現上我們將采取的方案是，我們把數據庫的數據用系統文件的形式存儲，但是我們把系統文件抽象成磁盤來看待，在磁盤讀寫中，我們通常把若干個扇區作為一個統一單元來讀寫，這個統一單元叫塊區，于是當我們把操作系統提供的文件看做”磁盤“時，我們讀寫文件也基于”塊區“作為單位，這里看起來有點抽象，在后面代碼實現中我們會讓它具體起來。
接下來我們看看如何實現數據庫系統最底層的文件系統，這里需要注意的是，我們不能把文件當做一個連續的數組來看待，而是要將其作為“磁盤”來看待，因此我們會以區塊為單位來對文件進行讀寫。由于我們不能越過操作系統直接操作磁盤，因此我們需要利用操作系統對磁盤讀寫的優化能力來加快數據庫的讀取效率，基本策略就是，我們要將數據以二進制的文件進行存儲，操作系統會盡量把同一個文件的數據存儲在磁盤同一軌道，或是距離盡可能接近的軌道之間，然后我們再以”頁面“的方式將數據從文件讀入內存，具體的細節可以從代碼實現中看出來，首先創建根目錄simple_db,然后創建子目錄file_manager，這里面用于實現數據庫系層文件系統功能，在file_manager中添加block_id.go，實現代碼如下：
package file_manager
import (
"crypto/sha256"
"fmt"
)
type BlockId struct {
file_name string //區塊所在文件
blk_num uint64 //區塊的標號
}
func NewBlockId(file_name string, blk_num uint64) *BlockId{
return &BlockId {
file_name: file_name,
blk_num: blk_num,
}
}
func (b *BlockId) FileName() string{
return b.file_name
}
func (b *BlockId) Number() uint64 {
return b.blk_num
}
func (b *BlockId) Equals(other *BlockId) bool {
return b.file_name == other.file_name && b.blk_num == other.blk_num
}
func asSha256(o interface{}) string {
h := sha256.New()
h.Write([]byte(fmt.Sprintf("%v", o)))
return fmt.Sprintf("%x", h.Sum(nil))
}
func (b *BlockId) HashCode() string {
return asSha256(*b)
}
BlockId的作用是對區塊的抽象，它對應二進制文件某個位置的一塊連續內存的記錄，它的成分比較簡單，它只包含了塊號和它所包含數據來自于哪個文件。接下來繼續創建Page.go文件，它作用是讓數據庫系統分配一塊內存，然后將數據從二進制文件讀取后存儲在內存中，其實現代碼如下：
package file_manager
import (
"encoding/binary"
)
type Page struct {
buffer []byte
}
func NewPageBySize(block_size uint64) *Page {
bytes := make([]byte, block_size)
return &Page{
buffer: bytes,
}
}
func NewPageByBytes(bytes []byte) *Page {
return &Page{
buffer: bytes,
}
}
func (p *Page) GetInt(offset uint64) uint64 {
num := binary.LittleEndian.Uint64(p.buffer[offset : offset+8])
return num
}
func uint64ToByteArray(val uint64) []byte {
b := make([]byte, 8)
binary.LittleEndian.PutUint64(b, val)
return b
}
func (p *Page) SetInt(offset uint64, val uint64) {
b := uint64ToByteArray(val)
copy(p.buffer[offset:], b)
}
func (p *Page) GetBytes(offset uint64) []byte {
len := binary.LittleEndian.Uint64(p.buffer[offset : offset+8]) //8個字節表示后續二進制數據長度
new_buf := make([]byte, len)
copy(new_buf, p.buffer[offset+8:])
return new_buf
}
func (p *Page) SetBytes(offset uint64, b []byte) {
length := uint64(len(b))
len_buf := uint64ToByteArray(length)
copy(p.buffer[offset:], len_buf)
copy(p.buffer[offset+8:], b)
}
func (p *Page) GetString(offset uint64) string {
str_bytes := p.GetBytes(offset)
return string(str_bytes)
}
func (p *Page) SetString(offset uint64, s string) {
str_bytes := []byte(s)
p.SetBytes(offset, str_bytes)
}
func (p *Page) MaxLengthForString(s string) uint64 {
bs := []byte(s) //返回字符串相對于字節數組的長度
uint64_size := 8 //存儲字符串時預先存儲其長度，也就是uint64,它占了8個字節
return uint64(uint64_size + len(bs))
}
func (p *Page) contents() []byte {
return p.buffer
}
從代碼看，它支持特定數據的讀取，例如從給定偏移寫入或讀取uint64類型的整形，或是讀寫字符串數據，我們添加該類對應的測試代碼，創建page_test.go：
package file_manager
import (
"testing"
"github.com/stretchr/testify/require"
)
func TestSetAndGetInt(t *testing.T) {
page := NewPageBySize(256)
val := uint64(1234)
offset := uint64(23) //指定寫入偏移
page.SetInt(offset, val)
val_got := page.GetInt(offset)
require.Equal(t, val, val_got)
}
func TestSetAndGetByteArray(t *testing.T) {
page := NewPageBySize(256)
bs := []byte{1, 2, 3, 4, 5, 6}
offset := uint64(111)
page.SetBytes(offset, bs)
bs_got := page.GetBytes(offset)
require.Equal(t, bs, bs_got)
}
func TestSetAndGetString(t *testing.T) {
// require.Equal(t, 1, 2) 先讓測試失敗，以確保該測試確實得到了執行
page := NewPageBySize(256)
s := "hello, 世界"
offset := uint64(177)
page.SetString(offset, s)
s_got := page.GetString(offset)
require.Equal(t, s, s_got)
}
func TestMaxLengthForString(t *testing.T) {
//require.Equal(t, 1, 2)
s := "hello, 世界"
s_len := uint64(len([]byte(s)))
page := NewPageBySize(256)
s_len_got := page.MaxLengthForString(s)
require.Equal(t, s_len, s_len_got)
}
func TestGetContents(t *testing.T) {
//require.Equal(t, 1, 2)
bs := []byte{1, 2, 3, 4, 5, 6}
page := NewPageByBytes(bs)
bs_got := page.contents()
require.Equal(t, bs, bs_got)
}
從測試代碼我們可以看到Page類的用處，它就是為了讀寫uint64,和字符串等特定的數據，最后我們完成的是文件管理器對象，生成file_manager.go，然后實現代碼如下：
package file_manager
import (
"os"
"path/filepath"
"strings"
"sync"
)
type FileManager struct {
db_directory string
block_size uint64
is_new bool
open_files map[string]*os.File
mu sync.Mutex
}
func NewFileManager(db_directory string, block_size uint64) (*FileManager, error) {
file_manager := FileManager{
db_directory: db_directory,
block_size: block_size,
is_new: false,
open_files: make(map[string]*os.File),
}
if _, err := os.Stat(db_directory); os.IsNotExist(err) {
//目錄不存在則創建
file_manager.is_new = true
err = os.Mkdir(db_directory, os.ModeDir)
if err != nil {
return nil, err
}
} else {
//目錄存在，則先清除目錄下的臨時文件
err := filepath.Walk(db_directory, func(path string, info os.FileInfo, err error) error {
mode := info.Mode()
if mode.IsRegular() {
name := info.Name()
if strings.HasPrefix(name, "temp") {
//刪除臨時文件
os.Remove(filepath.Join(path, name))
}
}
return nil
})
if err != nil {
return nil, err
}
}
return &file_manager, nil
}
func (f *FileManager) getFile(file_name string) (*os.File, error) {
path := filepath.Join(f.db_directory, file_name)
file, err := os.OpenFile(path, os.O_CREATE|os.O_RDWR, 0644)
if err != nil {
return nil, err
}
f.open_files[path] = file
return file, nil
}
func (f *FileManager) Read(blk *BlockId, p *Page) (int, error) {
f.mu.Lock()
defer f.mu.Unlock()
file, err := f.getFile(blk.FileName())
if err != nil {
return 0, err
}
defer file.Close()
count, err := file.ReadAt(p.contents(), int64(blk.Number()*f.block_size))
if err != nil {
return 0, err
}
return count, nil
}
func (f FileManager) Write(blk *BlockId, p *Page) (int, error) {
f.mu.Lock()
defer f.mu.Unlock()
file, err := f.getFile(blk.FileName())
if err != nil {
return 0, err
}
defer file.Close()
n, err := file.WriteAt(p.contents(), int64(blk.Number()*f.block_size))
if err != nil {
return 0, err
}
return n, nil
}
func (f *FileManager) size(file_name string) (uint64, error) {
file, err := f.getFile(file_name)
if err != nil {
return 0, err
}
fi, err := file.Stat()
if err != nil {
return 0, err
}
return uint64(fi.Size()) / f.block_size, nil
}
func (f *FileManager) Append(file_name string) (BlockId, error) {
new_block_num, err := f.size(file_name)
if err != nil {
return BlockId{}, err
}
blk := NewBlockId(file_name, new_block_num)
file, err := f.getFile(blk.FileName())
if err != nil {
return BlockId{}, err
}
b := make([]byte, f.block_size)
_, err = file.WriteAt(b, int64(blk.Number()*f.block_size)) //讀入空數據相當于擴大文件長度
if err != nil {
return BlockId{}, nil
}
return *blk, nil
}
func (f *FileManager) IsNew() bool {
return f.is_new
}
func (f *FileManager) BlockSize() uint64 {
return f.block_size
}
文件管理器在創建時會在給定路徑創建一個文件夾，然后特定的二進制文件就會存儲在該文件夾下，例如我們的數據庫系統在創建一個表時，表的數據會對應到一個二進制文件，同時針對表的操作還會生成log等日志文件，這一系列文件就會生成在給定的目錄下，file_manager類會利用前面實現的BlockId和Page類來管理二進制數據的讀寫，其實現如下：
package file_manager
import (
"os"
"path/filepath"
"strings"
"sync"
)
type FileManager struct {
db_directory string
block_size uint64
is_new bool
open_files map[string]*os.File
mu sync.Mutex
}
func NewFileManager(db_directory string, block_size uint64) (*FileManager, error) {
file_manager := FileManager{
db_directory: db_directory,
block_size: block_size,
is_new: false,
open_files: make(map[string]*os.File),
}
if _, err := os.Stat(db_directory); os.IsNotExist(err) {
//目錄不存在則創建
file_manager.is_new = true
err = os.Mkdir(db_directory, os.ModeDir)
if err != nil {
return nil, err
}
} else {
//目錄存在，則先清除目錄下的臨時文件
err := filepath.Walk(db_directory, func(path string, info os.FileInfo, err error) error {
mode := info.Mode()
if mode.IsRegular() {
name := info.Name()
if strings.HasPrefix(name, "temp") {
//刪除臨時文件
os.Remove(filepath.Join(path, name))
}
}
return nil
})
if err != nil {
return nil, err
}
}
return &file_manager, nil
}
func (f *FileManager) getFile(file_name string) (*os.File, error) {
path := filepath.Join(f.db_directory, file_name)
file, err := os.OpenFile(path, os.O_CREATE|os.O_RDWR, 0644)
if err != nil {
return nil, err
}
f.open_files[path] = file
return file, nil
}
func (f *FileManager) Read(blk *BlockId, p *Page) (int, error) {
f.mu.Lock()
defer f.mu.Unlock()
file, err := f.getFile(blk.FileName())
if err != nil {
return 0, err
}
defer file.Close()
count, err := file.ReadAt(p.contents(), int64(blk.Number()*f.block_size))
if err != nil {
return 0, err
}
return count, nil
}
func (f FileManager) Write(blk *BlockId, p *Page) (int, error) {
f.mu.Lock()
defer f.mu.Unlock()
file, err := f.getFile(blk.FileName())
if err != nil {
return 0, err
}
defer file.Close()
n, err := file.WriteAt(p.contents(), int64(blk.Number()*f.block_size))
if err != nil {
return 0, err
}
return n, nil
}
func (f *FileManager) size(file_name string) (uint64, error) {
file, err := f.getFile(file_name)
if err != nil {
return 0, err
}
fi, err := file.Stat()
if err != nil {
return 0, err
}
return uint64(fi.Size()) / f.block_size, nil
}
func (f *FileManager) Append(file_name string) (BlockId, error) {
new_block_num, err := f.size(file_name)
if err != nil {
return BlockId{}, err
}
blk := NewBlockId(file_name, new_block_num)
file, err := f.getFile(blk.FileName())
if err != nil {
return BlockId{}, err
}
b := make([]byte, f.block_size)
_, err = file.WriteAt(b, int64(blk.Number()*f.block_size)) //讀入空數據相當于擴大文件長度
if err != nil {
return BlockId{}, nil
}
return *blk, nil
}
func (f *FileManager) IsNew() bool {
return f.is_new
}
func (f *FileManager) BlockSize() uint64 {
return f.block_size
}
由于我們要確保文件讀寫時要線程安全，因此它的write和read接口在調用時都先獲取互斥鎖，接下來我們看看它的測試用例由此來了解它的作用，創建file_manager_test.go，實現代碼如下：
package file_manager
import (
"testing"
"github.com/stretchr/testify/require"
)
func TestFileManager(t *testing.T) {
// require.Equal(t, 1, 2) //確保用例能執行
fm, _ := NewFileManager("file_test", 400)
blk := NewBlockId("testfile", 2)
p1 := NewPageBySize(fm.BlockSize())
pos1 := uint64(88)
s := "abcdefghijklm"
p1.SetString(pos1, s)
size := p1.MaxLengthForString(s)
pos2 := pos1 + size
val := uint64(345)
p1.SetInt(pos2, val)
fm.Write(blk, p1)
p2 := NewPageBySize(fm.BlockSize())
fm.Read(blk, p2)
require.Equal(t, val, p2.GetInt(pos2))
require.Equal(t, s, p2.GetString(pos1))
}
通過運行上面測試用例可以得知file_manager的基本用法。它的本質是為磁盤上創建對應目錄，并數據庫的表以及和表操作相關的log日志以二進制文件的方式存儲在目錄下，同時支持上層模塊進行相應的讀寫操作，它更詳細的作用在我們后續的開發中會展現出來。
