type
date
status
slug
summary
tags
category
icon
password
网址
KeyValueStore
一个使用C + TCP + NtyCo实现的，支持多种存储引擎的Key-Value存储系统，支持多种语言客户端。
解决长、短链接之间的映射关系的问题，在数据库中构建的强查找的数据结构，通过短链接查表重定向获取实链接，可作为一个中间件使用。
文件介绍
- NtyCo: 协程的实现，kvstore是基于协程实现；
- kvs-client: 支持多语言客户端封装；
- kvstore.c: 实现了网络基础库与kv应用协议解析，默认使用Array
- rbtree.c: 实现了RBTree 并封装了符合kvstore的api
- hash.c: 实现了Hash 并封装了符合Hash的api
- dhash.c: 实现了DHash 并封装了符合DHash的api
- skiptable.c: 实现了SkipTable 并封装了符合SkipTable的api
- log.c: 日志文件
- testcase.c: 测试用例
代码编译
执行
执行举例
详细描述
1.头文件在\KVStore\NtyCo\core\nty_coroutine.h文件中，可根据需要进行开启（1）或关闭（0）功能：
key-value存储的概念与应用
1.Key-Value存储是一种通过键值对(key-value pair)形式存储数据的方法。
2.应用场景包括问题答案存储、短链接生成、用户名密码管理等。
3.Key-Value存储通过纯内存操作实现，提供快速查找和访问数据的能力。
e.g. chatgpt : question, answer ⇒ key, value
- 独立进程，耦合度低，利于维护；
- 通过网络（tcp）访问
eg. set name king (13字符)
http ⇒ head + body: 有效命令占用比不高（X）
udp ⇒ 发送后没有确认（X）
tcp ⇒ 占用低，有确认（✓）
- 强查找的数据结构(array, rbtree, hash, dhash, skiptable)
- 图床，人员管理
KV存储的数据结构选择
1.选择数据结构时考虑查找频率和查找效率，如rbtree、hash等。
2.数据量不大时，可使用array等简单数据结构；数据量大时，需要高效的数据结构如B树、哈希等。
KV存储的实现与协议设计
1.KV存储实现包括TCP服务器和存储引擎两部分。
2.协议设计需考虑数据的解析和命令的执行，如SET、GET、COUNT、DELETE、EXIST等。
3.命令格式通常包括命令名、键、值等，如SET命令包含key和value。
KV存储的实践与架构
1.KV存储的实现包括一个独立的进程、TCP网络协议、以及强查找数据结构如红黑树、B树等。
2.KV存储服务器通过TCP协议接收客户端数据，解析并存储键值对。
3.访问KV存储时，客户端发送命令和数据，服务器查找并返回对应值。
KV存储的系统架构与网络通信
1.KV存储系统通常由多个组件构成，包括网络通信模块、数据存储模块和业务逻辑处理模块等。
2.网络通信模块负责处理客户端的连接请求、数据的收发和传输等任务。
3.数据存储模块采用适当的数据结构和方法来存储键值对数据，提供高效的访问能力。
4.业务逻辑处理模块根据客户端的请求执行相应的操作，如SET、GET、COUNT、DELETE、EXIST等，并返回结果给客户端。
KV存储的数据结构与命令实现
1.KV存储使用多种数据结构（如红黑树、哈希表）来存储键值对，提供高效的查找和操作能力。
2.每个命令（如set、get）的实现都依赖于底层数据结构的操作，需要正确处理数据的存储和检索。
3.命令实现还需考虑错误处理，如当键或值不存在时，应返回适当的错误码或信息给客户端。
KV存储的协议定义与命令格式
1.协议定义参考Redis，采用特定字符分隔token和描述命令。
2.命令格式包括token数量、命令长度、键和值的长度等信息。
KV存储的协议解析与命令处理
1.协议解析负责从接收到的数据中提取命令和相关参数。
2.命令处理根据解析出的命令和参数执行相应的操作，如set、get等。
3.解析和处理过程中需验证命令的格式和参数的正确性，确保数据的完整性和安全性。
KV存储的错误处理与协议解析
1.错误处理包括检测命令参数数量是否正确，以及处理格式错误等。
2.协议解析涉及将接收到的数据分割成token，并根据token类型执行相应命令。
KV存储的优缺点
1.KV存储适合做服务器，但不适合做业务。
2.C和C++适合做服务器，但不适合做业务开发。
3.流媒体服务器、统计功能等适合用C和C++编写。
KV存储的性能测试
测试用例完善，包括set、get、delete和exist命令的测试。
KV存储的代码归纳
1.将测试用例和代码整合，使用connectionFD传递参数。
2.引入红黑树数据结构，修改key值为字符串类型。
3.对比红黑树代码和原始代码的区别，包括节点定义和元素数量统计。
4.红黑树的插入和删除操作使用compare函数对比key值。
5.封装红黑树的初始化、销毁和提供接口。
KV存储的架构设计
1.构建三层架构：引擎层、接口层和协议层。
2.引擎层包括红黑树、哈希表、skip table等数据结构。
3.接口层提供标准的get、put、count、exist、delete接口。
4.协议层负责协议解析，包括set、get等命令。
5.网络层接收数据，传递给协议层，再由接口层和引擎层处理数据。
6.存储层负责将数据同步到文件，用于持久化。
KV存储的封装设计
1.封装红黑树为SO库，提供动态加载的接口。
2.设计过滤器模式，匹配不同的KV energy和操作方法。
3.定义KV energy和KV energy ops结构体，实现面向对象的思想。
红黑树的性能测试
1.编写测试用例，测试红黑树插入十万个key的性能。
2.定义message数组，用于循环插入数据。
3.测量插入十万个key所需的时间，结果约为八秒。
KV存储的基础
1.KV存储基于协程实现，我们感知不到协程的存在。
2.协程提供了最基础的网络层，KV存储构建在其上。
性能和稳定性测试
1.测试产品的性能和稳定性，包括并发连接数、测试用例、QPS等。
2.并发连接数测试：测量系统能创建的协程数。
3.测试用例验证：验证业务发出的命令返回的结果是否匹配。
4.QPS测试：测量系统在单位时间内能处理的请求数。
QPS测试的准确性
1.通过屏蔽打印信息和优化测试代码，提高QPS测试的准确性。
2.屏蔽打印信息后，再次测量得到更准确的数据。
3.最终测量得到QPS为33333。
哈希存储引擎的添加
1.增加哈希存储引擎，封装哈希表的接口。
2.通过enable哈希宏，将哈希存储引擎添加到系统中。
3.初始化、destroy、put、get、delete、exist等接口的实现。
哈希存储引擎的性能对比
1.对比哈希和红黑树的性能，发现哈希在某些情况下的性能不及红黑树。
2.哈希表实现中的链式冲突导致性能下降。
3.通过去掉判断存在的循环，提高哈希的性能。
哈希存储引擎的性能对比
1.对比哈希和红黑树的性能，发现哈希在某些情况下的性能不及红黑树。
2.哈希表实现中的链式冲突导致性能下降。
3.通过去掉判断存在的循环，提高哈希的性能。
分布式KV存储
1.通过主从复制实现分布式KV存储。
2.Set操作执行后，将消息发送到从机。
3.从机接收消息并同步数据。
日志和持久化（5）
1.通过日志和持久化确保数据的可靠性。
2.引入内存池，将内存块同步到磁盘。
问题
一.数组删除问题（3）
1.数组删除后，count值不更新，导致索引错误。
2.delete操作在查找和set过程中出现问题，导致数据覆盖。
3.解决方案：
（1）.通过for循环查找key和value不等于零的元素。
（2）.内存池解决数组删除问题内存池解决数组删除问题
1）.引入内存池组件，用于管理固定大小的内存块。
2）.内存池通过头插法构建块链表，解决数组删除问题。
3）.将数组代码改编为使用内存池，实现动态删除。
>内存池的使用
1).分配固定大小的内存块，每块包含指针指向下一块。
2).初始化error table时使用内存池分配内存。
3).查找、set操作通过遍历内存池分配的块来完成。
二.哈希冲突问题（5）
在哈希表的使用过程中，随着数据的增加，原有的哈希表可能会变得过于拥挤，导致哈希冲突增多，进而影响查找、插入和删除操作的效率。
解决：动态扩展哈希表（Dynamic Expanding Hash Table）是一种能够自动调整其大小以应对数据增长或减少的哈希表实现。动态扩展哈希表会在必要时自动增加其容量（即存储桶的数量），并重新分布现有的数据项，以减少冲突。
关键点：
- 负载因子（Load Factor）：负载因子是哈希表中已占用的存储桶数与总存储桶数的比例。当负载因子超过某个预设的阈值（如0.75）时，哈希表会触发扩展操作。
- 扩展操作：
- 增加、更大的存储桶数组来实现。
- 重新哈希：将原哈希表中的每个元素根据新的哈希函数和更大的存储桶数组重新计算哈希值，并放置到新的位置。
- 哈希函数：在扩展后，可能需要调整哈希函数以确保分布均匀，减少冲突。
- 性能考虑：虽然扩展操作本身可能代价较高，但它确保了哈希表在数据增长时仍能保持较高的操作效率。
可以把这个table这里改到十万，这实际上是一种手动调整哈希表大小的方式，而非动态扩展。动态扩展哈希表会自动根据当前负载情况决定是否扩展，并在需要时自动进行。
动态扩展哈希表通过自动调整其大小来优化性能，减少哈希冲突，并保持高效的查找、插入和删除操作。它是处理动态数据集时的一种非常有用的数据结构。
实现步骤和策略：
(1). 负载因子监测
- 负载因子：定义为哈希表中已存储的元素数量与哈希表总容量的比率。
- 监测：哈希表会定期或每次插入/删除元素时检查其负载因子。
(2). 扩容触发条件
- 当负载因子超过某个预设的阈值（如0.75）时，哈希表会触发扩容操作。这个阈值可以根据具体实现和应用场景进行调整。
(3). 扩容操作
- 分配新空间：哈希表会分配一个新的、更大的存储桶数组。新数组的大小通常是原数组大小的倍数（如2倍）。
- 重新哈希：
- 遍历原哈希表中的每个元素。
- 对每个元素使用新的哈希函数（可能根据新数组的大小进行了调整）计算新的哈希值。
- 将元素放置到新数组中的相应位置。
(4). 哈希函数调整
- 在扩容后，哈希函数可能需要调整以确保元素在新数组中的分布尽可能均匀。这通常涉及到调整哈希函数中的某些参数，如除数（在模运算中）或位掩码（在位运算中）。
QPS
QPS（Queries Per Second）是衡量系统性能的一个重要指标，特别是在处理数据库查询、网络请求或任何需要响应用户请求的系统中。它表示每秒钟能够处理的查询数量。
QPS 的重要性
- 性能评估：通过监测 QPS，可以了解系统在高负载情况下的表现。
- 容量规划：可以帮助团队进行资源分配和硬件配置，以确保在流量高峰期系统依然能够正常运行。
- 负载测试：在开发过程中，通常会对应用进行压力测试，以确定其最大承受能力。
如何提高 QPS
- 优化查询：
- 确保 SQL 查询是高效的，使用索引等。
- 减少不必要的数据检索，只获取所需的信息。
- 缓存机制：
- 使用缓存来存储频繁访问的数据，减少对数据库的直接查询。
- 负载均衡：
- 使用负载均衡器将请求分发到多个服务器上，从而提升整体处理能力。
- 异步处理：
- 将一些耗时操作异步化，以减少请求等待时间，提高并发处理能力。
- 架构优化：
- 考虑微服务架构，将不同功能模块拆分开来，使得每个服务都能独立扩展和优化。
- 代码优化：
- 定期审查和重构代码以消除性能瓶颈。
测试用例运行及10W条QPS测试
测试用例详细数据
类别 | 测试量 | time_used(s) | qps(request/second) |
RBTree | 10W | 32.233 | 3000 |
ㅤ | 50W | 164.737 | 3000 |
ㅤ | 100W | 323.053 | 3000 |
Hash | 10W | 45.240 | 2000 |
ㅤ | 50W | 411.099 | 1000 |
ㅤ | 100W | 1513.323 | 0 |
Dhash | 10W | 32.615 | 2000 |
ㅤ | 50W | 177.021 | 2000 |
ㅤ | 100W | 344.869 | 2000 |
SkipTable | 10W | 40.287 | 2000 |
ㅤ | 50W | 393.252 | 1000 |
ㅤ | 100W | 2673.24 | 0 |