《区块链金融》课件 第4章 数据存储

微课视频版区块链金融第4章数据存储目录01.NoSQL数据库02.LevelDB数据库03.数据存储方案04.比特币的数据存储第4章数据存储区块链中最重要的数据是交易数据和合约数据。数据存储分为：内存暂存和存储介质持久化存储。在区块链系统中，一个新区块生成前的所有交易数据都暂存在内存系统中，随着区块生成，数据被持久存储到存储介质中。NoSQL数据库PART014.1NoSQL数据库第4章数据存储NoSQL（NotOnlySQL），非关系型数据库。易扩展、结构简单、大数据量、读写性能高。NoSQL数据库是为了解决海量及异构数据的存储及管理难题而产生的。采用非关系数据模型，包括键值模型、列模型以及文档模型等。NoSQL分类键值存储可以看成映射，即为Value建立Key，通过Key快速定位其Value。Key-Value型典型的是通过哈希表实现Key到Value的映射。典型的数据库包括LevelDB、Redis、TokyoCabinet/Tyrant、MemcacheDB、Voldemort、BerkeleyDB等。键值（Key-Value）存储型数据是按列为单位存储的。针对结构化和半结构化数据的存储很方便，方便实现数据压缩，对列数据的查询有非常大的I/O优势。典型的数据库包括HBase、Hypertable、Cassandra等。列（ColumnFamily）存储型文档（Document）存储型图存储型是图形关系的最佳存储模式，利用图论构建Key-Value映射关系，比较适用于关系复杂的数据管理。典型的数据库包括Neo4J、FlockDB、GraphDB等。图（Graph）存储型第4章数据存储文档存储采用类似json的格式存储，形式为文档型，通过对某些字段建立索引，实现关系数据库的某些功能。文档存储数据库可看作键值存储的升级版，允许文档间嵌套键值，处理复杂数据时，比键值型的查询效率更高。典型的数据库包括MongoDB、CouchDB、SequoiaDB等。基于类似面向对象语言的语法操作数据库，以对象的方式存取数据。典型数据库包括DB4O、Versant等。对象（Object）存储型比较高效，支持XML内部查询语法，如XQuery、Xpath等。典型数据库包括BerkeleyDBXML、BaseX等。XML存储型LevelDB数据库PART024.2LevelDB数据库第4章数据存储Google开发的单机版、开源Key-Value型的NoSQL数据库LevelDB采用日志结构合并树（LogStructuredMergeTree，LSM-Tree）作为底层数据结构，磁盘批量的顺序写性能要远高于随机写性能。数据写阶段，首先在内存中完成随机写操作，并排序，数据达到一个约定的值，一并顺序写入磁盘文件。然后在后台将小的有序文件合并为大的有序文件，提高查询效能。这种将随机写转换为顺序写的存储模式具有极高的写性能，其写性能达到40万条/秒。LevelDB特点Key和Value支持任意字节长度。字节长度任意可以按照Key排序，也可以自定义排序函数。排序方式灵活内存占用低支持快照（Snapshot）功能，使得读操作不受写操作影响，保持数据的一致性。支持快照（Snapshot）功能第4章数据存储LevelDB是持久化的Key-Value数据存储系统，内存占用低。采用Snappy压缩算法，减小存储空间，提高I/O效率。采用Snappy压缩算法支持原子批量操作，提供基本的读、写及删除操作接口。支持批量操作4.2.1LevelDB整体架构第4章数据存储LevelDB提供数据存取功能和基本操作接口。存储分为由跳表（Skiplist）组成的内存存储及由SSTable（SortedStringTable）组成的磁盘存储，涉及6个主要部分：内存中的MemTable、ImmuTableMemTable、磁盘上的Current文件、Manifest文件、Log文件及SSTable文件。所有Key-Value数据都存储在Memtable、ImmutableMemtable和SSTable中，最终以SSTable形式存储在磁盘中。4.2.1LevelDB整体架构第4章数据存储整体架构如图4-1所示。4.2.1LevelDB整体架构第4章数据存储1.Memtable与ImmuTableMemtableMemtable与ImmuTableMemtable是数据在内存中的存储位置。两者数据结构完全相同，Memtable允许读和写，ImmuTableMemtable仅读。Memtable的数据占用内存达到一定数值时（默认为4MB），系统自动将其转换为ImmutableMemtable，然后自动生成一个新的Memtable，供新数据写入。ImmutableMemtable的数据将等待系统转存（Dump）到磁盘，依次写入一个Level0的新建SSTable文件中。4.2.1LevelDB整体架构第4章数据存储1.Memtable与ImmuTableMemtableMemtable和ImmuTableMemtable的核心数据结构都是跳表（Skiplist）。数据的读、写、删除操作都是通过Skiplist实现的。Skiplist是链表的扩展，是可以替代平衡树的一种数据结构，树平衡是基于随机算法实现的。Skiplist维护的是一个有序数据集，数据的插入和删除操作比较简单。4.2.1LevelDB整体架构第4章数据存储2.SSTable文件（1）SSTable文件SSTable文件由内存表ImmutableMemtable中的数据导出并Compaction后形成。SSTable采用分层结构，从Level0到Level6，共7层，每层多个SSTable。SSTable是Key-Value数据对在磁盘持久化存储的数据结构文件，内部按Key排序，除Level0层外，其他层的SSTable文件的Key之间不会存在重叠现象。4.2.1LevelDB整体架构第4章数据存储2.SSTable文件（2）SSTable存储结构存储结构如图所示。连续且固定大小的块（Block）组成。Block是基本读写单位，缺省值4KB，可配。包含数据存储区和数据管理区。数据存储区在前，由若干连续的Block组成，存放Key-Value数据对。数据管理区在后，存放管理数据。4.2.1LevelDB整体架构第4章数据存储2.SSTable文件（2）SSTable存储结构数据管理区也可以称索引区。MetaBlockIndex：

