萬盛學電腦網

瀏覽器 Windows 10 WPS Office 防毒軟體 資料庫 Excel 教學 檔案管理 Word 教學 網頁製作 裝機必備軟體 Linux 教學

您现在的位置： 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> PHP 程式設計

從零手寫一個文件型 NoSQL 數據庫：PHP 實現 Hash 索引 + 鏈表衝突解決

項目緣起與設計目標

受《PHP 核心技術與最佳實踐》啟發，本文展示如何用純 PHP 實現一個高性能的 嵌入式 Key-Value 存儲引擎。設計目標：

  • 無外部依賴，純文件存儲（適合無法安裝 Redis/Memcached 的環境）
  • 支援 add、get、delete 三大核心操作
  • 採用 哈希桶 + 拉鏈法 解決衝突，查找平均 O(1)
  • 雙文件架構：.idx 索引文件 + .dat 數據文件

存儲結構設計

1. 索引文件結構

分為兩個區域：

  • 桶指針區：固定大小 DB_BUCKET_SIZE * 4 字節（每桶一個 4 字節無符號整數，指向索引記錄區鏈表頭）。
  • 索引記錄區：動態增長，每條記錄固定 DB_INDEX_SIZE = 128 + 12 = 140 字節：
偏移長度字段說明
04 字節next_offset同桶下一條記錄在索引區的偏移（0 表示鏈表結束）
4128 字節key鍵名，不足右填充 \x00
1324 字節data_offset數據在 .dat 文件中的偏移
1364 字節data_len數據長度

2. 數據文件結構

純粹順序追加存儲 Value，無結構化元數據，讀取時由索引指導偏移與長度。

核心算法：Times33 Hash

經典字符串哈希算法，分布均勻、計算快速：

private function times33Hash(string $key): int {
    $key = substr(md5($key), 0, 8); // 取 MD5 前 8 字符增加熵
    $hash = 0;
    for ($i = 0; $i < 8; $i++) {
        $hash += 33 * $hash + ord($key[$i]);
    }
    return $hash & 0x7FFFFFFF; // 保證非負整數
}

完整類實現 (DB.php)

<?php
define('DB_BUCKET_SIZE', 262144);      // 2^18 個桶
define('DB_KEY_SIZE', 128);            // Key 最大長度
define('DB_INDEX_SIZE', DB_KEY_SIZE + 12);

define('DB_SUCCESS', 1);
define('DB_FAILURE', -1);
define('DB_KEY_EXISTS', -2);

class DB {
    private $idx_fp;
    private $dat_fp;
    private $closed = false;

    /** 打開/創建數據庫 */
    public function open(string $pathName): int {
        $idxPath = $pathName . '.idx';
        $datPath = $pathName . '.dat';
        $isNew   = !file_exists($idxPath);

        $mode = $isNew ? 'w+b' : 'r+b';
        $this->idx_fp = fopen($idxPath, $mode);
        $this->dat_fp = fopen($datPath, $mode);
        if (!$this->idx_fp || !$this->dat_fp) return DB_FAILURE;

        if ($isNew) {
            // 初始化桶指針區為全 0
            $zero = pack('L', 0);
            for ($i = 0; $i < DB_BUCKET_SIZE; $i++) {
                fwrite($this->idx_fp, $zero, 4);
            }
        }
        return DB_SUCCESS;
    }

    /** 插入記錄（Key 存在則返回 DB_KEY_EXISTS） */
    public function add(string $key, string $value): int {
        if (strlen($key) > DB_KEY_SIZE) return DB_FAILURE;

        $bucketOffset = ($this->times33Hash($key) % DB_BUCKET_SIZE) * 4;
        $idxEnd = (int)fstat($this->idx_fp)['size'];
        $datEnd = (int)fstat($this->dat_fp)['size'];
        $valLen = strlen($value);

        // 構建索引記錄塊
        $block = pack('L', 0);                    // next = 0
        $block .= $key;
        $block .= str_repeat("\x00", DB_KEY_SIZE - strlen($key)); // 填充
        $block .= pack('L', $datEnd);             // data_offset
        $block .= pack('L', $valLen);             // data_len

        // 讀取桶頭指針
        fseek($this->idx_fp, $bucketOffset, SEEK_SET);
        $head = unpack('L', fread($this->idx_fp, 4))[1];

        if ($head === 0) {
            // 桶為空，直接寫入
            fseek($this->idx_fp, $bucketOffset, SEEK_SET);
            fwrite($this->idx_fp, pack('L', $idxEnd), 4); // 更新桶頭
            fseek($this->idx_fp, 0, SEEK_END);
            fwrite($this->idx_fp, $block, DB_INDEX_SIZE);
            fseek($this->dat_fp, 0, SEEK_END);
            fwrite($this->dat_fp, $value, $valLen);
            return DB_SUCCESS;
        }

        // 桶非空，遍歷鏈表檢查 Key 是否已存在
        $pos = $head;
        $prev = 0;
        while ($pos) {
            fseek($this->idx_fp, $pos, SEEK_SET);
            $rec = fread($this->idx_fp, DB_INDEX_SIZE);
            $currKey = substr($rec, 4, DB_KEY_SIZE);
            if (strncmp($key, $currKey, strlen($key)) === 0) {
                return DB_KEY_EXISTS; // Key 已存在
            }
            $prev = $pos;
            $pos = unpack('L', substr($rec, 0, 4))[1];
        }

        // 追加到鏈表尾部
        fseek($this->idx_fp, $prev, SEEK_SET);
        fwrite($this->idx_fp, pack('L', $idxEnd), 4); // 更新前驅 next
        fseek($this->idx_fp, 0, SEEK_END);
        fwrite($this->idx_fp, $block, DB_INDEX_SIZE);
        fseek($this->dat_fp, 0, SEEK_END);
        fwrite($this->dat_fp, $value, $valLen);
        return DB_SUCCESS;
    }

