luohaha/mypaxos

My multi-paxos service implement :-)

MyPaxos

My multi-paxos service implement :-)

说明

这是对multi-paxos协议服务的实现，并提供了给了使用者可以拓展的简单接口，以及简单的客户端。本实现有如下特性：

• 实现了multi-paxos中连续同一leader提交时，优化协议流程，将prepare和accept流程，优化到只有accept流程。
• 实现了节点崩溃恢复的机制。
• 提供了简单的易用的拓展接口给使用者，使用者可以基于此实现基于paxos服务的系统。
• 提供了分组功能，单个节点上可以设置多个虚拟分组，各个分组之间逻辑独立。

paxos协议的简单说明

Paxos算法解决的问题是在一个可能发生上述异常的分布式系统中如何就某个值达成一致，保证不论发生以上任何异常，都不会破坏决议的一致性。一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点都执行相同的操作序列，那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。

paxos协议中有三种角色：

• proposer : 提案的发起者
• accepter : 提案的接受者
• learner : 提案的学习者

paxos协议保证在每一轮的提案中，只要某一个提案被大于半数的accepter接受，本轮的提案也就生效了，不会再被修改和破坏。具体的算法说明可以看维基百科。

使用

使用MyPaxos协议服务，需要下面几步：

• 实现提交成功时需要执行的回调函数PaxosCallback
• 在各个节点上修改配置文件，启动paxos服务器
• 启动客户端，执行提交请求

我在这里使用MyPaxos来实现一个分布式的简单kv存储。

• 配置文件信息

{
    "nodes" : [{
        // 节点1，服务器端口为33333
        "id" : 1,
        "host" : "localhost",
        "port" : 33333
    },
    {
        "id" : 2,
        "host" : "localhost",
        "port" : 33334
    },
    {
        "id" : 3,
        "host" : "localhost",
        "port" : 33335
    }],
    "myid" : 1,    //本节点的id
    "timeout" : 1000, //通信超时
    "learningInterval" : 1000, // learner的学习时间间隔
    "dataDir" : "./dataDir/", // 数据持久化的位置，用于崩溃恢复
    "enableDataPersistence" : false // 是否开启数据持久化功能
}

• 提交成功后的回调函数

public class KvCallback implements PaxosCallback {
	/**
	 * 使用map来保存key与value映射
	 */
	private Map<String, String> kv = new HashMap<>();
	private Gson gson = new Gson();

	@Override
	public void callback(String msg) {
		/**
		 * 一共提供了三种动作： get : 获取 put : 添加 delete : 删除
		 */
		MsgBean bean = gson.fromJson(msg, MsgBean.class);
		switch (bean.getType()) {
		case "get":
			System.out.println(kv.get(bean.getKey()));
			break;
		case "put":
			kv.put(bean.getKey(), bean.getValue());
			System.out.println("ok");
			break;
		case "delete":
			kv.remove(bean.getKey());
			System.out.println("ok");
			break;
		default:
			break;
		}
	}

}

• 消息格式

public class MsgBean {
	
	private String type;
	private String key;
	private String value;
	public MsgBean(String type, String key, String value) {
		super();
		this.type = type;
		this.key = key;
		this.value = value;
	}
	public String getType() {
		return type;
	}
	public void setType(String type) {
		this.type = type;
	}
	public String getKey() {
		return key;
	}
	public void setKey(String key) {
		this.key = key;
	}
	public String getValue() {
		return value;
	}
	public void setValue(String value) {
		this.value = value;
	}

}

• 启动服务器

public class ServerTest {
	public static void main(String[] args) {
		MyPaxos server = new MyPaxos("./conf/conf.json");
		// 设置分组group1
		server.setGroupId(1, new KvCallback());
		// 设置分组group2
		server.setGroupId(2, new KvCallback());
		try {
			server.start();
		} catch (IOException | InterruptedException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
}

• 启动客户端，并发送请求

public class ClientTest {
	public static void main(String[] args) {
		MyPaxosClient client = new MyPaxosClient("localhost", 33333);
		try {
		    // 发往group1
			client.submit(new Gson().toJson(new MsgBean("put", "name", "Mike")), 1);
			// 发往group2
			client.submit(new Gson().toJson(new MsgBean("put", "name", "Neo")), 2);
			// 发往group1
			client.submit(new Gson().toJson(new MsgBean("get", "name", "")), 1);
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
}

• 结果

节点1

paxos server-1 start...
ok
ok
Mike

节点2

paxos server-2 start...
ok
ok
Mike

节点3

paxos server-3 start...
ok
ok
Mike

参考文献和资料

• Lamport, Leslie. "The part-time parliament." ACM Transactions on Computer Systems (TOCS) 16.2 (1998): 133-169.
• Lamport, Leslie. "Paxos made simple." ACM Sigact News 32.4 (2001): 18-25.
• Primi, Marco. Paxos made code. Diss. University of Lugano, 2009.
• Chandra, Tushar D., Robert Griesemer, and Joshua Redstone. "Paxos made live: an engineering perspective." Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing. ACM, 2007.
• 微信自研生产级paxos类库PhxPaxos实现原理介绍
• Paxos理论介绍(1): 朴素Paxos算法理论推导与证明
• Paxos理论介绍(2): Multi-Paxos与Leader

mypaxos's Issues

请问一下分组group在这里起到了什么作用？

在Paxos里面好像没看到相关的描述

如何验证算法的正确性？

编写测试用例

编写测试用例，用于正确性验证

Image Lost

README中图片无法看了

无法再本地复现测试用例

路径非绝对路径,还有第一次LearnRequest的Value为NULL 不知道为什么？？

MyPaxos 好像不是Multi-Paxos协议的实现？

是不是优化了部分，没看到是它的实现呀，可能是我理解有误。

learner 在学习过程当中，有个问题。

learner 在学习过程当中，

// 当learner学习成功时，让accepter也去同步这个状态
this.accepter.getAcceptedValue().put(instance, k);

是否都要赋值，或许自己accepter 已经接受了值，这样不就是覆盖，类似于把值重新覆盖了呀。

完成动态成员变更

在mypaxos定义特殊提案，用于变更成员。当需要变更成员时，可触发propose。

GroupId

请问GroupId是用来干嘛的啊

缺少选举流程

Hi，
按目前的流程，客户端只能连接同一个机器（Proposer），如果连接另一个proposer,则instanceId会乱，是否觉得需要添加leader选举流程？

开始测试时，资源占用很大。

开启server 1 server 2 server 3 和client时，cpu占用100%

multi-paxos 优化 有逻辑错误

A B C三个节点，一开始通过A节点来提交，中间没有竞争发生，最终A提交的值被确定并且在A的proposer中的isLastSumbitSucc设置成true，紧接着，A发生分区（没有crash，只是网络波动），分区的这段时间内，通过B来提交，由于多数派存活，B提交的值是可以被确定的，B的值被确定后，A从分区中恢复过来，并且还来不及向其他节点学习最新的B提交的值，此时A又有新的值要提交了，由于刚才设置了isLastSumbitSucc，所以prepare阶段被跳过，接着发生了悲剧A提交的值被确定了（跟B提交的是同一个instanceID）。

报错

instanceRecover()方法中：
this.instanceState.putAll(gson.fromJson(data, new TypeToken<Map<Integer, Instance>>() {
}.getType()));
this.instanceState.forEach((key, value) -> {
if (value.value != null)
this.acceptedValue.put(key, value.value);
});
怎么导入到Idea中一直报错.