Raft协议的解读已经有很多，整体最主要的协议其实用论文中的两幅图就能大致表述了。最后再加上一个Snapshot的图解析基本就全。相对与Paxos而言，我个人认为Raft从实现协议的角度来说反而比Paxos要复杂。主要就是在于index的处理上。这此使用Go语言实现了一个Raft协议并支持snapshot。并且使用Raft协议实现了一个分布式的kv存储。
Raft的实现
Raft的成员变量
...
read more
28 Sep 2019 by John Brown
关于ABtest哈希算法正交性讨论
关于ABtest哈希算法正交性讨论
Hash正交性
正交性定义：首先任意一个hash_type都可以均匀的将流量均匀分成100份。使用hash_type1 进行哈希后得到\(x_i,i\in[0,100)\),即每份百分之1的流量，再使用hash_type2进行哈希后得到\(y_i,i\in[0,100)\)。如果某个key在被hash_type1进行hash后得到的流量与被hash_type2得到的流量是无关的，那么就说明hash_type1与hash_type2是两中hash方式是正交的。
例如一个1000000用户的流量，经过hash_type1与hash_type2进行hash，理想情况下 中具有相同每份y中的相同x流量的个数也是同样多的，即100个。如果使用数组命中计数的话，list[\(x*100 + y\)],...
read more
29 Jan 2019 by John Brown
ThreadPool, Coroutine, Promise与Future
ThreadPool, Coroutine, Promise与Future
ThreadPool
线程池，顾名思义，就是放着很多线程的大“池子”。主要用作并发量大，但每个任务需要处理的时间不是很长。比如接受或者发送网络请求的任务。之所以使用线程池，原因就是在线程的传创建和销毁在高并发先开销十分大，如果将线程先创建好放入“池子”中待命，随用随取。降低不必要的开销十分划算。
实现也非常的简单，创建队列，使用生产消费者模型（向队列中增加任务即生产者，将任务执行完成即消费者）。主要实现逻辑如下：
20 Aug 2018 by John Brown
分布式系统哈希分区处理问题
分布式系统哈希分区处理问题
分布式系统的存在，其重要的一个原因就是为了能够将负载很好的均摊到各个节点上，以数量优势提高性能，即分布式系统的可扩展性。大数据可以分布在多个主机的磁盘上，查询也可以有多个主机分别进行处理。分区的实现方式有很多种，目标基本一致，更好的将负载和查询均匀的分布在各个节点。如果分区不均匀(skew)，那么会使此分区甚至整个系统的效率下降。这篇文章主要讨论在高负载下如何避免热点(hot spot)数据。
本文主要针对我工作中所接触的RTRec流式系统中所使用的分布式系统hash分区做讨论，并从架构的美学(aesthetics)提出一个相对简约分区处理系统。现有流式集群使用一致性哈希，主要有两个原因：
- 保证其负载均衡。这里指的是数据层面的负载均衡，因为接入层已经进行了负载均衡。
- 保证处理与查询的key落在同一台机器(节点)上。流式系统一个重要的工作就是收集客户端产生的上报数据做处理。如果要对某一个用户的行为进行上报，最高效的方法就是将这个用户的行为进行收集缓存，统计，入库。这些要求就要保证处理同一个用户的机器是相同的。同理，对APP信息的曝光，下载记录也需要同一key落在同一台机器上。
系统由三部分组成，zookeeper，WatchDog，节点集群。拓扑图如图[1]所示。节点之间的通讯通过一个全局的路由表作为路由，节点集群中的每个节点与zk相连。zk有两个作用，第一个作用是保持路由表的一致性，第二个作用监控集群中的每一个节点的状态。WatchDog的作用是针对现有节点集群做一致性哈希策略，即生成全局的路由表，将路由表放在zk上进行保管，一旦路由表有变化，通知集群中的各个节点去zk上更新最新的路由表。
...read more
25 Jul 2018 by John Brown
6.824:Lab6-7 Replicated State Machine
Paxos
Introduction
在实验6-7中，将使用RSM（replicated state machine）的方法复写锁服务，在这个方法中，有一个节点为master，master接收来自client节点的请求并在所有的节点以相同的方式在所有的副本下执行。
当master节点失败，任何一个副本都会接管master的工作，因为这些副本都与那个失败的节点有着相同的状态。其中一个比较有挑战性任务时确保集群中的每一个节点所接受的信息是一致的（即哪些是副本，谁是master，哪些副本是keepalive的），即使存在网络分裂（network partition）或者是乱序的情况，数据仍然要保持一致。这里我们使用Paxos协议来实现这一策略。
在此次实验中，将要实现Paxos并使用达成集群成员的改变（view...
read more
22 May 2018 by John Brown
6.824:Lab4-5 Cache
Lab4-5 Caching Locks and Extents
Introduction(Lab4)
在这两个实验中，主要建立了锁和存储服务的缓存，以减少服务器负载并提高客户端的性能。
例如在Lab3中的测试，在一个YFS文件夹中建立100个文件，需要像这个文件夹（directory）的锁请求100次。这次的实验就是修改锁服务，让锁客户端只需要发送一次acquire...
read more
22 May 2018 by John Brown