    /** 查詢記錄 */
    public function get(string $key): ?string {
        $bucketOffset = ($this->times33Hash($key) % DB_BUCKET_SIZE) * 4;
        fseek($this->idx_fp, $bucketOffset, SEEK_SET);
        $pos = unpack('L', fread($this->idx_fp, 4))[1];

        while ($pos) {
            fseek($this->idx_fp, $pos, SEEK_SET);
            $rec = fread($this->idx_fp, DB_INDEX_SIZE);
            $currKey = substr($rec, 4, DB_KEY_SIZE);
            if (strncmp($key, $currKey, strlen($key)) === 0) {
                $dataOff = unpack('L', substr($rec, DB_KEY_SIZE + 4, 4))[1];
                $dataLen = unpack('L', substr($rec, DB_KEY_SIZE + 8, 4))[1];
                fseek($this->dat_fp, $dataOff, SEEK_SET);
                return fread($this->dat_fp, $dataLen);
            }
            $pos = unpack('L', substr($rec, 0, 4))[1];
        }
        return null;
    }

    /** 刪除記錄（僅標記索引移除，數據文件不物理刪除，避免空洞） */
    public function delete(string $key): int {
        $bucketOffset = ($this->times33Hash($key) % DB_BUCKET_SIZE) * 4;
        fseek($this->idx_fp, $bucketOffset, SEEK_SET);
        $head = unpack('L', fread($this->idx_fp, 4))[1];

        $curr = $head;
        $prev = 0;
        while ($curr) {
            fseek($this->idx_fp, $curr, SEEK_SET);
            $rec = fread($this->idx_fp, DB_INDEX_SIZE);
            $next = unpack('L', substr($rec, 0, 4))[1];
            $currKey = substr($rec, 4, DB_KEY_SIZE);
            if (strncmp($key, $currKey, strlen($key)) === 0) {
                // 從鏈表中移除
                if ($prev === 0) {
                    fseek($this->idx_fp, $bucketOffset, SEEK_SET);
                } else {
                    fseek($this->idx_fp, $prev, SEEK_SET);
                }
                fwrite($this->idx_fp, pack('L', $next), 4);
                return DB_SUCCESS;
            }
            $prev = $curr;
            $curr = $next;
        }
        return DB_FAILURE;
    }

    public function close(): void {
        if (!$this->closed) {
            fclose($this->idx_fp);
            fclose($this->dat_fp);
            $this->closed = true;
        }
    }

    private function times33Hash(string $key): int { /* 同前 */ }
}

性能測試結果

<?php
$db = new DB();
$db->open('/var/www/data/mydb');

// 寫入 10,000 條
$start = microtime(true);
for ($i = 0; $i < 10000; $i++) {
    $db->add("key$i", "value$i");
}
echo "寫入耗時: " . (microtime(true) - $start) * 1000 . " ms\n"; // ~793ms

// 讀取 10,000 條
$start = microtime(true);
for ($i = 0; $i < 10000; $i++) {
    $db->get("key$i");
}
echo "讀取耗時: " . (microtime(true) - $start) * 1000 . " ms\n"; // ~149ms

$db->close();

測試環境：PHP 7.4、SSD、單進程。讀取性能接近 Redis 1/10，寫入受限於 fsync 頻率。若需更高吞吐，可增加 fwrite 後調用 fflush 批量提交，或引入內存緩衝區定期刷盤。

適用場景與局限

優勢局限
零依賴、零配置、易部署無並發控制（多進程需外部鎖）
嵌入式應用、邊緣計算、輕量級緩存不支援範圍查詢、事務、備份恢復
數據持久化、重啟不丟失刪除不回收空間，長期運行需重建

總結

這個微型 NoSQL 引擎展示了數據庫核心原理：哈希索引 + 順序存儲 + 拉鏈衝突解決。雖然生產環境仍建議使用 Redis/RocksDB 等成熟方案，但理解其內部機制對於優化 SQL 索引、設計緩存策略、排查性能瓶頸極有裨益。

PHP 程式設計排行

推薦文章

萬盛學電腦網| 日本語版 | 設為首頁 | 加入收藏

copyright © 萬盛學電腦網 all rights reserved