# go-cache

**Repository Path**: alixeu/go-cache

## Basic Information

- **Project Name**: go-cache
- **Description**: 一个基于go的kv缓存数据库
- **Primary Language**: Go
- **License**: Apache-2.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2023-05-06
- **Last Updated**: 2023-07-14

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# go-cache

## 介绍

基于go语言实现内存级别的kV缓存数据库,内部类似redis

## 开发任务

-[x] RESP 2 (bytes 长度限制2147483647)
-[x] hash表 自实现
-[x] IO多路复用 (epoll)
-[ ] 命令
    -[x] 基础
        -[x] keys
        -[ ] info (内存,cpu,持久化,版本,进程)
    -[x] string
        -[x] get
        -[x] mget
        -[x] set
        -[x] mset
        -[x] del
    -[x] Hash
        -[x] hget
        -[x] hmget
        -[x] hgetall
        -[x] hset
        -[x] hdel
    -[x] list
        -[x] lpush
        -[x] rpush
        -[x] lpop
        -[x] rpop
        -[x] lrange
    -[x] set
        -[x] sadd
        -[x] smember
        -[x] sismember
        -[x] srem
    -[x] sortedset
        -[x] zadd
        -[x] zrange
    -[ ] stream
        -[ ] xadd
        -[ ] xgroup
        -[ ] xreadgroup
        -[ ] xread
        -[ ] xack
        -[ ] xpending
-[x] aof 日志
    -[x] aof 追加 (everySec)
    -[x] aof 重写 (异步)
-[ ] 慢查询记录
-[x] key过期清除
  -[x] 惰性删除
  -[ ] 定时删除
      -[ ] lru
      -[ ] lfu
-[ ] rdb 文件

### hash表

- hash冲突 链表解决
- 建立2个hash表 rehash时相互转化
- 渐进式rehash (负载因子大于等于0.75)
    * 第一次负载因子到达 0.75
        * 新建hash表 (长度为旧hash表的2倍)
    * 写操作只会发生在新的hash表上
    * 当读操作发生在旧hash表上 进行渐进式hash
        1. 将该key所在的列表上的所有元素重新计算hash值
        2. 赋值到新hash对应的位置上
    * 负载因子再次到达 0.75 而且旧表中还有数据
        1. 将旧表的长度扩大2倍变为新表
        2. 对旧表的重新进行rehash
        3. 之前的新表标记为旧表
    * 负载因子再次到达 0.75 而且旧表中没有数据
        * 新建hash表 (长度为旧hash表的2倍)

### io多路复用(kqueue以后在做)

- 原生 goroutine-per-connection 模式由于多个go程的存在 需要进行并发控制 性能容易降低, 在大量请求的时候 每一个go程占用2m
  内存会增加
- epoll 系统调用
    1. 不需要返回监听的所有的 fd ,只用返回有事件的 fd 不用拷贝太多数据
    2. 红黑树管理 fd 比线性查找效率更高
    3. 分为边缘触发(处理事件时 不进行删除) 和水平触发 (处理事件时进行删除)
- 相关系统调用
    1. `epoll_create(int size) int` 创建一个epoll实例
        * linux 2.6 引入 epoll_create1 可以设置更多参数 比如默认wait是否为阻塞
    2. `epoll_ctl(int epfd, int op, int fd, struct epoll_event *event)`将一个文件描述符加入或者移出 epoll 实例的事件表中
       epfd 为epoll的实例, op 为操作 1是添加 2是删除 3是修改已经存在的, event 关注的事件
    3. `epoll_wait(int epfd, struct epoll_event *events, int maxevents, int timeout)` 等待一个或多个文件描述符上的事件
       maxevents一次能处理最大的事件数量 timeout表示等待事件的超时时间 -1代表阻塞
    4. `` 
- 注意点:
    1. go语言使用的go程在关闭时操作系统会自动回收所有空间,可是使用了系统调用的空间就不会自动回收空间 syscall.Close(c.fd)对所有的空间进行回收

### 命令的笔记

1. 实现跳表来支撑 sortedset 
    - 缺点 对应跳表记录排名这一点没想出来😥
2. keys 自己实现统配符 * ？的匹配
    - 一开始使用回溯算法匹配后来发现可以优化为动规

### aof 

1. 只对写入修改删除命令做aof
2. 对于有过期时间的命令要转化为时间戳来存储
3. aof追加写落盘频率(每1s落盘一次)
4. 重写aof (异步读取数据)
   - 当旧aof大小到达8m时候进行重写 (64m)
   - 读取整个数据库的数据重写生成一个新的aof文件
   - 重写的时候名字暂为remake.aof
   - 期间aof落盘会落盘到cache.aof (缓存重写aof时的操作)
   - 在重写完毕的时候删除旧aof
   - 重写完改名appendonly.aof
   - 将cache.aof中的内容追加到appendonly.aof中(此时会阻塞主线程)

    
底层系统调用:
1. open  
   - 获得一个没用的fd标识,用于分配给要打开的文件 
   - 根据路径寻找到对应的文件 获取到对应的inode
     * 先去目录项缓存 dcache 里面寻找
     * 调用 vfs 的lookup() ->  ext4_lookup() 具体实现 
       1. ext4 中 inode 保存在 一个数组里
       2. / 的 inode是预先定义好的 inode号码为2
     * 从 / 对应的inode  递归ext4_lookup() 找到对应的inode
   - 将inode信息建立一个flie对象 然后和fd绑定
2. read
   - 得到fd对应的文件描述符 
   - 去看看页缓存 没有就去读取对应的页
     * 在inode中获得iblock块的位置 ext4交给磁盘驱动来读取到数据 将块写到一个或多个页中
     * 进行预读 将附件的块也读到内存中
   - 将内存复制到用户内存中
3. write
   - 通过fd获得file 中的address_space来关联文件和内存
   - 通过基数树来查找到对应的缓存页
   - 将缓存页在内核态中进行写操作 将页标记为脏页
   - 等待写回
     * 落盘
     * 脏页超时
     * 内存紧张
     * 脏页数量太多
   - 在超级块中获得脏页数据
   - 10次写入后还有脏页数据就将全部协会

异步启动使用原子操作保证不影响主线程

*Q* 原子操作在不同架构平台的情况
32位下 64位的int 没有做到内存对齐
1. 跨越了多个缓存行的读写操作 ,原子操作可能出现问题
2. 导致部分读写,不能一次读写

解决不使用int64, 使用int32来保证原子操作 (减少了内存对齐的考虑)

### 慢查询日志

1. 记录 id, 命令名, 参数, 客户端地址, 端口, 开始时间, 执行时间, 内存情况, 
2. 只保存120条数据慢查询数据 (循环数组)
3. 可以以csv格式保存 slowlog.csv 慢查询日志到磁盘(防止宕机丢失) 

### 可重用的删除
1. 当检查到key过期的时候不直接删除,而是放进一个队列中
2. 当有新的k-v到达时,不直接申请空间,而是到这个队列里面去去选取一个node直接改变其内容
3. 只有当空间内存不够的时候,新建一个go程去删除队列中数据(因为内存不够的时候就不会进行写操作了,所以铁安全)