Raft Based Distributed Cache

基于Raft论文实现的,整体思路就是由Raft算法维持集群状态的一致性（节点丢失，增加问题）,一致性hash将数据分散到各个节点上

支持的功能

leader选举.不管是刚启动还是leader丢失,都能保证一轮选举选出新leader
集群成员动态更变,保证集群半数以上server活着,依然能对外提供服务
基于一致性hash保证缓存数据的负载均衡,客户端连接也是连接到目标数据节点上
客户端由于配置了集群的信息,也可以生成一致性hash,虽然跟服务器可能不一致,但是正常情况是命中率很高.
在集群没有节点丢失是100%命中,即出现不命中的情况,会同步服务的节点状况,发起二次请求,不影响后续的请求.
缓存数据的备份(内存快照 + 写操作的日志 = 完整缓存数据)

技术点

Raft算法.
一致性Hash.
Netty,集群节点之间的通信使用的Netty.
NIO.
处理客户端请求的这部分通信,之前采用的netty性能不太好,Netty是个异步通信框架,做同步后性能会很差.然后自己实现的. 多线程跟单线程都尝试过,多线程是有不错的性能提升,但是一做线程同步,性能急剧下降,通信数据最早使用的是google protoBuf序列化反序列化,不够灵活,重点还慢,后来自己实现的,通过单例减少对象的反复创建,将序列化后的数据直接放入channel的写缓冲区(DirectBuffer),减少数据的拷贝,从而提升这部分的性能.
并发编程.

处理客户端请求

尝试了使用下面三种方式

1)单线程.
客户端连接到读取客户端数据,给客户端返回的数据全在单线程里面
2)多线程_1.
一个线程接收客户端连接,然后将连接均分到多个读个线程,并注册到对应的Selector.多个线程访问共享数据需要加锁.
3)多线程_2.
一个线程接收所有客户端连接,有任务放入队列, 多个线程负责读,一个线程处理读到的数据,然后将返回结果,放入队列,多个写线程取任务返回客户端不要加锁,但是需要阻塞队列.
结果表明:单线程方式是最快的,对于短,且无阻塞的任务,多线程带来的效率提升不足以弥补多线程同步带来的性能问题.
顺带提下常见问题Redis为什么采用单线程?

线程切换开销.后台处理数据只是内存中读一个数据,有线程切换的开销任务都处理完了,但是是现在机器都是多核的,控制线程数量,完全可以做到并行.
采用多线程必然存在并发线程安全问题.线程安全主要有两种解决方案
a) 基于锁,做线程同步.结果就是对于短,且无阻塞的任务,多线程带来的效率提升不足以弥补多线程同步带来的性能问题
b) mvcc.可能有效,没尝试过,但是并发写的时候性能不会太好.

Quick Start

chmod -R 777 ./out
cd out
./build.sh 5 可以快速在本机上部署五个实例的集群
./kill_all.sh 5 可以关闭这五台集群
./kill.sh 1 可以关闭id = 1 的一个实例
./start.sh 1 可以开启id = 1 的一个实例
./client.sh 简单的命令行客户端
反复创建(执行build.sh) 而没有对应关掉的话,自己jps 查看下手动kill
build.sh 之后一定要有kill，才能再build,pid文件存在创建实例的时候会自己退出

缓存的存储(下面性能测试,测的时候是放在内存中的数据)

使用HashMap作为索引.
基于内存映射文件存储具体数据.
缓存的插入是追加的方式,满足很好的局部性,性能没有大的下降
随机读,在数据量较大的时候,有明显的下降,数据较小的时候性能差不多.

raft

leader 选举.
节点在倒计时内没有收到来自leader心跳,会在一个随机时间内0-500ms,(150-300,论文推荐)发起选举,在选举之前先预选举(防止应为自身网络原因而没有收到来自leader心跳包) 收到半数以上的节点当选为leader,并向所有follower 发送心跳信息. 最终基本达到了,不管是集群刚启动,还是leader挂了,都能一轮选举选出leader.
数据同步.
基本上所有能看到的数据同步原理都差不多. leader 跟 follower 的心跳包中,包含了节点的数据信息. zookeeper中是事务id,RocketMQ是文件偏移量,leader根据这个信息将之后的数据同步给follower.
安全性.
1. 同时存在两个leader?
  半数以上的投票才能当选为leader,所以每一轮选举最多只能选出一个leader
2. 当选为leader的节点,没有包含最多的数据?
  所有写操作,只有半数以上节点确认才提交,所以一定有半数以上的节点含有最新的数据,投票的时候,若节点数据少于该节点,是不会把选票投给它. 所以,只有含有最新数据的节点才能当选为leader.
3. leader接收到半数以上节点确认,并在本地提交数据,这时候leader挂了,其他节点没有提交,这条数据如何处理?
  raft论文是选择放弃这条消息,也有直接当做已经提交数据,还有通过查询是否得到半数以上确认决定是否提交. 这里我采用的方式,是让现在的leader把它当做一条新消息,等待半数以上确认然后提交.

recycle

1. 标记.
  缓存的回收是先标记的,达到一定数量然后再回收,标记的过程,不需要任何线程同步
1. 回收.
  这个步骤是唯一跟主线程需要做线程同步的地方,通过重建文件的方法,将写操作,在新旧文件里面都操作一次,读请求依然,请求到原来的文件里面. 在创建文件完成后,关闭服务器的读写请求,然后做资源的切换,切换完成后开启服务读写,服务器的读写功能关闭的时间很短, 通过这种方式,使得主线程在垃圾回收期间,对外提供服务基本无影响,主线程没有用到任何锁,性能很高.
```
//重建cache文件
cacheFileGroup.rebulid();

//关闭读请求
canRead.set(false);
//通过sleep 使得正在执行的读请求,能够正常执行完成
try {
    Thread.sleep(100);
} catch (InterruptedException e) {
    logger.warn(e.toString());
}

//资源切换
cacheFileGroup.setRebulidEffective();

//开启服务的读功能
canRead.set(true);
```

性能测试(只是跟redis对比测试)

该程序是在本机上跑的五个实例的集群,redis 单机的.
对于100w 次的请求没有任何请求异常
每秒能处理读请求 9.0w redis 9.5w
每秒能处理写请求 7.1w redis 9.3w
每秒能处理删除请求 8.3w redis 8.5w
一致性hash的数据倾斜问题,在虚拟节点开到200个的时候,即hash环上有1000个节点的时候,
对于100w 次的请求每个节点处理的数据都是 20w +/- 50 基本没有数据倾斜问题
即使对收到的消息直接返回,不做任何处理依然没有redis快,语言本身的性能差异摆在哪里的.

总结(遇到的坑)

lock.lock() 一定要在finally里面unlock 释放锁，状态转换的时候可能会中断该线程，导致锁没有释放最后其他线程无限等待状态
lock 里面不要放io这种耗时操作，io 阻塞后的线程切换并不会释放锁，切换别的线程拿不到锁，也是白搞
本来是用map维护socket连接的，最后自己粗心了，创建socket之后没有put进去,导致监听该socket连接的server 创建过多连接，导致线程池线程耗完，无法处理后续连接.(后面使用nio,和netty做通信,没有再为每个连接创建一个线程了)
考虑所有的情况，不要在编码的时候合并流程（即使该流程是不会发生的）,可以在编码完成后再合并

liubenwei/QCache

Raft Based Distributed Cache

支持的功能

技术点

处理客户端请求

Quick Start

缓存的存储(下面性能测试,测的时候是放在内存中的数据)

raft

recycle

性能测试(只是跟redis对比测试)

总结(遇到的坑)