指明各MetaBlock的偏移与大小。IndexBlock：

指明各DataBlock的偏移与大小。Footer：

指明MetaBlockIndex和IndexBlock的偏移与大小。4.2.1LevelDB整体架构第4章数据存储2.SSTable文件（3）数据存储区结构结构如图所示。数据存储区的Block含3个字段：Data、Type及CRC。Type字段1B，标识是否采用数据压缩算法。CRC字段4B，数据校验码。Data字段存放实际数据，前部是Entry列表，存放由小到大排列的Key-Value数据对；尾部存放“重启点”（RestartPoint）及一条“重启点数量”记录。4.2.1LevelDB整体架构第4章数据存储2.SSTable文件（3）数据存储区结构Data存储结构如图所示。4.2.1LevelDB整体架构第4章数据存储2.SSTable文件（3）数据存储区结构重启点：如果存储的多条相邻记录的Key有重叠，如Keyn=“myhome”、Keyn+1=“myhouse”，则“myho”重叠，Keyn+1只存“use”，“myho”从Keyn中获取。为防止Keyn数据损坏，无法读取重叠部分数据，每隔一定数量的记录会强制加入一个重启点，表示从这条记录开始存储Key的完整值。假设Keyn+1是重启点，则Keyn+1存储“myhouse”。Block会将重启点的偏移量及重启点数量存放在Block尾部块中。4.2.1LevelDB整体架构第4章数据存储2.SSTable文件（3）数据存储区结构Data字段前部分是Entry列表，每条记录都是一对Key-Value值，每条记录包含5个字段，结构如图所示。Key共享长度，以Keyn+1为例，和上一条记录共享的Key长度是“myho”的长度，即5个字符；Key非共享长度，Keyn+1只存储“use”，长度是3；Value的长度是Key-Value中Value的长度；Key非共享内容是指实际存储的“use”；Value内容是Key-Value中Value的具体内容。4.2.1LevelDB整体架构第4章数据存储2.SSTable文件（4）数据管理区结构数据管理区有4种类型：MetaBlock、MetaBlockIndex、IndexBlock及文件末尾块Footer。

MetaBlock：布隆过滤器块，存储Key的过滤器信息。

MetaBlockIndex：指向MetaBlock的一组Handle，是MetaBlock的索引。4.2.1LevelDB整体架构第4章数据存储2.SSTable文件（4）数据管理区结构

