老山君 發表於 2023-12-7 00:00:00

2000 行代码，带你写一个自己的 SQL 数据库

<p>
        在 C 被当做“高级语言”，雷布斯和小马哥还在写代码的年代，<strong>数据库</strong>还不是一个成熟的事物。</p>
<p data-track="3">
        和很多技术从简单到复杂的发展历程不太一样，数据库首先成熟并被大规模使用的是 RDBMS（关系型数据管理系统），后来才逐渐兴起了实现相对简单，以 Redis 为代表的 KV 型的数据库。</p>
<p data-track="4">
        数据库从后端的技术上看是一个算法、数据结构、系统工程、性能优化的交汇点。</p>
<p data-track="5">
        笔者一直对数据库领域充满了兴趣，前前后后主导和参与了很多数据库及相关系统的开发。这三年的主要业余时间都在研究数据库，由于大多数数据库项目都历史悠久，代码量基本都在50万行以上，阅读起来让人颇感头疼。咬牙坚持了两年，有了一点点心得。</p>
<p data-track="6">
        因此决定写一个<strong>代码量尽量少</strong>，但又能有<strong>现代数据库的基本架构的项目</strong>，于是花了一周时间写了<strong>“GO SQL DB”</strong>。</p>
<p data-track="7">
        “Go SQL DB” 是一个研究目的的<strong>支持SQL查询的关系型</strong>数据库。主要目标是为了向数据库爱好者展示一个关系型数据库的基本原理和关键设计。</p>
<p data-track="8">
        因此，为了便于理解，采取了很多取巧但不是很严谨的设计，代码量控制在了 2000 行左右（包含了 400 多行的单元测试代码）。</p>
<div class="pgc-img">
        <img title="2000 行代码，带你写一个自己的 SQL 数据库" alt="2000 行代码，带你写一个自己的 SQL 数据库" class="syl-page-img" src="https://zhuji.jb51.net/uploads/img/202305/6ae37b2a00a97dd815c50012a0877b45.jpg">
</div>
<p>
        <strong>特性列表</strong></p>
<ol start="1">
<li>
                纯 Golang 实现，不依赖任何第三方包。仅在单元测试中引入了 goconvey</li>
        <li>
                单元测试覆盖率≈ 73.5%</li>
</ol>
<p>
        <strong>存储引擎</strong></p>
<ol start="1">
<li>
                基于 B+Tree 的数据检索结构</li>
        <li>
                基于 4KB 分页的磁盘持久化引擎</li>
        <li>
                接近 POD（Plain Old Data）的序列化 &amp; 反序列化</li>
</ol>
<p>
        <strong>SQL Parser</strong></p>
<ol start="1">
<li>
                Tokenizer 基于 text/scanner 实现</li>
        <li>
                支持简单的 SELECT、INSERT 语法</li>
        <li>
                SELECT 支持数值类型的 WHERE</li>
        <li>
                支持 LIMIT，但暂不支持 ORDER BY</li>
        <li>
                如果你想要了解可以生产可用的 SQL Parser 是如何实现的，请参考我从 CrockroachDB 剥离的 SQL-2011 标准支持的 SQL Parser</li>
</ol>
<p>
        <strong>执行计划 Planner</strong></p>
<ol start="1">
<li>
                基于火山模型（Volcano Model）的 Select 实现</li>
        <li>
                基于 HTTP 的查询和插入接口</li>
</ol>
<p>
        <strong>实现的局限</strong></p>
<ol start="1">
<li>
                暂时没有实现 DDL，仅有固定的 Schemastruct Row { Id uint32 Sex byte Age uint8 Username byte Email byte Phone byte }</li>
        <li>
                SQL 语法的有限支持，参见单测用例<br>
                Tokenizer 由于是基于 Golang 语言本身的一个取巧实现，对于一些字符串里的特殊字符支持会出现问题，可以通过加 “ 解决</li>
</ol>
<p>
        <strong>传送门</strong></p>
<p data-track="29">
        GitHub地址：</p>
<p data-track="30">
        https://github.com/auxten/go-sqldb</p>
<p data-track="31">
        SQL-2011 SQL Parser：</p>
<p data-track="32">
        https://github.com/auxten/postgresql-parser</p>
<p data-track="33">
         基于火山模型（Volcano Model）的 Select 实现：</p>
<p data-track="34">
        https://github.com/auxten/go-sqldb/blob/main/planner/select.go</p>
<p data-track="35">
         单测用例：</p>
<p data-track="36">
        https://github.com/auxten/go-sqldb/blob/main/parser/parser_test.go</p>
<p>
        <strong>特别感谢</strong></p>
