# SG-ColBase

**Repository Path**: ZTZTZT123/sg-col-base

## Basic Information

- **Project Name**: SG-ColBase
- **Description**: 一种高效的列式数据库
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 3
- **Forks**: 0
- **Created**: 2021-11-11
- **Last Updated**: 2024-05-14

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# SG-ColBase

## 介绍
本课题提出一种偏关系型列式数据库内核数据库内核。在实现读写并发控制、数据回滚、原子性日志写入、宕机数据重做，来保证完备的事务支持之后。通过字段级锁、快照读，去扩展数据库内核执行的并行度。使用布隆过滤器、资源缓存池、内存池、跳跃表、无阻塞日志缓存、数据异步写入机制，提高系统整体的执行效率。在数据存储方面引入列式存储、逻辑键、LSM-tree。在提高数据压缩比，减少数据缝隙的同时，让所有磁盘数据操作均为顺序增量写入。配合异步批量操作的特性，大幅度提高了数据写入速度。得益于列式存储带来的纵向数据连续的特性，减少纵向遍历带来的磁盘扫描，相比于传统关系型数据库在大数据分析的场景下效率有质的飞跃。在后续的开发中，本课题会聚焦在此数据库内核的分布式集群版本。集中解决分布式数据库集群中的主从复制、故障转移、数据分区、分布式事务等重点难点问题，向NewSQL数据库进军。

