從零寫個數(shù)據(jù)庫系統(tǒng)：磁盤的基本原理和數(shù)據(jù)庫底層文件系統(tǒng)實現(xiàn)
我做過操作系統(tǒng)，完成過tcpip協(xié)議棧，同時也完成過一個具體而微的編譯器，接下來就剩下數(shù)據(jù)庫了。事實上數(shù)據(jù)庫的難度系數(shù)要大于編譯器，復(fù)雜度跟操作系統(tǒng)差不多，因此我一直感覺不好下手。隨著一段時間的積累，我感覺似乎有了入手的方向，因此想試試看，看能不能也從0到1完成一個具有基本功能，能執(zhí)行一部分sql語言的數(shù)據(jù)庫系統(tǒng)。由于數(shù)據(jù)庫系統(tǒng)的難度頗大，我也不確定能完成到哪一步，那么就腳踩香蕉皮，滑到哪算哪吧。
目前數(shù)據(jù)庫分為兩大類，一類就是Mysql這種，基于文件系統(tǒng)，另一類是redis，完全基于內(nèi)存。前者的設(shè)計比后者要復(fù)雜得多，原因在于前者需要將大量數(shù)據(jù)存放在磁盤上，而磁盤相比于內(nèi)存，其讀寫速度要慢上好幾個數(shù)量級，因此如何組織數(shù)據(jù)在磁盤上存放，如何通過操控磁盤盡可能減少讀寫延遲，這就需要設(shè)計精妙而又復(fù)雜的算法。首先我們先看看為何基于文件的數(shù)據(jù)庫系統(tǒng)要充分考慮并且利用磁盤的特性。
一個磁盤通常包含多個可以旋轉(zhuǎn)的磁片，磁片上有很多個同心圓，也稱為”軌道“，這些軌道是磁盤用于存儲數(shù)據(jù)的磁性物質(zhì)。而軌道也不是全部都能用于存儲數(shù)據(jù)，它自身還分成了多個組成部分，我們稱為扇區(qū)，扇區(qū)才是用于存儲數(shù)據(jù)的地方。扇區(qū)之間存在縫隙，這些縫隙無法存儲數(shù)據(jù)，因此磁頭在將數(shù)據(jù)寫入連續(xù)多個扇區(qū)時，需要避開這些縫隙。磁片有上下兩面，因此一個磁片會被兩個磁頭夾住，當(dāng)要讀取某個軌道上的數(shù)據(jù)時，磁頭會移動到對應(yīng)軌道上方，然后等盤片將給定扇區(qū)旋轉(zhuǎn)到磁頭正下方時才能讀取數(shù)據(jù)，盤片的結(jié)構(gòu)如下：
一個磁盤會有多個盤片以及對應(yīng)的磁頭組成，其基本結(jié)構(gòu)如下：
從上圖看到，每個盤片都被兩個磁頭夾住，這里需要注意的是，所有磁頭在移動時都必須同時運動，也就是當(dāng)某個磁頭想要讀取某個軌道時，所有磁頭都必須同時移動到給定軌道，不能是一個磁頭移動到第10軌道，然后另一個磁頭挪到第8軌道，同時在同一時刻只能有一個磁頭進行讀寫，基于這些特點使得磁片的讀寫速度非常慢。
有四個因素會影響影響磁盤讀寫速度，分別為容量，旋轉(zhuǎn)速度，傳輸速度和磁頭挪動時間。容量就是整個磁盤所能存儲的數(shù)據(jù)量，現(xiàn)在一個盤片的數(shù)據(jù)容量能達到40G以上。旋轉(zhuǎn)速度是指磁盤旋轉(zhuǎn)一周所需時間，通常情況下磁盤一分鐘能旋轉(zhuǎn)5400到15000轉(zhuǎn)。傳輸速率就是數(shù)據(jù)被磁頭最后輸送到內(nèi)存的時間。磁頭挪動時間是指磁頭從當(dāng)前軌道挪動到目標(biāo)軌道所需要的時間，這個時間最長就是當(dāng)磁頭從最內(nèi)部軌道移動到最外部軌道所需時間，為了后面方便推導(dǎo)，我們磁頭挪動的平均時間設(shè)置為5ms。
假設(shè)我們有一個2個盤片的磁盤，其一分鐘能轉(zhuǎn)10000圈，磁盤移動的平均時間是5ms，每個盤面包含10000個軌道，每個軌道包含500000字節(jié)，于是我們能得到以下數(shù)據(jù)
首先是磁盤容量，它的計算為 500,000字節(jié) 10000 個軌道 4個盤面 = 20,000,000,000字節(jié)，大概是20G
我們看看傳輸率，一分鐘能轉(zhuǎn)10000圈，于是一秒能轉(zhuǎn)10000 / 60 = 166圈，一個軌道含有500000字節(jié)，于是一秒能讀取 166 * 500000 這么多字節(jié)，約等于83M。
接下來我們計算一下磁盤的讀寫速度，這個對數(shù)據(jù)庫的運行效率影響很大。我們要計算的第一個數(shù)據(jù)叫旋轉(zhuǎn)延遲，它的意思是當(dāng)磁頭挪到給定軌道后，等待磁盤將數(shù)據(jù)起始出旋轉(zhuǎn)到磁頭正下方的時間，顯然我們并不知道要讀取的數(shù)據(jù)在軌道哪個確切位置，因此我們認為平均旋轉(zhuǎn)0.5圈能達到給定位置，由于1秒轉(zhuǎn)166圈，那么轉(zhuǎn)一圈的時間是 (1 / 166)秒，那么轉(zhuǎn)半圈的時間就是(1 / 166) * 0.5 約等于 3ms。
我們看傳輸1個字節(jié)所需時間，前面我們看到1秒讀取大概83MB的數(shù)據(jù)，也就是1秒讀取83,000,000字節(jié)，于是讀取一個字節(jié)的時間是 (1 / 83,000,000) 大概是0.000012ms。于是傳輸1000字節(jié)也就是1MB的時間是0.000012 * 1000 也就是0.012毫秒.
我們看將磁盤上1個字節(jié)讀入內(nèi)存的時間。首先是磁頭挪到給定字節(jié)所在的軌道，也就是5毫秒，然后等待給定1字節(jié)所在位置旋轉(zhuǎn)到磁頭下方，也就是3毫秒，然后這個字節(jié)傳輸?shù)絻?nèi)存，也就是上面計算的0.000012毫秒，于是總共需要時間大概是8.000012毫秒。
同理將1000字節(jié)從磁盤讀入內(nèi)存或從內(nèi)存寫入磁盤所需時間就是5 + 3 + 0.012 = 8.012毫秒。這里是一個關(guān)鍵，我們看到讀取1000個字節(jié)所需時間跟讀取1個字節(jié)所需時間幾乎相同，因此要加快讀寫效率，一個方法就是依次讀寫大塊數(shù)據(jù)。前面我們提到過一個軌道由多個扇區(qū)組成，磁盤在讀寫時，一次讀寫的最小數(shù)據(jù)量就是一個扇區(qū)的大小，通常情況下是512字節(jié)。
由于磁盤讀寫速度在毫秒級，而內(nèi)存讀寫速度在納秒級，因此磁盤讀寫相等慢，這就有必要使用某些方法改進讀寫效率。一種方法是緩存，磁盤往往會有一個特定的緩沖器，它一次會將大塊數(shù)據(jù)讀入緩存，等下次程序讀取磁盤時，它先在緩存里查看數(shù)據(jù)是否已經(jīng)存在，存在則立即返回數(shù)據(jù)，要不然再從磁盤讀取。這個特性對數(shù)據(jù)庫系統(tǒng)來說作用不大，因此后者必然會有自己的緩存。磁盤緩存的一個作用在于預(yù)獲取，當(dāng)程序要讀取給定軌道的第1個扇區(qū)，那么磁盤會把整個軌道的數(shù)據(jù)都讀入緩存，比較讀取整個軌道所用時間并不比讀取1個扇區(qū)多多少。
我們前面提到過，當(dāng)磁頭移動時，是所有磁頭同時移動到給定軌道，這個特性就有了優(yōu)化效率的機會，如果我們把同一個文件的的數(shù)據(jù)都寫入到不同盤面上的同一個軌道，那么讀取文件數(shù)據(jù)時，我們只需要挪到磁頭一次即可，這種不同盤面的同一個軌道所形成的集合叫柱面。如果文件內(nèi)容太大，所有盤面上同一個軌道都存放不下，那么另一個策略就是將數(shù)據(jù)存放到相鄰軌道，這樣磁頭挪動的距離就會短。
另一種改進就是使用多個磁盤，我們把一個文件的部分數(shù)據(jù)存儲在第一個磁盤，另一部分數(shù)據(jù)存儲在其他磁盤，由于磁盤數(shù)據(jù)的讀取能同步進行，于是時間就能同步提升。通常情況下，”民用“級別的數(shù)據(jù)庫系統(tǒng)不需要考慮磁盤結(jié)構(gòu)，這些是操作系統(tǒng)控制的范疇，最常用的MySQL數(shù)據(jù)庫，它對磁盤的讀寫也必須依賴于操作系統(tǒng)，因此我們自己實現(xiàn)數(shù)據(jù)庫時，也必然要依賴于系統(tǒng)。因此在實現(xiàn)上我們將采取的方案是，我們把數(shù)據(jù)庫的數(shù)據(jù)用系統(tǒng)文件的形式存儲，但是我們把系統(tǒng)文件抽象成磁盤來看待，在磁盤讀寫中，我們通常把若干個扇區(qū)作為一個統(tǒng)一單元來讀寫，這個統(tǒng)一單元叫塊區(qū)，于是當(dāng)我們把操作系統(tǒng)提供的文件看做”磁盤“時，我們讀寫文件也基于”塊區(qū)“作為單位，這里看起來有點抽象，在后面代碼實現(xiàn)中我們會讓它具體起來。
接下來我們看看如何實現(xiàn)數(shù)據(jù)庫系統(tǒng)最底層的文件系統(tǒng)，這里需要注意的是，我們不能把文件當(dāng)做一個連續(xù)的數(shù)組來看待，而是要將其作為“磁盤”來看待，因此我們會以區(qū)塊為單位來對文件進行讀寫。由于我們不能越過操作系統(tǒng)直接操作磁盤，因此我們需要利用操作系統(tǒng)對磁盤讀寫的優(yōu)化能力來加快數(shù)據(jù)庫的讀取效率，基本策略就是，我們要將數(shù)據(jù)以二進制的文件進行存儲，操作系統(tǒng)會盡量把同一個文件的數(shù)據(jù)存儲在磁盤同一軌道，或是距離盡可能接近的軌道之間，然后我們再以”頁面“的方式將數(shù)據(jù)從文件讀入內(nèi)存，具體的細節(jié)可以從代碼實現(xiàn)中看出來，首先創(chuàng)建根目錄simple_db,然后創(chuàng)建子目錄file_manager，這里面用于實現(xiàn)數(shù)據(jù)庫系層文件系統(tǒng)功能，在file_manager中添加block_id.go，實現(xiàn)代碼如下：
package file_manager
import (
"crypto/sha256"
"fmt"
)
type BlockId struct {
file_name string //區(qū)塊所在文件
blk_num uint64 //區(qū)塊的標(biāo)號
}
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的作用是對區(qū)塊的抽象，它對應(yīng)二進制文件某個位置的一塊連續(xù)內(nèi)存的記錄，它的成分比較簡單，它只包含了塊號和它所包含數(shù)據(jù)來自于哪個文件。接下來繼續(xù)創(chuàng)建Page.go文件，它作用是讓數(shù)據(jù)庫系統(tǒng)分配一塊內(nèi)存，然后將數(shù)據(jù)從二進制文件讀取后存儲在內(nèi)存中，其實現(xiàn)代碼如下：
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個字節(jié)表示后續(xù)二進制數(shù)據(jù)長度
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) //返回字符串相對于字節(jié)數(shù)組的長度
uint64_size := 8 //存儲字符串時預(yù)先存儲其長度，也就是uint64,它占了8個字節(jié)
return uint64(uint64_size + len(bs))
}
func (p *Page) contents() []byte {
return p.buffer
}
從代碼看，它支持特定數(shù)據(jù)的讀取，例如從給定偏移寫入或讀取uint64類型的整形，或是讀寫字符串?dāng)?shù)據(jù)，我們添加該類對應(yīng)的測試代碼，創(chuàng)建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) 先讓測試失敗，以確保該測試確實得到了執(zhí)行
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,和字符串等特定的數(shù)據(jù)，最后我們完成的是文件管理器對象，生成file_manager.go，然后實現(xiàn)代碼如下：
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) {
//目錄不存在則創(chuàng)建
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)) //讀入空數(shù)據(jù)相當(dāng)于擴大文件長度
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
}
文件管理器在創(chuàng)建時會在給定路徑創(chuàng)建一個文件夾，然后特定的二進制文件就會存儲在該文件夾下，例如我們的數(shù)據(jù)庫系統(tǒng)在創(chuàng)建一個表時，表的數(shù)據(jù)會對應(yīng)到一個二進制文件，同時針對表的操作還會生成log等日志文件，這一系列文件就會生成在給定的目錄下，file_manager類會利用前面實現(xiàn)的BlockId和Page類來管理二進制數(shù)據(jù)的讀寫，其實現(xiàn)如下：
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) {
//目錄不存在則創(chuàng)建
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)) //讀入空數(shù)據(jù)相當(dāng)于擴大文件長度
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接口在調(diào)用時都先獲取互斥鎖，接下來我們看看它的測試用例由此來了解它的作用，創(chuàng)建file_manager_test.go，實現(xiàn)代碼如下：
package file_manager
import (
"testing"
"github.com/stretchr/testify/require"
)
func TestFileManager(t *testing.T) {
// require.Equal(t, 1, 2) //確保用例能執(zhí)行
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的基本用法。它的本質(zhì)是為磁盤上創(chuàng)建對應(yīng)目錄，并數(shù)據(jù)庫的表以及和表操作相關(guān)的log日志以二進制文件的方式存儲在目錄下，同時支持上層模塊進行相應(yīng)的讀寫操作，它更詳細的作用在我們后續(xù)的開發(fā)中會展現(xiàn)出來。
