levy5307/blog

https://levy5307.github.io/blog/

blog's Issues

Google Refptr

https://levy5307.github.io/blog/google-refptr/

最近工作中发现了一个关于智能指针的=运算符重载的经典代码实现，记录一下：

scoped_refptr& operator=(std::nullptr_t) {
reset();
return *this;
}
// Sets managed object to null and releases reference to the previous managed
// object, if it existed.
void reset() { scoped_refptr().swap(*this); }

scoped_refptr& operator=(T* p) { return *this = scoped_refptr(p); }
// Unified assignment operator.
scoped_refptr& operator=(scoped_refptr r) noexcept {
swap(r);
return *this;
}
void swap(scoped_refptr& r) noexcept { std::swap(ptr_, r.ptr_); }

可以只看operator=(std::nullptr_t), 由于将this赋值给null，所以this需要释放。此时operator=这个函数不好实现，因为如果在函数退出前释放的话，释放后的任何操作都相当于操作了已释放对象(可参考附录1我在pr中的描述)。

这里的google的实现是：将this和一个临时变量进行swap, 该临时对象的ptr_为null，交换后临时对象的ptr_变成了this->ptr_，this->ptr_变成了null，这是前提。然后经典的来了，当reset函数退出时，

临时变量退出了其作用区域，会被释放，根据指针的特性，其对应的其ptr_指向的空间也会释放，由于此时临时对象的ptr_是this->ptr_，所以reset退出时，实际释放的是this->ptr_。

下面的几个函数原理是一样的，这里就不解释了

具体代码文件：https://chromium.googlesource.com/chromium/src/+/master/base/memory/scoped_refptr.h

附录1：XiaoMi/rdsn#361

Backup Request Client

https://levy5307.github.io/blog/backup-request-client/

Backup request function can optimize the long tail problem of read delay, suitable for users with low consistency requirements.

Investigation

There are two ways to implement backup request.

Hedged requests
A client first sends one request to the replica believed to be the most appropriate, but then falls back on sending a secondary request after the first request has been outstanding for more than the 95th-percentile(or 99th-percentline, etc) expected latency. The client cancels remaining outstanding requests once the first result is received. This approach limits the additional load to approximately 5%(1%) while substantially shortening the latency tail. This approach limits the additional load to approximately 5%(1%) while substantially shortening the latency tail.

This approach limits the benefits to only a small fraction of requests(the tail of the latency distribution).

Tied requests
the client send the request to two different servers, each tagged with the identity of the other server (“tied”). When a request begins execution, it sends a cancellation message to its counterpart. The corre- sponding request, if still enqueued in the other server, can be aborted imme- diately or deprioritized substantially.

There is another variation in which the request is sent to one server and forwarded to replicas only if the ini- tial server does not have it in its cache and uses cross-server cancellations.

This approach limits the benefits to not only the tail of the latency, but also median latency distribution. But it result in higher network load.

Rdsn Rpc

https://levy5307.github.io/blog/rdsn-rpc/

rpc_engine:
成员变量：
std::vector<std::vectorstd::unique_ptr> _client_nets; // <format, <CHANNEL, network*> format: network_header_format，目前只有NET_HDR_DSN; CHANNEL: 有RPC_CHANNEL_TCP和RPC_CHANNEL_UDP两个
std::unordered_map<int, std::vectorstd::unique_ptr> _server_nets; // <port, <CHANNEL, network*>>
不同的CHANNEL使用不同的network, 也就是udp和tcp有不同的网络连接

成员函数：
error_code start(const service_app_spec &aspec); 根据配置文件创建_client_nets和_server_nets network, 其中_server_nets包括asio_network_provider
void call(message_ex *request, const rpc_response_task_ptr &call); 发送请求，会根据request->server_address来决定是调用call_ip和call_group
void call_ip 根据format和CHANNEL从_client_nets中选取相应的network，然后使用network::send_message将消息发送出去
void reply(message_ex *response, error_code err = ERR_OK) 发送回复，根据port和CHANNEL从_server_nets选取相应的network，然后使用network::send_message将消息发送出去
void forward(message_ex *request, rpc_address address) 通过调用call_ip转发请求到address
void on_recv_request(network *net, message_ex *msg, int delay_ms) 接收到请求时的处理, 创建一个task，将其放入队列中。随后队列将该task取出，该task主要执行replication_service_app::on_intercepted_request函数，
根据是读或者写响应请求调用replica_stub::on_client_write或者replica_stub::on_client_read
note:
Q: 为什么reply接口从_server_nets中获取network？
A: 因为server的代表的是我们是网络提供方，这里客户端发来的请求，reply的时候当然需要通过server再发送回去

network: 一个虚类, 表示一个网络连接
成员变量：
int _message_buffer_block_size; buffer block大小
int _max_buffer_block_count_per_send; 单次发送的最大buffer block大小
rpc_engine *_engine; 指向rpc_engine的指针
成员函数：
void on_recv_request(message_ex *msg, int delay_ms); 接收信息的回调函数，将会直接调用rpc_engine::on_recv_request
void on_recv_reply(message_ex *msg, int delay_ms); 回复信息的回调函数，将会直接调用rpc_engine::on_reply_request
virtual void send_message(message_ex *request) = 0; 发送信息，rpc_engine将会调用该函数
virtual void inject_drop_message(message_ex *msg, bool is_send) = 0; drop掉该msg
message_parser *new_message_parser(network_header_format hdr_format); 创建一个新的message parser，用于：1.接收到一个rpc request message时解析出blob信息。2.parse blob信息用于获取rpc_message

connection_oriented_network : public network 用于tcp连接
成员变量：
client_sessions _clients; to_address与rpc_session之间的map(rpc_address–rpc_session_ptr)
server_sessions _servers; from_address与rpc_session之间的map(rpc_address–rpc_session_ptr)
ip_connection_count _ip_conn_count; from_ip与connection_count之间的map(uint32_t–uint32_t)
uint64_t _cfg_conn_threshold_per_ip; 配置中指定的每个ip上最大的连接数
成员函数：
rpc_session_ptr get_server_session(::dsn::rpc_address ep); 根据rpc_address ep从_servers中获取到其对应的rpc_session_ptr
void on_server_session_accepted(rpc_session_ptr &s); 根据rpc_session_ptr &s获取from_address与rpc_session之间的映射，存入_servers中，_ip_conn_count中为相应的ip的连接count+1
void on_server_session_disconnected(rpc_session_ptr &s); 将rpc_session_ptr &s从_server中移除，并在_ip_conn_count为相应的ip的连接count减1
bool is_conn_threshold_exceeded(::dsn::rpc_address ep); 从_ip_conn_count获取ep的ip的连接数量, 判断其连接数量是否超过配置的上限。
bool on_client_session_connected(rpc_session_ptr &s); 根据rpc_session_ptr &s获取to_address与rpc_session之间的映射，存入_clients中
void on_client_session_disconnected(rpc_session_ptr &s); 将rpc_session_ptr &s从_clients中移除。
virtual void send_message(message_ex *request) override;
1.根据to_address从_clients中获取rpc_session_ptr，如果没有，则创建一个新的
2.如果是新创建的，则调用其asio_rpc_session::connect用于建立网络连接, 这里使用boost的async_connect，传入一个callback，当connect成功后，先调用send_message把消息全部发送出去，然后调用read_next循环去读
3.不管是不是新创建的session，都rpc_session::send_message。如果不是新的session则直接把消息发送出去; 如果是新创建的，由于还没有连接好，则把消息挂入发送队列中，暂时不发送
void inject_drop_message(message_ex *msg, bool is_send); 从message_ex *msg中获取rpc_session_ptr, 如果为空，则根据to_address从_clients中去查找, 最后通过rpc_session::close关闭rpc session

asio_network_provider : public connection_oriented_network 监听端口，当有连接到来时创建连接session，并使用session读连接中的数据
virtual error_code start(rpc_channel channel, int port, bool client_only)
1.listen端口
2.调用do_accept，该函数调boost的async_accept用于异步accpet连接，每当有连接到来时都执行其指定的callback:
1.该callback首先为新的连接创建一个asio_rpc_session，
2.调用on_server_session_accepted向_servers中添加from_address与rpc_session之间的映射
3.并调用asio_rpc_session的start_read_next接口，用于读取连接的数据
rpc_session_ptr create_client_session(::dsn::rpc_address server_addr) 根据地址server_addr创建一个asio_rpc_session
note:
有一个natvierun的tool_app，在系统启动时，service_api_c.cpp的run()函数369行，会获取nativerun并调用其install函数，用于初始化spec.network_default_server_cfs,
后面传递给service_app_spec::init函数，初始化spec.network_client_config和spec.network_server_config, 随后在rpc_engine::start中具体创建asio_network_provider

rpc_session: 虚基类, 表示一个rpc session
成员函数：
bool unlink_message_for_send();
1.auto n = _messages.next(); 从_messages中获取下一个message_ex中的dlink* (在_messages中各个message_ex通过dlink*连接)
2.auto lmsg = CONTAINING_RECORD(n, message_ex, dl); 根据dlink *获取包含他的message_ex指针
3.将lmsg放入到_sending_buffers中，准备发送
4.如果_messages中还存在消息，则跳到2继续
void send_message(message_ex *msg);
1.msg->io_session = this 设置msg的rpc session
2.msg->dl.insert_before(&_messages) 将msg插入到_messages中, 并将_message_count+1
3.如果处于连接状态(SS_CONNECTED == _connect_state)、没有其他进程在发送(!is_sending_next)并且发送队列_sending_msgs中有消息待发送,
则使用unlink_message_for_send从_messages摘下消息放入发送缓冲区_sending_buffers和_sending_msgs中，准备发送消息;
否则直接退出, 此时只是将消息放入了_messges中并没有发送，等连接建立时，会将其发送出去
4.调用send函数进行发送(send是个虚函数，各子类有不同的定义, 发送成功后会调用on_send_completed)
void on_send_completed(uint64_t signature) 发送消息，直到发送消息列表都发送完
1.清空发送缓冲区sending_buffers
2.如果没有其他进程在发送(!is_sending_next), 则unlink_message_for_send从_messages摘下消息放入发送缓冲区_sending_buffers和_sending_msgs中，并调用send函数继续发送。
void on_failure(bool is_write)
1.on_disconnected 设置_connect_state = SS_DISCONNECTED
2.根据是否是client来判断调用_net.on_client_session_disconnected或者_net.on_server_session_disconnected。这两个函数用于分别清空connection_oriented_network中的_clients或者_servers等成员数据
3.clear_send_queue(bool resend_msgs) 对于_sending_buffers和_messages中的剩余的消息，如果resend_msgs=true, 则将其重新发送;
如果resend_mesgs=false,并且is_request(是个请求)、!is_forwarded(不是转发请求)，则通过接受一个空emptry的方式模拟failure（因为如果不resend, callback将会等到超时才会invoke, 太慢了）
virtual void do_read(int read_next) = 0
bool on_recv_message(message_ex *msg, int delay_ms)
note:
Q: 为什么发送缓冲区有_sending_buffers和_sending_msgs两个？
A: _sending_buffers内的buffer是void *buf保存，可以直接用于发送; sending_msgs内保存的是message_ex, 可以用于计算发送的messge count

asio_rpc_session
void do_read(int read_next)
1.调用boost接口异步读,异步读传递一个callback, 该callback处理读取完之后的逻辑。
2.如果读取成功, on_message_read并解析
…
n.调用start_read_next继续读
void connect()
1.调用boost接口去异步创建连接, 创建完之后调用其callback
2.如果创建成功:
1.调set_connected，执行connection_oriented_network::on_client_session_connected，向_clients中添加to_address与rpc_session之间的映射
2.rpc_session::on_send_complete 处理发送消息，直到所有消息发送完毕
3.start_read_next 读取消息

rpc_client_matcher: 用于匹配rpc request和rpc response、以及处理超时。
成员变量：
typedef std::unordered_map<uint64_t, match_entry> rpc_requests;
rpc_requests _requests[MATCHER_BUCKET_NR]; key-request id, value-match_entry（callback、timeout task、超时时间戳）
成员函数：
void on_call(message_ex *request, const rpc_response_task_ptr &call): 当执行rpc call时，注册request id、callback和超时timeout task
bool on_recv_reply(network *net, uint64_t key, message_ex *reply, int delay_ms), 当收到rpc response时，调用该函数用于触发callback调用(通过将callback task enqueue, enqueue的task会被异步调用执行)

note:
主动创建连接：connection_oriented_network::send_message发送消息时，如果没有session，则创建一个新的，放入_clients中, 连接创建后，先调用send_message将消息发送完，然后调用rpc_session::start_read_next去循环读
监听连接到来：asio_network_provider::start，在系统启动时调用该函数，调用async_accept接收连接session，放入_servers中, 连接创建后直接调用rpc_session::start_read_next去循环读

                          上层逻辑处理

                             |  ^
                       call  |  |  
                             V  |
                          rpc_engine
                             |  ^
      network::send_message  |  | rpc_engine::on_recv_request   
                             V  |  发送出去 -->                       network                             <-- 从网络读取
                             |  ^
  rpc_session::send_message  |  |  network::on_recv_request
                             V  |  rpc_session::do_read
                          rpc_session

Raft

https://levy5307.github.io/blog/raft/

一、Raft算法概述

不同于Paxos算法直接从分布式一致性问题出发推导出来，Raft算法则是从多副本状态机的角度提出，用于管理多副本状态机的日志复制。Raft实现了和Paxos相同的功能，它将一致性分解为多个子问题：Leader选举（Leader election）、日志同步（Log replication）、安全性（Safety）、日志压缩（Log compaction）、成员变更（Membership change）等。同时，Raft算法使用了更强的假设来减少了需要考虑的状态，使之变的易于理解和实现。

Raft将系统中的角色分为领导者（Leader）、跟从者（Follower）和候选人（Candidate）：

Leader：接受客户端请求，并向Follower同步请求日志，当日志同步到大多数节点上后告诉Follower提交日志。

Follower：接受并持久化Leader同步的日志，在Leader告之日志可以提交之后，提交日志。

Candidate：Leader选举过程中的临时角色。

Raft算法角色

Raft要求系统在任意时刻最多只有一个Leader，正常工作期间只有Leader和Followers。

Raft算法角色状态转换如下：

Raft算法角色状态转换

Follower只响应其他服务器的请求。如果Follower超时没有收到Leader的消息，它会成为一个Candidate并且开始一次Leader选举。收到大多数服务器投票的Candidate会成为新的Leader。Leader在宕机之前会一直保持Leader的状态。

Raft算法将时间分为一个个的任期（term），每一个term的开始都是Leader选举。在成功选举Leader之后，Leader会在整个term内管理整个集群。如果Leader选举失败，该term就会因为没有Leader而结束。

二、Leader选举

Raft 使用心跳（heartbeat）触发Leader选举。当服务器启动时，初始化为Follower。Leader向所有Followers周期性发送heartbeat。如果Follower在选举超时时间内没有收到Leader的heartbeat，就会等待一段随机的时间后发起一次Leader选举。

Follower将其当前term加一然后转换为Candidate。它首先给自己投票并且给集群中的其他服务器发送 RequestVote RPC （RPC细节参见八、Raft算法总结）。结果有以下三种情况：

赢得了多数的选票，成功选举为Leader；

收到了Leader的消息，表示有其它服务器已经抢先当选了Leader；

没有服务器赢得多数的选票，Leader选举失败，等待选举时间超时后发起下一次选举。

Leader选举过程

选举出Leader后，Leader通过定期向所有Followers发送心跳信息维持其**。若Follower一段时间未收到Leader的心跳则认为Leader可能已经挂了，再次发起Leader选举过程。

Raft保证选举出的Leader上一定具有最新的已提交的日志，这一点将在四、安全性中说明。

三、日志同步

Leader选出后，就开始接收客户端的请求。Leader把请求作为日志条目（Log entries）加入到它的日志中，然后并行的向其他服务器发起 AppendEntries RPC （RPC细节参见八、Raft算法总结）复制日志条目。当这条日志被复制到大多数服务器上，Leader将这条日志应用到它的状态机并向客户端返回执行结果。

Raft日志同步过程

某些Followers可能没有成功的复制日志，Leader会无限的重试 AppendEntries RPC直到所有的Followers最终存储了所有的日志条目。

日志由有序编号（log index）的日志条目组成。每个日志条目包含它被创建时的任期号（term），和用于状态机执行的命令。如果一个日志条目被复制到大多数服务器上，就被认为可以提交（commit）了。

Raft日志

Raft日志同步保证如下两点：

如果不同日志中的两个条目有着相同的索引和任期号，则它们所存储的命令是相同的。

如果不同日志中的两个条目有着相同的索引和任期号，则它们之前的所有条目都是完全一样的。

第一条特性源于Leader在一个term内在给定的一个log index最多创建一条日志条目，同时该条目在日志中的位置也从来不会改变。

第二条特性源于 AppendEntries 的一个简单的一致性检查。当发送一个 AppendEntries RPC 时，Leader会把新日志条目紧接着之前的条目的log index和term都包含在里面。如果Follower没有在它的日志中找到log index和term都相同的日志，它就会拒绝新的日志条目。

一般情况下，Leader和Followers的日志保持一致，因此 AppendEntries 一致性检查通常不会失败。然而，Leader崩溃可能会导致日志不一致：旧的Leader可能没有完全复制完日志中的所有条目。

Leader和Followers上日志不一致

上图阐述了一些Followers可能和新的Leader日志不同的情况。一个Follower可能会丢失掉Leader上的一些条目，也有可能包含一些Leader没有的条目，也有可能两者都会发生。丢失的或者多出来的条目可能会持续多个任期。

Leader通过强制Followers复制它的日志来处理日志的不一致，Followers上的不一致的日志会被Leader的日志覆盖。

Leader为了使Followers的日志同自己的一致，Leader需要找到Followers同它的日志一致的地方，然后覆盖Followers在该位置之后的条目。

Leader会从后往前试，每次AppendEntries失败后尝试前一个日志条目，直到成功找到每个Follower的日志一致位点，然后向后逐条覆盖Followers在该位置之后的条目。

四、安全性

Raft增加了如下两条限制以保证安全性：

拥有最新的已提交的log entry的Follower才有资格成为Leader。

这个保证是在RequestVote RPC中做的，Candidate在发送RequestVote RPC时，要带上自己的最后一条日志的term和log index，其他节点收到消息时，如果发现自己的日志比请求中携带的更新，则拒绝投票。日志比较的原则是，如果本地的最后一条log entry的term更大，则term大的更新，如果term一样大，则log index更大的更新。

Leader只能推进commit index来提交当前term的已经复制到大多数服务器上的日志，旧term日志的提交要等到提交当前term的日志来间接提交（log index 小于 commit index的日志被间接提交）。

之所以要这样，是因为可能会出现已提交的日志又被覆盖的情况：

已提交的日志被覆盖

在阶段a，term为2，S1是Leader，且S1写入日志（term, index）为(2, 2)，并且日志被同步写入了S2；

在阶段b，S1离线，触发一次新的选主，此时S5被选为新的Leader，此时系统term为3，且写入了日志（term, index）为（3， 2）;

S5尚未将日志推送到Followers就离线了，进而触发了一次新的选主，而之前离线的S1经过重新上线后被选中变成Leader，此时系统term为4，此时S1会将自己的日志同步到Followers，按照上图就是将日志（2， 2）同步到了S3，而此时由于该日志已经被同步到了多数节点（S1, S2, S3），因此，此时日志（2，2）可以被提交了。；

在阶段d，S1又下线了，触发一次选主，而S5有可能被选为新的Leader（这是因为S5可以满足作为主的一切条件：1. term = 5 > 4，2. 最新的日志为（3，2），比大多数节点（如S2/S3/S4的日志都新），然后S5会将自己的日志更新到Followers，于是S2、S3中已经被提交的日志（2，2）被截断了。

增加上述限制后，即使日志（2，2）已经被大多数节点（S1、S2、S3）确认了，但是它不能被提交，因为它是来自之前term（2）的日志，直到S1在当前term（4）产生的日志（4， 4）被大多数Followers确认，S1方可提交日志（4，4）这条日志，当然，根据Raft定义，（4，4）之前的所有日志也会被提交。此时即使S1再下线，重新选主时S5不可能成为Leader，因为它没有包含大多数节点已经拥有的日志（4，4）。

五、日志压缩

在实际的系统中，不能让日志无限增长，否则系统重启时需要花很长的时间进行回放，从而影响可用性。Raft采用对整个系统进行snapshot来解决，snapshot之前的日志都可以丢弃。

每个副本独立的对自己的系统状态进行snapshot，并且只能对已经提交的日志记录进行snapshot。

Snapshot中包含以下内容：

日志元数据。最后一条已提交的 log entry的 log index和term。这两个值在snapshot之后的第一条log entry的AppendEntries RPC的完整性检查的时候会被用上。

系统当前状态。

当Leader要发给某个日志落后太多的Follower的log entry被丢弃，Leader会将snapshot发给Follower。或者当新加进一台机器时，也会发送snapshot给它。发送snapshot使用InstalledSnapshot RPC（RPC细节参见八、Raft算法总结）。

做snapshot既不要做的太频繁，否则消耗磁盘带宽， 也不要做的太不频繁，否则一旦节点重启需要回放大量日志，影响可用性。推荐当日志达到某个固定的大小做一次snapshot。

做一次snapshot可能耗时过长，会影响正常日志同步。可以通过使用copy-on-write技术避免snapshot过程影响正常日志同步。

六、成员变更

成员变更是在集群运行过程中副本发生变化，如增加/减少副本数、节点替换等。

成员变更也是一个分布式一致性问题，既所有服务器对新成员达成一致。但是成员变更又有其特殊性，因为在成员变更的一致性达成的过程中，参与投票的进程会发生变化。

如果将成员变更当成一般的一致性问题，直接向Leader发送成员变更请求，Leader复制成员变更日志，达成多数派之后提交，各服务器提交成员变更日志后从旧成员配置（Cold）切换到新成员配置（Cnew）。

因为各个服务器提交成员变更日志的时刻可能不同，造成各个服务器从旧成员配置（Cold）切换到新成员配置（Cnew）的时刻不同。

成员变更不能影响服务的可用性，但是成员变更过程的某一时刻，可能出现在Cold和Cnew中同时存在两个不相交的多数派，进而可能选出两个Leader，形成不同的决议，破坏安全性。

成员变更的某一时刻Cold和Cnew中同时存在两个不相交的多数派

由于成员变更的这一特殊性，成员变更不能当成一般的一致性问题去解决。

为了解决这一问题，Raft提出了两阶段的成员变更方法。集群先从旧成员配置Cold切换到一个过渡成员配置，称为共同一致（joint consensus），共同一致是旧成员配置Cold和新成员配置Cnew的组合Cold U Cnew，一旦共同一致Cold U Cnew被提交，系统再切换到新成员配置Cnew。

Raft两阶段成员变更

Raft两阶段成员变更过程如下：

Leader收到成员变更请求从Cold切成Cnew；

Leader在本地生成一个新的log entry，其内容是Cold∪Cnew，代表当前时刻新旧成员配置共存，写入本地日志，同时将该log entry复制至Cold∪Cnew中的所有副本。在此之后新的日志同步需要保证得到Cold和Cnew两个多数派的确认；

Follower收到Cold∪Cnew的log entry后更新本地日志，并且此时就以该配置作为自己的成员配置；

如果Cold和Cnew中的两个多数派确认了Cold U Cnew这条日志，Leader就提交这条log entry；

接下来Leader生成一条新的log entry，其内容是新成员配置Cnew，同样将该log entry写入本地日志，同时复制到Follower上；

Follower收到新成员配置Cnew后，将其写入日志，并且从此刻起，就以该配置作为自己的成员配置，并且如果发现自己不在Cnew这个成员配置中会自动退出；

Leader收到Cnew的多数派确认后，表示成员变更成功，后续的日志只要得到Cnew多数派确认即可。Leader给客户端回复成员变更执行成功。

异常分析：

如果Leader的Cold U Cnew尚未推送到Follower，Leader就挂了，此后选出的新Leader并不包含这条日志，此时新Leader依然使用Cold作为自己的成员配置。

如果Leader的Cold U Cnew推送到大部分的Follower后就挂了，此后选出的新Leader可能是Cold也可能是Cnew中的某个Follower。

如果Leader在推送Cnew配置的过程中挂了，那么同样，新选出来的Leader可能是Cold也可能是Cnew中的某一个，此后客户端继续执行一次改变配置的命令即可。

如果大多数的Follower确认了Cnew这个消息后，那么接下来即使Leader挂了，新选出来的Leader肯定位于Cnew中。

两阶段成员变更比较通用且容易理解，但是实现比较复杂，同时两阶段的变更协议也会在一定程度上影响变更过程中的服务可用性，因此我们期望增强成员变更的限制，以简化操作流程。

两阶段成员变更，之所以分为两个阶段，是因为对Cold与Cnew的关系没有做任何假设，为了避免Cold和Cnew各自形成不相交的多数派选出两个Leader，才引入了两阶段方案。

如果增强成员变更的限制，假设Cold与Cnew任意的多数派交集不为空，这两个成员配置就无法各自形成多数派，那么成员变更方案就可能简化为一阶段。

那么如何限制Cold与Cnew，使之任意的多数派交集不为空呢？方法就是每次成员变更只允许增加或删除一个成员。

可从数学上严格证明，只要每次只允许增加或删除一个成员，Cold与Cnew不可能形成两个不相交的多数派。

一阶段成员变更：

