# 使用说明
- “kv-store-v1”：存放全部的项目源码，项目使用C语言完成，代码总量在5000行左右。其中的“code_init”文件夹为前期验证rbtree、btree的增/删/查操作，使用```int```型作为元素类型。
- “Document”：存放项目开发过程中用到的文档或工具。
要运行本项目，需要准备两台Linux机器，“客户端”存放“kv-store-v1”的“tb_kvstore.c”、“服务端”存放“kv-store-v1”中剩余的所有代码（不包括“code_init”文件夹）。编译指令如下：
服务端：
```gcc -o main main.c kvstore.c array.c rbtree.c btree.c hash.c dhash.c skiplist.c```
```./main 9998```
客户端：
```gcc -o tb_kvstore tb_kvstore.c```
```./tb_kvstore 192.168.154.130 9998```
视频讲解参考B站：“[【C语言项目笔记】基于C语言实现内存型数据库(kv存储)](https://www.bilibili.com/video/BV1kC411a7xg/)”
下面是整个项目的说明文档，更舒服的排版可以看看CSDN：“[基于C语言实现内存型数据库(kv存储)](https://blog.csdn.net/weixin_46258766/article/details/136228729)”。
***
# 基于C语言实现内存型数据库(kv存储)
[toc]
> - 源代码仓库见Github：[kv-store仓库](https://github.com/jjejdhhd/kv-store)
> - 参考视频：“零声教育”的“[linux基础架构-Kv存储](https://app0k9osxub4596.h5.xiaoeknow.com/p/decorate/page/eyJpZCI6NDI3OTU2MiwiY2hhbm5lbF9pZCI6IiJ9)”。
> - 其他源码：[协程](https://github.com/wangbojing/NtyCo)。
***
# 1. 项目背景
## 1.1 Redis介绍
  本项目主要想仿照Redis的交互方式，实现一个基本的“**内存型数据库**”，所以首先来介绍一下Redis。随着互联网的普及，只要是上网的APP基本上都需要和相应的服务器请求数据，通常来说，这些数据被服务器保存在“磁盘”上的文件中，称之为“**磁盘型数据库**”。但是面对海量用户时(比如秒杀活动)，磁盘IO的读写速率不够快从而导致用户体验下降，并且服务器数据库的压力也非常大。鉴于很多请求只是读取数据，这就启发我们将一些热点数据存放在内存中，以便快速响应请求、并且减轻磁盘的读写压力。
当然，上述只是一个初步的想法，后续如何清理内存数据、分布式存储等可以参考B站的科普视频，讲的非常简洁易懂：
> - [【趣话Redis第一弹】我是Redis，MySQL大哥被我坑惨了！](https://www.bilibili.com/video/BV1Fd4y1T7pD/)---“缓存穿透、缓存击穿、缓存雪崩”、“定时删除、惰性删除、内存淘汰”
> - [【趣话Redis第二弹】Redis数据持久化AOF和RDB原理一次搞懂！](https://www.bilibili.com/video/BV1sV4y147Jz/)---“RDB+AOF”
> - [【趣话Redis第三弹】Redis的高可用是怎么实现的？哨兵是什么原理？](https://www.bilibili.com/video/BV1MW4y187AH/)---“主观下线、客观下线”、“哨兵选举”、“故障转移”
> - [趣话Redis：Redis集群是如何工作的？](https://www.bilibili.com/video/BV1ge411L7Sh/)---“哈希桶”、“集群工作+主从复制”
下面是一些典型的面试题：
> - 为什么要使用Redis？
> > 1. 从高并发上来说：直接操作缓存能够承受的请求是远远大于直接访问数据库的，所以我们可以考虑把数据库中的部分数据转移到缓存中去。这样用户的一部分请求会直接到缓存，而不用经过数据库。
> > 2. 从高性能上来说：用户第一次访问数据库中的某些数据，因为是从硬盘上读取的，所以这个过程会比较慢。将该用户访问的数据存在缓存中，下一次再访问这些数据的时候就可以直接从缓存中获取了。操作缓存就是直接操作内存，所以速度相当快。
>
> - 为什么要使用Redis而不是其他的，例如Java自带的map或者guava？
> >   缓存分为本地缓存和分布式缓存，像map或者guava就是本地缓存。本地缓存最主要的特点是轻量以及快速，生命周期随着jvm的销毁而结束。在多实例的情况下，每个实例都需要各自保存一份缓存，缓存不具有一致性。redis或memcached之类的称为分布式缓存，在多实例的情况下，各实例共用一份缓存数据，缓存具有一致性。
>
> - Redis应用场景有哪些?
> > 1. 缓存热点数据，缓解数据库的压力。
> > 2. 利用Redis原子性的自增操作，可以实现计数器的功能。比如统计用户点赞数、用户访问数等。
> > 3. 分布式锁。在分布式场景下，无法使用单机环境下的锁来对多个节点上的进程进行同步。可以使用Redis自带的SETNX命令实现分布式锁，除此之外，还可以使用官方提供的RedLock分布式锁实现。
> > 4. 简单的消息队列。可以使用Redis自身的发布/订阅模式或者List来实现简单的消息队列，实现异步操作。
> > 5. 限速器。可用于限制某个用户访问某个接口的频率，比如秒杀场景用于防止用户快速点击带来不必要的压力。
> > 6. 好友关系。利用集合的一些命令，比如交集、并集、差集等，实现共同好友、共同爱好之类的功能。
>
> - 为什么Redis这么快？
> > 1. Redis是基于内存进行数据操作的Redis使用内存存储，没有磁盘IO上的开销，数据存在内存中，读写速度快。
> > 2. 采用IO多路复用技术。Redis使用单线程来轮询描述符，将数据库的操作都转换成了事件，不在网络I/O上浪费过多的时间。
> > 3. 高效的数据结构。Redis每种数据类型底层都做了优化，目的就是为了追求更快的速度。
>
> - 参考视频：[为什么要使用Redis？](https://www.bilibili.com/video/BV1sS4y1w7Cf/)、[Redis的应用场景有哪些？](https://www.bilibili.com/video/BV1GG4y1H7tK/)、[Redis，好快！](https://www.bilibili.com/video/BV1va411a7pc/)
## 1.2 项目预期及基本架构
<div align=center>
```mermaid
flowchart RL
A["客户端"]
subgraph ser["服务端"]
direction LR
tcp("tcp server\nkv_protocol")
engine("store-engine\narray/rbtree/btree/hash/dhash/skiplist")
tcp<-->engine
end
ser--"2：OK"-->A
A--"1：SET name humu"-->ser
style A fill:#FFFFDE, stroke:#AAAA33
```
</div><div align=center>
图1 项目框架
</div>
  于是我们现在就来实现这个“内存型数据库”，**本项目使用C语言，默认键值对key-value都是```char*```类型**。如上图所示，我们希望“客户端”可以和“服务端”通讯，发送相应的指令并得到相应的信息。比如“客户端”插入一个新的键值对“(name: humu)”，那么就发送“SET name humu”；“服务端”接收到这个数据包后，执行相应的操作，再返回“OK”给“客户端”。鉴于**kv存储需要强查找的数据结构**，我们可以使用rbtree、btree、b+tree、hash、dhash、array(数据量不多，比如http头)、skiplist、list(性能低不考虑)。最终，下表列出了我们要实现的所有数据结构及其对应的指令：
<div align=center>
表1 kv存储协议对应的数据结构及命令
</div>
<div align=center><table style="border-collapse:collapse;border-spacing:0" class="tg"><thead><tr><th style="border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;font-weight:normal;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:middle;word-break:normal">操作/<br>数据结构</th><th style="border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;font-weight:bold;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:middle;word-break:normal">插入</th><th style="border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;font-weight:bold;overflow:hidden;padding:10px 5px;text-align:center;vertical-a
基于C语言实现内存型数据库（kv存储）.zip （29个子文件） 
archieC316 kv-store-v1 
rbtree.c 33KB skiplist.c 11KB tb_kvstore.c 11KB hash.c 9KB dhash.h 2KB dhash.c 11KB kvstore.h 856B code_init rbtree_int.c 32KB basic_echo.c 2KB btree_int.c 35KB hash.h 2KB array.h 1KB array.c 8KB main 63KB btree.c 43KB kvstore.c 13KB main.c 12KB btree.h 2KB skiplist.h 2KB rbtree.h 2KB README.md 88KB Document 
PPT-基于C语言实现内存型数据库.pptx 14.17MB readme.md 508B 开发框架.emmx 8KB
NetAssist.exe 634KB
红黑树生成步骤.html 38KB PPT模板.pptx 14.39MB 画图.eddx 89KB
表格备份.xlsx 12KB资源评论