## 系统设计
### 系统结构设计
![系统架构示意图](https://images.gitee.com/uploads/images/2022/0520/152743_0891c159_2243360.png "屏幕截图.png") 
### 模块设计

#### 资源缓存池设计：
数据库内核作为IO密集型应用，使用缓存减少磁盘IO是必须要做的。但如果使用操作系统提供的页高速缓存来缓存资源，则每次获取资源都需要进行系统调用，并将数据从内核空间拷贝到用户空间。因此在这里本课题选择禁用页高速缓存，而在用户空间内对资源做缓存，减少内核态用户态切换的开销。本课题选择使用LRU（最近最少使用）算法进行缓存淘汰，来平衡缓存命中率和缓存淘汰效率。为了提高资源缓存池的并行度，本课题依据资源的唯一id将资源分区存放在不同资源缓存池中，分区上锁控制访问。并使用一致性哈希的算法，让资源池扩展分区时减少对整体资源池运行的影响。

#### 数据架构设计：
为了减少数据占用空间，本课题使用逻辑键代替物理键。并在列上分段划分资源（从磁盘加载进内存的单位）。访问数据时会以列段为单位从资源缓存池中获取，列段中的数据在内存中连续存储。这样的设计配合用户态的资源缓存池，使列的大规模访问几乎等同于内存的顺序访问，极大的提升了大规模数据分析统计的效率。数据的删除额外按段记录，这种逻辑删除的设计减少了数据移动。让数据的一切修改操作均为顺序增量写入。

#### 索引架构设计：
索引使用分区的设计，提高执行效率和并行度。在访问时会根据key值在分区信息表中二分查找确定key值所在的索引分区。
磁盘组织结构：传统的关系型磁盘数据库往往使用B+Tree作为索引的磁盘结构，但他对大数据量的索引修改并不友好。比如在B+Tree的中间写入大量数据的话会造成大量的磁盘移动和随机访问。因此本课题选择使用对写入性能极高的LSM-tree，每次索引修改时只需在文件末尾追加写入操作记录列表（key序）。LSM-tree也有它的问题，它每一次读进磁盘时都需要将多个key序的操作记录列表归并排序并还原成key序的key-value列表。但是得益于分区机制，它每一次的工作量并不会太大。为了进一步优化，还会在操作记录列表个数达到阈值时将此分区全量归并，提高读取的效率。
内存数据结构：为了更好的契合LSM-tree，使用跳表（SkipList）作为索引在内存的数据结构。它可以直接在上述LSM-tree所给到的有序key-value链表上构建索引节点。相比于传统的红黑树，跳表有更高的性能。在实现中也提供了层节点倍数这样的参数来平衡数据检索性能和索引修改性能之间的平衡。

#### 布隆过滤器架构设计：
布隆过滤器使用分区的设计，提高执行效率和并行度。根据key的哈希值分区，并使用二分查找算法定位分区。由于哈希值远大于分区布隆过滤器所表示的范围，需要通过哈希值取模范围区间最大值来做映射。当范围区间最大值为2的幂次时，映射就是均匀的。

#### 事务设计：
事务有四个特性：A（原子性）、C（一致性）、I（隔离性）、D（持久性）。一致性是最终目标，其它三个特性是达到一致性的方法。
隔离性：通过多种方法来隔离多个用户在操作数据库时彼此之间的影响。在对数据实时性要求较高的场景下，通过对数据上读写锁来控制对数据的访问。在仅要求读到合法数据的场景下，读快照数据来隔离读写并发。快照读时事务的隔离级别为读提交。
原子性：内存中的原子性通过加锁实现。在磁盘操作中，原子性指磁盘数据修改只有成功和失败两种状态，不存在中间状态。这在磁盘上分散的数据中是难以做到的，本课题选择使用一种原子的日志追加机制来实现。追加的日志可能超过一个磁盘扇区大小，这就使日志的写入存在中间状态。选择通过在文件头部增加有效文件长度字段来去除中间状态。
持久性：在提交时日志先写磁盘再写内存，配合有效的宕机数据重做机制。使提交函数执行成功之后数据不会丢失。                                                          

#### 异步增量写入设计：
在事务提交时，将日志写入磁盘后不同步等待数据写入磁盘，而是将任务交给异步增量写入线程。此线程会在缓存中的日志数目超过阈值时批量写入数据，并更新数据写入进度。这个机制中有一个问题，确保资源加载进磁盘之前，对它的所有操作已经写入磁盘。延后更新是提高性能所一直倡导的，因此本课题选择在从磁盘读取资源之前判断缓存中是否有此资源未写入的日志，如果有会将缓存中的所有日志写入磁盘。以此来达到高水平的延后更新。

#### 无阻塞日志缓存：
在日志缓存写满后，异步写入线程会锁住日志缓存，开始依据缓存中的日志增量写入。这往往会消耗较长时间，这段时间日志缓存无法向事务提供缓存服务。为了降低对事务提交的影响，开发了一种无阻塞的缓存池。内部的两个缓存池交替对外提供日志缓存服务，当一个缓存写满向磁盘写入数据，另一个缓存对外提供日志缓存服务。

#### 宕机数据重做：
在宕机恢复时，依据有效日志进度和数据写入进度读取未更新至磁盘的日志。由于数据写入进度可能更新不及时，所以宕机数据恢复需要做幂等性。

#### 数据快照读：
在读写并行的方面借鉴了Copy-On-Write的思想。传统的Copy-On-Write通过在操作前拷贝一个快照，然后操作期间的读操作都对快照进行，修改后再将指针指向快照。以此来隔离读写操作。在这种机制下完全不需要通过锁来串行读写操作，增加了系统的并行度。但会带来大量的拷贝和内存申请操作，而且写操作期间可能没有并发的读操作，这就让很多操作变得无用。本课题选择一直维护一个快照数据，彻底隔离当前数据和快照数据。在每一次数据提交时增量的更新快照，减少对数据的全量拷贝，且只在创建快照时申请一次内存。

#### 内存管理：
普通进程的内存分配通常交给系统来做。操作系统通过内核方法来为进程分配内存，并通过伙伴分配算法减少内存碎片。但是数据库内核这种内存频繁申请的应用，频繁的系统调用申请内存会占用大量的CPU时间，拉低程序运行效率。因此本课题需要在用户空间创建内存池，在进程开始时一次性向操作系统申请大段内存。在运行时用户空间的内存池提供内存申请服务，减少内核态的内存申请。并使用伙伴分配算法减少内存缝隙。
同步的内存释放同样会占用大量服务线程时间。因此本课题在大段内存释放时，将任务提交给线程池异步去做，减少服务线程的阻塞。

#### 流量限制：
在数据库内核运行过程中，可能在一段时间内出现超大量的请求。若不加以限制，会因为大量线程切换而出现响应缓慢、系统负载大的情况。平常的限流算法如滑动窗口、漏桶算法，都是对单位时间内接受的请求数量进行限制。并没有考虑到请求长时间没有结束，而产生系统中大量请求堆积的问题。
为防止这种情况的出现，本课题研发了一种改进的令牌桶算法来限制系统中的并行服务线程数。

## 系统实现
### 数据存储架构
为实现存储紧密、便于修改检索的数据存储结构。放弃传统关系型数据库的行式结构，转而拥抱列式数据存储结构。

#### 整体结构
从表的视角来看，本课题的数据是纵向按列存储的。相较于行式存储，这样的列式存储将每一列数据隔离。这使多个线程可以没有数据竞争的同时访问一行数据的不同字段。
BigTable模型基于传统的KV数据库存储，这导致大量的物理键冗余存储，实际数据只占据存储空间的一小部分。而SG-ColBase数据以逻辑键组织在一起，提高了存储空间中有效数据所占的比例。
为了减少单个数据存储模块的负载，将列上的数据划分为多个段。每个段作为一个资源（磁盘存储和加载进内存的单位）。
![数据存储架构图](https://images.gitee.com/uploads/images/2022/0520/154213_0aa9076b_2243360.png "屏幕截图.png")

#### 数据增量写入
由于列式数据按照字段的数据类型所占字节个数紧密存储。这种特性使数据在修改操作时，可以通过下标直接定位数据在磁盘中的位置并修改。由于数据为无序分散的存储，在数据插入操作时，可以随机选取空闲列段在尾部插入。为了防止在数据删除时键值相对位置移动，在删除时选择使用额外一块资源增量的记录删除数据的下标（逻辑删除）。

#### 数据增量写入优化
在批量操作时，可能会有部分可以化简的操作。比如同一数据先修改一个值再修改为另一个值。又比如先添加一个数据再将这个数据修改为另一个值，这样多步连续操作的结果和直接改成最终值的结果是一样的。为了解决这个问题，实现了一种化简算法，可以识别并化简数据的操作链。在数据增量写入时，为了减少不必要的随机写。在写入前将数据依据磁盘位置排序。

### 索引存储架构
为了避免使用B+Tree作为磁盘索引所带来的写入时节点分裂和随机访问，支持大数据量写入操作。本课题没有使用B+Tree作为索引磁盘存储结构。转而使用LSM-tree。在内存中使用跳跃表作为有序集合。相比于红黑树，它拥有更快的操作速度，并且可以直接在从磁盘中读到的有序集合上建立索引。复杂度为O（n）而红黑树为O（nlogn）。

#### LSM-tree整体结构
宏观上来看，LSM-tree在磁盘中的存储结构就是多个有序的操作序列。这让本课题只需要将操作记录顺序追加在文件末尾即可完成数据的修改。相比于在整体有序集合中随机写，数据增量写入的效率获得了极大的提高。但这样的存储结构为读取带来了不利因素。在B+Tree中，由于数据是全局有序的，可以只读取其中的一部分数据。但在LSM-tree中，数据被划分为多个有序的操作序列。只读取其中一部分无法得到正确的结果。因此在每一次读取时本课题都需要读取全部数据，并将多个有序操作序列归并还原。

#### LSM-tree优化
为了降低LSM-tree读取时的劣势，采取了许多举措。首先是将列上的索引按值范围分区存储。在进行数据检索时，本课题只需要读取所要检索数据的分区即可完成。这极大的减少了数据检索所需要读取的数据。为了使数据检索的复杂度不变，使用二分查找算法定位分区。当单个分区的LSM-tree磁盘存储中有序操作序列个数过多时，在反序列化时会导致较长时间的归并操作。本课题开发了一种归并机制。在有序操作序列的个数超过阈值时，就会对磁盘存储做整体归并。最后在用户空间内构建资源缓存池，减少磁盘读取次数。

#### SkipList内存存储结构
使用红黑树作为索引内存存储结构的最大问题是构建它的时间复杂度为O（nlogn）。就算依据从磁盘中读取到的已排序的集合创建，复杂度仍旧不变。SkipList实际上就是拥有索引的有序链表。相比于传统有序链表，可以通过索引节点来加速数据访问。且仍保留了链表便于修改的优点。因此它可以直接在LSM-tree反序列化后提供的有序链表上直接生成索引节点，做到O（n）复杂度的构建SkipList。在实现中提供了层倍数参数可以平衡修改和查询之间的效率。经过测试，相比于红黑树。SkipList在修改和查询操作中执行速度均有约30%的提高。

### 布隆过滤器架构
布隆过滤器是一种使用BitMap作为底层数据结构的高效数据过滤机制

#### BitMap数据结构
布隆过滤器底层使用BitMap实现。由于BitMap使用数据所在位置的bit来标记数据是否存在，所以可以用更小的空间存放更多的数据。比如存放从0到32位无符号整数最大值的所有数据。32位无符号整数数组需要字节，而BitMap只需要字节。并且可以支持O（1）时间复杂度判断是否包含。

#### 布隆过滤器整体结构
由于上述BitMap的优势，本课题选择使用BitMap作为布隆过滤器的底层数据结构。在检查数据是否存在时，获取BitMap数据哈希值所在位置的bit来判断数据是否存在。为了减少布隆过滤器数据的全量读取，将布隆过滤器分段存储。在数据判断时，只需要读取所在数据分区的数据即可。由于数据碰撞，布隆过滤器删除比较困难。因此在数据删除时，布隆过滤器不做删除。为了防止布隆过滤器因此误判率过高，会定期重新扫描所有数据，重建布隆过滤器。

### 资源缓存池
为减少系统调用所带来的损耗，本课题禁用操作系统的页高速缓存，转而在用户空间内建立资源缓存池。

#### LRU缓存淘汰实现
在LRU缓存淘汰中，一般需要一个队列来维护访问情况，一个哈希表来实现资源快速提取。让两种数据结构中的数据以O（1）复杂度相互访问，是提高缓存池执行效率的关键。将哈希值作为链表节点，让哈希表可以O（1）的访问到队列。让资源池在提取资源的时候可以高效的维护在队列里的位置。再通过冗余键的方式，通过节点里的key值O（1）的访问到哈希表。这样资源淘汰时也可以快速删除队列中最不常访问的元素在哈希表中的存储。
![LRU缓存结构示意图](https://images.gitee.com/uploads/images/2022/0520/154741_1fdff888_2243360.png "屏幕截图.png")

#### 分区并行实现
当资源池存在操作并发时，需要一些措施来保证数据一致性。比如无锁的CAS（Compare And Set）操作。它可以在用户态保证一致性，减少系统调用。它适用于竞争少且操作时间短的数据并发。但资源缓存池由于大量用户线程的大量调用会有超高的并发，并且如果缓存缺页触发IO会导致长时间的操作。因此，CAS并不适用于资源池。另外一种就是对数据访问加锁来保证一致性。但当大量线程竞争一把锁时，并行度太低，导致大量线程阻塞。为了提高资源池并行度，本课题将数据分区隔离。访问相同分区的数据才竞争一把锁。在定位分区时，使用二分查找算法。这样就可以在资源提取效率几乎不变的情况下，通过分区隔离数目控制资源池的并行度。

#### 并行度扩展实现
通常使用哈希取模作为分区依据，这种方法拥有最低的执行复杂度。但是当想增加分区来扩展资源池整体的并发度（增加分区）时，就需要重新哈希取模。这使几乎所有数据都需要移动分区，在移动过程中会让整个资源池处于不可用的状态。为了减少扩展并行度对资源池整体可用性的影响，本课题转而使用一致性哈希算法作为分区依据。这种算法依据哈希值的范围为资源分区，在并行度扩展时会将原有的某个分区分裂。这种操作只影响被执行分裂操作的分区，对资源池整体可用性影响不大。

#### 资源异步释放
在进行资源淘汰时，从队尾选择最久未使用的资源进行淘汰。但是在淘汰的时候被淘汰的资源可能还在被用户线程使用（持有指针）。如果盲目的释放资源，会导致内存溢出。因此，本课题需要一个机制。等待所有用户使用完后再释放。如果使用一个保证内存可见性的变量来标记，循环等待的话。虽然可以在用户态完成等待，但是其它用户线程往往会对资源进行较长时间操作。这导致线程长时间忙等，占用大量CPU时间。因此本课题使用读写锁来做。所有资源池的获取操作会对获取到的资源上读锁，资源释放前需要获取到所要释放资源的写锁。这样在资源获取时，由于读锁和读锁是共享的，不会有任何的阻塞。释放资源操作也会阻塞直到所有读锁释放后，即所有用户线程使用此资源完毕后进行。在具体操作时，同步执行在数据结构中移除数据的操作，保证其他用户线程无法获取到已经淘汰的资源。阻塞等待和资源释放交给线程池异步执行，减少占用所在资源池分区的锁。


### 事务支持实现
事务有ACID四大特性，分别是原子性、隔离性、持久性、一致性。一致性是目标，原子性、隔离性、持久性是达到目标的途径。为了完备的事务支持，本课题采取了许多举措。
5.5.1 基于读写锁的并发控制
对资源的操作分为读操作和写操作，读操作。多个读操作可以并行执行，但读写、写写操作由于数据竞争在一般情况下不可以并行。基于以上情况，使用读写锁在访问资源前获取资源锁来控制多个用户线程对同一资源的并发访问。为了平衡事务的一致性与执行效率，通过不同的调用方式，提供了不同的隔离级别。如读提交隔离级别（当前读）在访问后立刻释放资源锁、可重复读隔离级别在事务提交之后再释放资源锁。锁机制会保证资源访问的原子性、可见性、有序性，从而进一步保障数据库在内存中数据的原子性和隔离性。
考虑到OLAP场景需要对单列全部数据进行访问。列中的每个数据都获取一遍锁会导致性能大幅度下降。因此没有将锁粒度细到每行每字段级别，而资源级别上锁（每列段每字段）。

#### 基于快照的并发控制
一般使用Copy-On-Write写时复制的机制解决上述读写操作无法并发的问题。数据会在写操作前进行复制，对复制数据做写操作，最后将修改结果覆盖原数据。一般多用于读多写少的业务场景。在大规模数据写入场景下由于大量的内存申请操作，执行效率会急剧下降。传统关系型数据库使用的MVCC多版本并发控制会带来同样的问题。
为了解决上述问题，开发了一种数据快照机制。数据快照在资源读入内存时创建，与资源拥有相同的生命周期，并与资源完全隔离。在用户写资源前不需要做拷贝。当用户可以接受读提交（快照读）的事务隔离级别时，在做读操作时会读取快照数据。由于快照数据与资源完全隔离，对快照数据的读操作与对资源的写操作可以并行执行。在每一次事务提交时会依据日志，增量的更新快照数据。这种快照机制可以兼顾读写操作的并行和大规模数据写入的支持。快照数据需要读写锁来控制访问。快照更新时上写锁，读取时上读锁。

#### 原子性日志写磁盘
事务提交时，为了防止数据库宕机而导致数据不一致。将事务的操作日志追加写入日志文件完成后，再写入日志缓存。而在操作日志追加写入日志文件时，如果操作日志过长，可能会涉及多个扇区的写入。这就会导致日志写入操作不具有原子性，这就使在日志写入时宕机会导致数据不一致。为了使日志追加写入文件具有原子性，在文件头设有字段记录文件有效长度（8字节，原子读写）。在日志追加写入文件之后，通过修改文件有效长度字段即可实现原子性的日志追加写入文件。
![日志文件结构示意图](https://images.gitee.com/uploads/images/2022/0520/154945_85c0f8e1_2243360.png "屏幕截图.png")

#### 无阻塞日志缓存
事务提交时，将日志追加写入文件后，再写日志缓存。等待日志堆积到阈值后，依据日志将对数据的改动同步到磁盘中。对于日志缓存来说，事务提交操作为写操作，读取日志并将数据改动同步至磁盘为读操作。因此数据同步和提交操作是无法并行的。为了减少数据同步时对事务提交操作的阻塞，开发了一种无阻塞缓存。内部由两个缓存构成，分别为服务缓存和同步缓存。服务缓存向事务对象提供日志缓存服务，当日志堆积到阈值时，缓存切换。服务缓存切换为同步缓存，依据日志将数据改动同步至磁盘。同步缓存切换为服务缓存，向事务对象提供服务。
在实现时考虑到当触发缓存切换时，同步缓存可能还未完成将改动同步至磁盘。因此本课题选择在缓存切换前阻塞等待同步缓存工作完成。
![无阻塞缓存示意图](https://images.gitee.com/uploads/images/2022/0520/155115_d8c5f2e6_2243360.png "屏幕截图.png")

#### 数据异步写入
为了减少事务提交时的阻塞，在日志写入磁盘、缓存之后立刻返回。将数据同步任务交给专用线程异步的去做。使用信号量来控制线程的数据同步，在事务提交后会释放日志个数的信号量，线程在每次做数据同步前需要获取阈值个数的信号量。当没有获取到时会阻塞让出CPU，减少对CPU的占用。在完成批量数据同步之后更新文件中的数据同步进度字段。
异步的数据写入可能会导致在资源重新读进内存前，数据改动仍未同步到磁盘。为了防止这种情况发生，本课题开发了一种机制。在每一个资源读进磁盘之前会判断日志缓存中是否存在此资源未同步至磁盘的改动。如果存在，会直接释放阈值个数的信号量，强制数据改动同步至磁盘。在成功同步后再将资源读进内存。以此来实现高效、安全的数据异步写入。
日志文件过长可能会导致磁盘空间不足。因此在每次数据同步后，如果日志文件长度超过阈值且文件中的所有数据改动均被同步到磁盘，则清空日志文件。减少日志文件占用的磁盘空间。

#### 宕机数据重做
在数据库运行时，可能会由于断电、系统异常、磁盘空间耗尽等原因发生宕机。如前文所述，本课题已经为宕机数据恢复做了许多准备：原子性日志追加写文件、日志先写磁盘再写内存、幂等的数据同步。在宕机数据恢复时，通过有效文件长度字段和数据同步进度字段，确定未同步至磁盘的日志。读取并将数据改动同步至磁盘，更新数据同步进度。
由于数据同步操作是具有幂等性的，即使在数据同步后数据同步进度字段因宕机未成功更新，导致在数据恢复时同步相同数据。依然可以保证数据一致性。

### 内存池实现
内存池是一种动态内存分配与管理技术，通常情况下，C++程序员习惯直接使用new，delete，malloc, free等API申请和释放内存，这样导致当程序运行的时间很长的时候，由于所申请的内存块的大小不定，频繁使用时会造成大量的外部内存碎片从而降低程序和操作系统的性能。比如，系统依次分配了16byte、8byte、16byte、4byte，还剩余8byte未分配。这时要分配一个24byte的空间，操作系统回收了一个上面的两个16byte，总的剩余空间有40byte，但是却不能分配出一个连续24byte的空间。这时操作系统就需要将内存重整，腾出连续空间来满足用户进程的请求。
不管是每次内存申请释放内存时的系统调用，还是外部碎片导致的操作系统内存重整。都会大幅度的降低用户进程的工作效率。为了解决上述问题，本课题开发了一种在进程内使用的支持高并发的内存池。
内存池使用伙伴分配算法，把所有的空闲页框分组为 11 块链表，每一块链表分别包含大小为1，2，4，8，16，32，64，128，256，512 和 1024 个连续的页框。对1024 个页框的最大请求对应着 4MB 大小的连续RAM 块。每一块的第一个页框的物理地址是该块大小的整数倍。例如，大小为 16个页框的块，其起始地址是 16 * 2^12 （2^12 = 4096，这是一个常规页的大小）的倍数。
假设要请求一个256（129~256）个页框的块。算法先在256个页框的链表中检查是否有一个空闲块。如果没有这样的块，算法会查找下一个更大的页块，也就是，在512个页框的链表中找一个空闲块。如果存在这样的块，内核就把512的页框分成两等分，一般用作满足需求，另一半则插入到256个页框的链表中。如果在512个页框的块链表中也没找到空闲块，就继续找更大的块——1024个页框的块。如果这样的块存在，内核就把1024个页框块的256个页框用作请求，然后剩余的768个页框中拿512个插入到512个页框的链表中，再把最后的256个插入到256个页框的链表中。如果1024个页框的链表还是空的，算法就放弃并发出错误信号。
简而言之，就是在分配内存时，首先从空闲的内存中搜索比申请的内存大的最小的内存块。如果这样的内存块存在，则将这块内存标记为“已用”，同时将该内存分配给应用程序。如果这样的内存不存在，则操作系统将寻找更大块的空闲内存，然后将这块内存平分成两部分，一部分返回给程序使用，另一部分作为空闲的内存块等待下一次被分配。
以上过程的逆过程就是页框块的释放过程，也是该算法名字的由来。内核试图把大小为 b 的一对空闲伙伴块合并为一个大小为 2b 的单独块。满足以下条件的两个块称为伙伴：
1.两个块具有相同的大小，记作 b
2.它们的物理地址是连续的
3.第一块的第一个页框的物理地址是 2 * b * 2^12 的倍数

### 令牌桶限流
本课题使用一种改进的令牌桶对数据库内核中并行的服务线程数进行限制。事务对应令牌，事务池对应令牌桶。在数据库内核初始化时，构建一个拥有指定个数事务对象的事务池。用户请求时，首先需要向事务池申请一个事务对象。如果事务池中没有事务对象的话，阻塞直到事务池中出现事务对象并申请成功。随后开始执行数据库操作。执行完毕后，将事务对象放回事务池。
以上流程可以让在数据库内核中并行的服务线程数量最多不超过初始化时设定的阈值。事务池的线程安全使用互斥量保证，并使用信号量限制并行访问数量。


### 与MySQL、HBase对比实验
SG-ColBase、MySQL测试环境：
处理器：	Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
机带 RAM：	16.0 GB 
系统类型：	Windows10，64 位操作系统, 基于 x64 的处理器
HBase测试环境：
5个RegionServers，使用阿里云ECS。

### 测试表结构
为了方便测试，测试表只有两个字段。姓名和年龄字段分别为定长字符串和四字节整数类型。并在年龄字段创建索引。MySQL额外创建了自增主键字段。由于SG-ColBase自带逻辑主键，没有创建。
SG-ColBase创建表时每列数据分1000段存储，字段的辅助资源分别有10和50个分区。

![表创建图](https://images.gitee.com/uploads/images/2022/0520/155543_694bd5b7_2243360.png "屏幕截图.png")

### 事务压力测试
测试情景：每个事务向数据库插入100行随机数据，共10000个事务。这里使用事务功能完善的MySQL进行对比

![事务性能对比](https://images.gitee.com/uploads/images/2022/0520/155720_3b444533_2243360.png "屏幕截图.png")

从整体上可以看到MySQL的TPS和SG-ColBase是有差距的。MySQL和SG-ColBase的事务都采用了异步写入的机制。但由于MySQL使用B+Tree索引，在异步插入随机数据时会导致随机写磁盘，甚至导致磁盘数据移动。使异步写入线程长时间占用磁盘时间，影响事务的提交。而SG-ColBase使用的是LSM-tree索引，通过顺序增量写入。大幅度的降低了异步对磁盘时间的占用，减少对事务提交的影响。MySQL的SQL解析也是造成差距的原因。
SG-ColBase的TPS随着线程数的增多而提高，这是由于索引文件顺序批量写入的速度极快，让CPU成为TPS的瓶颈。并且数据插入机制是随机选取数据段的，减少了线程之间资源的竞争。因此线程的增多提高了TPS。
MySQL的TPS随着线程数的增多而微降，这是因为索引文件随机写入速度较慢，磁盘IO是事务的瓶颈。线程数提高反而会因为数据竞争而阻塞。

### 查询压力测试
测试场景：在1000W条数据的测试表中，测试依据年龄字段（有索引）随机查询100W次。为了模拟业务真实场景，其中有部分查询数据库中不存在。这里使用HBase与SG-ColBase进行对比。

![查询性能对比](https://images.gitee.com/uploads/images/2022/0520/155952_54977257_2243360.png "屏幕截图.png")

从整体上可以看到，SG-ColBase在单线程时QPS大幅度领先HBase。这主要是由于SG-ColBase使用了逻辑主键的数据架构，节约了大量的内存，让内存可以容纳更多的有效数据。HBase的集群网络IO也是造成差距的原因。在四线程时这种领先继续保持。当线程数达到了十六线程时，SG-ColBase的QPS开始下降。原因可能是无法为进程分配足够的线程而导致了大量的线程切换。而HBase得益于分布式集群的架构，查询被分摊到多台机器，QPS继续走高。期待未来SG-ColBase的分布式集群版本能在大量线程的QPS上击败HBase。

### 大数据写入压力测试

![大数据量写入对比](https://images.gitee.com/uploads/images/2022/0520/160139_156ef361_2243360.png "屏幕截图.png")

本课题可以看到在15W条数据的规模下，SG-ColBase的写入性能大幅度领先于HBase。除了分布式架构下的网络开销外，SG-ColBase的索引文件分段技术也发挥了很大的作用。在1500W条数据写入的场景下，SG-ColBase被HBase反超。可能是在大规模写入时，分布式架构分摊了磁盘写入压力。还是期待SG-ColBase的分布式版本能够超越HBase。