IndexBlock：索引数据块，存放DataBlock索引信息。每条记录指向一个DataBlock，其Key值为所指向的DataBlock最后一条数据的Key，Value为指向该DataBlock位置的Handle。每条索引信息包含3个内容，如图4-6所示。IndexBlocki的第一个字段Key存放大于或等于DataBlocki中最大的Key值，第二个字段Offset存放DataBlocki在SSTable文件中的起始位置，第三个字段Size存放DataBlocki的长度。通过Offset及Size确定DataBlock在SSTable文件中的具体位置。4.2.1LevelDB整体架构第4章数据存储2.SSTable文件（4）数据管理区结构

IndexBlock：IndexBlock结构，如图4-6所示。图4-6IndexBlock结构图4.2.1LevelDB整体架构第4章数据存储2.SSTable文件（4）数据管理区结构

IndexBlockIndexBlocki的第一个字段Key存放的Key值可以不是DataBlocki中最大Key值的具体值。图4-6中，假设DataBlocki的最大Key=“name”，DataBlocki+1的最小Key=“nice”，IndexBlocki的第一个字段Key要同时满足大于或等于DataBlocki的最大Key（name）且小于DataBlocki+1的最小Key（nice）。那么，IndexBlocki的第一个字段存放new也符合规定。4.2.1LevelDB整体架构第4章数据存储2.SSTable文件（4）数据管理区结构

