导读
《F1：A Distributed SQL Database That Scales》是Google构建的用于支持广告业务的分布式关系型数据库系统。作为一个混合型数据库系统，它结合了高可用、NoSQL数据库的扩展性以及传统SQL数据库的一致性和可用性。F1数据库整体基于Google Spanner构建，Spanner主要为上层的F1提供了跨数据中心的数据复制功能和一致性保证。而F1通过使用结构化数据分层架构模型和合理的应用设计，来降低数据备份带来的延迟，并提供了全功能的SQL支持。该论文也成为很多厂商实现合约中的SQL功能的重要参考。
区块链执行SQL的可能性
业务系统中的数据是以结构化的组织存在，使用结构化语言查询可以极大提升业务人员访问数据的便捷性。
SQL(Structured Query Language，结构化查询语言)是一种特定目的的编程语言，广泛应用于关系数据库管理系统，例如大家所熟知的MySQL、Oracle等。SQL是高级的非过程化编程语言，它允许用户在高层数据结构上工作，不需要用户指定对数据的存放方法，也不需要用户了解其具体的数据存放方式，这种灵活的方式自然衍生出了很多优秀的SQL执行引擎。
以我们熟知的MySQL为例，其中就包括了InnoDB、MyIsam和Memory等执行引擎，不同的执行引擎之间各有优劣，在不同的使用场景上会发挥出不同的作用，但是其向上的表现却是一致的，由此我们衍生出了在传统区块链的基础上来构建高效可用的SQL执行引擎的设计思想。
存储引擎从很大程度上限制了执行引擎的实现，传统的区块链系统一般会采用键值对的NoSQL数据库，将产生的状态数据以键值对的形式进行存储，同时方便世界状态的计算。为了保证区块链底层的存储结构不发生大的变化，我们需要设计一个方式，尽可能将SQL执行引擎建立在键值对数据库之上。在Google的F1中本身就是基于NoSQL数据库进行扩展，这让在区块链上执行SQL有了一定的可能性。
然而问题在于，要想解决区块链上执行SQL语句，就必须要解决SQL语句的编译问题以及如何将SQL的结构化数据保存到KV数据库当中，这也是我们本篇分享的主要内容：SQL编译与数据存储。
SQL编译
同大部分语言一样，SQL编译主要是将SQL语言转化为AST(Abstract Syntax Tree，抽象语法树)，然后才能基于生成的语法树来设计我们的执行引擎。
既然谈到了编译，必然离不开在编译原理中离不开的两个话题：词法分析和语法分析。
词法分析是将字符序列转换为标记(token)的过程；语法分析则是根据某种给定的形式文法对token构成的输入文本进行分析并确定其语法结构的一种过程，主要作用是进行语法检查并构建有输入的token组成的数据结构(一般是语法分析树、抽象语法树等层次化的数据结构)。
如果通俗的来讲，将编程语言的编译类比为自然语言，那么词法分析关注的是你说了什么内容，语法分析则是关注与你说的内容是不是正确的，是否能够让人理解的。
词法分析相对而言比较简单，语法分析则相对来说会复杂很多，笼统地说语法分析方法可以分为自顶向下分析算法和自底向上分析算法，两者的主要区别是一种是“扩展”，一种是“规约”，至于语法分析是如何工作的，此处篇幅有限不再过多展开介绍，读者可自行了解编译的语法分析方法，包括遇到歧义或要回溯时是如何处理的。
上述算法依据的语法规则一般称之为上下文无关语法，一个语法表达式一般会表达为S->AB的形式，将产生式左侧的符号称之为非终结符，代表可以继续扩展或产生的符号；只能出现在右边的称之为终结符，无法再产生新的符号。
BNF(Backus Normal Form，巴科斯范式)是一种用于表示上下文无关语法的语言，事实上很多编译器都是可以通过编写类似的语法表达式，用工具直接生成一个编译器，如Java编译器就是通过Antlr4来生成的。
尽管有现成的方式可以帮助我们生成编译器，但是完整的描述出SQL语言的语法表达式本身就是一件繁琐且工作量很大的事，索性我们能从很多地方获取到这个语法表达式文件，例如从MySQL官网可以获取到MySQL的语法表达式(因为“SQL方言”的存在不同SQL数据库语法表达式会略微不同)，在现有的SQL语法表达式的基础上进行修改可以大大减少设计工作量。
CREATE TABLE IF NOT EXISTS testTable
(
id bigint(20) NOT NULL,
name varchar(32) NOT NULL,
exp bigint(20) NOT NULL DEFAULT '0'
);这是一个创建数据表的SQL语句，我们可以用这样的范式来表示我们的创建表的过程：
CREATE [TEMPORARY] TABLE [IF NOT EXISTS] tbl_name(create_definition,...)[table_options][partition_options]如果范式中包含其他的子范式，当其被匹配到时，就会执行我们所期望的流程。
例如使用goYacc我们可以将我们定义的范式逻辑转化为一个golang语言的编译器，假设基于goYacc将其中一种创建表的SQL范式编写为如下：
CreateTableStmt:"CREATE" OptTemporary "TABLE" IfNotExists TableName TableElementListOpt AsOpt{stmt := $6.(*ast.CreateTableStmt)stmt.Table = $5.(*ast.TableName)stmt.IfNotExists = $4.(bool)stmt.IsTemporary = $2.(bool)$$ = stmt}其中$$表示的范式的最终返回值，$x表示的第x个位置的返回值，如$4表示的就是IfNotExists返回的结果，而AST的节点数据结构则需要我们事先定义好。
最终我们可以将上述创建表的SQL语句生成为一个AST的结构如下所示(忽略了name字段的展示)：
当有了AST这个数据结构之后，就可以使用Visitor模式对树的每个节点进行访问，来获取我们想要的信息以及生成执行过程。
数据存储
通过上一小节，相信大家对SQL的编译以及AST有了一个基本的概念，现在来讨论另一个问题，如何将SQL数据存入到键值对数据引擎中。
主要分为：表信息存储、表内行数据存储以及索引存储。
▲ 表信息存储
对于数据表的信息，例如表名、行信息和索引信息等这些内容，可以将表结构以某种序列化方式转化为二进制格式来进行保存，键值对的key则可以为每个表生成一个唯一的表ID，来作为表信息的索引，当需要使用对应的表结构时，只需将其反序列化为表结构即可，相对来说表信息转化为键值对保存是比较容易的。
▲ 表内行数据存储
数据表内的行数据存储会复杂一些，以上述创建的SQL表为例，假设向其中插入的某一条数据的SQL语句如下：
INSERT INTO testTable (id, name) VALUES(001, "tom");首先，我们要确定这一行数据的key，可以将key的生成规则抽象的表示为：
tablePrefix{TableID}_recordPrefixSep{RowID}。其中tablePrefix和recordPrefixSep都是固定前缀，用于标识表和行信息的开始，而TableID则为创建表时生成的唯一ID，对于行ID，当表内存在整数型的主键则会将这一主键值作为行ID，否则将同样会为改行分配一个唯一的行ID，由此一行数据的key可以确定下来。
对于一行数据的value，可以将每一列的数据紧凑的排列在一起即可，例如上述描述的插入语句的数据，用16进制来表示可以描述为01746f6d00，01表示的列id的值，746f6d表示的是列name的值(即"tom")，00则表示列exp的默认值，而这些数据的类型可以从表信息中获取到，无需保存在行的value中。
当然这样表示一行数据的value肯定是不够的，实际上还需要基于数据编码的基础上增加：版本号、该行内容包含的列数据数量、分别是哪些列的数据以及每一列的数据起始偏移等，附带上这些额外的信息后才是一个完整的一行数据。
▲ 索引存储
另一个比较关键数据就是对索引的存储，需要再次说明的是：对于一个表内的每一列信息，都会分配一个唯一列ID来进行标识。
索引主要分为唯一索引和非唯一索引两类：
唯一索引在存储时将索引值作为key，行ID作为value来进行索引信息的保存，具体的一个唯一索引key表示为：
tablePrefix{tableID}_indexPrefixSep{indexID}_indexedColumnsValueindexPrefixSep同样为固定前缀，用于表示索引列信息的开始，所以一个完整的唯一索引信息key还包含了表ID和列ID。
非唯一索引在存储时将索引值和行ID组合未做key，value则保存空值，通过依赖于存储引擎在遍历时按字典序的特点获取到对应的非唯一索引下的所有行ID，具体一个非唯一索引key表示为：
tablePrefix{tableID}_indexPrefixSep{indexID}_indexedColumnsValue_rowID同样的一个完整的非唯一索引key还包含了表ID和列ID。
综上，通过对于SQL编译处理以及SQL数据键值对存储，让大家可以大致的了解常见的SQL数据如何存储到键值对存储引擎中的设计理念。
小结
本文主要介绍了SQL的编译处理以及如何将SQL转化到键值对存储引擎的技术方案，引发了如何基于现有的区块链架构来执行SQL语句的思考，如何通过SQL执行来拓宽区块链的业务使用场景的实践。
但这远没有结束，此过程之中还有很多问题需要我们研究思考，例如如何进行外键关联，如何进行复杂的笛卡尔积查询以及如何合理度量SQL执行的复杂度。
同样需要注意的是，并不是所有的需求都适合于区块链，例如基于非索引的查询在目前的区块链系统中就显得很不合理，这需要存储引擎的的配合。
总的来说在区块链上执行SQL并不是不可能的，但需要我们不断的去探索一个合理的可以高效的在区块链上执行SQL功能的解决方案：更易用、更高效、更强大。
大家看了这篇文章如果有好的想法，欢迎在评论区与我们交流。
参考文献
[1]《F1: A Distributed SQL Database That Scales》：https://static.googleusercontent.com/media/research.google.com/zh-CN//pubs/archive/41344.pdf
[2] HTAP DB：http://www.vldb.org/pvldb/vol13/p3072-huang.pdf
[3] MySQL Statements：https://dev.mysql.com/doc/refman/5.7/en/sql-statements.html
[4] goYacc：https://godoc.org/golang.org/x/tools/cmd/goyacc
[5] TiDB parser：https://github.com/pingcap/parser
[6] TiDB架构介绍：https://pingcap.com/blog-cn/#%E6%9E%B6%E6%9E%84
作者简介
陶烨琪
来自趣链科技基础平台部，区块链虚拟机研究小组
有任何想了解的技术问题、对文章的建议
欢迎进技术交流群和我们一起探讨～
添加小助手桔子（微信：18458407117）
