| 主权项 |
一种支持敏捷开发和横向扩展的数据存储与查询方法，其特征在于：将数据抽象为一个二元组(Key, MiniTable)，任意MiniTable由唯一的Key标识；MiniTable由若干数据行组成，并且由预先定义的模式限制数据行的结构，行按模式定义的主键进行排序；Key‑MiniTable模式有三个基本原语和三个物理实体，三个物理实体分别为：客户端，利用三个基本原语向Key服务器发起请求，并接收请求结果；Key服务器，接收客户端发起的请求，查找Key对应MiniTable所处MiniTable服务器的IP地址及端口号，据此转发该请求给对应MiniTable服务器；MiniTable服务器，接收Key服务器转发的请求，解析该请求的类SQL语句，生成执行计划，并在分布式存储系统中获取和写入数据，完成请求返回结果给客户端；Key‑MiniTable模式的三个基本原语为：1）Boolean Create (Key, 列名1:数据类型, 列名2:数据类型,……, 列名n:数据类型, PRIMARY KEY: 列名)，创建一个标识为Key的MiniTable，并定义该MiniTable的模式；若创建成功返回True，创建失败则返回False；2）Boolean Delete (Key)，删除Key对应的MiniTable；若删除成功返回True，删除失败或不存在对应Key则返回False；3）String Query (Key, 类SQL语句)，在Key对应的MiniTable内部执行类SQL语句，Query原语返回其参数中类SQL语句的返回值；类SQL语句包括十个保留字：Select、Where、Insert、Update，Delete、Order By、Limit、Distinct、And 、Or；六个运算符：=、>、>=、<=、<、<>；保留字与运算符的语法和语 义与SQL标准定义相同；Key服务器有三个核心数据结构：1）B+树：存储Key与地址号之间的对应关系；2）地址转换表：存储地址号与IP地址和端口号之间的对应关系；3）MiniTable服务器监控表：存储每一个地址号对应MiniTable服务器的负载情况；当Key服务器收到一个原语请求时，检查是否是合法Query原语；若是合法Query原语，则从B+树中查询Key对应的地址号；若Key不存在，则返回Key不存在信息；若Key存在，则在地址转换表中查询地址号对应的IP地址和端口号；若IP地址和端口号不存在，则返回错误；若存在，则将该请求转发给IP地址和端口号对应的MiniTable服务器；若请求不是合法Query原语，则检查是否为合法Create原语；若是合法Create原语，则在B+树中查询是否存在给定的Key；若Key存在，则返回Key已存在信息；若Key不存在，则根据调度算法和MiniTable服务器监控表分配一个地址号，更新MiniTable服务器监控表，利用地址号查询对应的IP地址和端口号，并转发请求给对应的MiniTable服务器；若请求不是合法Create原语，则检查是否为合法Delete原语；若是合法Delete原语，则在B+树中查询是否存在给定的Key；若Key不存在，返回Key不存在信息；若Key存在，则在地址转换表中查询地址号对应的IP地址和端口号，并删除B+树中对应的Key，更新MiniTable服务器监控表，查询IP地址和端口号，转发请求给对应的MiniTable服务器；MiniTable服务器有两个核心数据结构：1）内存表：根据缓存策略，将部分MiniTable存储在内存中；2）MiniTable锁：记录已加锁的MiniTable；MiniTable服务器收到Key服务器转发的请求后，对请求做语义解析，判断请求操作的MiniTable是否加锁；若加锁则将该请求加入等待队列；若未加锁，则对MiniTable加锁，并生成执行计划；之后，判断MiniTable是否在内存表中，若在内存表中直接执行请求；若不在内存表中，则进一步判断是否有足够内存空间；若没有，则根据调度策略，将部分MiniTable写入分布式文件系统；写入时比较MiniTable内存版本与文件版本的区别，仅将更新的部分以日志压缩格式写入；在获取足够内存空间后，从分布式文件系统读入MiniTable文件，解压缩；将MiniTable日志文件转换为数据格式存入内存表；之后执行请求，解锁MiniTable，并返回结果。 |