Footer：位于SSTable文件的末尾，存放指向MetaBlockIndex及IndexBlock的Handle。Handle通过偏移量Offset及Size确定Block的位置。Footer块用于定位MetaBlockIndex和IndexBlock，结构如图所示。MetaIndex_handle指明MetaBlockIndex的起始位置和大小（最大20B）；Index_handle指明IndexBlock的起始位置和大小（最大20B）。这两个字段是索引的索引，是为了读出索引值而设立。填充区用于补齐上面40B。最后是8B的魔数，验证是否为合法的SSTable文件。4.2.1LevelDB整体架构第4章数据存储2.SSTable文件（5）SSTable文件空间每个SSTable文件的上限为2MB。Level0最多有4个SSTable文件，当4个文件存储空间用尽，选择一个文件Compaction到Level1的SSTable文件中。Level1，大小不超过10MB。Level2，大小不超过100MB。Level3及以上的大小不超过上一个Level×10的大小。4.2.1LevelDB整体架构第4章数据存储3.Log文件（1）Log文件Log是日志文件，缺省4MB，可配。Log是预写Log（Write-AheadLog，WAL）机制。WAL机制是先将数据顺序写入Log文件，写入成功后再写入内存的Memtable中。这种机制既保证了数据的持久化存储，又可以在系统意外崩溃时利用Log文件恢复未及时持久化存储的Memtable数据结构内容。Log文件的记录无序，且主要在恢复内存数据时使用。4.2.1LevelDB整体架构第4章数据存储3.Log文件（2）Log文件的建立当Memtable转换为ImmutableMemtable时，新的Log文件和对应的Memtable同时被创建。4.2.1LevelDB整体架构第4章数据存储3.Log文件（3）Log数据结构基本读取单位：Block，如图4-8所示。一个Log文件由若干个连续的Block组成。每个Block大小是32KB。图4-8Log文件分块结构4.2.1LevelDB整体架构第4章数据存储3.Log文件（3）Log数据结构Key-Value对以记录（Record）形式存储。一个Block可以由多条Record组成。每条Record可以存储若干对Key-Value数据，记录的结构如图4-9所示。图4-9Record结构4.2.1LevelDB整体架构第4章数据存储3.Log文件（3）Log数据结构每条Record包含数据（Data）和记录头（RecordHeader）两部分。Data字段存储Key-Value数据对。RecordHeader占用7B空间，分为3个字段：校验和（ChechSum）、Length、Type。4.2.1LevelDB整体架构第4章数据存储3.Log文件（3）Log数据结构ChechSum：CRC验证码，是Type和Data字段的校验码，占4B空间。进行读操作时，先对数据进行校验运算，如果结果和CheckSum字段相同，说明数据正确。Length：是Data字段的长度，占2B空间。Type：字段占1B空间。若一个Record长度>32KB，则需要分片。Type用于标记分片，取值有4个选项：Full、First、Middle及Last。4.2.1LevelDB整体架构第4章数据存储3.Log文件（3）Log数据结构如果一条Record能完整地存储在一个32KB的Block，说明该条Record小于32KB，则该Record的类型为Full；如果一条Record大于32KB，则该Record将被分片存储在相邻的Block中，类型将是其他3种选项中的1种。Record被分片的第一片数据类型标记为First；第二片存储在下一个Block中，类型标记为Middle，表示分片的中间部分；最后一个分片类型标记为Last。4.2.1LevelDB整体架构第4章数据存储3.Log文件（3）Log数据结构假设有3条数据，DataA为15KB，DataB为48KB，DataC为20KB，存储结构如图4-10所示。当Block剩余存储空间小于或等于7B，尾部留空，以0填充至32KB。图4-10Record在Log中的存储结构4.2.1LevelDB整体架构第4章数据存储3.Log文件（3）Log数据结构Data字段结构如图所示。SequenceNumber表示当前Record中第一个Key-Value数据对的编号，最后一个Key-Value对的编号通过SequenceNumber+Count计算得到；Count表示当前Record中包含Key-Value对的数量；Type表示当前Key-Value对的操作类型，只有写入和删除两种类型；Key-Length和Value-Length分别表示当前Key和Value的长度。4.2.1LevelDB整体架构第4章数据存储4.Current文件Current文件只记录当前正在运行的Manifest文件名称，如manifest.345。当Manifest文件随着SSTable产生新、旧文件更替时，Current文件则指明哪个Manifest文件是当前正在运行的。4.2.1LevelDB整体架构第4章数据存储5.Manifest文件Manifest文件是Log类型文件，格式和Log文件相同。记录SSTable文件的管理信息，如所属Level、文件名称、最小Key和最大Key等。图4-12是Manifest存储内容的示意图。图4-12Manifest存储结构示意图4.2.1LevelDB整体架构第4章数据存储5.Manifest文件Manifest实质是LevelDB的版本（Version）管理器。存放版本集合（VersionSet）。VersionSet是一个双向循环链表，链表的每个节点就是一个Version。Version通过结构体FileMetaData存放SSTable文件的元数据。4.2.1LevelDB整体架构第4章数据存储5.Manifest文件（1）VersionSetVersionSet的作用：通过链表管理所有Version。VersionSet是Version的集合，管理所有存活的Version。随着频繁的数据插入、删除操作，LevelDB内部会不停地生成新Version。此时，老版本Version可能正被使用。因此，同一时刻可能存在多个Version。系统每产生一个新Version，就往这个链表的尾部插入一个节点。链表尾部的节点就是CurrentVersion。4.2.1LevelDB整体架构第4章数据存储5.Manifest文件（2）Version多版本并发控制（Multi-VersionConcurrencyControl，MVCC）：解决数据库的并发访问，尤其是读、写同一数据产生的冲突。MVCC为数据的每次修改保存一个版本（Version），版本与时间戳关联，通过维持同一数据的多个版本，使得读写操作不产生冲突。MVCC实质是通过保存数据在某时刻的快照实现的。每一个执行操作的用户，看到的都是数据库特定时刻的快照，任何未完成的写操作都不会被其他用户看到，对数据进行更新时先标记，然后在其他地方添加新数据，形成一个新Version。4.2.1LevelDB整体架构第4章数据存储5.Manifest文件（2）VersionLevelDB的Version是为了实现MVCC而采用的多版本管理机制。一个Version代表一个数据版本，是LevelDB所有层的SSTable文件组成的集合。系统每执行一次Compaction操作，LevelDB将在当前版本基础上结合VersionEdit创建一个新Version。4.2.1LevelDB整体架构第4章数据存储5.Manifest文件（2）VersionVersionEdit是一个数据结构。描述本次Compaction后新增的FileMetaData及被删掉的文件编号。结构体FileMetaData是每个Version内部的存储结构，如图4-13所示。一个FileMetaData用于描述一个SSTable文件，是SSTable的元数据信息。每层中都有多个FileMetaData。图4-13FileMetaData存储结构4.2.1LevelDB整体架构第4章数据存储5.Manifest文件（2）VersionFileMetaData结构各字段的含义Refs：FileMetaData结构体的引用次数，为0则删除此Version。AllowedSeeks：标识允许的最大查找次数。Number：文件编号，用来唯一标识一个SSTable文件，全局递增。FileSize：标识SSTable的文件大小。Smallest：标识最小的InternalKey。Largest：标识最大的InternalKey。图4-13FileMetaData存储结构4.2.1LevelDB整体架构第4章数据存储5.Manifest文件（3）VersionEdit数据库的频繁读、写操作，会不断产生新的VersionEdit，并把数据的变化记录到VersionEdit结构中。VersionEdit是LevelDB两个连续Version之间的差异量。差异量包括本次Compaction操作时新增的和删除的文件，即：VersoinN+VersoinEdit=VersionN+1。4.2.1LevelDB整体架构第4章数据存储5.Manifest文件（3）VersionEditVersionEdit的数据结构如图4-14所示。图4-14VersionEdit的数据结构4.2.1LevelDB整体架构第4章数据存储5.Manifest文件（3）VersionEditVersionEdit结构中各字段含义：Comparator：比较器名称，系统创建时确定。Log_number：最小的有效LogNumber，小于Log_numbers的Log文件可删除。Prev_log_number：已废弃，为兼容老版本的LevelDB保留代码。Next_file_number：下一文件编号。Last_sequence：SSTable中的最新SequenceNumber。Compact_pointers：记录每一层要进行下一次Compaction的起始Key。Deleted_files：本次操作要删除的SSTable文件。New_files：本次操作新增的SSTable文件。图4-14VersionEdit的数据结构4.2.1LevelDB整体架构第4章数据存储5.Manifest文件Manifest文件保存着VersionEdit经过序列化后的数据。每个VersionEdit相当于Log文件中的一条Record。写VersionEdit时，先通过函数EncodeTo序列化，然后将结果作为一条Record添加到Manifest文件末尾；读出来的每条内容是VersionEdit通过函数EncodeTo序列化后的数据，读记录时通过函数DecodeFrom反序列化，得到的就是VersionEdit保存的原始数据，即当前的Version以及VersionSet。实质：每个VersionEdit就是保存在Manifest文件中的一条Record。4.2.1LevelDB整体架构第4章数据存储6.MinorCompaction与MajorCompaction