<ol start="1">
<li>
                Marshal/Unmarshal Code generation：https://github.com/andyleap/gencode/</li>
        <li>
                Document-oriented, embedded SQL database: genji：https://github.com/genjidb/genji</li>
        <li>
                CockroachDB：https://github.com/cockroachdb/cockroach</li>
        <li>
                Let’s Build a Simple Database：https://cstack.github.io/db_tutorial/</li>
</ol>
<p>
        <strong>SQL数据库的历史</strong></p>
<p data-track="43">
        最后说一下SQL数据库的历史吧。</p>
<p data-track="44">
        上世纪 60 年代，由于 IT 技术尚未普及，硬件能力也捉襟见肘。程序员面临的业务逻辑还不是很复杂，但更可怕的是当时没有 Google，更没有 GitHub、Stack Overflow。即使是构建一个最简单的增删改查系统也需要自己手动调用操作系统反人类的 API，应用各种数据结构、算法去完成数据的存储和检索。</p>
<p data-track="45">
        和很多技术从简单到复杂的发展历程不太一样，数据库首先成熟并被大规模使用的是 RDBMS（关系型数据管理系统），后来才逐渐兴起了实现相对简单，以 Redis 为代表的 KV 型的数据库。</p>
<p data-track="46">
        关系型数据库的大规模应用和 SQL 被普遍认可成为了关系型数据库的标准查询语言有很大的关系：</p>
<p data-track="47">
        SQL 编程语言最初是 IBM 研究人员 Raymond Boyce 和 Donald Chamberlin 在 1970 年代开发 “System R” 的过程中落地的。SQL 当时被称为 SEQUEL（这也是SQL普遍读法的由来）后来由于注册商标的问题，才改名为 SQL。SQL 的发明很大程度上是参考了 Edgar Frank Codd 于 1970 年发布论文《A Relational Model of Data for Large Shared Data Banks》。</p>
<div class="pgc-img">
        <img title="2000 行代码，带你写一个自己的 SQL 数据库" alt="2000 行代码，带你写一个自己的 SQL 数据库" class="syl-page-img" src="https://zhuji.jb51.net/uploads/img/202305/c87875fbef3f54d3c8a2e7c0fb35b32d.jpg">
</div>
<p data-track="48">
        1977 年，32 岁的程序员 Larry 从在 IBM 工作的好基友 Oates 那里拿到一本内部期刊《IBM Research Journal》，从上面读到了 System R 的一些消息。由于技术人员对技术的敏感性，他们觉得这玩意儿一定会大火，于是三个 30 多岁的程序员决定去创业，于是自己凑钱创建了一个软件开发公司。公司名也是取得相当直白：SDL（Software Development Labs，”软件开发实验室”）。随着 IBM System R 的推出市场，SQL 语言迅速普及，Larry 原来只是想开发一个兼容 System R 的数据库系统，跟在 IBM 后面喝点汤。</p>
<p data-track="49">
        但 System R 竟然把返回的 Error Codes 当成了秘密保护了起来。不让我加入，那我就跟你打，于是 Larry 把公司名改成 “Relational Software, Inc” 准备跟 IBM 死磕。1 年后，他们开发出了数据库产品的第一个版本并把它命名为 “Oracle”，更让大家开心的是他们成功的把产品卖给了美国海军和中央情报局等政府部门。于是大家买了个蛋糕给公司过了一个一周岁的生日，留下了这张照片：</p>
<div class="pgc-img">
        <img title="2000 行代码，带你写一个自己的 SQL 数据库" alt="2000 行代码，带你写一个自己的 SQL 数据库" class="syl-page-img" src="https://zhuji.jb51.net/uploads/img/202305/bd4dd7fa77f8370cfab237bc5f9d02ad.jpg">
</div>
<p data-track="50">
        1979 年，RSI 公司发布了 Oracle v2 和一个自己的 SQL 版本……</p>
<p data-track="51">
        7 年之后 Oracle 上市，程序员 Larry 和 Oates 走上人生巅峰，持剑少年变恶龙……</p>
<p data-track="52">
        System R 把 Error Codes 作为机密保护起来的做法像极了日后 Oracle 收购 Sun MicroSystems 获得了 Java 的版权后把 Java 的函数接口申请专利的做法。</p>
<p data-track="53">
        Oracle 上市的同年，SQL 正式被 ANSI（American National Standards Institute）定为标准，第二年 SQL 成为了 ISO 标准，编号：ISO/IEC 9075。此后分别在：1989, 1992, 1996, 1999, 2003, 2006, 2008, 2011, 2016 年不断增补，就有了后世经常提到的 SQL-89、SQL-92、SQL:2011 等叫法。</p>
<p>
        原文链接：https://www.toutiao.com/i6972006154901652000/</p>
頁: [1]
查看完整版本: 2000 行代码，带你写一个自己的 SQL 数据库