成员变更限制每次只能增加或删除一个成员（如果要变更多个成员，连续变更多次）。

成员变更由Leader发起，Cnew得到多数派确认后，返回客户端成员变更成功。

一次成员变更成功前不允许开始下一次成员变更，因此新任Leader在开始提供服务前要将自己本地保存的最新成员配置重新投票形成多数派确认。

Leader只要开始同步新成员配置，即可开始使用新的成员配置进行日志同步

转载地址：https://zhuanlan.zhihu.com/p/32052223?utm_source=wechat_session&utm_medium=social&utm_oi=658624251268173824

另附 raft论文翻译：https://github.com/levy5307/raft-zh_cn

raft

https://levy5307.github.io/blog/consensus-protocol-summary/

链式复制(Chain Replication)

写入只能将请求发送至head节点，写入流程：

读取则只能将请求发送到tail节点。tail节点一定保存的是未提交的最新值，所以从tail读取可以保证强一致性。
优点：

简单、容易实现
读操作和写操作分配到不同的节点上，所以吞吐会更高
链式复制的每个节点（除了尾结点）都会产生写复制操作，而主从复制的写复制操作集中在主节点，这样就增加了主节点的负担
可用性强。要保证N个节点挂掉集群仍然可用，链式存储只要有N+1个节点就可以了，但是主从方式需要2N+1个节点

缺点： 写请求需要沿链流经所有的节点，延迟会比较高。相当于延迟换吞吐。

Ref: https://levy5307.github.io/blog/chain-replication/

CRCQ（Chain Replication with Apportioned Queries）

针对于CR的优化，读取操作可以发往任意的server、而非只能发往tail节点。为实现该功能，对每个key维护一个version和clean标记
写入则与CR相同，都是由head节点发起。写入流程：

读取则可以向任意server发送请求。当该server中的clean标记为dirty时，需要向tail查询当前提交的最新version，然后将该version数据返回给客户端。

优点：

除了具备CR的优点外，还可以将读请求分散到全部的server上，吞吐更高
缺点：
写请求需要流经所有的节点，延迟会比较高。
需要对每个key维护一个version和clean标记，更适合于内存型存储

Ref: https://levy5307.github.io/blog/object-storage-on-CRAQ/

Hermes

任意节点都可以写入和读取，并且读取操作都是本地读。
写入可以任意节点发起，发起的节点则叫做coordinator。写入流程：

读取时，如果该key在当前node上的状态是val，则直接返回。如果是inv，则block住一直等到其状态变为val。
优点： 任意节点都可以发起读取和写入，性能比较高，对负载均衡也更友好。
缺点： 类似于CRCQ，每个key都需要维护一些数据（比如key的状态），更适合内存型数据库

Ref: https://levy5307.github.io/blog/Hermes/

PacificA

该协议由Manager指定一个Replication Group中的primary，写入和读取请求都发往Primary，以此来保证强一致性。
对于写入，要求必须所有副本都写入成功才能提交。对于读取，则只需要从Primary本地读取就可以了。

优点：可用性高。对于拥有2N+1个节点的集群，PacificA可以容忍2N个节点挂掉（对于挂掉的节点，manager会及时将其移除，不会影响写入可用性）
缺点：容易抖动。由于写入需要所有节点都成功写入，所以只要有一个节点写入较慢，就会影响写入的延迟。
Ref: https://levy5307.github.io/blog/PacificA/

Raft

同PacificA一样，读写都是发往Primary。与PacificA不同的是，其不用依赖额外的Manager制定primary，而是通过选举的方式选出primary。
另外，Raft要求所有写入只要有超过一半的副本写入成功就可以了。
所以相较于PacificA:

PacificA对延迟抖动更敏感。少数的慢节点基本不会影响Raft协议的写入，该节点可以写入完成后再同步追赶日志。
Raft可用性不如PacificA。对于拥有2N+1个节点的集群，PacificA可以容忍2N个节点挂掉。而Raft则只能容忍N个节点挂掉（其实可以通过增加副本数来一定弥补）

Ref: https://levy5307.github.io/blog/raft/

Atomic Memory Order

https://levy5307.github.io/blog/atomic-memory-order/

虽然是六种类型，但是理解了四种同步的情形基本就差不多了。

对于单线程来说，编译器会在不影响程序执行结果的前提下对原子语句顺序进行重排，同时有些弱序cpu(spark是弱序，但x86是强序)也会对指令执行顺序进行重排。但是这种重拍对于多线程来说可能就会造成问题。

Sequential consistency: 即对于所有的环境变量，代码在线程中运行的顺序与程序员看到的代码顺序一致。对于弱序cpu需要添加内存栅栏（mem fence）


Relaxed ordering: 不保证顺序，性能最高。有可能会由于编译器或者cpu的重排导致程序运行出问题。


Release – acquire: Release保证在其之前的(所有)语句一定会先与该Release语句执行, Acquire语句保证在其之后的（所有）语句一定会后语该语句执行。Release用于store，Acquire用于load。


Release – consume: 如果只想同步一个 x 的读写操作，结果把 release 之前的写操作都顺带同步了？如果想避免这个额外开销怎么办？用 release – consume。同步还是一样的同步，这回副作用弱了点：memory_order_cosume只保证原子操作发生在与其（memory_order_consume指定的）有关的原子操作之前，对于无关的操作则无法保证顺序。例如：

atomic<string*> ptr;
atomic data;

producer:

string *p = new string(

Object Storage On Craq

https://levy5307.github.io/blog/object-storage-on-CRAQ/

Strong Consistency

in our system provides the guarantee that all read and write operations to an object are executed in some sequential order, and that a read to an object always sees the latest written value.

Eventual Consistency

in our system implies that writes to an object are still applied in a sequential order on all nodes, but eventually-consistent reads to different nodes can return stale data for some period of inconsistency (i.e., before writes are applied on all nodes). Once all replicas receive the write, however, read operations will never return an older version than this latest committed write. In fact, a client will also see monotonic read consistency if it maintains a session with a particular node (although not across sessions with different nodes)

Chain Replication

写请求都发送到head结点，然后该写请求逐渐从头结点向后迁移，直到tail结点提交了写入时，则代表此次写入提交了。读请求都从tail结点读取。所以在tail结点可以保持所有操作的全局有序，并且读操作会获取到最新的写入数据。因此是强一致的。但是这样的代价是，该链表的scale-out能力被限制了。
不能从中间结点读取，这样会导致读取不同的结点获取不同的值，并且有可能查到一些陈旧的数据，所以只能满足了最终一致性，无法满足强一致性。

CR比传统的主从方式也有优点：
即读和写操作分配到不同的结点上，并且写请求的压力在各个结点均匀分布(primary-secondary的方式先写入primary，然后由primary扩散至所有sencondary，这样primary是一个中心，而且读也要发送至primary, 压力会比较大。)。所以会拥有更好的吞吐。

CRAQ: Chain Replication with Apportioned Queries

A node in CRAQ can store multiple versions of an object, each including a monotonically-increasing version number and an additional attribute whether the version is clean or dirty. All versions are initially marked as clean.


When a node receives a new version of an object (via a write being propagated down the chain), the node appends this latest version to its list for the object.


  
    If the node isn`t the tail,it marks the version as dirty, and propagates the write to its successor.
  
  
    Otherwise, if the node is the tail, it marks the version as clean, at which time we call the object version (write) as committed. The tail node can then notify all other nodes of the commit by sending an acknowledgement backwards through the chain.
  



When anacknowledgment message for an object version arrives at a node, the node marks the object version as clean. The node can then delete all prior versions of the object.


When a node receives a read request for an object:


  
    If the latest known version of the requested object is clean, the node returns this value.
  
  
    Otherwise, if the latest version number of the object requested is dirty, the node contacts the tail and asks for the tail’s last committed version number (a version query). The node then returns that version of the object; by construction, the node is guaranteed to be storing this version of the object. We note that although the tail could commit a new version between when it replied to the version request and when the intermediate node sends a reply to the client, this does not violate our definition of strong consistency, as read operations are serialized with respect to the tail.

Note that an object’s “dirty” or “clean” state at a node can also be determined implicitly, provided a node deletes old versions as soon as it receives a write commitment acknowledgment. Namely, if the node has exactly one version for an object, the object is implicitly in the clean state; otherwise, the object is dirty and the properly ordered version must be retrieved from the chain tail

备注

这里backup request可以借鉴这种实现方式来实现强一致性。即：在所有结点上对key维护不同的version，当向secondary读时，如果当前key是clean的，则直接返回。否则向primary查询当前key的最新version，然后返回给客户端。

CRAQ’s throughput improvements over CR arise in two different scenarios:

Read-Mostly Workloads have most of the read requests handled solely by the C−1 non-tail nodes (as clean reads), and thus throughput in these scenarios scales linearly with chain size C.


Write-Heavy Workloads have most read requests to non-tail nodes as dirty, thus require version queries to the tail. We suggest, however, that these version queries are lighter-weight than full reads, allowing the tail to process them at a much higher rate before it becomes saturated. This leads to a total read throughput that is still higher than CR.

Singleton Thread Safe

https://levy5307.github.io/blog/singleton-thread-safe/

最近重构rdsn代码，创建了一个logger_proxy类，发现一些单例的线程安全问题，记录如下。

一、懒汉式

最初通过继承singleton的方式来实现的单例，如下：
class logger_proxy : public singleton<logger_proxy>
{
}

而singleton使用的是静态变量来实现的懒汉式单例：
template
class singleton
{
public:
singleton() = default;

// disallow copy and assign
singleton(const singleton &) = delete;
singleton &operator=(const singleton &) = delete;

static T &instance()
{
    static T _instance;
    return _instance;
}

};

在运行dsn_nfs_test的时候，当主线程退出时，会子线程会接收到SIGSEGV(signal id = 11)，所以子线程会执行第26行的代码，打印该warn日志。
void native_linux_aio_provider::get_event()
{
struct io_event events[1];
int ret;

task::set_tls_dsn_context(node(), nullptr);

const char *name = ::dsn::tools::get_service_node_name(node());
char buffer[128];
sprintf(buffer, 

2pc

https://levy5307.github.io/blog/2pc/

在分布式系统中，不能简单的向所有节点发送提交请求，然后各个节点去独立的执行事务提交。例如：

某些节点检测到违反约束或者冲突因而决定终止，而其他节点则可能成功提交


发送给某些节点的提交请求可能因为网络原因丢失，而发往其他节点的请求则顺利通过


某些节点可能在日志记录写入之前发生崩溃，然后再恢复时回滚，而其他节点成功提交

因为部分节点提交成功、而其他一些节点提交失败的情况，将会破坏原子性。

之前的文章讲到过，分布式事务的原子性是由2pc来保证的。

2pc的基本流程

Chubby

https://levy5307.github.io/blog/Chubby/

一致性client库 or 分布式锁

chubby实现的是一个中心化锁所服务，基于其一些优势:

服务改造的时候，直接用分布式锁更容易实现
许多服务有小数据存储的要求，chubby提供了小数据存储
对大部分程序员更熟悉锁
一致性client库需要client拥有多台机器来做投票选举

粗粒度锁 or 细粒度锁

细粒度锁指的是只会持有锁很短的时间（秒级或更短），而粗粒度锁指的是持有比较长的时间，比如说是用于选主，通常都会是几小时甚至几天。这两种粒度的锁对锁服务提出了不同的要求。

粗粒度的锁因为隔很长的时间才需要访问锁服务一次，所以对server端的负载压力很小，并且这个负载跟client端的处理速率关联很小（意思是即使client端每秒处理很多请求，锁服务的server端收到的请求速率也不会明显增加）。另外，锁服务server端的机器故障对client的影响也比较小。

细粒度的锁就完全相反了，server端的失败可能造成很多client阻塞。性能和扩容的能力都很重要，因为server端的负载和client的处理速率密切相关。
Chubby只试图提供粗粒度的锁，客户端也可以直接根据他们的应用实现细粒度锁。

系统结构

Chubby主要有两个组成部分，server和client library。Chubby的一个个cell中有五台server组成一个集群，其中一个master，其他为slave。五台机器按照Paxos协议选举出master，要想成为master必须得到五台中大多数的投票。master会以租约的形式运行，只要它能得到副本的同意（即续租），那么租约便能定时更新然后延长master的运行时间。

客户端会向DNS请求Chubby服务器列表，然后随机发起访问，非master服务器会依据自身的存储的集群信息向客户端反馈哪台是master，然后客户端重定向到master。

如果一个副本挂了，并且几个小时都没有恢复，一个替换系统就会选一台新机器，启动chubby服务，然后更新DNS table。master会定期从DNS table拉数据，就会得知这个变化，然后在数据库中更新cell成员的列表，这个列表也是通过普通的一致性协议在副本间维护一致性的。

与此同时，新的副本会从存储在文件系统的数据库备份中取得最近几次的拷贝，并且在活跃的的那些副本那里取得更新。等这个机器成功处理了master的一个等待commit的请求后（说明此时数据已经是最新了），这个机器就可以参与投票了。

文件、目录

chubby的文件与unix文件系统基本一样，这样的好处是chubby文件既可以被chubby api访问，也可以被其他文件系统（例如GFS）的api访问。

/ls/foo/wombat/pouch

ls即lock service，是所有Chubby的文件名字通用的前缀，并且代表了锁服务。第二个组件（foo）是Chubby cell的名字

有临时和永久的节点，所有节点都可以被显示的删除，临时节点当没有client打开它们时就会被自动删除，所以临时的节点可以被用来检测client是否存活。

每个节点都有各种元数据，包括三个ACLs名字，这三个ACLs用于控制读取、写入和更改ACL名字。ACLs其实是位于ACL路径之下的文件。如果文件F写了其ACL名称为foo,ACL目录包含了文件foo，该文件中有一个叫做bar的条目，那么接下来用户bar将有权限对文件F做写入。

强制锁 or 建议锁

强制锁指的是当client没有持有锁时则不可访问资源

建议锁指的是只有其它client想要持有同样的锁时才会产生冲突，持有锁对于访问资源来说并不是必要的。

Chubby采用的是建议锁，理由如下：

Chubby锁常常保护其它服务的资源，而不是Chubby中跟锁关联的文件，而使用强制锁往往意味着要对其它服务做额外的修改。


当用户需要访问锁住的文件进行调试或管理目的时，我们并不想用户关掉程序。


我们的开发者使用很常见的错误检测方式，写assert语句比如‘assert 锁X被持有了’，所以强制锁的方式对他们来说意义不大。

Sequence

在分布式系统中锁是复杂的，因为消息是不确定的，进程也可能会挂掉。

举个例子，一个进程持有一个锁L，然后发起一个请求R，然后挂掉。另一个进程就会去持有这个锁L，然后在R到达前做一些操作。等R到达后，它可能就会在没有锁L的保护下进行操作，潜在的会造成不一致的数据。

这里的意思是这个锁L保护了一段数据data，按理说这个R应该在这个data上进行操作的，但是由于进程挂掉，导致另一个进程修改了这个data，所以R就可能在不一致的数据上进行操作。

Chubby提供了一种在使用锁的时候使用序列号的方法来解决这个问题。在每次获得锁后都会请求一个序列号（一个描述锁状态的字符串），client在发送请求的时候，会把这个序列号发给服务端，服务端会检测这个序列号的合法性。服务端可以通过和Chubby之间维护的cache来检测这个序列号的合法性，或者是直接和自己最近观测到的序列号比较。服务端可以通过和Chubby之间维护的cache来检测这个序列号的合法性，或者是直接和自己最近观测到的序列号比较

尽管序列号机制很简单，但是有些协议发展的很慢，不能带上序列号，chubby因此提供了另一种不完美但是更容易的方式来解决这个问题。如果一个client是以正常的方式释放锁的，那么这个锁立刻可以被其他的client获得，但是如果一个锁是因为client挂掉或不可访问而丢掉的，锁服务器会等一段叫lock-delay的时间来防止其它的client获得这个锁

Events

Chubby的client端可以订阅一些事件，这些事件通过回调的方式异步发送给client，包括：

文件内容修改


子结点的添加、移除、或修改。


Chubby主节点出故障


一个句柄（包括它的锁）已经变得不可用


获得锁


来自其他客户端的锁冲突请求

Cache

客户端会有自己的本地缓存，这样可以减少对Chubby的读压力。Chubby使用的是一致性的、write-through缓存。该缓存由记录有缓存的客户端列表的master发送出来的无效信号保持一致性。协议确保客户端能够互相看到一个一致的Chubby状态视图，或者是一个错误。

当文件的数据或者元数据被改变时，修改会被阻塞，直到master发送数据的无效信号到每一个可能缓存该数据的客户端上。修改只会有在服务器知道每个客户端都将缓存置为无效后才会被处理，要么是因为客户端确认了缓存的失效，要么是客户端确认其缓存的数据租约到期。

Session and KeepAlives

Chubby的会话是指一个Chubby客户端与一个Chubby单元之间的联系；它会存在一段时间，并且通过周期性的握手（即KeepAliveb）来维护。当会话有效时，client端的handle，锁，缓存都是有效的。

当client第一次连接cell时，它会请求一个新的会话，当client结束时会显示的终止会话，或者当这个会话一分钟内没有调用和打开handle时，也会被隐式的关闭

每个会话都有个对应的租约，master承诺在租约内不会单向的关闭会话，master可以延长这个租约，但不能减少。收到KeepAlive后，master会阻塞这个RPC，直到client的租约接近过期，然后master会允许这个RPC返回，就可以通知client新的租约超时时间。master可以任意扩展租约超时，默认是12s，但是过载的master可以指定更大的值来减少KeepAlive RPC的数量。client在收到响应后，就会马上发起一个新的KeepAlive，因此几乎总是有一个KeepAlive被阻塞在master。 除开用来扩展租约之外，KeepAlive还被用来传递事件和缓存失效给client。如果事件或者缓存失效发生了，master允许KeepAlive立刻返回。

同时客户端维护了一个本地租约过期时间，如果客户端的本地缓存租约过期了，由于此时它就无法确定 master 是否已经结束了这个 session，客户端就需要清空并禁用它的缓存，此时 session 处于 jeopardy 状态。客户端会继续等待一个称为 grace period 的时长，默认是45秒。如果在grace period 结束之前，客户端和 master 又完成了一次成功的 KeepAlive 交互，那么客户端就会再次使它的缓存有效。否则，客户端就假设 session 已过期。

Chubby的client库可以通知应用程序jeopardy事件，当会话恢复正常时，会通知应用程序safe事件，当会话超时时，会通知应用程序超时事件。这些信息使应用程序可以知道会话的状态，在不确定会话是否关闭时可以停下来等一会儿，如果只是个临时性的问题的话，就可以自动恢复而不用重启应用。这避免了应用重启的巨大开销。

Fail-overs

在master挂掉的时候，如果master选举很快，那client可以在自己的本地超时过期前就联系上新的master；否则，client的本地超时过期后，client可以利用grace period来让会话在fail-over期间得以维持，也就是说，grace period其实增加了client端的租约超时时间。

上图是client端在master fail-over时利用grace period来保留会话的一个例子。从图中可以看到client的本地租约已经超时，client进入了jeopardy状态，在grace period期间，client成功的联系上了新的master。一旦client成功联系上新master，对应用程序而言，就像是没有失败发生一样。为了实现这个，新master必须要重建旧master的内存状态，一个新选举出来的master需要进行的流程：

首先选一个新的client epoch号，client需要在每个调用中带上这个epoch号。master会拒绝使用旧epoch号的client端，这可以防止新master对一个很老的发送给旧master的包作出响应。


新master可能会对master-location请求作出响应，但不会对跟session有关的请求作出响应。


新master根据数据库中持久化的信息在内存中构建锁和会话的数据结构，会话的租约被扩展到之前的master可能已经使用的最大值。


master现在允许client执行KeepAlive


给每个会话生成一个fail-over事件，使client端刷新缓存，因为client可能错过了缓存失效事件，并且警告应用程序其它事件可能也丢掉了。（因为旧master挂的时候可能还来不及发送各种事件就挂了）。


master等待client端确认fail-over事件或者是client端的会话超时。


master允许所有的操作正常进行。


如果client使用一个旧的handle，新的master会在内存中构建这个handle的状态。如果这个重建的handle后续被关了，master也会在内存中记录下来，使得在这个master的任期内不可能再重新创建一个相同的handle。


在一段时间后，master会把没有handle打开的临时文件给删了，因此client端需要在这段时间内刷新自己对临时文件的handle。这个机制有个不好的地方是在fail-over期间如果一个临时文件的所有client端都失去了会话，这个临时文件也不能及时被删除（需要等这段时间结束，通常是1min）

Rdsn Service

https://levy5307.github.io/blog/rdsn-service/

service node: 一个服务，例如meta/collector/replica, 并不是对应一台物理机器，在run.sh中会使用-applist指定该机器要启动的node类型, 例如：
 
$PWD/pegasus_server config.ini -app_list meta
service_node里有一个service_app, 其有几个子类，例如：replication_service_app、meta_service_app、info_collector_app, node不同的类型里包含了不同的service_app
 
service engine: 一台物理机器上只有一个, 是一个单例, 用于管理service node, 其成员函数start_node用于根据service_app_spec启动一个service node
 
replica_stub: 用于管理replica分片，在replication_service_app中存储一个replica_stub类型实例
 
replica: 表示一个表分片副本

Rocksdb

https://levy5307.github.io/blog/rocksdb/

rocksdb_verbose_log:是否打印与rocksdb相关的一些调试日志                                                                                                                                                            

rocksdb_abnormal_get_time_threshold_ns: 如果get操作的时长超过了该数值，那么将会被写入日志。0代表不会写入

rocksdb_abnormal_get_size_threshold: 如果get操作获取的value的长度大于了该数值，那么将会被写入日志。0代表不会写入

rocksdb_abnormal_multi_get_time_threshold_ns:  如果multi-get操作的时长超过了该数值，那么将会被写入日志。0代表不会写入

rocksdb_abnormal_multi_get_size_threshold: 如果multi-get操作的key-value的size之和超过了该数值，那么将会被写入日志。0代表不会写入

rocksdb_abnormal_multi_get_iterate_count_threshold: 如果multi-get操作的key-value的数量超过了该数值，那么将会被写入日志。0代表不会写入

rocksdb_write_buffer_size:单个memtable的最大size。一旦memtable大小超过该数值，将会被标记为不可修改的，并且会创建一个新的memtable。然后，一个后台线程会把memtable的内容落盘到一个SST文件。

rocksdb_max_write_buffer_number: memtable的最大数量，包括active-memtable和immutable-memtable，如果active memtable被填满，并且memtable的总数量大于该数值，那么将会被延缓写入。

当刷新进程执行的比写入更慢时，有可能会发生这种情况。

rocksdb_max_background_flushes:支持的并发的后台flush线程数量。flush线程在高优先级的线程池中

rocksdb_max_background_compactions:支持的并发的后台compaction线程数量。conpaction线程在低优先级的线程池中

rocksdb_num_levels: rocksdb的LSM tree的层数

rocksdb_target_file_size_base and rocksdb_target_file_size_multiplier:

level 1层的文件大小最大为target_file_size_base字节。每高一层其文件大小比前面一层大的target_file_size_multiplier倍。默认情况下rocksdb_target_file_size_multiplier是１，也就是说每层的文件大小相同。

增大rocksdb_target_file_size_base将会导致每层的文件数量减少。我们推荐将rocksdb_target_file_size_base设置为max_bytes_for_level_base / 10，这样level 1层将最大有10个文件

rocksdb_max_bytes_for_level_base and rocksdb_max_bytes_for_level_multiplier:

rocksdb_level0_file_num_compaction_trigger: 如果level 0中的文件数量超过了该指定数值，L0->L1 compaction将会被触发

rocksdb_level0_slowdown_writes_trigger:  如果level 0中的文件数量超过了该指定数值，那么写入速度将会被降低到rocksdb.delayed-write-rate

rocksdb_level0_stop_writes_trigger:如果level 0中的文件数量超过了该指定数值，那么写入将会被禁止

rocksdb_compression_type:压缩算法类型。

压缩算法类型, 支持 none，snappy，lz4，zstd几种选项。支持为每一层单独配置压缩算法，用逗号分隔，如:“none,none,snappy,zstd” 表示L0，L1不进行压缩，L2使用snappy压缩，L3往下使用zstd压缩。

rocksdb_disable_table_block_cache: 如果该值被设置为true,则表示禁用block cache功能

rocksdb_block_cache_capacity and rocksdb_block_cache_num_shard_bits:

rocksdb_block_cache_capacity: block cache总的内存使用量

rocksdb_block_cache_num_shard_bits: shard block cache所使用的bit数量. block cache分很多shard, 便于并发操作, shard的数目为2^rocksdb_block_ache_num_shard_bits.

rocksdb_disable_bloom_filter: 如果该值被设置为true,则表示禁用bloom filter功能

pegasus cure

https://levy5307.github.io/blog/pegasus-cure/

pegasus对于每个partition采用一主两备份的方式来进行管理，该一主两备被称作一个replica group。当meta server对replica group进行修改时，有可能会产生primary不可用、secondary数量确实等情况，此时则需要对该replica group进行修复，该过程叫做cure。
meta server中使用定时任务来定期检查各个replica group的状态信息以对replica group进行修复。

Primary不可用
当primary不可用时，首先要考虑的是从secondary中选择一个将其提升为primary。然而此时secondary也有可能不存在，所以也要根据实际情况进行分类解决。

Secondary数量>0
此时则在所有的secondary中选择一个提升为primary，选取的规则如下：

对比该app下的primary数量，选择拥有较少数量的节点对应的secondary
如果两个相等，则选择该app的partition数量最少的
还是相等的话，则选择所有app下primary数量最少的
如果还是相等，则选择所有app下partition数量最少的
因为产生决策时，而真正执行则需要一段时间。因此，这里的数量统计不仅仅要考虑正在服务的replica，也要包括将来要服务的replica。

新创建的partition(last_drop为空)
当secondary数量为0时，也有可能是该partition是新创建的，此时只需要在partition中选择一个提升为primary就可以了。具体的选择方法和上述相同。

该partition的所有replica都不可用
当secondary数量为0，并且该partition并非是新创建的，则表明此时该partition中的所有replica都不可用。
待补充

缺少Secondary

多Secondary
这种情况是由于负载均衡策略导致的，此时只要选择出这些secondary所在的node中partition数量最少的一个node，将其对应的secondary remove就可以了。

未完待续

Rdsn Task

https://levy5307.github.io/blog/rdsn-task/

一、global相关
service_spec: global specification
成员变量：
std::vector threadpool_specs 保存所有threadpool的specification

成员函数：
bool init()
1.从配置文件的[core] section读取配置参数
2.threadpool_spec::init(threadpool_spec)获取所有threadpool的specification –> threadpool_spec
3.task_spec::init()

二、threadpool相关
threadpool_code: threadpool_spec的index，内部只有一个int型_internal_code保存customizable id
DEFINE_THREAD_POOL_CODE用于定义一个threadpool_code, 例如：代码中可以调用DEFINE_THREAD_POOL_CODE(THREAD_POOL_INVALID)去创建一个name=THREAD_POOL_INVALID的threadpool_code(根据name去注册customizable id)

threadpool_spec: thread pool specification
static bool init(std::vector &specs) 读取配置中所有threadpool的specification, specs是输出参数
1. 创建一个default_spec，从配置文件的[threadpool..default] section读取thread pool的默认参数
2. 然后遍历所有的threadpool code, 根据threadpool code获取其name，然后根据default_spec, 以及从配置文件[threadpool.{name}] section获取具体的配置参数来好偶去spec, 放入所有的specs中
成员变量：
std::string name thread_pool的名字(例如threadpool.THREAD_POOL_DEFAULT)
dsn::threadpool_code pool_code threadpool_spec的index
int worker_count 该threadpool的线程数量
worker_priority_t worker_priority 该threadpool的优先级

note: 目前只有task engine用到了thread pool

三、task相关
static std::array<std::unique_ptr, TASK_SPEC_STORE_CAPACITY> s_task_spec_store: 全局std::array, 保存所有的task_spec, 下标是task_code

task_code: 仅有一个int类型成员用于保存task code
构造时会调用task_spec::register_storage_task_code, 注册task code并创建相应的task_spec
可以使用DEFINE_TASK_CODE/DEFINE_TASK_CODE_RPC/DEFINE_TASK_CODE_AIO等宏去注册task code(并创建相应的task_spec), 其将会去创建相应的task_code
所以task_code和task_spec是在系统启动时候就创建好的，所以toollets可以将join point加入到所有的task_spec中

task_spec: 保存task specification(包括task code, 以及各种join point)
static函数task_spec::register_storage_task_code; 用于注册task code并创建相应的task_spec, 如果task_type是TASK_TYPE_RPC_REQUEST，还要注册ack_code

task:
在创建时，会去s_task_spec_store中找相应的task_spec, task执行的不同阶段, 会去调用spec中不同的join_point.execute

task_worker: task线程，创建时为其指定一个task queue
void start() 标记_is_running=true, 并创建一个线程运行run_internal()函数。最终线程进入loop()函数，不断从task queue中取出task执行task->exec_internal(根据task_worker_pool::_spec.dequeue_batch_size去batch size个)
note: 由于queue有可能是共享的，所以queue的内部实现需要加锁

simple_timer_service::timer_service 定时任务服务
void add_timer(task *task) 将task加入到定时服务中
1.创建一个boost::asio::deadline_timer类型的timer
2.timer->expires_from_now(boost::posix_time::milliseconds(task->delay_milliseconds())) 设置delay时间
3.调用timer->async_wait, wait指定的delay时间. 同时指定一个callback，该callback将执行task->enqueue(timer_task::enqueue)
timer_task::enqueue最终将改task放入到了task_worker_pool中的对应的task queue中，随后task_worker会异步的取出该task执行，执行完task的callback后将task的状态设置为READY，以便再次执行(task::exec_interval在运行完其exec()函数后，会判断其状态，如果不是Finish状态，则继续将task入队).
并将其delay时间为interval_milliseconds, 只是delay时间变为了timer_interval, 这样task::enqueue再次入队时，由于delay时间不为0，则调用add_timer，跳到了1。
note:
1.所以timer_task的执行最终也是放入到task_queue中，正如其名字，timer_service只是提供了一个定时服务，最终执行的还是task_worker_pool中定义的线程
2.这样看定时任务也不是特别精确准时

task_worker_pool: task线程池
成员变量：
threadpool_spec _spec threadpool specification
task_engine *owner 指向task_engine的指针
service_node *_node 指向service_node的指针
std::vector<task_worker *> _workers 所有的task线程
std::vector<task_queue *> _queues 所有的task_queue(每个分片一个queue)
std::vector<timer_service *> _per_queue_timer_svcs 所有的定时任务服务(每个分片一个queue)

成员函数：
void create() 紧跟在构造函数之后使用
1.如果_spec.partitioned等于true，分片数量qCount=_spec.worker_count(每个分片一个queue), 否则qCount=1. 创建qCount个queue, 放入_queues中
2.创建qCount个timer_service，放入_per_queue_timer_svcs
3.根据_spec.worker_count来创建task_worker，执行task_worker::create函数，并将所有worker放入_workers。
在创建task_worker时需要为其指定task_queue，如果是分片模式，则每个worker一个queue，否则所有的worker都指定同一个queue(因为只有一个)
void start() 启动task_work_pool
1.启动所有的定时任务
2.启动所有的task_worker
void add_timer(task *t)
1.idx = (_spec.partitioned ? static_cast(t->hash()) % static_cast(_per_queue_timer_svcs.size()) : 0) 获取分片index, 如果_spec中指定是分片模式，则根据task *t的hash值与定时队列的数量取模，否则就是0(此时只有一个定时任务queue)
2._per_queue_timer_svcs[idx]->add_timer(t) 向queue中插入该定时任务
void enqueue(task *t) 将task *t插入到task queue中
1.计算分片index
2.根据分片获取相应的queue，将task *t放入到queue中

task_engine: 每个service_node有且仅有一个task_engine, 在service_node::start函数中，会创建一个task_engine，并调用其create接口
成员变量：
std::vector<task_worker_pool *> _pools 所有的thread pool, 一个task_engine有多个thread pool
volatile bool _is_running 是否正在运行
service_node *node 指向service_node的指针，每个service都有一个task_engine
成员函数：
void create(const std::list &pools) 创建所有的thread pool
遍历所有的threadpool_code,
1.获取改threadpool_code对应的threadpool_spec
2.根据threadpool_spec new一个task_worker_pool
3.调用workerPool->create()
4.将workerPool放入到_pools中
void start() 对所有的thread pool执行task_worker_pool::start

TODO:

其他：
join_point:
join_point里面包含一个advice_entry双向循环链表,可以通过put_back,put_front等函数向其中添加advice_entry，在调用execute时将所有advice_entry执行一遍。
可以用于错误注入等，向代码的执行中注入各种逻辑操作。例如task中就有各种join_point,用于在task运行时的不同阶段,注入不同的代码

toollets:
在配置文件中通过toollets定义，在service_api_c.cpp的run()函数中，会初始化toollets, 遍历所有的task_spec, install各种join point到task_spec中

Leveldb

https://levy5307.github.io/blog/leveldb/

Log files

log文件保存一系列的最新更新，每次更新都追加到当前的log文件中，当log文件达到其预定义的size上限时，其将会被转换成sorted table（*.ldb），并且创建一个新的log文件用于接收更新。在内存中保存当前log文件的副本(memtable)，每次读都会查阅一次memtable，以便每次读取的时候都可以获取到最新的更新

Sorted tables

sorted table(*.ldb)是一系列的根据key排序的entry组成。entry中的每个key对应一个value或者一个Deletion marker（Deletion marker用于淘汰存在于之前的sorted table中的entry)。
所有的sorted table被组织成一系列的level。从log file产生的sorted table被放置在young level(也就是level 0)，当young file的数量超过一定数量的时候（目前4个），所有的young files将和所有的与之有重叠的level 1 files merge成新的level 1 files(每个level 1文件存储2MB数据)
在young level可能存在重叠的keys，然而其它层的的文件不存在重叠的key 。对于L>=1，当我们合并后的level L文件总大小超过10^L时，并且与所有的与之重叠的level L+1的文件合并成一系列新的level L+1 files。这些合并操作产生的效果是，逐渐地令所有的在young level的最新更新操作仅仅以bulk read和bulk write的方式写入到largest level

overlap(重叠)
level 0中的各个文件之间的key有overlap，但是level > 0的层的文件中没有重叠。
有序
文件中的key是有序的，就是说在文件中小key记录排在大Key记录之前，各个level的SSTable都是如此。当level > 0时，在文件间也是有序的(level > 0)

SSTable:
1.Table::Open()
打开文件调用Table::Open()，该函数读取sstable的除了data block之外的其他所有的block
2.cache: Table中维护的对data block的lru缓存，每次读取data block时，需要先从缓存中读取，如果缓存中没有，再去硬盘文件中读取该data block，并放入_cache中
3.VersionSet::table_cache: Table缓存
为table维护了一个缓存–>TableCache(lru cache), 缓存所有已打开的文件。

当从sstable中查找一个key时:
1.先去TableCache中去查找Table，如果查找到了，说明该文件已经打开过（即已经读取过除data block之外的所有block）, 如果没有找到，则先调用Table::Open打开文件，并将其加入缓存中。
2.调用Table::InternalGet去查找key。首先从meta block（bloom filter）查看该key是否存在，如果bloom filter说明不存在，那么就真的不存在，直接返回。如果bloom filter说明存在，则不一定存在，需要调用Table::BlockReader去查找data block。
2.1 首先从_cache中查找该data block是否被缓存, 如果已缓存，则直接从_cache中获取data block, 否则则需要从硬盘中读取该data block, 然后在data block中去查找该key(有序的)

spanner

https://levy5307.github.io/blog/spanner/

Spanner是谷歌开发的一款可扩展的、全球分布式的数据库，其复制技术可以用来服务于全球可用性和地理局部性。

其提供了几个特性：

在数据的副本配置方面，应用可以在一个很细的粒度上进行动态控制。应用可以详细规定哪些数据中心包含哪些数据，数据距离用户有多远（控制用户读取数据的延迟），不同数据副本之间距离有多远（控制写操作的延迟），以及需要维护多少个副本（控制可用性和读操作性能）。数据也可以被动态和透明地在数据中心之间进行移动，从而平衡不同数据中心内资源的使用。


Spanner有两个重要的特性，很难在一个分布式数据库上实现，即Spanner提供了读和写操作的外部一致性，以及在一个时间戳下面的跨越数据库的全球一致性的读操作。这些特性使得Spanner可以支持一致的备份、一致的MapReduce执行[12]和原子模式变更，所有都是在全球范围内实现，即使存在正在处理中的事务也可以。

之所以可以支持这些特性，是因为Spanner可以为事务分配全球范围内单调向前的commit timestamp，即便事务可能是分布式的。这些时间戳反映了事务串行化的顺序。除此以外，这些串行化的顺序满足了外部一致性的要求：如果一个事务T1在另一个事务T2开始之前就已经提交了，那么，T1的commit timestamp就要比T2的commit timestamp小。Spanner是第一个可以在全球范围内提供这种保证的系统。实现这种特性的关键技术就是一个新的TrueTime API及其实现，这个在后面将会详细讲解。

实现

Chain Replication

https://levy5307.github.io/blog/chain-replication/

Chain Replication Protocol

Reply Generation

The reply for every request is generated and sent by the tail.

Query Processing

Each query request is directed to the tail of the chain and processed there atomically using the replica of objID stored at the tail.

Update Processing

Each update request is directed to the head of the chain. The request is processed there atomically using replica of objID at the head, then state changes are forwarded along a reliable FIFO link to the next element of the chain (where it is handled and forwarded), and so on until the request is handled by the tail.

Coping with Server Failures

For this purpose, we employ a service, called the master, that:

detects failures of servers,


informs each server in the chain of its new predecessor or new successor in the new chain obtained by deleting the failed server,


informs clients which server is the head and which is the tail of the chain.

Using Paxos to coordinate those master instances, so they behave in aggregate like a single process that does not fail.

Three cases

(i) failure of the head, (ii) failure of the tail, and (iii) failure of some other server in the chain.

Failure of the Head

This case is handled by the master removing H from the chain and making the successor to H the new head of the chain.

Failure of the Tail

This case is handled by removing tail T from the chain and making predecessor T− of T the new tail of the chain.

Failure of Other Servers

Failure of a server S internal to the chain is handled by deleting S from the chain.

This, however, could cause the Up- date Propagation Invariant to be invalidated unless some means is employed to ensure update requests that S received before failing will still be forwarded along the chain (since those update requests already do appear in HistiobjID for any predecessor i of S) The Update Propagation Invariant in this case is preserved by:

The master first informs S’s successor S+ of the new chain configuration and then informs S’s predecessor S−.The Update Propagation Invariant is preserved by requiring that the first thing a replica S− connecting to a new successor S+ does is: send to S+ (using the FIFO link that connects them) those requests in HistS− that might not have reached S+;

Note: 也就是说，如果不用采用上述补救措施的话，而是S挂掉后不采取任何措施，由S+继任，并且S-继续向S+传递，这样会有一个问题：由于S挂掉了，那么S+中将会缺少一部分update操作日志(即中间会有一个空洞), 这样一致性都无法保证了

Extending a Chain

A new server could, in theory, be added anywhere in a chain. In practice, adding a server T+ to the very end of a chain seems simplist. For a tail T+, the value of SentT+ is always the empty list, so initializing SentT+ is trivial. All that remains is to initialize local object replica HistT+ in a way that objID satisfies the Update Propagation Invariant.

Strong Consistency

What is Strong Consistency

operations to query and update individual objects are executed in some sequential order


the effects of update operations are necessarily reflected in results returned by subsequent query operations.

Why CR is Strong Consistency

Strong consistency thus follows because query requests and update requests are all processed serially at a single server (the tail).

链式复制的优点

链式复制的每个节点（除了尾结点）都会产生写复制操作，而主从复制的写复制操作集中在主节点，这样就增加了主节点的负担；


主从复制要想提供强一致性（consistency），一般都会用上分布式一致性（consensus）算法；而链式复制由于写复制的顺序性，更容易实现强一致性


链式复制可用性强，例如要保证N个节点挂掉，集群仍然可用，链式存储只要有N+1个节点就可以了，但是主从方式需要2N+1个节点

tcp slow start调研

https://levy5307.github.io/blog/tcp-slow-start/

背景

有用户反应在系统刚启动时的请求耗时会比较长，所以针对这个问题进行了调研。了解到了tcp的slow start特性，并对此进行了测试。

测试

将测试分为同机房测试和跨机房测试。

跨机房测试

使用get operation, value=1kB大小，使用c3 client to c4 server进行了跨机房访问，请求100次。

recv/send buffer大小: 512 Bytes
average = 190478 us, max = 214527 us, min = 1601 us
耗时比较大，前面的请求(约几百个)基本都在200ms左右，后面的有所减少，慢慢减少到了1.6ms

recv/send buffer大小: 默认情况(4 * 1024)。其中，{1: latency}代表第一个请求的延时
1: latency = 12102 us
2: latency = 1871 us
average = 1789 us, max = 12102 us, min = 1528 us

recv/send buffer大小: 8 * 1024
1: latency = 14661 us
2: latency = 2015 us
average = 1830 us, max = 14661 us, min = 1581 us

recv/send buffer大小: 16 * 1024
1: latency = 12206 us
2: latency = 1906 us
average = 1750 us, max = 12206 us, min = 1534 us

recv/send buffer大小: 32 * 1024
1: latency = 12390 us
2: latency = 1975 us
average = 1823 us, max = 12390 us, min = 1571 us

recv/send buffer大小: 64 * 1024
1: latency = 13539 us
2: latency = 1931 us
average = 1831 us, max = 13539 us, min = 1550 us

根据上面的测试，发现两个情况：

当buffer大小 < 数据大小时，最开始的一批请求都会非常慢，随后的请求会变快


当buffer大小 > 数据大小时，第一个请求会比较慢，第2个rpc之后的耗时明显变小。此时即使再增大buffer大小，请求耗时也不会减少，即此时的请求耗时和设置的recv/send buffer大小没关系

根据第2条，可以看出第2个rpc之后的耗时明显减少，所以考虑加入fake rpc来做warm up。加入之后，请求100次情况：

1: latency = 3723 us
2: latency = 1896 us
average = 1714 us, max = 3904 us, min = 1561 us

所以添加fake rpc，对于提升第一次请求速度确实有帮助。

总结：

通过调研得知，tcp协议是有slow start算法的，即最初的时候会设置滑动窗口比较小，后续根据网络状况再调整滑动窗口大小。但是仅仅是改变客户端和服务端两边的buffer大小是没有太大意义的，因为我们无法改变中途所经过的路由器的滑动窗口大小。此时整个链路的瓶颈是在中途所经过的路由器上，所以即使再增大buffer大小，请求耗时也不会减少。但是如果将服务断/客户端的buffer设置过小时（远小于系统默认值），此时的瓶颈在服务端/客户端，所以请求最开始会很慢，随后随着窗口变大也会变得越来越快。


发送fake rpc是非常有效的，因为该fake rpc会经过整个请求的链路，且tcp的slow start算法对于滑动窗口是指数级增长的，所以会将整个链路的滑动窗口大小都调大，从而减少后续的请求耗时。

同机房测试

另外，使用ycsb也进行了同机房访问测试(c4 client to c4 server)：

未使用opentable（用于拉取表路由信息）进行warm up(value大小=1KB):

recv/send buffer大小: 512 Bytes
average = 211.22 us, max = 136703 us, min = 97 us, count = 572286

recv/send buffer大小: 默认情况(4 * 1024)
average = 195.31 us, max = 136959 us, min = 96 us, count = 614644

recv/send buffer大小: 8 * 1024
average = 201.28 us, max = 140543 us, min = 97 us, count = 595120

recv/send buffer大小: 16 * 1024
average = 202.53 us, max = 136063 us, min = 96 us, count = 594949

recv/send buffer大小: 32 * 1024
average = 197.24 us, max = 131711 us, min = 95 us, count = 606562

recv/send buffer大小: 64 * 1024
average = 204.27 us, max = 143231 us, min = 100 us, count = 590427

可见请求耗时和设置的窗口大小无关。

使用opentable进行warmup后，没有fake rpc

recv/send buffer大小: 64 * 1024
average = 223.86 us, max = 36991 us, min = 79 us, count = 535692

可见，进行warmup后，相比未进行warmup，效果有了很大提升。

使用opentable进行warmup并发送fake rpc

recv/send buffer大小: 64 * 1024
average = 302.69 us, max = 48895 us, min = 82 us, count = 266561

结果显示请求耗时和设置的窗口大小无关，和是否发送fake rpc也无关。但是提前opentable拉去表配置的效果提升很大

总结： 由于同机房内部网络状况都会比较好，tcp协议默认此时不会出现丢包等情况，所以滑动窗口一开始就会设置成最大，即使我们手动设置也是如此。所以此时不管发送fake rpc还是改变buffer大小，都对请求耗时没有影响

Thread Local

https://levy5307.github.io/blog/thread-local/

G++ now implements the C++11 thread_local keyword; this differs from the GNU __thread keyword primarily in that it allows dynamic initialization and destruction semantics. Unfortunately, this support requires a run-time penalty for references to non-function-local thread_local variables even if they don’t need dynamic initialization, so users may want to continue to use __thread for TLS variables with static initialization semantics.

What is precisely the nature and origin of this run-time penalty?

Answer
The dynamic thread_local initialization is added in commit 462819c. One of the change is:

semantics.c (finish_id_expression): Replace use of thread_local
variable with a call to its wrapper.

So the run-time penalty is that, every reference of the thread_local variable will become a function call. Let’s check with a simple test case:

// 3.cpp
extern thread_local int tls;
int main() {
tls += 37; // line 6
tls &= 11; // line 7
tls ^= 3; // line 8
return 0;
}

// 4.cpp

thread_local int tls = 42;

When compiled*, we see that every use of the tls reference becomes a function call to _ZTW3tls, which lazily initialize the the variable once:

00000000004005b0

:
main():
4005b0: 55 push rbp
4005b1: 48 89 e5 mov rbp,rsp
4005b4: e8 26 00 00 00 call 4005df <_ZTW3tls> // line 6
4005b9: 8b 10 mov edx,DWORD PTR [rax]
4005bb: 83 c2 25 add edx,0x25
4005be: 89 10 mov DWORD PTR [rax],edx
4005c0: e8 1a 00 00 00 call 4005df <_ZTW3tls> // line 7
4005c5: 8b 10 mov edx,DWORD PTR [rax]
4005c7: 83 e2 0b and edx,0xb
4005ca: 89 10 mov DWORD PTR [rax],edx
4005cc: e8 0e 00 00 00 call 4005df <_ZTW3tls> // line 8
4005d1: 8b 10 mov edx,DWORD PTR [rax]
4005d3: 83 f2 03 xor edx,0x3
4005d6: 89 10 mov DWORD PTR [rax],edx
4005d8: b8 00 00 00 00 mov eax,0x0 // line 9
4005dd: 5d pop rbp
4005de: c3 ret

00000000004005df <_ZTW3tls>:
_ZTW3tls():
4005df: 55 push rbp
4005e0: 48 89 e5 mov rbp,rsp
4005e3: b8 00 00 00 00 mov eax,0x0
4005e8: 48 85 c0 test rax,rax
4005eb: 74 05 je 4005f2 <_ZTW3tls+0x13>
4005ed: e8 0e fa bf ff call 0 // initialize the TLS
4005f2: 64 48 8b 14 25 00 00 00 00 mov rdx,QWORD PTR fs:0x0
4005fb: 48 c7 c0 fc ff ff ff mov rax,0xfffffffffffffffc
400602: 48 01 d0 add rax,rdx
400605: 5d pop rbp
400606: c3 ret
Compare it with the __thread version, which won't have this extra wrapper:

00000000004005b0

:
main():
4005b0: 55 push rbp
4005b1: 48 89 e5 mov rbp,rsp
4005b4: 48 c7 c0 fc ff ff ff mov rax,0xfffffffffffffffc // line 6
4005bb: 64 8b 00 mov eax,DWORD PTR fs:[rax]
4005be: 8d 50 25 lea edx,[rax+0x25]
4005c1: 48 c7 c0 fc ff ff ff mov rax,0xfffffffffffffffc
4005c8: 64 89 10 mov DWORD PTR fs:[rax],edx
4005cb: 48 c7 c0 fc ff ff ff mov rax,0xfffffffffffffffc // line 7
4005d2: 64 8b 00 mov eax,DWORD PTR fs:[rax]
4005d5: 89 c2 mov edx,eax
4005d7: 83 e2 0b and edx,0xb
4005da: 48 c7 c0 fc ff ff ff mov rax,0xfffffffffffffffc
4005e1: 64 89 10 mov DWORD PTR fs:[rax],edx
4005e4: 48 c7 c0 fc ff ff ff mov rax,0xfffffffffffffffc // line 8
4005eb: 64 8b 00 mov eax,DWORD PTR fs:[rax]
4005ee: 89 c2 mov edx,eax
4005f0: 83 f2 03 xor edx,0x3
4005f3: 48 c7 c0 fc ff ff ff mov rax,0xfffffffffffffffc
4005fa: 64 89 10 mov DWORD PTR fs:[rax],edx
4005fd: b8 00 00 00 00 mov eax,0x0 // line 9
400602: 5d pop rbp
400603: c3 ret

This wrapper is not needed for in every use case of thread_local though. This can be revealed from decl2.c. The wrapper is generated only when:

It is not function-local, and


It is extern (the example shown above), or


The type has a non-trivial destructor (which is not allowed for __thread variables), or


The type variable is initialized by a non-constant-expression (which is also not allowed for __thread variables).

Conclusion
In all other use cases, it behaves the same as __thread. That means, unless you have some extern __thread variables, you could replace all __thread by thread_local without any loss of performance.

Ford Fulkerson

https://levy5307.github.io/blog/ford-fulkerson/

本文主要讲解最大流问题的Ford-Fulkerson解法。可以说这是一种方法，而不是算法，因为它包含具有不同运行时间的几种实现。该方法依赖于三种重要**：残留网络，增广路径和割。

在介绍着三种概念之前，我们先简单介绍下Ford-Fulkerson方法的基本**。首先需要了解的是Ford-Fulkerson是一种迭代的方法。开始时，对所有的u,v属于V，f(u,v)=0(这里f(u,v)代表u到v的边当前流量)，即初始状态时流的值为0。在每次迭代中，可以通过寻找一个“增广路径”来增加流值。增广路径可以看做是从源点s到汇点t之间的一条路径，沿该路径可以压入更多的流，从而增加流的值。反复进行这一过程，直到增广路径都被找出为止。

举个例子来说明下，如图所示，每条红线就代表了一条增广路径，当前s到t的流量为3。

当然这并不是该网络的最大流，根据寻找增广路径的算法我们其实还可以继续寻找增广路径，最终的最大流网络如下图所示，最大流为4。

接下来我们就介绍如何寻找增广路径。在介绍增广路径之前，我们首先需要介绍残留网络的概念。

残留网络

顾名思义，残留网络是指给定网络和一个流，其对应还可以容纳的流组成的网络。具体说来，就是假定一个网络G=（V，E），其源点s，汇点t。设f为G中的一个流，对应顶点u到顶点v的流。在不超过C（u，v）的条件下（C代表边容量），从u到v之间可以压入的额外网络流量，就是边（u，v）的残余容量（residual capacity），定义如下：

r（u，v）=c（u，v）-f（u，v）

举个例子，假设（u，v）当前流量为3/4，那么就是说c（u，v）=4，f（u，v）=3，那么r（u，v）=1。

我们知道，在网络流中还有这么一条规律。从u到v已经有了3个单位流量，那么从反方向上看，也就是从v到u就有了3个单位的残留网络，这时r（v，u）=3。可以这样理解，从u到v有3个单位流量，那么从v到u就有了将这3个单位流量的压回去的能力。

我们来具体看一个例子，如下图所示一个流网络

其对应的残留网络为：

增广路径

在了解了残留网络后，我们来介绍增广路径。已知一个流网络G和流f，增广路径p是其残留网络Gf中从s到t的一条简单路径。形象的理解为从s到t存在一条不违反边容量的路径，向这条路径压入流量，可以增加整个网络的流值。上面的残留网络中，存在这样一条增广路径：

其可以压入4个单位的流量，压入后，我们得到一个新的流网络，其流量比原来的流网络要多4。这时我们继续在新的流网络上用同样的方法寻找增广路径，直到找不到为止。这时我们就得到了一个最大的网络流。

流网络的割

上面仅仅是介绍了方法，可是怎么证明当无法再寻找到增广路径时，就证明当前网络是最大流网络呢？这就需要用到最大流最小割定理。

首先介绍下，割的概念。流网络G（V，E）的割（S，T）将V划分为S和T=V-S两部分，使得s属于S，t属于T。割（S，T）的容量是指从集合S到集合T的所有边（有方向）的容量之和（不算反方向的，必须是S-àT）。如果f是一个流，则穿过割（S，T）的净流量被定义为f（S，T）（包括反向的，SàT的为正值，T—>S的负值）。将上面举的例子继续拿来，随便画一个割，如下图所示：

割的容量就是c(u,w)+c(v,x)=26

当前流网络的穿过割的净流量为f(u,w)+f(v,x)-f(w,v)=12+11-4=19

显然，我们有对任意一个割，穿过该割的净流量上界就是该割的容量，即不可能超过割的容量。所以网络的最大流必然无法超过网络的最小割。

可是，这跟残留网络上的增广路径有什么关系呢？

首先，我们必须了解一个特性，根据上一篇文章中讲到的最大流问题的线性规划表示时，提到，流网络的流量守恒的原则，根据这个原则我们可以知道，对网络的任意割，其净流量的都是相等的。具体证明是不难的，可以通过下图形象的理解下，

和上面的割相比，集合S中少了u和v，从源点s到集合T的净流量都流向了u和v，而在上一个割图中，集合S到集合T的流量是等于u和v到集合T的净流量的。其中w也有流流向了u和v，而这部分流无法流向源点s，因为没有路径，所以最后这部分流量加上s到u和v的流量，在u和v之间无论如何互相传递流，最终都要流向集合T，所以这个流量值是等于s流向u和v的值的。将s比喻成一个水龙头，u和v流向别处的水流，都是来自s的，其自身不可能创造水流。所以任意割的净流量都是相等的。

万事俱备，现在来证明当残留网络Gf中不包含增广路径时，f是G的最大流。

假设Gf中不包含增广路径，即Gf不包含从s到v的路径，定义S={v:Gf中从s到v存在一条通路}，也就是Gf中s能够有通路到达的点的集合，显然这个集合不包括t，因为s到t没有通路。这时，我们令T=V-S。那么（S，T）就是一个割。如下图所示：

那么，对于顶点u属于S，v属于T，有f（u，v）=c（u，v）。否则（u，v）就存在残余流量，因而s到u加上u到v就构成了一条s到v的通路，所以v就必须属于S，矛盾。因此这时就表明当前流f是等于当前的割的容量的，因此f就是最大流。

伪代码

Ford-Fulkerson方法的伪代码如下。其中<u,v>代表顶点u到顶点v的一条边，<u,v>.f表示该边的流量，c是边容量矩阵，c(i,j)表示边<i,j>的容量，当边<i,j>不存在时，c(i,j)=0。e为残存网络矩阵，e(i,j)表示边<i,j>的值，当边<i,j>不存在时，e(i,j)=0。E表示边的集合。f表示流网络。

Ford-Fulkerson:

for <u,v> ∈ E
    <u,v>.f = 0

while find a route from s to t in e
    m = min(<u,v>.f, <u,v>  ∈ route)
    for <u,v> ∈ route
        if <u,v>  ∈ f
            <u,v>.f = <u,v>.f + m
        else
            <v,u>.f = <v,u>.f - m

Ford-Fulkerson方法首先对图中的所有边的流量初始化为零值，然后开始进入循环：如果在残存网络中可以找到一条从s到t的增广路径，那么要找到这条这条路径上值最小的边，然后根据该值来更新流网络。

Reference

https://www.cnblogs.com/DarrenChan/p/9563511.html

Pegasus使用NVMe的调研

https://levy5307.github.io/blog/pegasus-nvme/

NVMe

NVMe: 即Non-Volatile Memory Express，是专为固态存储器设计的新型传输协议。SATA (Serial Advanced Technology Attachment) 并非专为固态硬盘等闪存存储器设计，相比之下，NVMe使硬盘的性能得到极大的提升。

参考文档：https://en.wikipedia.org/wiki/NVM_Express

SpanDB

最近读paper时发现了SpanDB。根据SpanDB的描述，将WAL和lsm tree的前几层放在NVMe中，可以有效提高性能和吞吐，同时也能兼顾成本

Paper

项目地址

SpanDB的架构

将磁盘分为SD和CD。SD意为speed disk，即高速磁盘，这里是指NVMe。CD意为capacity disk，是低速大容量盘。

将WAL和LSM的top n层放到SD里，因为WAL直接影响写请求的延迟和吞吐，而LSM的top n层是热数据。这里的n是根据负载和吞吐情况动态自适应的。


将LSM的剩余层放入CD中，这一部分数据大多是冷数据，且数据量大。将这一部分数据放入CD主要是基于成本考虑

通过SPDK访问SD，SPDK意为Storage Performance Development Kit，其通过引入以下技术，实现高性能存储技术。官方文档：

将存储用到的驱动转移到用户态，避免系统调用


支持零拷贝


避免在IO链路上使用锁


使用轮询硬件，而不是中断。断模式带来了不稳定的性能和延时的提升

下图是采用NVMe盘，不同场景下采用ext4和SPDK的吞吐和延迟对比

为了使RocksDB兼容SPDK，在SPDK上实现了一个轻量级自带缓存的文件系统TopFS

SpanDB的优点

性能高。SpanDB相较于RocksDB，吞吐提升了8.8倍，延时降低了9.5%-58.3%。


具备无缝替代原生RocksDB的能力。这样可以方便我们做测试，然而不推荐用SpanDB替换，社区不成熟。

Pegasus借鉴与优化

Pegasus可以借鉴SpanDB的优化方案：

将shared log放入一个NVMe盘中（后期如果移除掉shared log的话，可以把这个节约一个NVMe盘）


另外选取一个NVMe盘存储private log和lsm-tree的top n层，n的选取根据负载和吞吐动态自适应。（这里需要修改RocksDB的实现）


lsm-tree的其他几层的cold data存放在SATA SSD盘中


使用SPDK访问NVMe盘，进一步提升io性能。可能需要像SpanDB一样在SPDK之上实现一个文件接口层。

这样优化后，可以使Pegasus降低读写延迟，提高系统吞吐，从而可以降低成本。

从硬件上来说，Pegasus需要2块NVMe的小盘，其他的盘均使用普通的SSD。

Backup Request Implementation

https://levy5307.github.io/blog/backup-request-implementation/

背景
在当前的pegasus实现中，由于向secondary读取会导致不一致的情况发生，所以目前Pegasus仅仅支持对primary副本的读取。但是在某些情况下（例如：负载均衡、热点写入等）经常会导致primary不稳定。所以我们希望在primary不稳定时能够读取secondary，通过牺牲部分强一致性来降低请求的长尾并提高系统的可用性。backup request便是用来实现此功能的。

设计实现

backup reqeust的实现原理比较简单：当client向primary发送请求后，经过一段时间延时后（通常是p999），如果其response仍然没有返回，则随机选择一台secondary并向其发送backup request。最后获取最快返回来的response进行处理。

这里发送secondary请求的延时我们建议选择p999，因为backup request操作是用来实现消除长尾的，并不是提升集群性能的。如果将该值设置过低，则会由于backup request的请求量过大而导致集群压力增大（假设选择p50作为其延时，这样便会有50%的请求向secondary发送请求，系统负载便会增大50%）。

限流

如果backup request流量太多，可能会导致集群负载增加，进而影响稳定性。因此我们希望能对其添加限流。

但是backup request限流不能像普通的读写限流一样，直接对于超出预期的流量简单的返回ERR_REJECT，因为在backup request的实现中，客户端只会接收最快返回的response。这样由于发送到secondary的backup request马上返回了ERR_REJECT的response，那么客户端就不会再接收发往primary的请求了。

一个想法是在客户端侧加限流。但是这样带来的问题就是没办法像服务端一样去对限流值进行动态配置，因为我们没办法去修改业务的应用。

最终我们采用的方法还是在服务端加限流，但是对于被限流的backup request，我们不去发送response，让客户端去等待primary返回的response。

如何使用
在pegasus java client中，我们增加了一个接口，通过该接口可以打开某个表的backup reqeust功能。其实现如下：
public PegasusTableInterface openTable(String tableName, int backupRequestDelayMs) throws PException;

相比于老版本的openTable接口，我们增加了一个backupRequestDelayMs参数。这个参数便是上文所指的时延，即：向primary发送请求，如果过了backupRequestDelayMs毫秒response仍没有返回，则向secondary发送backup request。需要注意的是，backupRequestDelayMs <= 0代表禁用backup reqeust功能。

另外在老版本的openTable接口中，backup request功能默认是关闭的。

性能测试

下面表格里展示了是否打开backup request的性能对比，这里我们选取了未打开backup request时读请求的p999时间作为backup request的delay时间。数据显示，打开backup request之后get请求的p999时延基本没有变化，而p9999时延却有了数倍的降低。

另外，由于delay时间设置的是p999时间，大约1000个请求里只有1个请求会发送backup request，因此额外请求量（也就是开启backup request的额外开销）比例在0.1%左右。依此类推，若想要降低P999时延，则可以将 backupRequestDelayMs 设置为P99延迟，由此会增加1%的额外读流量。

set/get operation:

  test case
  enable backup request
  qps
  read/write propotion
  read avg
  read p95
  read p99
  read p999
  read p9999
  write avg
  write p95
  write p99
  write p999
  write p9999




  3-clients 15-threads
  no
  1 : 3
  7076
  880.6512836149132
  428.0
  727.0
  138495.0
  988671.0
  2495.0710801540517
  6319.0
  9023.0
  36319.0
  531455.0


  3-clients 15-threads
  yes, delay 138ms
  1 : 3
  6987
  1010.1412488662884
  403.0 
  7747.0
  138751.0
  153599.0
  2476.104380444753
  6859.0
  9119.0
  13759.0
  185855.0


  3-clients 100-threads
  no
  1 : 0
  140607
  707.98960978
  1474.0
  2731.0
  5511.0
  167551.0
   
   
   
   
   


  3-clients 100-threads
  yes, delay 5ms
  1 : 0
  77429
  1288.01461934
  2935.0
  3487.0
  6323.0
  71743.0
  —-
  —-
  —-
  —-
  —


  3-clients 30-threads
  no
  30 : 1
  87198
  306.9600544730426
  513.0
  805.0
  4863.0
  28271.0
  1369.4669874672938
  2661.0
  5795.0
  22319.0
  51359.0


  3-clients 30-threads
  yes, delay 5ms
  30 : 1
  88541
  298.22470022339127
  493.0
  711.0
  4483.0
  18479.0
  1467.6130963728997
  3263.0
  6411.0
  17439.0
  50975.0

Multi-get/Batch-Set operation:

  test case
  enable backup request
  qps
  read/write porpotion
  read avg
  read p95
  read p99
  read p999
  read p9999
  write avg
  write p95
  write p99
  write p999
  write p9999




  3-clients  7-threads
  no
  20 : 1
  24113
  200.37956913733476
  277.0
  410.0
  2317.0
  21647.0
  2034.1923768463382
  4283.0
  6427.0
  18271.0
  62687.0


  3-clients  7-threads
  yes, deley 2ms
  20 : 1
  23756
  197.48540031650361
  268.0
  351.0
  2173.0
  5759.0
  2187.199077764627
  4531.0
  6551.0
  21551.0
  63999.0


  3-clients  15-threads
  no
  20 : 1
  30980
  236.7482510418767
  348.0
  526.0
  3535.0
  25695.0
  5361.380053671262
  14087.0
  20223.0
  40639.0
  90815.0


  3-clients  15-threads
  yes, delay 3ms
  20 : 1
  30483
  244.1182599024727
  386.0
  540.0
  3105.0
  13287.0
  5377.992155339365
  14119.0
  19535.0
  31311.0
  103103.0

Reference

The Tail at Scale

backup request in brpc

backup request investigation

Hermes

https://levy5307.github.io/blog/Hermes/

Introduction

当今的共识协议过多的关注于吞吐throughput，而忽视了延迟latency，例如Chain Replication，便是一个典型的利用延迟换吞吐的例子。但是目前延迟已经变成一个越来越重要的指标。

Hermes便是一个兼具吞吐和延迟的共识协议，对于读操作，则可以在任何副本上进行读取；写操作，则意味着任一副本都可以启动写入。

读取实现低延迟和高吞吐的关键在于：

能够在任何副本上提供读取服务


能在本地完成读取

写入能够实现低延迟和高吞吐的关键在于：

去中心化：为减少网络跳数并保持整个副本集合之间的负载均衡，任何副本都必须能够发起写操作并驱动它完成(通过与剩余的副本进行通信)，同时避免集中式序列化点。例如：CR就要求在特定节点上启动所有的写操作，因此无法分散写操作


inter-key并发：对不同的key的独立写入应该能够并行进行，以启用内部和多线程并行请求执行。


快速：快速写入需要最大程度地减少消息往返次数，避免长消息链，以及hunning techniques，否则会增加写入延迟

可靠的共识协议

可靠的共识协议分为两类：1. 基于多数的协议，通常是Paxos的变体；2. 要求活动节点具有问题定成员资格的协议（即：基于成员资格的协议）

基于多数的协议: 要求大多数节点进行响应才能提交写入，因此只要大多数相应，它自然可以容忍失败。但是，基于多数的协议为了高性能付出了一些代价，因为在没有所有副本响应的情况下，无法保证给定的写入已到达所有副本。这使得本地读取成为一件非常有挑战的事情。因此，大多数基于多数的协议都放弃了本地读取。但是可能支持去中心化和inter-key并发写入

基于成员资格的协议：此类协议要求副本组中的所有操作节点都响应写操作。这样做可以确保已提交的写入已到达集合中的所有副本，这自然促进了本地读取，而不妨碍写入性能。

CRAQ就是基于成员资格的协议。在CRAQ中，节点是按链组织的，写操作直接写入头部。头部沿链向下传播，直到到达尾部才完成。随后尾部向上游传播确认消息，使所有节点都知道写入的完成情况。CRAQ通过允许从所有节点本地读取来优化改善了CR。但是如果非尾结点正在尝试读服务，它已经看到了从头到尾向下游传播的写消息，但是没有看到ack消息向上传播，则其必须查询尾节点来查看写入是否已经完成。

CRAQ可以结合本地读取和inter-key并发来实现高吞吐量，但是无法满足低延迟要求：虽然读操作是本地的，因此非常快。但是写入操作必须依次遍历多个节点，从而产生了过高的等待时间开销。

Hermes
Hemers是一种可靠的基于成员资格的广播协议，提供高吞吐和低延迟，并且同时提供线性化读取、写入和RMWs(single-key transactions)。Hemers优化了无故障的常见情况，并以当今典型的复制程度(3-7副本)、数据中心内、内存数据存储为目标。

Overview
在Hermes中，读取操作完全在本地执行。写入操作可以由任何replica启动并快速完成、而不会发生冲突。如下图所示，写入一个key的流程如下：

Volatile

https://levy5307.github.io/blog/volatile/

Q: Why do we use volatile keyword?

A: Consider this code:

int some_int = 100;

while(some_int == 100)
{
//your code
}

When this program gets compiled, the compiler may optimize this code, if it finds that the program never ever makes any attempt to change the value of some_int, so it may be tempted to optimize the while loop by changing it from while(some_int == 100) to something which is equivalent to while(true) so that the execution could be fast (since the condition in while loop appears to be true always). (if the compiler doesn’t optimize it, then it has to fetch the value of some_int and compare it with 100, in each iteration which obviously is a little bit slow.)

However, sometimes, optimization (of some parts of your program) may be undesirable, because it may be that someone else is changing the value of some_int from outside the program which compiler is not aware of, since it can’t see it; but it’s how you’ve designed it. In that case, compiler’s optimization would not produce the desired result!

So, to ensure the desired result, you need to somehow stop the compiler from optimizing the while loop. That is where the volatile keyword plays its role. All you need to do is this,

volatile int some_int = 100; //note the 'volatile' qualifier now!

In other words, I would explain this as follows:

volatile tells the compiler that,

“Hey compiler, I’m volatile and, you know, I can be changed by some XYZ that you’re not even aware of. That XYZ could be anything. Maybe some alien outside this planet called program. Maybe some lightning, some form of interrupt, volcanoes, etc can mutate me. Maybe. You never know who is going to change me! So O you ignorant, stop playing an all-knowing god, and don’t dare touch the code where I’m present. Okay?”

Well, that is how volatile prevents the compiler from optimizing code. Now search the web to see some sample examples.

Microsoft Socrates

https://levy5307.github.io/blog/microsoft-socrates/

当前，越来越多的企业和组织将数据托管在云上。同时其对DB系统提供了更高的要求。这些要求包括高安全性、高可用性、支持超大规模数据、低价及灵活的付费（pay-as-you-go）、以及高性能。此外，服务需要是弹性的，可以随着负载的变化自动增长或者收缩，使得用户可以利用pay-as-you-go的模式来节省成本。

事实证明，在云上使用传统的、整体架构的database架构是无法满足这些需求的：

为了充分利用集群中的计算资源，增大某些节点吞吐及减少某些节点吞吐，可能需要在节点间搬移数据，然而这对于传统database的代价非常高昂。


支持大规模数据量和高可用之间是矛盾的。高可用需要一个很短的恢复时间，然而这在传统的数据库中需要非常小的数据量才能实现。该问题在内部部署的传统数据库并不存在，因为其使用了特殊的、昂贵的硬件来支持高可用。然而这些硬件在云上是不可能提供的。


内部部署可以控制软件的更新时间并且可以仔细规划停机时间，这在云上也是无法满足的。

为了解决这些问题，过去十年有很多对于OLTP database上云的研究。一个主要的idea是将计算功能和存储功能解耦，并且分别去部署计算资源与存储资源。第一个使用该idea的商业系统是Amazon Aurora。

当前论文描述了Socrates，一个新的OLTP database架构，其通过微软在Azure数以百万计的database的经验得来。Socrates将计算层与存储层分离开来，另外Socrates还将database log和存储分离，并将log模块作为一个一级模块。日志与存储分离也意味着持久性（由日志层实现）和可用性（由存储层实现）分离。持久性是为了防止数据库数据丢失的基础特性。可用性是在故障存在的场景下提供高质量服务所需要的。传统的实现通常将持久性实现和高可用性耦合在一起。其中高可用性是通过维持多个副本来实现。然而将两者分离是很有意义的：

与高可用性相反，持久性不需要多个副本。


与持久性相反，高可用性不需要固定数量的副本。

分离两者使得Socrates可以采取更合适的机制来处理。具体来说，Socrates相比于其他失眠上的database，更少的存储在本地昂贵快速存储上的副本数量、更少的整体的副本数量、更少的网络带宽以及更少的计算资源来维护副本更新。

  **
  Today
  Socrates




  Max DB Size
  4TB
  100TB


  Availability
  99.99
  99.999


  Upsize/downsize
  O(data)
  O(1)


  Storage impact
  4x copies(+backup)
  2x copies(+backup)


  CPU impact
  4x single images
  25% reduction


  Recovery
  O(1)
  O(1)


  Commit Latency
  3ms
  < 0.5ms


  Log Throughput
  50MB/s
  100+MB/s

上表列出了Socrates在可扩展性、可用性、弹性、资源消耗以及性能的优异表现。如何做到这些是本篇论文的主题

State Of The Art

这一节介绍一些市面上常用的接触DBaaS系统。

SQL DB是微软Azure上的一款DBaaS。其基于HADR来构建。HADR是基于日志复制的状态机实现，其拥有一个Primary用户处理所有的update事务，并将update log同步至所有的Secondary节点。日志复制是分布式数据库系统中保持副本一致性的标准做法。另外，Primary会周期性的备份数据到Azure的XStore存储服务上：

每5分钟备份一次日志


每天做一次整个数据库的增量备份


每周做一次数据库的完全备份

下图所示为HADR的架构图:

Secondary节点只处理只读事务，当一个Primary挂掉时，其中一个Secondary会被选为新Primary。使用HADR架构，SQL DB需要四个节点（一个Primary和三个Secondary）用以保证高可用和高持久性。但是由于日志每5分钟备份一次，如果所有的4个节点都挂了，是会存在数据丢失的。

HADR有如下优点：

在Azure上部署了上百万个database，成熟稳定


每个计算节点都有database的全量本地数据拷贝，性能比较高

HADR的缺点：

由于每个计算节点都有database的全量本地数据拷贝，database的数据量无法超越单机存储上限


当运行一个long-running的事务时，当日志的增长超过了磁盘容量的上限，在事务提交之前并不能截断该日志。


O(size-of-data)问题，扩建一个新节点的代价与数据量大小成线性关系，Backup/Restore和扩容/缩容的代价与数据量大小成线性关系。

这就是为什么SQL DB的容量上限被限制在4TB。

另外一个基于日志复制状态机的云数据库系统的例子是Spanner。具体可以参考Google Spanner

在过去十年，很多关于云数据库的研究都提出了一个名叫shared disk的架构。在这个架构中将计算和存储进行了划分。AWS Aurora是第一个采用该架构的商业化DBaaS。在Aurora中，一个Primary Compute节点处理update事务，并且每个log record会被传输到6个用于持久化数据的Storage Server。这6个Storage Server会被分不到3个可用的地区。当该6个Storage Service中的4个已经成功持久化后，该事务就可以提交。为了提高扩展性，在存储层将数据和log进行了分区。

Important SQL Server Features

Socrates构建在一些基础之上，这些基础在SQL Server中也有所呈现。这一节介绍了独立于Socrates开发、但对Socrates至关重要的一些SQL Server特性。

Page Version Store

为了在同时有写的情况下提供读snapshot的能力（也就是snapshot隔离级别），SQL为database的record维护了多个版本。在HADR架构中，所有的版本都是存储在本地临时存储中。但是Socrates并没有这样做，它把所有版本的数据都存储在了共享存储层，这样所有的计算节点可以共享所有的数据版本。

Accelerated Database Recovery

SQL的Accelerated Database Recovery(ADR)利用了上述的持久化version store。在ADR之前，SQL Server使用RIES-style恢复模式：

首先，分析日志


对于最后一次checkpoint以后的未提交且成功的事务，回放其redo日志


对于最后一次checkpoint以后的未提交且失败的事务，回放其undo日志

在这种模式下，对于一个长时间运行的事务，undo阶段可能会变得无限长。使用多版本存储可以优化这种情况：在一个共享的、持久性的version store中，系统可以在宕机重启后立马访问已经提交的版本，系统在很多情况下可以忽略undo阶段的影响, 在分析和redo阶段后马上变得可用，这是一个很短的常量时间（该常量时间由checkpoint的interval决定）。

Resilient Buffer Pool Extension

在2012年，SQL Server发布了一个叫做buffer poll extension(BPE)的功能，其将buffer poll从内存延伸到了本地SSD磁盘上（在内存和磁盘上使用相同的生命周期和驱逐策略）。在Socrates中扩展了这种**，使得buffer pool具有可恢复性，例如故障后的恢复。这个组件叫做RBPEX，他作为对数据页的缓存机制服务于存储层和计算层。这种方式使得宕机后节点可以快速恢复到之前的性能：如果宕机时比较短暂的（例如软件升级后的机器重启），相比传统的从远程server读取缓存的page，读取和回放更新日志记录的代码会更小，提高了可用性。

RBIO protocol

Socrates将数据库引擎的组件分布在多层之中。为了支持更丰富的计算分布，扩展了传统的SQL Server网络层（称为Unified Communication），使用了一种新的协议，称为Remote Block I/O，简称RBIO。RBIO是一种无状态协议，强类型，支持自动版本控制，对短暂性故障具有可快速恢复性，并且对最佳副本选择具有QoS支持。

Snapshot Backup/Restore

当数据库文件存储在Azure中时，SQL Server 2016引入了快速备份的能力。这个feature依赖于XStore实现的blob snapshot的特性，XStore是一个日志结构的存储系统，备份几乎是实时的，因为它只需要维护一个指针(时间戳)指向当前日志的头部。Socrates扩展了这个feature，将备份/恢复的工作完全使用XStore snapshot。因此，Socrates可以不用消耗计算层的CPU和IO就可以在常量时间内完成备份或者恢复。在XStore的快照机制下，一个数百TB的大数据库也可以在分钟内完成备份。

当然，apply log使机器状态恢复到正确、启动机器、对restore的database刷新其cache都需要一些时间，但是这些时间与data size无关。Bacup/restore是Scorate消除了size-of-data操作的一个显著例子。

I/O Stack Virtualization

在I/O栈的最低层，SQLServer使用一个叫作File Control Block(FCB)的抽象层作为。FCB层抽象了底层设备的细节，提供给上层I/O的能力，支持多个文件系统、多样的存储平台和I/O模式。Socrates通过实现新的FCB instance广泛的使用了这个IO虚拟化层，该FCB instance在计算过程中隐藏Socraetes的存储层次结构。这种方法帮助我们再不改变太多SQL Server组件的情况下实现Socrates。大多数组件相信它们是一个独立的、独立的数据库系统的组件，而在FCB层之上的任何组件都不需要处理分布式、异构系统的复杂性（Socrates实际上是这样的系统）

Socrates Architecture

Lsm

https://levy5307.github.io/blog/lsm/

导引

随着activity flow(活动流)管理系统中的long-lived(长生命期)事务的商业化使用，针对事务日志记录提供索引化的访问需求也在逐步增长。传统的，事务日志机制主要专注于失败和恢复，需要系统能够在偶然的事务回滚中可以回退到一个相对近期的正常历史状态，而恢复的执行则通过批量化的顺序读取完成。然而，随着系统需要管理越来越多的复杂行为，组成单个长生命期活动的事件的持续时间和个数也会增长到某种情况，在该情况下，需要实时查看已经完成的事务步骤以通知用户目前已经完成了哪些。与此同时，一个系统的处于活动状态的事件总数，也会增长到某种情况，在该情况下，用于记录活动日志的基于内存的数据结构开始无法工作，尽管内存价格的不断下降是可以预计的。这种对于过去的行为日志的查询需求，意味着索引化的日志访问将会越来越重要。

即使是对于当前的事务系统来说，如果对在具有高插入频率上的历史记录表上的查询提供了索引支持，其价值也是很明显的。网络应用，电子邮件，和其他的近事务系统通常会产生不利于它们的主机系统的大量日志。为了便于理解，还是从一个具体的大家都熟知的例子开始，在下面的例1.1和1.2中我们使用了一个修改版的TPC-A benchmark。需要注意的是，为了便于表述，本文中的例子都采用了一些特定的参数值，当然这些结果应该都很容易进行推广。还要指出的是，尽管历史记录表和日志都是一些时间序列相关的数据，LSM-Tree中的索引节点并不一定具有与之相同的key值顺序。唯一的假设就是与查询频率相比的高更新率。

5分钟法则

下面的两个例子都依赖于5分钟法则。该法则是说当页面访问频率超过每60秒就会被访问一次的频率后，可以通过加大内存来将页面保存到内存，以避免磁盘访问来降低系统总体开销。60秒在这里只是个近似值，实际上是磁盘提供每秒单次IO的平摊开销与每秒缓存4K bytes的磁盘页的内存开销的比值。用第3节的术语来说，就是COSTp/COSTm。在这里，我们会从经济学的角度上简单看下如何在磁盘访问和缓存在内存之间进行权衡。需要注意的是，由于内存价格与磁盘相比下降地更快，60秒这个值实际应该会随着时间而变大。但是在1995年的今天它是60秒，与1987年的5分钟相比，它却变小了，部分是因为技术性的(不同的缓存假设)原因，部分是因为介于二者之间的廉价量产磁盘的引入。

例1.1 考虑TPC-A benchmark中描述的每秒执行1000个事务(该频率可以被扩展，但是此处我们只考虑1000TPS)的多用户应用程序。每个事务会更新一个列值，从一个Balance列中取出数目为Delta的款项，对应的记录(row)是随机选定的并且具有100字节大小，涉及到三个表：具有1000条记录的Branch(分公司)表，具有10000条记录的Teller(出纳员)表，以及具有100,000,000条记录的Account表；更新完成之后，该事务在提交之前会向一个历史记录表中插入一条50字节的记录，该记录具有如下列：Account-ID，Branch-ID，Teller-ID，Delta和时间戳。

根据磁盘和内存成本计算下，可以看出Account表在未来的很多年内都不可能是内存驻留的，而Branch和Teller表目前是可以全部存入内存中的。在给定的假设下，对于Account表的同一个磁盘页的两次访问大概要间隔2500秒{!磁盘页是4K bytes，Account表每行是100bytes，这样每次读会涉及到4k/100=40条记录，TPS是1000,这样2500秒内读到的行数就是4010002500=100,000,000。2500秒就是这么算出来的}，很明显这个值还未达到5分钟法则中缓存驻留所需要的访问频率。现在每次事务都需要大概两次磁盘IO，一次用于读取所需的Account记录(我们忽略那种页面已经被缓存的特殊情况)，一次用于将之前的一个脏的Account页写出来为读取腾出缓存空间(necessary for steady-status behavior)。因此1000TPS实际上对应着大概每秒2000个IO。如果磁盘的标称速率是25IO/s，那么这就需要80个磁盘驱动器，从1987年到如今(1995)的8年间磁盘速率(IOPS)每年才提高不到10%，因此现在IOPS大概是40IO/s，这样对于每秒2000次IO来说，就需要50个磁盘。对于TPC应用来说，磁盘的花费大概占了整个系统成本的一半，尽管在IBM的大型机系统中这个比例要低一些。然而，用于支持IO的开销很明显在整个系统成本中正在不断增长，因为内存和CPU成本下降地比磁盘要快。

例1.2 现在来考虑一个在具有高插入量的历史记录表上的索引，可以证明这样的一个索引将会使TPC应用的磁盘开销加倍。一个在“Account-ID+Timestamp”上的联合索引，是历史记录表能够对最近的account活动进行高效查询的关键，比如：

Select * from History

Where History.Acct-ID = %custacctid

And History.Timestamp > %custdatetime;

如果Acct-ID Timestamp索引不存在，这样的一个查询将需要搜索历史记录表中的所有记录，因此基本上是不可行的。如果只是在Acct-ID上建立索引，可以得到绝大部分的收益，但是即使将Timestamp排除，我们下面的那些开销考虑也不会发生变化{!即去掉Timestamp也不会省掉什么开销}，因此我们这里假设使用的是最有效的联合索引。那么实时地维护这样的一个B-树索引需要多少资源呢？可以知道，B树中的节点每秒会生成1000个，考虑一个20天的周期，每天8小时，每个节点16字节，这意味着将会有576,000,000{!1000208*3600}个节点，占据的磁盘空间是9.2GBytes，即使是在没有浪费空间的情况下，整个索引的叶节点都大概需要2.3million个磁盘页。因为事务的Acct-ID值是随机选择的，每个事务至少需要一次读取，此外基本上还需要一次页面写入。根据5分钟法则，这些索引页面也不应该是内存驻留的(磁盘页大概每隔2300秒被读一次)，这样所有的IO都是针对磁盘的。这样针对Account表的更新，除了现有的2000IO/s就还需要额外的2000IO/s，也就需要再购买50个磁盘，这样磁盘的需求就加倍了。同时，这还是假设用于将日志文件索引维持在20天的长度上的删除操作，可以作为一个批处理任务在空闲时间执行。

现在我们已经分析了使用B-树来作为Acct-ID Timestamp索引的情况，因为它是当前商业系统中使用的最通用的基于磁盘的访问方法。事实上，也没有什么其他经典的磁盘索引结构可以提供更好的IO性价比。在第5节中我们还会讨论下如何得出这样的结论的。

本文提出的LSM-Tree访问方法使得我们可以使用更少的磁盘运动来执行在Acct-ID Timestamp上的频繁插入操作。LSM-Tree通过使用某种算法，该算法会对索引变更进行延迟及批量处理，并通过一种类似于归并排序的方式高效地将更新迁移到磁盘。正如我们将在第5节看到的，将索引节点放置到磁盘上的这一过程进行延迟处理，是最根本的，LSM-Tree结构通常就是包含了一系列延迟放置机制。LSM-Tree结构也支持其他的操作，比如删除，更新，甚至是那些具有long latency的查询操作。只有那些需要立即响应的查询会具有相对昂贵的开销。LSM-Tree的主要应用场景就是像例1.2那样的，查询频率远低于插入频率的情况(大多数人不会像开支票或存款那样经常查看自己的账号活动信息)。在这种情况下，最重要的是降低索引插入开销；与此同时，也必须要维护一个某种形式的索引，因为顺序搜索所有记录是不可能的。

在第2节，我们会引入2-组件LSM-Tree算法。在第3节，我们会分析下LSM-Tree的性能，并提出多组件LSM-Tree。在第4节，我们会描述下LSM-Tree的并发和恢复的概念。在第5节，我们会讨论下其他的一些访问方式，以及它们的性能。第6节是总结，我们会指出LSM-Tree的一些问题，并提出一些扩展建议。

两组间LSM-Tree算法

LSM-Tree由两个或多个类树的数据结构组件构成。本节，我们只考虑简单的两个组件的情况，同时假设LSM-Tree索引的是例1.2中的历史记录表中的记录。如下图

在每条历史记录表中的记录生成时，会首先向一个日志文件中写入一个用于恢复该插入操作的日志记录。然后针对该历史记录表的实际索引节点会被插入到驻留在内存中的C0树，之后它将会在某个时间被移到磁盘上的C1树中。对于某条记录的检索，将会首先在C0中查找，然后是C1。在记录从C0移到C1中间肯定存在一定时间的延迟，这就要求能够恢复那些crash之前还未被移出到磁盘的记录。恢复机制将会在第4节讨论，现在我们只是简单地认为那些用于恢复插入的历史记录数据的日志记录可以被看做逻辑上的日志；在恢复期间我们可以重构出那些已经被插入的历史记录，同时可以重建出需要的那些记录并将这些记录进行索引以恢复C0丢失的内容。

向驻留在内存中的C0树插入一个索引条目不会花费任何IO开销。但是，用于保存C0的内存的成本要远高于磁盘，这就限制了它的大小。这就需要一种有效的方式来将记录迁移到驻留在更低成本的存储设备上的C1树中。为了实现这个目的，在当C0树因插入操作而达到接近某个上限的阈值大小时，就会启动一个rolling merge过程，来将某些连续的记录段从C0树中删除，并merge到磁盘上的C1树中。图2.2描述了这样的一个过程。

C1树具有一个类似于B-树的目录结构，但是它是为顺序性的磁盘访问优化过的，所有的节点都是100%满的，同时为了有效利用磁盘，在根节点之下的所有的单页面节点都会被打包(pack)放到连续的多页面磁盘块(multi-page block)上；类似的优化也被用在SB-树中。对于rolling merge和长的区间检索的情况将会使用multi-page block io，而在匹配性的查找中会使用单页面节点以最小化缓存需求。对于root之外的节点使用256Kbytes的multi-page block大小，对于root节点根据定义通常都只是单个的页面。

Rolling merge实际上由一系列的merge步骤组成。首先会读取一个包含了C1树中叶节点的multi-page block，这将会使C1中的一系列记录进入缓存。之后，每次merge将会直接从缓存中以磁盘页的大小读取C1的叶节点，将那些来自于叶节点的记录与从C0树中拿到的叶节点级的记录进行merge，这样就减少了C0的大小，同时在C1树中创建了一个新的merge好的叶节点。

merge之前的老的C1树节点被保存在缓存中的称为emptying block{!掏空ing，即该block中的那些节点正在被掏空}的multi-page block中，而新的叶节点会被写入到另一个称为filling block{!填充ing，即该block正在被不断地用新节点填充}的缓存中的multi-page block。当C1中新merge的节点填满filling block后，该block会被写入到磁盘上的新空闲区域中。如果从图2.2中看的话，包含了merge结果的新的multi-page block位于图中老节点的右侧。后续的merge步骤会随着C0和C1的索引值的增加而发生，当达到阈值时，就又会从最小值开始启动rolling merge过程。

新的merge后的blocks会被写入到新的磁盘位置上，这样老的blocks就不会被覆盖，这样在crash发生后的恢复中就是可用的。C1中的父目录节点也会被缓存在内存中，此时也会被更新以反映出叶节点的变动，同时父节点还会在内存中停留一段时间以最小化IO；当merge步骤完成后，C1中的老的叶节点就会变为无效状态，之后会被从C1目录结构中删除。通常，每次都是C1中的最左边的叶节点记录参与merge，因为如果老的叶节点都是空的那么merge步骤也就不会产生新的节点，这样也就没有必要进行。除了更新后的目录节点信息外，这些最左边的记录在被写入到磁盘之前也会在内存中缓存一段时间。用于提供在merge阶段的并发访问和从crash后的内存丢失中进行恢复的技术将会在第4节详细介绍。为了减少恢复时的重构时间，merge过程需要进行周期性的checkpoints，强制将缓存信息写入磁盘。

2.1 How a Two Component LSM-Tree Grows

为了追踪LSM-tree从诞生那一刻开始的整个变化过程，我们从针对C0的第一次插入开始。与C1树不同，C0树不一定要具有一个类B-树的结构。首先，它的节点可以具有任意大小：没有必要让它与磁盘页面大小保持一致，因为C0树永不会位于磁盘上，因此我们就没有必要为了最小化树的深度而牺牲CPU的效率{!如果看下B-树，就可以知道实际上它为了降低树的高度，牺牲了CPU效率。在当整个数据结构都是在内存中时，与二分查找相比，B-树在查找时，在节点内部的比较，实际上退化成了顺序查找，这样它查找一个节点所需的比较次数实际上要大于AVL的比较次数}。这样，一个2-3树或者是AVL树就可以作为C0树使用的一个数据结构。当C0首次增长到它的阈值大小时，最左边的一系列记录将会从C0中删除(这应是以批量处理的模式完成，而不是一次一条记录)，然后被重新组织成C1中的一个100%满的叶子节点。后续的叶节点会按照从左到右的顺序放到缓存中的一个multi-page block的初始页面中，直到该block填满为止；之后，该block会被写到磁盘中，成为C1树的磁盘上的叶级存储的第一部分。随着后续的叶节点的加入，C1树会创建出一个目录节点结构，具体细节如下。

C1树的叶节点级的后续multi-page block会按照键值递增的顺序被写入到磁盘中，以防止C0树大小超过阈值。C1树的上级目录节点被存放在独立的multi-page block buffers或者是单页面缓存中，无论存在哪里，都是为了更好地利用内存和磁盘；目录节点中的记录包含一些分隔点，通过这些分隔点可以将用户访问导引到单个的singe-page节点中，像B-树那样。通过这种指向叶级节点的single-page索引节点可以提供高效的精确匹配访问，避免了multi-page block的读取，这样就最小化了缓存需求。这样在进行rolling merge或者按range检索时才会读写multi-page block，对于索引化的查询(精确匹配)访问则读写singe-page节点。[22]中提出了一种与之类似但又稍有不同的结构。在一系列叶级节点blocks被写出时，那些由C1的目录节点组成的还未满的multi-page block可以保留在缓存中。在如下情况下，C1的目录节点会被强制写入磁盘：

1.由目录节点组成的某个multi-page block被填满了

2.根节点发生了分裂，增加了C1树的深度(成了一个大于2的深度)

3.执行Checkpoint

ck会被写出到磁盘。对于后两个情况，所有的multi-page block buffers和目录节点buffers都会被flush到磁盘。

当C0树的最右边的叶节点记录首次被写出到C1树后，整个过程就又会从两个树的最左端开始，只是从现在开始，需要先把C1中的叶子级别的multi-page block读入到buffer，然后与C0树中的记录进行merge，产生出需要写入到磁盘的新的C1的multi-page leaf block。

一旦merge过程开始，情况就变地更复杂了。我们可以把整个两组件LSM-tree的rolling merge过程想象成一个具有一定步长的游标循环往复地穿越在C0和C1的键值对上，不断地从C0中取出数据放入到磁盘上才C1中。该rolling merge游标在C1树的叶节点和更上层的目录级都会有一个逻辑上的位置。在每个层级上，所有当前正在参与merge的multi-page blocks将会被分成两个blocks：”emptying block”-它内部的记录正在搬出，但是还有一些信息是merge游标所未到达的，”filling block”-反映了此刻的merge结果。类似地，该游标也会定义出”emptying node”和”filling node”，这两个节点此刻肯定是已在缓存中。为了可以进行并发访问，每个层级上的”emptying block”和”filling block”包含整数个的page-sized C1树节点。(在对执行节点进行重组的merge步骤中，针对这些节点的内部记录的其他类型的并行访问将会被阻塞)。当所有被缓存的节点需要被flush到磁盘时，每个层级的所有被缓存的信息必须被写入到磁盘上的新的位置上(同时这些位置信息需要反映在上层目录信息中，同时为了进行恢复还需要产生一条日志记录)。此后，当C1树某一层级的缓存中的filling block被填满及需要再次flush时，它会被放到新的磁盘位置上。那些可能在恢复过程中需要的老的信息永不会被覆盖，只有当后续的写入提供了足够信息时它们才可以宣告失效。第4节来还会进行一些关于roling merge过程的更细节的解释，在那一节里还会考虑关于并发访问和恢复机制的设计。

在C1的某个层级上的rolling merge过程，需要很高的节点传输速率时，所有的读写都是以multi-page blocks为单位进行的，对于LSM-tree来说，这是一个很重要的效率上的优化。通过减少寻道时间和旋转延迟，我们认为与普通的B-树节点插入所产生的随机IO相比，这样做可以得到更大的优势(我们将会在3.2节讨论其中的优势)。总是以multi-page blocks为单位进行写入的想法源自于由Rosenblum和Ousterhout发明的Log-Structured File System，Log-Structured Merge-tree的叫法也源于此。需要注意的是，对于新的multi-page blocks的写入使用连续的新的磁盘空间，这就意味着必须对磁盘区域进行包装管理，旧的被丢弃的blocks必须能被重用。使用记录可以通过一个内存表来管理；旧的multi-page blocks作为单个单元被置为无效和重用，通过checkpoint来进行恢复。在Log-Structured File System中，旧的block的重用会引入显著的IO开销，因为blocks通常是半空的，这样重用就需要针对该block的一次读取和写入。在LSM-tree中，blocks是完全空的，因此不需要额外的IO。

2.2 Finds in the LSM-tree index

当在LSM-tree index上执行一个需要理解响应的精确匹配查询或者range查询时，首先会到C0中查找所需的那个或那些值，然后是C1中。这意味着与B-树相比，会有一些额外的CPU开销，因为现在需要去两个目录中搜索。对于那些具有超过两个组件的LSM-tree来说，还会有IO上的开销。先稍微讲一下第3章的内容，我们将一个具有组件C0，C1，C2…Ck-1和Ck的多组件LSM-tree，索引树的大小伴随着下标的增加而增大，其中C0是驻留在内存中的，其他则是在磁盘上。在所有的组件对(Ci-1,Ci)之间都有一个异步的rolling merge过程负责在较小的组件Ci-1超过阈值大小时，将它的记录移到Ci中。一般来说，为了保证LSM-tree中的所有记录都会被检查到，对于一个精确匹配查询和range查询来说，需要访问所有的Ci组件。当然，也存在很多优化方法，可以使搜索限制在这些组件的一个子集上。

首先，如果生成逻辑可以保证索引值是唯一的，比如使用时间戳来进行标识时，如果一个匹配查找已经在一个早期的Ci组件中找到时那么它就可以宣告完成了。再比如，如果查询条件里使用了最近时间戳，那么我们可以让那些查找到的值不要向最大的组件中移动。当merge游标扫描(Ci,Ci+1)对时，我们可以让那些最近某个时间段(比如τi秒)内的值依然保留在Ci中，只把那些老记录移入到Ci+1。在那些最常访问的值都是最近插入的值的情况下，很多查询只需要访问C0就可以完成，这样C0实际上就承担了一个内存缓冲区的功能。[23]中也使用了这一点，同时这也是一种重要的性能优化。比如，用于短期事务UNDO日志的索引访问模式，在中断事件发生时，通常都是针对相对近期的数据的访问，这样大部分的索引就都会是仍处在内存中。通过记录每个事务的启动时间，就可以保证所有最近的τ0秒内发生的事务的所有日志都可以在C0中找到，而不需要访问磁盘组件。

2.3 Deletes，Updates and Long-Latency Finds in the LSM-tree

需要指出的是删除操作可以像插入操作那样享受到延迟和批量处理带来的好处。当某个被索引的行被删除时，如果该记录在C0树中对应的位置上不存在，那么可以将一个删除标记记录(delete node entry)放到该位置，该标记记录也是通过相同的key值进行索引，同时指出将要被删除的记录的Row ID(RID)。实际的删除可以在后面的rolling merge过程中碰到实际的那个索引entry时执行：也就是说delete node entry会在merge过程中移到更大的组件中，同时当碰到相关联的那个entry，就将其清除。与此同时，查询请求也必须在通过该删除标记时进行过滤，以避免返回一个已经被删除的记录。该过滤很容易进行，因为删除标记就是位于它所标识的那个entry所应在的位置上，同时在很多情况下，这种过滤还起到了减少判定记录是否被删除所需的开销{!比如对于一个实际不存在的记录的查找，如果没有该删除标记，需要搜索到最大的那个Ci组件为止，但是如果存在一个删除标记，那么在碰到该标记后就可以停止了}。对于任何应用来说，那些会导致索引值发生变化{!比如一条记录包含了ID和name，同时是以ID进行索引的，那么如果是name更新了，很容易，只需要对该记录进行一个原地改动即可，但是如果是ID该了，那么该记录在索引中的位置就要调整了，因此是很棘手的}的更新都是不平凡的，但是这样的更新却可以被LSM-tree一招化解，通过将该更新操作看做是一个删除操作+一个插入操作。

还可以提供另一种类型的操作，可以用于高效地更新索引。一个称为断言式删除(predicate deletion)的过程，提供了一种通过简单地声明一个断言，就可以执行批量删除的操作方式。比如这样的一个断言，删除那些时间戳超过20天的所有的索引值。当位于最大组件里的受断言影响的记录，通过日常的rolling merge过程进入到内存时，就可以简单地将他们丢弃来实现删除。另一种类型的操作，long-latency find，对于那些可以等待很长时间(所需等待的时间实际上是由最慢的那个merge游标的速度决定的)的查询来说，它提供了一种高效地响应方式。通过向C0中插入一个find note entry，它被移入到更大的组件的过程实际上也就是该查询执行的过程，一旦该find note entry到达了LSM-tree中最大的那个组件的对应位置，该long-latency find所对应的那些匹配的RID列表也就生成完毕了。

3 Cost-Performance and the Multi-Component LSM-Tree
本节我们会从一个两组件LSM-tree开始分析下LSM-tree的性价比。同时会将LSM-tree与具有与之类似的索引规模的B-树进行对比，比较下它们在大量插入操作下的IO资源利用情况。正如我们将在第5节所述的那样，其他的基于磁盘的访问方式在插入新索引节点所需的IO开销上都基本上与B-树类似。我们在此处对LSM-tree和B-树进行比较的最重要的原因是这两个结构很容易比较，它们都在叶子节点上为每个以特定顺序索引的记录行保存了一个entry，同时上层目录信息可以沿着一系列页面大小的节点将各种访问操作进行指引。通过与低效但是很好理解的B-树的对比分析，对于LSM-tree在新节点插入上的所具有的IO优势的分析，可以更好地进行表达。

在3.2节中，我们会比较IO开销，并将证明两组件LSM-tree的开销与B-树的开销的比值实际上两个因子的乘积{!即3.2节中的公式3.4}。第一个因子， ，代表了LSM-tree通过将所有的IO以multi-page blocks进行得到的优势，这样通过节省大量的寻道和旋转延迟可以更有效地利用磁盘磁臂。COSTπ代表了磁盘以multi-page blocks为单位读写一个page时的开销，COSTp则代表了随机读写一个page时的开销。第二个因子是1/M，代表了在merge过程中的批量处理模式带来的效率提升。M是从C0中merge到C1中的一个page-sized的叶节点中的记录的平均数目。对于B树来说，每条记录的插入通常需要对该记录所属的节点进行两次IO(一次读出一次写入)，与此相比，可以向每个叶子中一次插入多条记录就是一个优势。根据5分钟法则，例1.2中的叶子节点在从B树中读入后之后短暂地在内存中停留，在它被再一次使用时它已不在内存了。因此对于B树索引来说就没有一种批量处理的优势：每个叶节点被读入内存，然后插入一条记录，然后写出去。但是在一个LSM-tree中，只要与C1组件相比C0组件足够大，总是会有一个批量处理效果。比如，对于16字节的索引记录大小来说，在一个4Kbytes的节点中将会有250条记录。如果C0组件的大小是C1的1/25，那么在每个具有250条记录的C1节点的Node IO中，将会有10条是新记录{!也就是说在此次merge产生个node中有10条是在C0中的，而C0中的记录则是用户之前插入的，这相当于将用户的插入先暂存到C0中，然后延迟到merge时写入磁盘，这样这一次的Node IO实际上消化了用户之前的10次插入，的确是将插入批量化了}。很明显，由于这两个因素，与B-树相比LSM-tree效率更高，而rolling merge过程则是其中的关键。

用来代表multi-page block比single-page的优势之处的实际上是个常量，为了使它生效我们无需对LSM-tree的结构进行任何处理。但是merge中的1/M的批量模式效率是跟C0和C1的大小之比成比例的；与C1相比，C0越大，效果越好；某种程度上说，这意味着我们可以通过使用更大的C0来节省额外的磁盘磁臂开销，但是这也需要更大的内存开销来容纳下C0组件。这也是在使用LSM-tree时需要考虑的，会在3.3节中对此进行研究。一个三组件LSM-tree具有一个内存组件C0和两个基于磁盘的组件C1和C2，并且随着组件大小随下标增加而增大。这样，除了C0和C1之间会有一个rolling merge过程，在C1和C2之间也会存在一个rolling merge过程，来负责在小的组件达到阈值大小时，将记录从小的组件中移到大的组件中。三组件LSM-tree的优势在于，它可以通过选择C1的大小来实现C0和C1以及C1和C2之间的比率大小来提高批处理效率。这样C0的大小就可以变得更小，可以大大地降低开销。{!因为在只有C0和C1的情况下，C1的大小有一个硬性要求，它必须能够容得下所有的记录，这样C0的大小选择就没有多少自由，而引人C2后，我们可以利用C2来保证可以存储下所有的记录，而C1就可以用来调整与C0的比例，而它就可以小点，这样由于目标是为了让C0/(C1+C0)尽量小，那么C0也可以变得小点就可以达到两组件下的效果}。

总结：为什么使用多组件？因为当C0相对于C1太小时，如果只使用两组间，批处理效果比较差。由于C1中一个叶节点一次性写入，所以批处理的效果 = C1叶节点中记录数量 * (C0 / C1)（参考上文第3节）

Dictionary Compression

https://levy5307.github.io/blog/dictionary-compression/

Dictionary compression

The compression techniques we have seen so far replace individual symbols with a variable length codewords.
In dictionary compression, variable length substrings are replaced by short, possibly even fixed length codewords.
Compression is achieved by replacing long strings with shorter codewords.
The general scheme is as follows:
The general scheme is as follows:
• The dictionary D is a collection of strings, often called phrases. For completeness, the dictionary includes all single symbols.
• The text T is parsed into a sequence of phrases: T = T1T2 . . . Tz, Ti ∈ D. The sequence is called a parsing or a factorization of T with respect to D.
• The text is encoded by replacing each phrase Ti with a code that acts as a pointer to the dictionary.
Here is a simple static dictionary encoding for English text:
• The dictionary consists of some set of English words plus individual symbols.
• Compute the frequencies of the words in some corpus of English texts. Compute the frequencies of symbols in the corpus from which the dictionary words have been removed.
• Number the words and symbols in descending order of their frequencies.
• To encode a text, replace each dictionary word and each symbol that does not belong to a word with its corresponding number. Encode the sequence of number using γ coding.

pegasus load balance

https://levy5307.github.io/blog/pegasus-load-balance/

Pegasus的负载均衡由meta server进行全局控制，其最小单元是replica。具体分为以下两个方面：

cure：当某些原因导致一个replica groupo不满足一主两备时，meta server会根据相应的策略进行调整，其中包括把不足的备份补全，或者把多余的备份剔除。这种策略叫做cure
balancer: meta server会定期所有replica server节点的replica情况做评估，当其认为replica在节点分布不均衡时，会将相应replica进行迁移。

如下两篇文章分别对这两种情况进行了介绍。

cure
balancer

C++返回值优化的小试验

https://levy5307.github.io/blog/cpp-return-value-optimization/

之前知道C++有返回值优化，但是一直有点不太敢用，生怕用不好就会导致性能问题。最近本着刨根问底的态度，亲自写代码试验了一下。

测试环境：gcc (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0

测试代码如下：

class Str
{
private:
int size;
public:
Str() { std::cout <<

User Specified Compaction

https://levy5307.github.io/blog/user-specified-compaction/

User Specified Compaction

Summary

In pegasus, sometimes we should add user specified compaction policy to reduce disk usage. This RFC proposes a user specified compaction design.

Design

Add two classes named with compaction_operation and compaction_rule.

compaction_filter_rule represents the compaction rule to filter the keys which are stored in rocksdb.
There are three types of compaction filter rule:

hashkey rule, which supports prefix match, postfix match and anywhere match.
sortkey rule. Just like hashkey rule, it also supports prefix match, postfix match and anywhere match.
ttl rule. It supports time range match with format [begin_ttl, end_ttl]

compaction_operation represents the compaction operation. A compaction operation will be executed when all the corresponding compaction rules are matched.
There are two types of compaction filter rule:

delete. It represents that we should delete this key when all the rules are matched.
update ttl. It represents that we should update ttl when all the rules are matched.

Finally, we should save the information about user specified compaction in app env. In order to make these information can still be retrieved after the machine is restarted.

Class Diagram

Here is the class diagram for user specified compaction.

      ┌─────────────┐                               ┌──────────────┐
      │   compact   ├───────────────────────────────►    compact   │
      │  operation  │                               │     rule     │
      └──────▲──────┘                               └───────▲──────┘
             │                                              │
   ┌─────────┴─────────┐                  ┌─────────────────┼──────────────────┐
   │                   │                  │                 │                  │
   │                   │                  │                 │                  │
   │                   │                  │                 │                  │

┌──────┴─────┐ ┌─────┴──────┐ ┌──────┴──────┐ ┌──────┴──────┐ ┌──────┴──────┐
│ │ │ │ │ │ │ │ │ │
│ update ttl │ │ delete │ │ hashkey rule│ │ sortkey rule│ │ ttl rule │
│ │ │ │ │ │ │ │ │ │
└────────────┘ └────────────┘ └─────────────┘ └─────────────┘ └─────────────┘

SpanDB

https://levy5307.github.io/blog/spandb/

KV存储支持了很多关键应用和服务。他们在内存中执行快速处理，但是仍然经常受到IO性能的限制。最新出现的高速商用NVMe SSD推动了新的KV系统设计，以利用其超低延迟和高带宽的优势。同时，将整个数据库扩展到该高端SSD需要很多资金。并且我们的研究表明，当前基于LSM的KV存储并未完全发挥NVMe的潜力，例如在50%写负载的情况下，在Optane PX4800X上部署的RocksDB与SATA SSD相比吞吐仅仅提高了23.58%。特别的，普通的KV存储设计的IO路径很严重的未充分利用超低延迟的NVMe SSD，尤其是对于small write。例如，通过ext4带来的延迟比通过英特尔SPDK接口高6.8-12.4倍。

在这个背景下，SpanDB出现了。它允许将大量数据托管在更便宜、更大的SSD上，同时将WAL和LSM-tree的前几层定位在更小、更快的NVMe上。为了更好的利用NVMe，SpanDB通过SPDK提供高速、并行的WAL写入，并启用异步请求处理以减轻线程间的同步开销，并通过基于polling-based IO高效工作。

SpanDB Overview

上图为SpanDB的整体架构图

将磁盘分为SD和CD。SD意为speed disk，即高速磁盘，这里是指NVMe。CD意为capacity disk，是低速大容量盘。

  将WAL和LSM的top n层放到SD里。因为WAL直接影响写请求的延迟和吞吐，而WAL通常是GB级别的，并且LSM的top n层是热数据，所以这两者放入SD。这里的n是根据负载情况动态自适应的，并非将CD简单的作为溢出层
  将LSM的剩余层放入CD中，这一部分数据大多是冷数据，且数据量大。将这一部分数据放入CD主要是基于成本考虑

通过SPDK通过使用SPDK直接访问NVMe SSD设备，绕过文件系统和Linux IO stack。SPDK意为Storage Performance Development Kit，其通过引入以下技术，实现高性能存储技术:

  将存储用到的驱动转移到用户态，避免系统调用
  支持零拷贝
  避免在IO链路上使用锁
  使用轮询硬件，而不是中断。断模式带来了不稳定的性能和延时的提升

Design And Implementation

Pegasus安全认证

https://levy5307.github.io/blog/pegasus-security/

在以往的Pegasus版本中，我们没有实现安全认证，这就意味着任何人只要知道Pegasus集群的地址，就可以访问Pegasus中的数据并对其进行修改，显然这会带来很大的安全隐患。所以我们在2.2.0版本中发布了Pegasus安全认证功能。

安全认证分为两个部分：身份认证和权限控制。身份认证用于识别用户的身份，对于非认证用户拒绝访问。而权限控制则基于身份认证获取到的用户身份，确定该用户拥有什么样的权限。

身份认证

Pegasus的身份认证功能是基于Kerberos实现的。Kerberos是由MIT提出的一种网络身份验证协议，其通过使用密钥加密技术为客户端/服务器应用程序提供强身份验证。但是它的缺点在于接口很琐碎，对用户不是十分友好。针对这个问题，我们采用了SASL+Kerberos的方式，Kerberos提供安全认证机制，而SASL提供了一个更为通用的标准接口。

由于SASL支持多种不同的mechanism，因此Pegasus需要实现客户端和服务端之间沟通机制，用于获取双方都支持的mechanism，并根据选取的mechanism和客户端的身份信息进行身份认证，其具体执行流程图如下：

从上图中可以看到，我们将客户端与服务端的沟通分为三个阶段：

第一阶段主要用于交换双方都支持的mechanism，并最终选取一个双方都支持的mechanism。

第二阶段主要用于对客户端的身份进行认证，这一段是SASL所规定的行为，具体可以参考SASL规范，这里不再赘述。

第三阶段则是身份认证成功后，客户端与服务端之间的正常rpc调用。

这里需要注意的是，在第一阶段或者第二阶段中如果发生了错误，则会导致认证失败、连接断开，也就无法开展后续的rpc调用。
另外，为了提供server端身份认证的执行效率，我们使用了credential cache。然而由于kerberos的credential是有生命期限的，因此我们需要在credential失效之前对其进行自动更新。为了实现这个功能，我们开启了一个后台定时任务对credential进行更新，当然，该定时周期也是根据当前credential的剩余生命时间计算而来。

权限控制

有了身份认证，我们解决了“用户是谁”的问题，然而对于“用户拥有什么样的权限”的问题，身份认证是无能为力的。为此，我们实现了一套基于用户身份信息的权限控制策略。

在Pegasus权限控制中，我们将用户的请求分为三类：

查看集群信息


表读写


集群控制

同时，将用户的角色分为三类：

super user。其拥有上述所有三种操作权限，这里设立一个super user主要是为了我们运维人员以及开发的内部工具对集群进行访问与操作。


表owner。表owner代表的是申请表的用户，其拥有表的读写权限和查看集群信息权限。


其他用户。其他用户只能够执行查看集群信息的操作，其他操作一概没有权限。

具体的角色和请求的权限对应关系如下表：

   
  super user
  表owner
  其他用户




  查看集群信息
  √
  √
  √


  表读写
  √
  √
  ×


  集群控制
  √
  ×
  ×

总结

实现了身份认证和权限控制功能，Pegasus便拥有了很高的安全性。这样一些对数据隐私要求高的用户便可以放心的接入Pegasus，而不用担心数据被读取和篡改的问题发生。

Pegasus Balancer

https://levy5307.github.io/blog/pegasus-balancer/

背景介绍

在当前pegasus balancer的实现中，meta server会定期对所有replica server节点的replica情况做评估，当其认为replica在节点分布不均衡时，会将相应replica进行迁移。

在balancer生成决策过程中需要考虑的因素有：

对于任意表，其partition在节点上的分布要均衡，这其中包括如下几个方面：

  某个partition的三个副本不能全部落在一个节点上
  primary的数量要均摊
  secondary的数量也要均摊

如果发现primary分配不均衡时，首先考虑的策略应该是对primary进行角色切换，而不是直接就进行数据拷贝
不仅要考虑节点间的负载均衡，也要尽量保证节点内各个磁盘的replica个数是均衡的

魔改Ford-Fulkerson

上面讲到，当primary分布不均衡时，首先考虑的策略是对进行角色切换，也就是说，需要寻找到一条从路径，将primary从“多方”迁移到“少方”。将迁移的primary数量作为流量，很自然的我们就想到了Ford-Fulkerson，即：

寻找一条从source到sink的增广路径
按照增广路径修改各边权重，形成残差网络
在残差网络中继续步骤1，直到找不到增广路径为止。

但是我们又不能直接套用Ford-Fulkerson。原因在于第2步中，按照Ford-Fulkerson，增广路上的一条权重为x的边意味着从A流向B的primary的个数为x，此时形成残差网络中，该边的权重需要减去x，然而其反向边也同时增加x（反向边的作用用于提供一个调整的机会，因为之前形成的增广路径很有可能不是最大流，该反向边用于调整此前形成的增广路径，具体参考Ford-Fulkerson算法）。但是在我们的模型中，反向边增加x是不合理的，例如，对于Partition[Primary: A, Secondary: (B, C)]，Primary从A向B流动，最终使得Partition成为[Primary: B, Secondary: (A, C)]，这时意味着：

A到B的流量减少
A到C的流量减少
B到A的流量增加
B到C的流量增加

这显然与Ford-Fulkerson的残差网络的反向边的权重变化是不同的。
所以我们将算法修改如下：

按照当前的partition分布生成图结构，并根据Ford-Fulkerson算法，找到一条增广路径
根据找到的增广路径，构造primary角色切换的决策动作。并在集群中执行该动作，生成新的partition分布
3.根据新的partition分布，迭代步骤1，一直到不能找到增广路径
从上面可以看出，该算法主要是对第2步进行了修改，并非像Ford-Fulkerson算法那样简单的进行边权重修改。

NOTE：我们在执行Ford-Fulkerson进行primary迁移的时候，是针对单个表的，也就是说构造网络、执行角色切换都是针对单个表的，当要对多个表进行迁移，则只要循环对所有表各执行上述流程就可以了。

当然，有可能我们执行完上述算法后，集群负载仍然不平衡，此时说明通过primary切换已经无法达到集群平衡了，那么接下来就必须要进行primary迁移了(即背景介绍中讲到的进行数据拷贝)。
同样，在执行完primary迁移后，也要对secondary进行迁移。但是secondary迁移就不用像primary这么复杂还要考虑角色切换了（因为在做primary迁移时能切换的已经切换过了），此时直接进行数据拷贝就可以了。
下面我们分别对这几个点进行详细讲解。

Primary负载均衡
Primary角色切换是Pegasus balancer整体逻辑的核心部分，先看一下这一块是如何实现的。

构造Ford-Fulkerson图

根据上文所述，primary角色切换采用的是改进Ford-Fulkerson来实现的，Ford-Fulkerson执行的第一步就是要构造partition分布图，其构造方式如下：

记N为某个表partition的数目，M为replica server节点数目
图中增加两个点source和sink，分别代表源点和汇点
如果某个节点A上primary的数目x >= N/M, 则从source到A添加一条有向边，边的权重为x - N/M，表示可以从该节点向外流出x - N/M个primary；反之，如果节点B上的primary数目y < N/M，则添加一条B到sink的有向边，其权重为N/M - y，表示可以向B流入N/M - y个primary
如果节点A上有一个primary，其对应的secondary在结点B上，则为A->B的有向边的权重+1

上图所示为在3 replica server集群上，一个7分片表的图情况：

由于N=8, M=3，则N/M = 2
由于只有节点B上的primary数量>2，则源点只指向B，其权重为B节点上的primary数量 - N/M = 6 - 2 = 4；其他节点则指向汇点t，其权重均为1
节点B上有6个primary其相应的secondary在C和D上，所以B->C和B->D上权重等于6。同理可以得出D->B, C->D, D->C的权重均为1

获取增广路径

另外，为了减少primary切换的数量，我们在寻找最大流时，需要寻找到最小费用最大流的增广路径，也就是说：

获取最大的流
在保证获取了最大流的前提下，选择费用最小的那条路径

为了达到这个目的，我们采用了dijstra算法来查找增广路经，以获取费用最小的路径。这里粘贴上代码，并加上必要的注释以帮助理解
void shortest_path(std::vector &visit,
std::vector &flow,
std::vector &prev,
std::vector<std::vector> &network)
{
int pos, max_value;
flow[0] = INT_MAX;

int graph_nodes = network.size();
while (!visit[graph_nodes - 1]) {
    pos = -1, max_value = 0;
    for (int i = 0; i != graph_nodes; ++i) {
	    // 在这里获取最大的流，用于满足1
        if (visit[i] == false && flow[i] > max_value) {
            pos = i;
            max_value = flow[i];
        }
    }

    if (pos == -1)
        break;

    visit[pos] = true;
    for (int i = 0; i != graph_nodes; ++i) {
	    // 这里的条件主要用于满足2，也就是说，已经获取了最大流了，保证当前选择的路径是最小费用的路径
        if (!visit[i] && std::min(flow[pos], network[pos][i]) > flow[i]) {
            flow[i] = std::min(flow[pos], network[pos][i]);
            prev[i] = pos;
        }
    }
}

}

primary角色切换

当获取到增广路径之后，接下来的工作则是按照获取到的路径进行primary角色切换了。在了解具体算法前，先看一下几个变量与结构的定义：

typedef std::map<std::string, int> disk_load: 表示磁盘负载，其key是disk tag，value则是该磁盘上的primary/partition count
std::vector prev: 表示该增广路径，prev[i]表示该路径上节点i的前置节点

算法具体执行步骤如下：

依次遍历增广路径中的每个节点(current)，并获取其在增广路径上的相邻节点(prev)
获取current和prev两个节点的磁盘负载(disk_load *current_load和disk_load *prev_load)
对prev中的每一个primary，查找其在current中是否有相应的secondary，如果有的话，则将该primary放入到potential_moving中，表示有可能move的primary
通过增广路径，可以获取到从prev应该move多少个primary到current上(plan_moving)
对于potential_moving中的所有的primary，选择plan_moving个磁盘负载差最大的primary(prev中primary所在的磁盘的负载 - current中相应的secondary所载磁盘的负载)，将选择出来的这些primary进行角色切换。这样选择的优点是不仅可以优化节点间的负载，同时还可以兼顾到磁盘的负载

copy primary

当没有成功获取增广路径时，则说明简单通过角色切换的方式已经无法达到负载均衡了，必须通过迁移primary来实现了。
迁移primary算法的实现相对简单，其具体执行步骤如下：

将节点按照primary数量按从小到大排序，得到pri_queue
对pri_queue上，id_min从左到右，id_max从右到左移动，如下图所示:
+------+------+------+------+------+------+------+------+
| |
V V
id_min --> <--id_max

对当前id_max上的所有primary，分别找到其对应的磁盘并获取其磁盘负载，选择负载最大的磁盘及其对应的primary，进行迁移
依次将id_min和id_max进行移动，重复上述步骤。直到id_min节点上的primary数量 >= N/M

NOTE： 上述构建图、查找增广路径、move primary和copy primary步骤都是针对一个表进行的操作，对于集群上的多个表，都要执行一次上述步骤。

secondary负载均衡
上述讲解了primary负载均衡，当然secondary也同样需要负载均衡，否则的话可能会出现不同节点上primary均衡，但是partition总数不均衡的情况。
因为在做primary迁移时已经做过角色切换了，secondary迁移就不用像primary这么复杂，不用考虑角色切换的问题了。此时直接进行copy就可以。因此secondary的负载均衡，直接采用copy primary一样的算法实现，这里不再赘述。
同理，secondary也要对所有表分别进行负载均衡。

Conlusion
当然对所有表执行完上述步骤也只是查找了一次增广路径而已，我们知道对于最大流问题，可能要查找多个增广路径。所以我们需要根据执行后集群是否处于load balance的状态来判断是否还要继续查找增广路径。

Backup Request

https://levy5307.github.io/blog/backup-request/

背景
在当前的pegasus实现中，由于向secondary读取会导致不一致的情况发生，所以目前Pegasus仅仅支持对primary副本的读取。但是在某些情况下（例如：负载均衡、热点写入等）经常会导致primary不稳定。所以我们希望在primary不稳定时能够读取secondary，通过牺牲部分强一致性来降低请求的长尾并提高系统的可用性。backup request便是用来实现此功能的。

设计实现

backup reqeust的实现原理比较简单：当client向primary发送请求后，如果经过一段时间延时后（通常是p999），如果其response仍然没有返回，则随机选择一台secondary并向其发送backup request。最后获取最快返回来的response进行处理。

这里发送secondary请求的延时我们建议选择p999，因为backup request操作是用来实现消除长尾的，并不是提升集群性能的。如果将该值设置过低，则会由于backup request的请求量过大而导致集群压力增大（假设选择p50作为其延时，这样便会有50%的请求向secondary发送请求，系统负载便会增大50%）。

如何使用
在pegasus java client中，我们增加了一个接口，通过该接口可以打开某个表的backup reqeust功能。其实现如下：
public PegasusTableInterface openTable(String tableName, int backupRequestDelayMs) throws PException;

相比于老版本的openTable接口，我们增加了一个backupRequestDelayMs参数。这个参数便是上文所指的时延，即：向primary发送请求，如果过了backupRequestDelayMs毫秒response仍没有返回，则向secondary发送backup request。需要注意的是，backupRequestDelayMs <= 0代表禁用backup reqeust功能。

另外在老版本的openTable接口中，backup request功能默认是关闭的。

性能测试

set/get operation:
| test case | enable backup request | qps | read/write propotion | read avg | read p95 | read p99 | read p999 | read p9999 | write avg | write p95 | write p99 | write p999 | write p9999 |
| —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | — |
| 3-clients 15-threads | no | 1 : 3 | 7076 | 880.6512836149132 | 428.0 | 727.0 | 138495.0 | 988671.0 | 2495.0710801540517 | 6319.0 | 9023.0 | 36319.0 | 531455.0|
| 3-clients 15-threads | yes, delay 138ms | 1 : 3 | 6987 | 1010.1412488662884 | 403.0  | 7747.0 | 138751.0 | 153599.0 | 2476.104380444753 | 6859.0 | 9119.0 | 13759.0 | 185855.0 |
| 3-clients 100-threads | no | 1 : 0 | 140607 | 707.98960978 | 1474.0 | 2731.0 | 5511.0 | 167551.0 | | | | | |
| 3-clients 100-threads | yes, delay 5ms | 1 : 0 | 77429 | 1288.01461934 | 2935.0 | 3487.0 | 6323.0 | 71743.0 | —- | —- | —- | —- | — |
| 3-clients 30-threads | no | 30 : 1 | 87198 | 306.9600544730426 | 513.0 | 805.0 | 4863.0 | 28271.0 | 1369.4669874672938 | 2661.0 | 5795.0 | 22319.0 | 51359.0 |
| 3-clients 30-threads | yes, delay 5ms | 30 : 1 | 88541 | 298.22470022339127 | 493.0 | 711.0 | 4483.0 | 18479.0 | 1467.6130963728997 | 3263.0 | 6411.0 | 17439.0 | 50975.0 |

Multi-get/Batch-Set operation:
| test case | enable backup request | qps | read/write porpotion | read avg | read p95 | read p99 | read p999 | read p9999 | write avg | write p95 | write p99 | write p999 | write p9999 |
| —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | — |
| 3-clients 7-threads | no | 20 : 1 | 24113 | 200.37956913733476 | 277.0 | 410.0 | 2317.0 | 21647.0 | 2034.1923768463382 | 4283.0 | 6427.0 | 18271.0 | 62687.0 |
| 3-clients 7-threads | yes, deley 2ms | 20 : 1 | 23756 | 197.48540031650361 | 268.0 | 351.0 | 2173.0 | 5759.0 | 2187.199077764627 | 4531.0 | 6551.0 | 21551.0 | 63999.0 |
| 3-clients 15-threads | no | 20 : 1 | 30980 | 236.7482510418767 | 348.0 | 526.0 | 3535.0 | 25695.0 | 5361.380053671262 | 14087.0 | 20223.0 | 40639.0 | 90815.0 |
| 3-clients 15-threads | yes, delay 3ms | 20 : 1 | 30483 | 244.1182599024727 | 386.0 | 540.0 | 3105.0 | 13287.0 | 5377.992155339365 | 14119.0 | 19535.0 | 31311.0 | 103103.0 |

Cassandra

https://levy5307.github.io/blog/Cassandra/

Cassandra的目标是构建在上百台的节点之上（可能会跨越多个不同的data center）。Cassandra用于设计满足Facebook的Inbox Search的存储需求，这要求该存储系统需要能够处理非常高的写吞吐，每天数十亿的写入，以及随着用户规模增长而扩容。并且由于用户根据地理位置可能被不同的data center服务，所以在不同的data center之间复制数据是很关键的。

Data Model

Cassandra中的表示一个分布式的、由key索引的多维map。value是一个高度结构化的object。row key是一个string类型数据，没有大小限制（通常是16-36 bytes大小）。对于一个replica中的单行读写，不管其涉及到的列有多少个，其操作都是原子的。Column可以组成一个set叫做column family，这与Bigtable很像。Cassandra有两种column family，分别是Simple column family和Super column family。其中Super column family可被视为在一个column family之中的column family

此外，应用可以指定Super column family和Simple column faily中的column排列顺序，包括按时间排序和按名字排序。时间排序在Inbox Search中得到了应用，因为其需要按照时间顺序展示结果。column family中的任一column都需要通过column_family:column的形式来访问。在一个super column family中的列需要通过column_family:super_column:column的形式来访问。代表性的应用使用一个专用的Cassandra集群，并且将其作为他们服务的一部分，尽管Cassandra支持多个表，并且每个表都有其自己的schema。

API

Cassandra API包括以下三种简单的方法：

insert(table, key, rowMutation)

get(table, key, columnName)

delete(table, key, columnName)

columnName可以是一个column family中的指定的column、一个column family，一个super column family或者一个super column中的column

System Architecture

对于运行在生产环境中的存储系统是非常复杂的。出了实际数据的持久化之外，存储系统还需要包括如下特性：scalable and robust solutions of load balance, membership and failure detection, failure recovery, replica synchronization, overload handling, state transfer, concurrency and job scheduling, request marshalling, request routing, system monitoring and alarming, and configuration management. 在本文中不讲述上述这些细节，主要集中在Cassandra中应用的核心的分布式技术： partitioning, replication, membership, failure handling and scaling。所有这些模块协同起来处理读写请求。一个对于key的读/写请求呗路由到Cassandra中的节点，该节点决定该key所在的副本。对于写入，系统将该请求路由到所有的副本，并且等待一定数量的副本的写入完成的ack。对于读取，根据client需要的一致性保证，系统可能会将请求路由到最近的副本，或者路由到所有的副本，等待一定数量的response。

Partitioning

Cassandra的一个关键特性是其拥有逐渐扩展的能力，这就需要能够动态的为数据在集群的一系列的节点上分区的能力。Cassandra使用一致性hash来对数据进行分区，该hash函数使用了保序hash函数。一致性hash的细节在这里就不细说了，可以参考文章数据分片。

基础的一致性hash有几个挑战：

每个节点在环上的位置时随机的，这会带来不同节点不统一的数据和负载分布


它忽略了节点的异构性问题

面对这些问题，通常有两种解决办法：

为每个节点分配环上的多个位置


分析换上的负载情况，然后具有轻负载的节点从环上向前移动，用以减轻高负载节点的负载

Cassandra选择第二种方法，因为它的设计和实现更容易驾驭，并且可以帮助负载均衡作出更加确定的选择。

Replication

pegasus load balance重构

https://levy5307.github.io/blog/load-balance-refactor/

背景

checker_load_balancer：用于功能测试
simple_load_balancer：主要用于cure，另外还有执行load balancer计划
greedy_load_balancer：用于生成load balancer计划。当前只有app load balance，后续要添加cluster load balance

重构

首先，把simple_load_balancer中cure的功能抽出来放入一个新创建类partition_healer，该类专门用于cure。load balance相关的功能放入greedy_load_balancer。这样simple_load_balancer便可以删掉。

另外，由于要加入cluster load balancer，不希望将这部分功能加入greedy_load_balancer了，因为这样会导致greedy_load_balancer过于臃肿。并且之前和昱晨聊过，加入了cluster load balancer之后，暂时先不希望把原先的load balance删掉，所以短期内两者应该会并存。
所以想将其抽出来放入一个单独的类中。

考虑了如下几种实现思路：

继承

将greedy_load_balancer的功能迁移到app_load_balancer中，集群负载均衡功能添加到cluster_load_balancer中。对于两者之间的公共代码，放入greedy_load_balancer。

问题：由于app load balance和cluster load balance策略同时存在，需要通过配置在两者之间切换，这样便将这些细节暴露给了meta_service。我希望这些细节对meta_service是透明的，load balance的问题，在自己内部解决，与meta_service无关。

Decorator

由于原有的负载均衡策略还保留，只是新增了一个cluster负载均衡功能，自然就想到了Decorator。实现一个新类cluster_load_balancer，作为greedy_load_balancer的Decorator，其内部可以通过一个变量来配置是使用cluster_load_balancer::balance还是greedy_load_balancer::balance，该变量可以通过远程变量控制。meta_service内部创建一个cluster_load_balancer就可以了。

问题：cluster_load_balancer和greedy_load_balancer里有大量重复代码和公用成员变量，使用这种方式不好复用。对于这种复用的情况，最好还是用继承

strategy

实现一个新的接口load_balance_policy，其有两个子类，分别实现app load balance和cluster load balance，在greedy_load_balance内部通过一个变量控制使用哪个policy。
meta_service持有一个greedy_load_balancer对象，无需关心使用哪个policy

最后

最后实现类图如下：

另外

有大量的重复代码如下：

for (const auto &kv : apps) {
const std::shared_ptr<app_state> &app = kv.second;
if (is_ignored_app(kv.first)) {
continue;
}
if (app->status != app_status::AS_AVAILABLE || app->is_bulk_loading || app->splitting())
continue;

bool enough_information = primary_balancer_per_app(app);
if (!enough_information) {
    return;
}
if (!balance_checker) {
    if (!t_migration_result->empty()) {
        if (_balancer_in_turn) {
            return;
        }
    }
}

}

可以使用visitor进行重构如下：
void for_apps_balance(const app_mapper &apps, const std::function<void(const std::shared_ptr<app_state> &)> &visitor) {
const std::shared_ptr<app_state> &app = kv.second;
if (is_ignored_app(kv.first)) {
continue;
}
if (app->status != app_status::AS_AVAILABLE || app->is_bulk_loading || app->splitting())
continue;

bool enough_information = visitor(app);
if (!enough_information) {
    return;
}
if (!balance_checker) {
    if (!t_migration_result->empty()) {
        if (_balancer_in_turn) {
            return;
        }
    }
}

}

调用代码：
for_apps_balance(apps, primary_balancer_per_app);
for_apps_balance(apps, copy_secondary_per_app);
for_apps_balance(apps, move_primary_per_app);

TODO: 其他待补充

关于数据分区的一些思考

https://levy5307.github.io/blog/thinking-about-partition/

目前团队所做的kv存储，对于数据分区所采用的方式是hash分区，即对key取hash值，对获取的hash值对partition取模。即：hash(key) % partition_count。

最近在思考这种方式的实现问题。

显然，这种方式由于对于连续的key，有可能获取到不同的hash值，所以并不能分配到同一个分片上。这样对于范围查询非常不友好，需要向所有的分片发送请求才能保证获取到该范围内的所有key。所以为了解决这个问题，团队项目采用了两级key的方式，即将key分为hashkey和sortkey，hashkey用于分区映射，同一个hashkey按照sortkey排序。这样同一个hashkey下的sortkey便可以存储于同一个partition下，即同一个hashkey下的sortkey可以支持范围查询。但是这样也带来一些问题：

hashkey+sortkey的方式并不符合主流的kv接口设计(如redis)，导致接口设计完全不同。


这种方式相当于一定程度上把数据分区交给了用户，也就是说，如果用户使用不当，将大量sortkey放置于同一个hashkey下，很容易产生热点partition。

个人认为，要想支持范围查询，还不如直接使用基于key范围的分片（HBase所采用的方案）。

kerberos

https://levy5307.github.io/blog/kerberos-%E5%8E%9F%E7%90%86/

最初设计

!{最初设计图}(../images/kerberous-1.png)

上图所示，最原始版本的权限认证过程是非常简单的：当需要某个服务的时候，就通过用户名和密码去访问该服务来进行验证。

问题：该方案的问题是每个服务都需要保存每个用户的用户名和口令，如果某用户修改口令，则需要访问所有的服务进行修改

增加认证服务

用户和服务有口令，另外增加一个认证服务(暂时令认证服务名为Charon)，将所有口令保存在一个单独的**数据库中。当需要访问某个服务的时候，需要首先得到Charon的认证。

具体时序图如下：

!{}(../images/kerberous-2.png)

问题： 明文传输client口令，容易被截获

增加AS(票据授权服务)和TGT（票据授权票）

在该步骤中增加了AS，该AS仍然属于Charon的一部分。通过下图可以看出，增加了一个用户申请TGT的过程。 TGT表示票据授权表，当用户获取了TGT后，就有权通过TGT向Charon申请访问邮件服务等。

在该过程中，用户仅通过用户名去向AS申请TGT，AS收到该请求后通过用户名去对该用户进行认证，认证成功后返回一个通过用户口令加密的TGT。用户接收到后通过用户口令解密便可以获取该TGT。这样避免了用户口令在网络上传输，避免了用户密码的泄露。

!{}(../images/kerberous-3.png)

• 问题：* ticket永久有效，当ticket被盗时，其他人便可以冒充该client去获取其邮件等信息并一直使用下去。

为ticket增加有效期

!{}(../images/kerberous-4.png)

由上文可知：

ticket不能永久有效，
但是也不能是一次性的，因为这样的话会导致每次请求服务都要走一遍认证流程，复杂且低效。所以ticket必须可重用

所以为ticket增加了有效期，一定程度上避免了ticket被盗取的问题，

问题：

在ticket有效期内，ticket仍然可能被盗取利用。
由于Charon与client和邮件服务等交互都通过了口令加密所以可以认证，Charson发送来的信息不会是其他人冒充的，同理，由于client和服务之间没有口令，所以两者之间发送的任何信息都是不可信的

服务与client之间增加口令

所以解决办法就是为二者之间发送口令

只有同时盗取了ticket和加密了的验证器才能冒充，虽然ticket不可重用, 但是可以设置验证器不可重用，验证器生成不像ticket一样那么复杂。这样就可以解决被同时盗取的问题。

Percolator

https://levy5307.github.io/blog/percolator/

Background

在Google公司内部，对于海量索引数据的创建和实时更新是必须面对的问题。Map Reduce解决了海量索引数据的批量创建问题，但是其却不能支持对增量数据的实时更新，其每次需要对全量索引数据进行一次重新创建。并且由于文档在Google上能否被检索到取决于全量索引的创建时间，因此导致其被索引到的时间间隔较长。

因此Google内部缺少一个支持海量数据存储、支持并行随机读写、支持跨行事务的分布式数据库。

Design

Percolator为大规模的增量计算提供了两个抽象：基于随机访问仓库的的ACID事务、以及用于组织增量计算的observers

Pacifica In Pegasus

https://levy5307.github.io/blog/PacificA-In-Pegasus/

PacificA是微软实现的一款强一致性的分布式共识协议，具有简单易实现、可用性高的优点。Pegasus就是使用PacificA协议来维护多副本之间的复制。

之前有篇文章讲过PacificA的原理与理论，如有疑惑请移步PacificA(https://levy5307.github.io/blog/PacificA/)

Read & Write
根据PacificA算法，读操作的处理是比较简单的，其只需要primary在本地读取到最新的值就可以了，secondary并不参与其中，这里不再赘述。但是对于写则会复杂很多，因为需要经过主从之间的2PC来实现，这里主要对写做一些讲解。

写入流程如上图所示。这里加几点说明：

对于同一个replica的写处理是单线程的，也就是说，对于每一个replica，只有一个线程在处理写请求。


上图中的WAL分为private log和shared log，其中private log保存在内存中，而shared log在磁盘上。在pegasus中，每个replica对应一个RocksDB，由于一个机器上有多个replica，那么如果打开了RocksDB的WAL的话，写入的时候将会在多个文件之间切换，导致随机写。所以在Pegasus中采用了shared log的机制来替代RocksDB的WAL。但是使用shared log也有个问题，就是当recover一个replica的时候需要做log split操作。所以Pegasus采用了shared log + private log的方式，private log保存在内存中，当添加potential secondary时，直接使用private log，对于rivate log缺失的部分通过重放shared log补全。

未完成

Anna

https://levy5307.github.io/blog/Anna/

在现在KV存储系统中，有些设计成全球范围内分布式的，有些设计成单机的。然而在近些年都逐渐收敛到云上。基于这个背景，我们设计了一个可以在任何scale上都运行的很好的KV系统。针对该KV系统，我们发现了四个设计需求：

partition。为了实现data scaling当然需要partition。但是我们实现partition不仅需要云上跨机器的，也需要跨cpu核以提供更高性能。


multi-master replication。为了实现workload scaling，我们需要实现multi-master replication使用多线程来同时响应读写请求。


wait-free execution。为了更大化使用多核机器的硬件使用率和性能，我们需要实现wait-free execution。这意味着每个线程都是在做有意义的工作，而无需等待其他线程。


coordination-free一致性模型。为了支持更广范围的应用，我们需要实现一个广泛范围的coordinator-free一致性模型。

这篇论文描述了Anna的设计和实现，为跨scale设计提供了一套架构和经验：

Coordination-free Actors。我们可以确定coordination-free actor模型对于scale从单机多核到分布式都提供了很优秀的性能，好过当前最高水平，并且可以提供平滑的扩缩容容以及时得repartition更加具有弹性。


Lattice-Powered Coordination-Free Consistency。一致性代码很简短而且模块化：不同的一致性level仅有至多60行代码的区别。


Cross-Scale Validation。我们与其他横跨不同scale的KV系统进行了对比：单机的Redis和根据地理位置分片的Apache Cassandra。我们发现Anna的性能在任何scale下都具有很有竞争力的性能，并且还能提供不同等级的一致性。

Lattices

Anna的一个设计核心组件便是lattice的使用。lattice的重要性主要体现在下面两点：

lattice对于update的操作顺序不敏感。这意味着即使不同的副本执行不同的update次序，也能够保证一致性。


lattice的组合可以实现一系列范围的一致性。之前的研究表明coordinator-free不能够实现最强等级一致性，例如linearizability或者serializability，但是可以实现相对强等级的一致性，例如causality和read-committed。我们的贡献在于证明可以使用lattice可以实现很多不同等级的一致性。

Distributed state model

这一节描述了Anna的actor模型。每个actor使用率lattice维护了一个状态机。当时我们发现即使这样也不够高效。因为共享内存的同步操作会耗费很多性能，因此Anna中基于异步信息发送避免了使用共享内存

Limitations of shared-memory

大量的multi-core kv系统使用了共享内存将整个存储的状态在多个线程间共享：每个线程都可以进行读或者写。需要对读和写操作进行同步，来防止冲突产生。同步可以通过有锁或者无锁的方式来实现，然而不管是否有锁，都会影响竞争情况下的可扩展性，因为cache一致性带来的性能损耗。latice并没有改变上述情况，如果使用了共享内存，一样会有相应的同步开销。

Message-passing

message-passing结构由一系列的actor组成，每个actor运行在一个单独的cpu核上。每个actor维护自己的状态且其他actor不可访问。actor运行一个loop，循环从input queue中获取客户端的请求以及其他核发来的消息进行处理。由于每个actor只会处理自己的local state，所以避免了共享内存，因此也避免了同步操作

message-passing有两种管理key的选择：single-master和multi-master replication。

single-master replication。在该模式下，每个key都会指派给一个单独的actor。这防止了对一个key的同时修改，因此而保证了一致性。但是这将一个key的更新频率限制在了单个actor的更新频率。


multi-master replication。一个key会被复制到多个actor，每个actor读取或者更新其本地副本。这也分为两种模式：coordination和coordination-free：





coordination是指当更新一个key时，actors可以参与协调控制，使得update按照一个全局的顺序，尽管多个actor可以处理updates，然而全局有序的广播使得每个actor都将这些update按照相同的顺序进行处理。


coordination-free模式中，每个actor在本地处理请求，并且不会引入inter-actor communication。所有update的communication在timer被触发、或者actor的请求负载减少的情况下进行。

coordination-free的multi-master模式将会导致副本间的不一致，因为副本将会以不同的顺序处理请求。因此Anna引入了lattice，借助lattice可以避免不一致的情况。

Anna architecture

Backup Request

https://levy5307.github.io/blog/backup-request-investigation/

Backup request function can optimize the long tail problem of read delay, suitable for users with low consistency requirements.

Investigation

There are two ways to implement backup request.

Hedged requests
A client first sends one request to the replica believed to be the most appropriate, but then falls back on sending a secondary request after the first request has been outstanding for more than the 95th-percentile(or 99th-percentline, etc) expected latency. The client cancels remaining outstanding requests once the first result is received. This approach limits the additional load to approximately 5%(1%) while substantially shortening the latency tail. This approach limits the additional load to approximately 5%(1%) while substantially shortening the latency tail.

This approach limits the benefits to only a small fraction of requests(the tail of the latency distribution).

Tied requests
the client send the request to two different servers, each tagged with the identity of the other server (“tied”). When a request begins execution, it sends a cancellation message to its counterpart. The corresponding request, if still enqueued in the other server, can be aborted immediately or deprioritized substantially.

There is another variation in which the request is sent to one server and forwarded to replicas only if the initial server does not have it in its cache and uses cross-server cancellations.

This approach limits the benefits to not only the tail of the latency, but also median latency distribution. But it result in higher network load.

Reference

The Tail at Scale

backup request in brpc

Cpp Trivial

https://levy5307.github.io/blog/cpp-trivial/

A trivially copyable type
is a type whose storage is contiguous (and thus its copy implies a trivial memory block copy, as if performed with memcpy), either cv-qualified or not. This is true for scalar types, trivially copyable classes and arrays of any such types.

A trivially copyable class
is a class (defined with class, struct or union) that:

uses the implicitly defined copy and move constructors, copy and move assignments, and destructor.
has no virtual members.
its base class and non-static data members (if any) are themselves also trivially copyable types.
This class inherits from integral_constant as being either true_type or false_type, depending on whether T is a trivially copyable type.

A trivially default constructible type
is a type which can be trivially constructed without arguments or initialization values, either cv-qualified or not. This includes scalar types, trivially default constructible classes and arrays of such types.

A trivially default constructible class
is a class (defined with class, struct or union) that:

uses the implicitly defined default constructor.
has no virtual members.
has no non-static data members with brace- or equal- initializers.
its base class and non-static data members (if any) are themselves also trivially default constructible types.

A trivial type
is a type whose storage is contiguous (trivially copyable) and which only supports static default initialization (trivially default constructible), either cv-qualified or not. It includes scalar types, trivial classes and arrays of any such types.

A trivial class
is a class (defined with class, struct or union) that is both trivially default constructible and trivially copyable, which implies that:

uses the implicitly defined default, copy and move constructors, copy and move assignments, and destructor.
has no virtual members.
has no non-static data members with brace- or equal- initializers.
its base class and non-static data members (if any) are themselves also trivial types.

分布式事务

https://levy5307.github.io/blog/distributed-transaction/

事务的属性

ACID，事务的4个属性，这个每个人都很熟悉。其中：

A代表原子性，即：事务中的操作要么全部正确执行，要么全部不执行。在分布式系统中，其主要有2pc协议来保证的（另外还有一个3pc协议，但是只停留在理论阶段，没有太多实践意义），后面我会专门写一篇文章来介绍2pc的原理以及各个产品的优化实践。

I代表隔离性，即：多个事务并发执行时，对每个事务来说，它并不会感知系统中有其他事务在同时执行。隔离性有很多个级别，针对不同的级别有多种不同的实现方法，如：MVCC、2PL等。

D代表持久性，即：一个事务在提交之后，该事务对数据库的改变是持久的。持久性主要通过redo log来保证的，即如果宕机导致内存中的数据丢失了，需要通过redo log回放来进行恢复。

最后一个是C，其代表一致性。其定义是比较模糊的：数据库必须保证事务的执行从一个一致性状态转移到另一个一致性状态。其主要是指保证事务操作后保持原有的数据的约束。比如转账事务完成后，转账的双方的总金额不能多页不能少。在ACID中，C是目的，AID是手段，为了达到C的目的而提供的手段。数据库必须实现了AID的这三个特性才有可能实现C。

另外说一句，对于一个涉及a、b节点的分布式事务，如果节点a提交了本地事务，而节点b还没来得及提交，从而其他事务看到了其中间状态，这个问题是由隔离性来解决的。很多人误以为是一致性，其实是不对的。另外这里的一致性和多副本的一致性也不是一个概念。多副本一致性是指：

查询和更新单个对象的操作按一定顺序执行


更新操作的效果必然反映在后续查询操作返回的结果中

Pacifica

https://levy5307.github.io/blog/PacificA/

PacificA是微软实现的一款强一致性的分布式共识协议，具有简单易实现、可用性高的优点

本篇文章的内容都是从微软发布的《PacificA: Replicationi in Log-Based Distributed Storage System》总结而来，如有疑惑请移步。

前提条件
对于PacificA，需要系统满足下述条件：

server可能发生故障，但是只有fail-stop故障，不能是fail-slow
message可以被丢弃或者乱序，但是不能被修改
网络分区可能发生
不同服务器上的时钟不一定同步，甚至不一定是松散同步的，但是时间漂移有上限

primary/backup结构

如上图所示，PacificA采取了primary-backup结构。同时我们将客户端请求分为两种：query和update。其中query不会更新数据、而update则会更新。
当一个replica group中的所有server都按照相同的顺序处理请求时，强一致性便可以得到保证。对于update请求，primary为其分配一个单调并连续增长的sn编号，并指示
所有的secondary按照编号顺序执行update请求。我们为每个replica维护了一个prepare list和commit point，该prepare list是按照sn排序的。在prepare list中commit point之前的部分叫做committed list。committed list中的数据保证不会丢失（除非系统发生不可忍受的故障，即发生了所有replica的永久性故障）
在primary-backup模型中，所有的请求都会发送给primary。对于query请求，primary只需要本地处理就可以了，其获取当前最新的数据返回给客户端。但是对于update请>求则需要所有的secondary都参与进来。其具体时序图如下：

由于：

只有当所有的secondary将该请求加入到prepare list中的之后，primary才会将其加入到committed list中，并且，
只有primary将该请求加入到committed list之后，secondary才会将其加入到committed list

所以，我们可以得到如下结论，我们称之为Commit Invariant。
Commit Invariant：Let p be the primary and q be any replica in the current configuration, committed(q) ⊆ committed(p) ⊆ prepared(q) holds.

在我们的replication模型里将数据管理和配置管理分割开来，接下来我们将看一下配置管理

配置管理
在我们的系统中，有一个叫做global configuration manager的组件存在，他用来管理所有replica group的配置，他保存当前的配置及其版本号

一个server可以根据failure detection探测到某个replica下线而删除某一个replica，相反也可以添加一个replica。这时该server需要将修改后的配置文件和当前配置的
版本号发送给configuration manager。当版本号和configuration manager保存的版本号匹配时，新的配置将被采纳并将配置版本号+1

当发生网络分区时，配置冲突将会发生：primary尝试删除secondary；而secondary则尝试将自己提升为primary。此时configuration manager将如何处理这种情况呢？其>实很简单，configuration manager只需要接收最早来的请求，而不管是primary发送来的、还是secondary发送来的。此时其接收到最早来的请求之后，会更新其本地保存>的版本号，所以第二个之后来的请求都将会被拒绝。

任何遵从Primary Invariant的错误探测机制都可以用来删除一个replica:

• Primary Invariant*: At any time, a server p considers itself a primary only if the configuration manager has p as the primary in the current configuration it maintains. Hence, at any time, there exists at most one server that considers itself a primary for the replica group.

租期和错误探测
即使有configuration manager来维护当前配置，但是Primary Invariant也不一定能够保证。

例如

s1将自己提升为primary，manager接受了
此时old primary并不知情，仍然在处理请求
假如old primary处理读，new primary在处理写，此时从old primary读取的数据有可能是旧值

这显然违反了强一致性。导致这个问题的根本原因是不同server上的配置文件的local view不一定相同，也就是说，有可能某些server上保存的是旧版本的配置文件、而没来得及更新。

为了解决这个问题采用了租期来作为错误探测机制。

在一个租期内，primary定期的向secondary发送beacons，并等待其acknowledge。如果在一个固定的时间(lease period)内没有收到acknowledge，那么primary则认为自己的租期已经结束了，此时priimary将停止处理任何请求并且联系configuration manager去移除相应的secondary。由于primary及时将自己租期结束，从而避免了old primary和新primary同时存在。

另外，对于secondary如果在一定时间(grace period)内没有收到来自primary的beacon，那么其同样会通知configuration manager，令其移除primary并令自己成为新的primary。如果lease period <= grace period，那么primary的响应一定是要早于secondary的，也就是说这样如果发生了primary切换，则说明一定是因为old primary不可用了。避免了old primary还可用时进行了primary切换、导致资源浪费的情况发生

NOTE: 为了减少failure detector占用过多的资源，可以将beacon和acknowledge附加在replication信息上，当数据通路空闲时再单独发送beacon

Reconfiguration, Reconciliation and Recovery

bigtable论文笔记

https://levy5307.github.io/blog/bigtable/

数据模型：(row:string, column:string,time:int64)->string
-行关键字：最大64K的字符串。

• Bigtable通过行关键字的字典顺序来维护数据

• 表中一定范围的行被动态分区，每个分区叫做一个Tablet

-单一行关键字下的每一个读或者写操作都是原子的，即支持单行事务

列族：列关键字组成的集合


  
    访问控制、磁盘和内存的计数都是在列族层面进行的
  
  
    同一列族的所有数据都属于同一类型（同一列族下的数据压缩在一起）
  


-先创建列族，然后才能在列族的任何列关键字下存放数据


  
    一张表中不同的列族数目要尽量小（最多几百个），并且列族在操作中很少改变
  
  
    列族名字必须是可打印的字符串
  



列关键字：命名语法如下：列族：限定词


  
    列族的名字必须是可打印的字符串，但是限定词可以是任意字符串
  
  
    一张表可以有无限多的列
  



时间戳：64位整型数，用时间戳来索引同一数据的不同版本


  
    数据项的不同版本按照时间戳倒序排列，所以最新的版本可以先读到
  
  
    为了减轻多个版本数据的管理负担，对每一个列族提供两个设置参数，通过这两个参数对废弃版本的数据进行自动垃圾回收（1.只保存最后n个版本数据，2.保存最近XXX时间内的数据）

BigTable构件：BigTable是建立在一些其他google的基础组件之上的

SSTable文件格式


  SSTable使用块索引来定位数据块，在打开SSTable的时候，索引被加载到内存。一次查找通过一次磁盘搜索完成：在内存索引里执行二分查找，找到对应的索引，然后从磁盘中读取合适的数据块,也可以把整个SSTable都映射到内存中，这样便不需要访问硬盘了。



Chubby分布式锁: 高可用、持久化的分布式锁服务


  
    一个Chubby服务包括了5个活动的副本，其中一个副本为master，并积极处理请求。
  
  
    使用paxos算法保证副本的一致性

实现：三个主要的组件

链接到每个客户程序的库


一个master服务器


  
    为tablet服务器分配tablets，
  
  
    检测新加入的或者过期失效的tablet服务器
  
  
    平衡tablet服务器的负载
  
  
    对GFS中的文件进行垃圾手机
  
  
    客户数据不经过master：直接和tablet服务器通信来进行读写操作，不以来master服务器来获取tablet的位置信息。因此大多数客户程序甚至完全不和master通信，所以实际应用中master的负载很轻
  



多个table服务器，每个tablet服务器都管理一组tablet(数十至上千个tablet)


  
    处理它所加载的tablet的读写操作
  
  
    分割增长的过大的tablet

每个表包含一组tablet（初始状态下每个表只有一个tablet，随着表中数据增长，被自动分割成多个tablet，默认每个tablet大小约为100M~200M）

上图是一个三层结构，分别为：Chubby file, METADATA, User tablet，其中METADATA包含 Root Tablet和Other METADATA tablets，即图中间两个。
每个tablet包含128M / 1K = 2^17，所以一共组多可以有2^17 * 2^17=2^34个tablet（Root tablet有2^17行，每行代表一个METADATA tablet，每个METADATA tablet也有2^17行，每行代表一个User tablet）

Root Tablet是METADATA的第一个tablet，这个表包含所有的Tablet的位置信息

Chubby file中：

包含了RootTablet的位置信息


Tablet服务器文件（代表该tablet服务器的状态）。


  
    当一个Tablet服务器启动时，它在Chubby的一个指定目录下建立一个唯一的文件，并且获取该文件的独占锁。
  
  
    Master服务器实时监控这个目录，因此Master服务器很了解Tablet服务器的状态
  
  
    Master轮询Tablet所有的服务器文件，检查Tablet服务器的状态。如果一个Tablet服务器丢失了文件或者master尝试和它通信都没有回应master则尝试获取其文件独占锁并删除其服务器文件，一旦Tablet服务器在Chubby上的服务器文件被删除了，Master就把分配给他的所有Tablet放入未分配的Tablet集合中

Master服务器记录了：

当前有哪些活跃的Tablet服务器


哪些Tablet分配给了哪些Tablet服务器


哪些Tablet还没有分配

• Master服务器启动步骤：*

  Master服务器从Chubby获取一个唯一的Master锁，用来阻止创建其它的Master服务器实例

  Master服务器扫描Chubby的服务器文件锁存储目录，获取当前正在运行的服务器列表

  Master服务器和所有的正在运行的Tablet服务器通信，获取每个Tablet服务器上Tablet的分配信息

  Master服务器扫描METADATA表获取所有的Tablet的集合。在扫描的过程中，当Master服务器发现了一个还没有分配的Tablet，Master服务器就将这个Tablet加入未分配的Tablet集合并等待合适的时机分配

上图中的tablet log就是REDO日志

恢复Tablet操作

Tablet服务器从METADATA中读取它的元数据(元数据中包含组成这个Tablet的SSTable列表，以及Redo point)


Tablet服务器把SSTable加载入内存


重复Redo之后的提交

对Tablet服务器进行写操作

检查格式是否正确、权限校验(权限验证通过从Chubby文件中读取的操作者列表来验证)


成功的修改会记录在提交日志里。并通过group commit（批量提交）的方式来提交吞吐量


当写操作提交后，写的内容插入到MemTable里

对Tablet服务器进行读操作

类似于写操作的完整性和权限检查


从SSTable和MemTable的合并视图里执行读操作

Compactions(空间压缩)

分为三类：

Minor Compaction. 随着写操作的执行，MemTable的大小不断增加，当MemTable大小到达一个阈值的时候，这个MemTable就会被冻结并创建一个新的MemTable，被冻结住的MemTable会被转换成SSTable(创建一个新的SSTable)，然后写入GFS


Merging Compaction. Merge compaction会读取一些SSTable和MemTable，合并成一个新的SSTable


Major Compaction. 会合并所有的SSTable并生成一个新的SSTable, Bigtable定期扫描它所有的Tablet，并定期对他们执行Major Compaction.

Major Compaction生成的SSTable不包含已删除的信息和数据，而非Major Compaction产生的SSTable可能含有特殊的删除条目。

共同点：都会产生新的SSTable

优化

局部性群组(Locality groups): 客户程序可以将多个列族组合成一个局部性群组


  
    对Tablet中的每个局部性群组都会生成一个单独的SSTable
  
  
    不会一起访问的列族分割成不同的局部性群组，可以提高读取操作的效率(避免了读取无用数据)
  
  
    可以以局部性群组为单位设定一些有用的调试参数，比如，可以把一个局部性群组声明为全部存储在内存中(在BigTable内部，我们利用这个特性提高METADATA表中具有位置相关性的列族的访问速度)
  



压缩：客户程序可以控制一个局部性群组的SSTable是否需要压缩


  
    以SSTable块为单位进行压缩。优点：读取少量数据的时候，不需解压整个文件
  
  
    两阶段压缩：1-Bentley and Mcllroy’s方式（在一个很大的扫描窗口里对常见的长字符串进行压缩）、2-快速压缩算法（在一个16KB的扫描窗口里寻找重复数据

）

缓存：采用二级缓存策略


  
    第一级缓存（扫描缓存）：缓存key-value对，对于重复读非常有效
  
  
    第二级缓存（块缓存）：对于经常读取临近数据的情况非常有效
  



Bloom过滤器：用于检索一个数据是否在集合中(内存中执行检索，而无需去硬盘中逐个查找所有SSTable), 其空间效率和查询时间比一般算法好的多，但是有一定的误识别率和删除困难。


commit日志的实现

假设: 每个tablet一个单独的日志文件，并且多个tablet会并行的写入

问题：那么将会导致大量的磁盘seek操作。

解决方法：对每个tablet服务器采用一个日志文件

缺点：这种解决方法提高了普通操作的性能，但是将恢复操作复杂化了。例如：tablet服务器A宕机了，服务器B/C/D分别接管服务器A的部分tablet，一个普遍的做法是B/C/D分别执行A的commit日志文件。但是由于对所有tablet都写在同一个commit日志文件中，所以B/C/D需要分别读取对所有的tablet的写入日志，然后挑选出自己需要接管的tablet，无疑性能低了很多（假如有100个Tablet服务器接管，那么需要读取100次）

改进：按照关键字(tablet, row name, log sequence number)排序，排序后同一个tablet的日志就连续存放在一起了。因此只需要一次磁盘seek操作之后顺序读取就可以了。

在向GFS中写入commit日志时可能会引起系统颠簸。为了确保在颠簸时仍能顺利进行，每个tablet服务器有两个日志写入线程，分别写入不同的日志文件（不同日志文件处于不同的GFS服务器上），如果在一个线程写入效率低的时候，则使用另外一个线程进行写入（因为每个日子都有序号，所以可以根据需要忽略掉由于线程切换导致的重复写入）

-tablet恢复提速

当master将一个tablet从一个tablet服务器转移到另一个tablet服务器时，源tablet服务器先对其进行一次minor compaction（减少其没有归并的记录，从而减少恢复时间），compaction完成之后，该服务器就停止为该tablet服务。在写在tablet之前，再做一次minor compaction, 以消除前面一次minor compaction过程中产生的未归并记录（通常会很快，这也是为什么执行两次minor compaction的原因，如果为了防止漏掉记录而在执行第一次minor compaction之前就停止为该tablet服务，第一次minor compactioin执行的时间会比较长，导致该tablet长时间得不到服务），第二次minor compaction之后，tablet就可以被装在到新的tablet服务器上了，并且不需要从日志中进行恢复

-利用不变性

除了SSTable缓存之外其他部分产生的SSTable都是不变的，可以利用这一点，例如：

从SSTable中读数据的时候，不需要进行同步操作，效率更高。


MemTable是唯一能被读写同时访问的可变数据结构，采用COW(Copy-on-Write)机制，这样也可以读写并行


由于SSTable不变，因此可以把移除已删除数据的问题，转换成对垃圾进行回收的方式（标记-删除的方式）


Tablet分割操作变得简单，因为SSTable不变，所以分割的Tablet可以使用原有的SSTable，而不必重新建立新的SSTable

Dynamo

https://levy5307.github.io/blog/Dynamo/

Dynamo是Amazon实现的一款KV存储。为了支持Amazon大规模且持续增长的用户，具有高可用、高扩展性的特性。Dynamo有一个重要的设计目标：允许应用自己控制自己的系统特性（例如持久性和一致性）让应用自己决定如何在功能、性能和成本效率之间取得折中。

Background

我们对我们的存储服务有如下几个要求：

Query Model: 通过唯一的key来对数据进行读写。状态以二进制的形式存储，并以唯一的key标识。没有操作跨越多个data item，并且没有relational schema。该需求是基于我们观察到很大部分的Amazon内部的服务只需要加单的query model、而不需要relational schema。Dynamo面向的是存储数据小于1MB的应用。


ACID properties: ACID是一组保证数据库事务可靠执行的特性。在数据库领域，对数据的单词逻辑操作成为事务。在Amazon的经验表明，让数据仓库支持ACID会使得它的可用性非常差。Dynamo不提供任何隔离保证，并且只允许单个key的操作。


Efficiency: 系统需要运行在通用硬件上。Amazon内部对服务的延迟有着严格的要求，通常使用p999来衡量。另外，服务需要有配置Dynamo的能力，以便能满足服务的延迟和吞吐要求。最终在性能、成本效率、可用性和持久性之间取得折中。


Other Assumptions: Dynamo仅仅在Amazon内部使用，因此假设其运行环境是安全的，因此没有authentication和authorization方面的需求。另外，每个服务使用其自己独立的Dynamo集群，因此我们的初始设计中，Dynamo的存储规模是几百个存储节点。

Design Considerations

商业系统中的数据复制都是同步的，这样可以提供一个强一致的数据访问接口。为了达到这种级别的一致性，这些算法强制牺牲了在某种错误场景下的可用性。其实对于服务器和网络故障比较容易出现的场景，可以通过使用乐观复制技术来提高可用性。在这种复制技术中，数据变更在后台同步到其他节点，并发更新和网络失联也是可以容忍的，这种方式也叫做异步复制，其无法满足强一致性。Dynamo设计为最终一致性的存储服务，即所有的更新最终会到达所有的副本。但是这种模式的挑战在于如何检测和解决冲突。而解决冲突也会带来两个问题：何时解决冲突以及谁来解决冲突。

何时解决冲突

一个非常重要的设计考虑是决定何时执行解决更新冲突，例如，是在读的时候还是写的时候去解决冲突。一些传统的数据仓库是在写的时候解决冲突，这样可以保证读流程足够简单。在这种系统中，如果写入不能到达全部或者大多数的副本，写入将会被拒绝。与此相反，Dynamo被设计为永远可写的数据仓库。对于Amazon的许多服务来说，拒绝写入会导致非常差的客户体验。例如，尽管在发生网络或者服务器故障的时候，也应该允许用户向购物车中添加或者删除商品。这种需求导致我们将冲突解决放在了读取操作，以保证写入永远不会被拒绝。

谁来解决冲突

下一个问题在于，谁来执行冲突解决。存储和应用都可以解决这件事情。如果是由存储来做，那么选择将会相当受限，因为存储系统只能选用比较简单的策略，例如：最新写入有效。另外一方面，应用更加理解其data schema，其可以选择一个更适合自己的冲突解决方案。例如，购物车可以选择合并冲突的版本，返回一个合并后的购物车。不过尽管这样会带来很大的灵活性，但是很多应用并不想实现自己的一套冲突解决机制，因此这种情况下可以由存储系统来解决，采用一些简单的策略，例如前面所说的最新写入有效。

另外，还有一些其他的关键设计：

Incremental scalability（增量扩展性）: Dynamo应该可以逐台机器的扩容，并且对系统及其运维人员的影响尽量小。


Symmetry（对称性）：每个节点的职责应该是相同的，不应当出现某些节点承担特殊角色或者特殊职责。根据我们的经验来说，对称性简化了系统的交付和运维。


Decentralization（去中心化）：去中心化是Symmetry的扩展，系统应该是去中心化、点对点的，而不应该是中心化的。在过去中心化导致了很多故障，现在的设计目标应该是尽量避免它。去中心化使得系统更加简单、更容易扩展并且更加高可用。


Heterogeneity（异构性）：系统要能够利用到基础设施的异构性。例如，负载的分布要和存储节点的能力成正比。对于逐步加入能力更强的新节点、且一次性升级现有节点的情况下，异构性支持是至关重要的。

System Architecture

生产环境的存储系统的架构是很复杂的。除了数据持久化之外，系统还要为以下组件设计高扩展与健壮的解决方案，这些组件包括：负载均衡、成员管理、故障检测、故障恢复、副本同步、过载处理、状态转换、并发与任务调度、请求压缩、请求路由、系统监控和报警、以及配置管理。在这篇文章里主要关注Dynamo使用到的、分布式系统中的几个核心技术：分区、复制、版本化（versioning）、成员管理、错误处理、规模扩展（scaling)。

System Interface

Dynamo使用key通过一个非常简单的接口来访问对象，它提供两个操作：

get(key): 该操作会定位到该key对应的所有的副本，并返回单个对象或者一个包含冲突版本的对象列表，以及一个context上下文。


put(key, context, object):该操作先根据key获取该object的存放位置，然后将其写入磁盘。

其中context包含了对象相关的元数据，例如对象的版本。其对调用方是不透明的。context信息和对象时存储到一起的，这样可以很容易验证put请求的context是否是合法的。

Dynamo将调用方提供的key和对象都视为不透明的字节序列。它对key应用MD5 hash产生一个128bit的ID，并根据该ID计算应该存储到哪个节点。

Partitioning Algorithm

Dynamo的设计核心需求之一就必须支持增量扩展（scale incrementally）。这要求需要有一个机制将数据动态分散到系统中的不同节点上。Dynamo的数据分片机制依赖于一致性hash。在一致性hash中，hash函数的输出范围通常作为一个固定的环。每个节点会随机分配一个落在该环上的值，其代表了该节点所在环上的位置。对一个数据项，通过如下步骤找到对应的存储节点：

首先对key取hash值


在环上沿着顺时针方向找到第一个所对应的hash值比该key的hash值更大的节点。

因此，每个节点都负责环上它的前继节点与自己范围内的区域。一致性hash的好处在于，添加或者删除节点只会影响相邻的节点，其他节点不受影响。

但是基础的一致性hash有如下缺点：

给每个节点随机分配一个位置会导致数据和负载的非均匀分布。


没有考虑到节点的异构因素，导致性能不理想。

为了克服这些问题，Dynamo使用了一致性hash的变种，即：每个节点并不是映射到环上的一个点、而是多个点（Cassandra采用了一致性hash的另一个变种，具体可以参考）。Dynamo使用虚拟节点的概念。一个虚拟节点看上去和一个普通节点一样，但是一个实际节点对应的不止一个虚拟节点。具体来说货，当一个新的节点添加到系统后，它将会被分配环上的多个位置。

虚拟节点会带来如下好处：

当一个节点不可用时（故障或例行维护），这个节点的负载会均匀分散到其他可用节点上


当一个节点重新可用时，或新加入一个节点时，这个节点会获得与其他节点大致相同的负载


一个节点负责的虚拟节点的数量可用根据节点容量来决定，这样可用充分利用物理基础设施中的异构性信息

Replication

为了实现高可用和持久性，Dynamo将数据复制到多个节点上。每个数据被复制到N个节点上，这里的N是由每个Dynamo集群自己配置的。每一个key都会被分配到一个coordinator节点，coordinator节点负责落到它管理范围内数据的复制。它除了自己复制一份之外，还会向环上沿着顺时针方向的N-1个节点上存储一个副本。因此每个节点都要负责从自己开始向前N个前继节点的数据范围。

如上图所示，当N=2时，Key的coordinator是节点D，但是其也会被复制到E和F。所以对于节点F，其负责的key范围是(A, F]。

存储某个特定key的所有节点组成一个列表，成为preference list。另外需要注意，由于Dynamo引入了虚拟节点，所以存储一个key的N个preference list，其物理节点可能少于N个，为了避免这个问题，preference list在选择节点的时候会跳过一些位置，以保证preference list里面的节点都在不同的物理节点上。

Data Versioning

Dynamo提供了最终一致性，所有更新都会异步的复制到所有副本。put()操作可以在应用到所有副本之前返回给调用者，因此将会导致紧接着的get()操作可能获取不到最新的数据。在没有故障的情况下，更新传播都是有一个时间上限的。然而在某些特定的故障场景下（服务器故障或者网络分区），更新可能在限定的时间内无法传递到所有副本。

Amazon有些场景可以容忍这种不一致性，并且可以在这种场景下继续运行。例如，购物车应用要求所有的“Add to Cart”操作永远不能丢失或者被拒绝。如果购物车当前最新的状态不可用，那么用户可以在一个稍老的版本上做修改，并且这种修改也是有意义的、并且需要保留。但是他不能取代购物车最新的状态，因为最新的状态也有一些改变需要保留。在这里需要注意的是，“add to cart”和“delete iter from cart”在Dynamo中都是使用put请求。当一个顾客想要向购物车中添加或者删除一个商品时，如果购物车当前最新的状态不可用，那么该商品将会被添加到老版本的购物车中，并由随后的步骤来解决冲突。

转redis Persistence Demystified

https://levy5307.github.io/blog/%E8%BD%ACredis-persistence-demystified/

http://oldblog.antirez.com/post/redis-persistence-demystified.html

Rate Limiter

https://levy5307.github.io/blog/rate-limiter/

Rate Limiter

In general, a rate is a simple count of occurrences over time. However, there are several different techniques for measuring and limiting rates.

Fixed Window
In a fixed window algorithm, a window size of n seconds (typically using human-friendly values, such as 60 or 3600 seconds) is used to track the rate. Each incoming request increments the counter for the window. If the counter exceeds a threshold, the request is discarded. The windows are typically defined by the floor of the current timestamp, so 12:00:03 with a 60 second window length, would be in the 12:00:00 window.

The advantage of this algorithm is that it ensures more recent requests gets processed without being starved by old requests. However, a single burst of traffic that occurs near the boundary of a window can result in twice the rate of requests being processed, because it will allow requests for both the current and next windows within a short time. Additionally, if many consumers wait for a reset window, for example at the top of the hour, then they may stampede your API at the same time.

Sliding window
This is a hybrid approach that combines the low processing cost of the fixed window algorithm, and the improved boundary conditions of the sliding log. Like the fixed window algorithm, we track a counter for each fixed window. Next, we account for a weighted value of the previous window’s request rate based on the current timestamp to smooth out bursts of traffic. For example, if the current window is 25% through, then we weight the previous window’s count by 75%. The relatively small number of data points needed to track per key allows us to scale and distribute across large clusters.

Token Bucket
A token bucket maintains a rolling and accumulating budget of usage as a balance of tokens. This technique recognizes that not all inputs to a service correspond 1:1 with requests. A token bucket adds tokens at some rate. When a service request is made, the service attempts to withdraw a token (decrementing the token count) to fulfill the request. If there are no tokens in the bucket, the service has reached its limit and responds with backpressure. For example, in a GraphQL service, a single request might result in multiple operations that are composed into a result. These operations may each take one token. This way, the service can keep track of the capacity that it needs to limit the use of, rather than tie the rate-limiting technique directly to requests

Leaky Bucket
A leaky bucket is similar to a token bucket, but the rate is limited by the amount that can drip or leak out of the bucket. This technique recognizes that the system has some degree of finite capacity to hold a request until the service can act on it; any extra simply spills over the edge and is discarded. This notion of buffer capacity (but not necessarily the use of leaky buckets) also applies to components adjacent to your service, such as load balancers and disk I/O buffers.

Conclusion

With twice the rate of requests being processed occured near the boundary of a window, fixed window is passed.

Sliding Windows are a variant of fixed Windows. The more Windows you have, the higher the accuracy, but the more resources you consume. The fewer Windows you have, the less resources you consume, but the less accurate you get.

So We mainly consider the following two ways：token bucket and leaky bucket.

Token Bucket vs Leaky Bucket

LB discards packets; TB does not. TB discards tokens.


LB sends packets at an average rate. TB allows for large bursts to be sent faster by speeding up the output.


TB allows saving up tokens (permissions) to send large bursts. LB does not allow saving


With LB, when there are a large number of burst requests in a short period of time, each request has to wait in the queue for a while before it can be answered, even if the server is not under any load.

Because LB does not allow saving tokens to send large bursts. So if we have a large request, which is large than the size of bucket, the request will not be processed.

So, I recommend choosing the token bucket algorithm.

jaas tgt renewal调研

https://levy5307.github.io/blog/jaas-tgt-renewal/

##背景

之前看java的官方文档和mit的文档里都写到，只要将renewTGT设置为true，那么jaas内部便会对tgt进行自动更新。

java官方文档(https://docs.oracle.com/en/java/javase/14/docs/api/jdk.security.auth/com/sun/security/auth/module/Krb5LoginModule.html)：

renewTGT:Set this to true, if you want to renew the TGT when it’s more than half-way expired (the time until expiration is less than the time since start time). If this is set, useTicketCache must also be set to true; otherwise a configuration error will be returned.

mit文档(https://web.mit.edu/java_v1.5.0_22/distrib/share/docs/guide/security/jgss/jgss-tiger.html)：

TGT Renewals
The Java Authentication and Authorizaton Server (JAAS) Kerberos login module in JDK 5.0, Krb5LoginModule, now supports Ticket Granting Ticket (TGT) renewal. This allows long-running services to renew their TGT automatically without user interaction or requiring the services to restart.
With this feature, if Krb5LoginModule obtains an expired ticket from the ticket cache, the TGT will be automatically renewed and be added to Subject of the caller who requested the ticket. If the ticket cannot be renewed for any reason, then Krb5LoginModule will use its configured callback handler to retrieve a username and password to acquire a new TGT.
To use this feature, configure Krb5LoginModule to use the ticket cache and set the newly introduced renewTGT option to true. Here is an example of a JAAS login configuration file that requests TGT renewal.
server {
com.sun.security.auth.module.Krb5LoginModule required
principal=principal@your_realm
useTicketCache=true
renewTGT=true;
};

但是社区同学联系我们说Pegasus当前没有针对tgt做自动更新，并且hbase实现了一个线程用于更新tgt。最初对于这位的说法我没有太当回事，觉得可能是他理解的问题，毕竟官方文档都这样写了。
但是想到hbase都这样做了，可能事情没有这么简单，还是要仔细调研再确认一下。所以去专门翻了下jaas的源码。

##renewTGT配置
通过查看LoginContext.login函数，确实可以看到，如果renewTGT设置为true的话，会在login的时候对tgt进行更新。
而且renewTGT这个配置仅仅是在login的时候用到，其他地方并没有使用。也就是说，这个配置仅仅会使login的时候去更新tgt，并没有文档中所说的会去持续更新。

所以可以肯定的一点是，renewTGT并不是持续更新的配置，而只是在login时做一次更新。

##tgt是否支持renew
继续看了下代码发现，tgt自身是支持自动renewal的，也就是说在tgt过期时，它会去自动刷新。

但是有一个限制：如果设置了renew till，那么如果当前时间超过了其renew till时间，就不会刷新了。当然，如果renew till设置为null，那确实也是会一直持续更新的，这样文档中也不算有问题，这时确实客户端代码无需自己实现刷新逻辑。

所以需要判断一下，这个renew till时间是怎么得来的，这个值到底有没有设置？

通过Krb5LoginModle.java中可以看到，如果tgt不存在，那么是需要通过向kdc来进行申请。

client向kdc发送申请，申请中携带了客户端这边配置的till时间



客户端收到kdc发送回的resp，并解析获取kdc返回的renew till时间

从这里可以看出，这个till时间是由客户端和服务端双方决定的，并不是客户端一方配置就可以决定的。也就是说，这个renew till时间我们不好掌控。这样的话，客户端代码最好实现更新的逻辑。
（翻到一篇博客讲到，这个renew till时间是取客户端till时间和kdc till时间两者的最小值：https://blog.51cto.com/caiguangguang/1383723）

另外通过查看，公司内部的这个renew till时间是10年，所以我们平时测试的话，确实不容易看出问题。
➜ /etc klist
Valid starting Expires Service principal
2021-04-01T23:03:39 2021-04-02T23:03:39
renew until 2031-03-30T23:02:57

##结论
短期来看代码中不做renew逻辑不会有问题，但是为了可靠起见，最好还是对其进行支持。

其他文档：https://andriymz.github.io/kerberos/authentication-using-kerberos/#keytab