LevelDB采用Compaction机制将ImmutableMemtable数据持久化成SSTable文件存储，并负责对已有记录压缩整理，删除无效的KV数据，将多个SSTable文件合并成少量的SSTable文件。

Compaction机制分为MinorCompaction和MajorCompaction两个操作。4.2.1LevelDB整体架构第4章数据存储6.MinorCompaction与MajorCompaction（1）MinorCompactionMinorCompaction操作是当ImmutableMemtable大小达到限定值时，由小到大遍历ImmutableMemtable中的数据，并依次写入一个Level0的新建SSTable文件中，写完后建立文件的Index数据。在MinorCompaction操作过程中，对于要删除的数据，只是做了一个删除标记，并未真正删除记录。4.2.1LevelDB整体架构第4章数据存储6.MinorCompaction与MajorCompaction（2）MajorCompactionMajorCompaction操作是当Leveli下的SSTable文件数目超过限定值后，通过合并不同层级的SSTable文件达到均衡各Level间SSTable文件数量的目的。LevelDB将从达到限定值的Leveli中选择一个SSTable文件，将其和Leveli+1的SSTable文件合并。4.2.1LevelDB整体架构第4章数据存储6.MinorCompaction与MajorCompaction（2）MajorCompactionLevelDB在某个Leveli进行MajorCompaction时，如果本次选择文件A，下次将选择在Key上相邻的文件B。这种文件选择机制使每个文件都有机会和Leveli+1的文件合并。4.2.1LevelDB整体架构第4章数据存储6.MinorCompaction与MajorCompaction（2）MajorCompaction在Level0上选择文件合并时，Level0的SSTable文件是通过MinorCompaction直接生成，存在多个Level0下的SSTable文件Key重复的可能。因此，要找出所有重复的SSTable文件和Level1的文件进行合并，即Level0可能会有多个文件参与MajorCompaction。在Leveli+1层，LevelDB选择Leveli+1中和Leveli选择的文件A在Key上有重复的所有文件与文件A进行Compaction。4.2.1LevelDB整体架构第4章数据存储6.MinorCompaction与MajorCompaction（2）MajorCompactionMajorCompaction的操作过程：对多个文件采用多路归并排序，依次找出其中最小的Key记录，即对多个文件中的所有记录重新排序。之后判断这个Key是否需要继续保存，如果不需要，直接忽略，如果需要，则继续保存，就将其写入Leveli+1层中新生成的一个SSTable文件。最后把Leveli层和Leveli+1层参与Compaction的文件全部删除。4.2.1LevelDB整体架构第4章数据存储6.MinorCompaction与MajorCompaction（2）MajorCompactionMajorCompaction的操作过程：判断一个Key-Value记录是否继续保存的标准：如果此Key已在小于Leveli中存在，那么这个Key在MajorCompaction过程中不保存；如果有删除标记，在MajorCompaction过程中不保存。4.2.1LevelDB整体架构第4章数据存储6.MinorCompaction与MajorCompaction（3）Compaction操作高消耗系统资源Compaction操作非常消耗CPU和磁盘I/O。因此，要么禁用MajorCompaction，要么在凌晨业务低峰期操作。4.2.2数据操作流程第4章数据存储1.写操作写操作接口：Put。写操作流程如图4-15所示。一次写操作：只涉及一次内存写一次磁盘顺序写所以LevelDB的写性能较强。图4-15LevelDB写流程4.2.2数据操作流程第4章数据存储1.写操作当写入一条Key-Value记录时，数据先写入Log文件，操作是磁盘顺序追加。Log写入成功后，再将数据写入Memtable。当Memtable的数据量达到设定值，转换为只读的ImmutableMemtable。然后，MinorCompaction操作把ImmutableMemtable写入磁盘SSTable文件，持久化存储。4.2.2数据操作流程第4章数据存储2.读操作读操作接口：Get。读操作流程如图4-16。图4-16LevelDB读流程4.2.2数据操作流程第4章数据存储2.读操作（1）读操作流程首先，构造查询所用的InternalKey，该Key是由：查询请求的UserKey+SequenceNumber+ValueType构成，SequenceNumber使用Snapshot的SequenceNumber或使用当前最新的last_sequence。然后用生成的Key依次尝试从Memtable、Immtable以及SST文件中查找。LevelDB首先查找内存中的Memtable，如果找到则返回Value；如果没有找到，继续查找ImmutableMemtable，如果找到，就返回Value；如果没找到，继续查找磁盘中的大量SSTable文件。4.2.2数据操作流程第4章数据存储2.读操作（2）定位SSTable文件查找SSTable时，首先从Level0中查找，如果找到，则返回Value，如果没找到则继续查找Level1中的文件，如此循环，直到在某Level中找到。如果遍历所有Level中的文件没有找到，说明系统中不存在要查找的Key。4.2.2数据操作流程第4章数据存储2.读操作（2）定位SSTable文件Manifest文件中的每条FileMetaData记录对应一个SSTable文件，存放着每个SSTable文件所包含的Key范围，因此可以从FileMetaData获得包含所查询Key的SSTable文件名，即定位SSTable文件。Level0的查找需顺序遍历所有FileMetaData，因为Level0的SSTable文件间Key的范围可能重叠，所以可能定位多个SSTable文件。其他Level，基于FileMetaData的Largest做二分查找，即可定位。4.2.2数据操作流程第4章数据存储2.读操作（3）定位具体Key-Value对在一个SSTable文件中定位一个Key的过程如下：LevelDB首先在内存的Cache中查找是否包含这个文件的缓存记录，如果包含，则从缓存中读取；如果不包含，则打开SSTable文件，同时将这个文件的索引部分加载到内存中并放入Cache中。Cache里则存放了此SSTable文件的索引部分，在内存的IndexBlock中通过二分查找，定位到包含要查询Key的DataBlock，然后根据Offset到打开的文件中读取这个DataBloc