在常用的Redis、LevelDB等键值存储数据库中，实现其核心存储引擎的数据结构其中之一就是跳表
本项目采用C++语言基于跳表实现的轻量级键值型存储引擎，实现了数据展示、数据添加、数据查询、数据删除、数据存储以及数据加载功能，并采用异步日志系统打印信息
在随机读写情况下，本项目每秒可处理写请求数目为15.22w，每秒可处理读请求数目为74.21w
- bin 生成可执行文件目录
- doc/kvdb.txt 数据存储文件
- doc/log.txt 后台日志信息文件
- src/asynclog.h 使用C++可变参数模板实现的异步日志打印系统
- src/main.cpp 使用skiplist.h的跳表数据结构进行简单的数据测试
- src/skiplist.h 跳表数据结构的核心实现
- test/stress_test.cpp 压力测试代码
- README.md 项目简介和描述
- makefile make编译脚本
- start_stress_test.sh 压力测试脚本
- 数据展示：DisplaySkipList
- 数据添加：InsertElement
- 数据查询：SearchElement
- 数据删除：DeleteElement
- 数据存储：StoreFile
- 数据加载：LoadFile
-
一、使用线程锁和条件变量的生产者-消费者模型进行异步日志系统后台分离打印日志，减少日志打印占用率
-
二、使用template模板抽象出key-value键值对的数据类型，提高泛化性
-
三、使用shared_ptr智能指针替代原生指针对跳表进行内存管理，防止内存泄露
-
四、使用shared_lock和lock_guard来管理读写锁shared_mutex，采用读者-写者模型进行线程间的同步，降低时间损耗
-
五、使用random库的伯努利二项分布随机数算法，基于一定的概率因子p(redis中取值为0.25)，从跳表中确定新节点要添加的层数
- 新节点至少会出现在第一层，也就是从第一层开始抛硬币
- 对于每一层，可以抽象成在做一个抛硬币的实验，如果硬币正面朝上(这个事件发生的概率为p)，新节点的层数就会增加1
- 重复这个随机过程直到硬币背面朝上为止(这个事件发生的概率为1 - p)，此时抛硬币过程结束，计算完成
- SkipList通常有一个预设的最大层数max_level，节点的层数不会超过这个值，若抛硬币一直抛到第max_level层还是正面朝上，此时也不会增加层数
SkipList层数高度：18
测试CPU：i5-12500H
CPU线程核心数：16
随机添加数据测试(使用1个写者线程)：
| 添加数据规模(条) | 耗时(秒) |
|---|---|
| 10w | 1.224277 |
| 50w | 2.940337 |
| 100w | 4.880983 |
每秒可处理写请求数目：15.22w
随机查询数据测试(使用16个读者线程)：
| 查询数据规模(条) | 耗时(秒) |
|---|---|
| 10w | 0.119567 |
| 50w | 0.667468 |
| 100w | 1.560527 |
每秒可处理读请求数目：74.21w
本项目使用C++11的random和thread等标准库进行随机数生成和线程构建和汇合等操作并进行压力测试，可以移植到多种操作系统下运行，下面以Linux环境为例：
对kv存储引擎进行简单的数据测试
- Linux> make
- Linux> ./bin/main
运行start_stress_test.sh来测试kv存储引擎的性能
- Linux> sh start_stress_test.sh