Liluoquan/SkipList-cpp

一个基于跳表的轻量级键值型存储引擎，并提供了服务端和客户端。

SkipList-cpp

NewSQL 是对各种新的可扩展/高性能数据库的简称，这类数据库不仅具有NoSQL对海量数据的存储管理能力，还保持了传统数据库支持 ACID 和 SQL 等特性。其中，非关系型数据库redis，以及levedb，rockdb其核心存储引擎的数据结构就是跳表。

本项目基于跳表实现的轻量级键值型存储引擎，使用C++实现。插入数据、删除数据、查询数据、数据展示、数据落盘、文件加载数据，以及数据库大小显示。

在随机写读情况下，该项目每秒可处理写请求数（QPS）: 36.723w，每秒可处理读请求数（QPS）: 33.168w（测试条件基于实验室服务器下，不同性能和环境有影响）

本项目还提供了存储引擎的客户端和服务端，并在服务端中实现了读操作和写操作的分离，提高读取速度。

性能测试

分别按照 10万、50万、100万条存取请求对存储引擎进行压力测试。

跳表树高 level 为：18

采用随机插入和读取数据进行测试。

测试环境

硬件平台：

• 阿里云 轻量应用服务器 （双核4G，6M 带宽）

编译环境：

• gcc version 7.4.0 (Ubuntu 7.4.0-1ubuntu1~18.04)
• GNU Make 4.1

系统版本：

• Ubuntu 18.04

本地插入数据测试

单线程写入指只有一个线程向存储引擎写入数据，双线程写入指两个线程同时向存储引擎写入数据。

插入数据规模 / 万条	单线程写入耗时 / 秒	双线程写入耗时 / 秒
10	0.164538	0.321821
50	1.12636	2.37523
100	2.72307	5.47412

• 单线程下，每秒可处理写请求数（QPS）：36.723w
• 双线程下，每秒可处理写请求数（QPS）：18.268w
• 注：最终QPS 取数据量最大的 QPS

本地读取数据测试

单线程读取指只有一个线程向存储引擎写入数据，双线程读取指两个线程同时向存储引擎读取数据。

读取数据规模 / 万条	单线程读取耗时 / 秒	双线程读取耗时 / 秒
10	0.136557	0.102825
50	1.13001	0.984998
100	3.01494	1.82848

• 单线程下，每秒可处理读请求数（QPS）：33.168w
• 双线程下，每秒可处理读请求数（QPS）：54.690w
• 注：最终QPS 取数据量最大的 QPS

项目运行方式

运行 shell 脚本

sh ./run.sh

获得三个可执行文件

./bin
├── client
├── server
└── test
    ├── test_base_function
    ├── test_stress
    └── test_threadPool

• client：实例客户端
• server：实例服务端
• test_base_function：存储引擎的基本功能测试
• test_stress：存储引擎的压力测试
• test_threadPool：服务端的线程池功能测试

如何在自己的项目中使用该存储引擎？

包含头文件 ./base/SkipList.h ，然后调用相关接口即可。

待优化

• 键值存储引擎只能使用重载了 operator < 的数据类型/对象，如果使用其他类型需要自定义比较函数，可以考虑把这部分抽象出来，给出一个接口，让用户放入自定义的比较函数。
• 存储引擎的读取使用线程池，只用一个线程负责写操作，不适用于大量写操作的场合。
• 可以加上一致性协议，例如 raft 来构成分布式存储，结合高并发网络框架后可以对外提供分布式存储服务。