作者: Unmesh Joshi
译者: java达人
来源: https://martinfowler.com/articles/patterns-of-distributed-systems/
预写日志中的索引，显示最近一次成功的复制。
问题
服务器崩溃并重新启动后，可使用“Write-Ahead Log”模式恢复状态。但是，如果服务器发生故障，Write-Ahead Log不足以提供可用性。如果单个服务器发生故障，则客户端将无法运行，直到服务器重新启动。为了获得更多可用的系统，我们可以在多个服务器上复制日志。使用领导者和追随者模式，领导者会将其所有日志条目复制到追随者法定数。现在，如果领导者失败，则可以选举新的领导者，并且客户可以像以前一样继续使用集群。但是仍然有几处可能出问题：
• leader在将其日志发送给任何追随者之前可能会失败。• 领导者可能会在向一些追随者发送日志条目时失败，无法将其发送给大多数的追随者。
在这些错误场景中，一些追随者可能在其日志中丢失条目，而一些追随者可能拥有比其他追随者更多的条目。因此，对于每个follower来说，了解日志的哪一部分对客户端是安全可用的就变得很重要了。
解决方案
high-water mark是日志文件的一个索引，它记录已知已成功复制到追随者Quorum的最后一个日志条目。在复制过程中，领导者还会将high-water mark传递给追随者。集群中的所有服务器应该只向请求低于high-water mark更新的客户端传输数据。
这是操作顺序：
Figure 1: High-Water Mark
对于每个日志条目，leader将其附加到其本地预写日志中，然后将其发送给所有追随者。
代码语言：javascript复制leader (class ReplicationModule...)
private Long appendAndReplicate(byte[] data) {
Long lastLogEntryIndex = appendToLocalLog(data);
logger.info("Replicating log entries from index " lastLogEntryIndex);
replicateOnFollowers(lastLogEntryIndex);
return lastLogEntryIndex;
}
private void replicateOnFollowers(Long entryAtIndex) {
for (final FollowerHandler follower : followers) {
replicateOn(follower, entryAtIndex); //send replication requests to followers
}
}追随者处理复制请求并将日志条目附加到它们的本地日志中。在成功附加日志条目之后，它们将拥有的最新日志条目索引响应到leader。该响应还包括服务器的当前Generation Clock。
代码语言：javascript复制follower (class ReplicationModule...)
private ReplicationResponse handleReplicationRequest(ReplicationRequest replicationRequest) {
List<WALEntry> entries = replicationRequest.getEntries();
for (WALEntry entry : entries) {
logger.info("Applying log entry " entry.getEntryId() " in " serverId());
wal.writeEntry(entry);
}
return new ReplicationResponse(SUCCEEDED, serverId(), replicationState.getGeneration(), wal.getLastLogEntryId());
}Leader在收到响应时跟踪在每个服务器上复制的日志索引。
代码语言：javascript复制class ReplicationModule…
recordReplicationConfirmedFor(response.getServerId(), response.getReplicatedLogIndex());
long logIndexAtQuorum = computeHighwaterMark(logIndexesAtAllServers(), config.numberOfServers());
if (logIndexAtQuorum > replicationState.getHighWaterMark()) {
var previousHighWaterMark = replicationState.getHighWaterMark();
applyLogAt(previousHighWaterMark, logIndexAtQuorum);
replicationState.setHighWaterMark(logIndexAtQuorum);
}通过查看所有追随者的日志索引和领导者本身的日志，并获取大多数服务器上可用的索引，可以计算出High-Water Mark。
代码语言：javascript复制class ReplicationModule…
Long computeHighwaterMark(List<Long> serverLogIndexes, int noOfServers) {
serverLogIndexes.sort(Long::compareTo);
return serverLogIndexes.get(noOfServers / 2);
}领导者将high-water mark作为常规心跳的一部分或作为单独的请求向追随者传播。追随者随后相应地设定了他们的high-water mark。
任何客户端只能读取低于high-water mark的日志条目。超出high-water mark的日志条目对客户机是不可见的，因为没有确认条目是否被复制，如果leader失败，而其他服务器被选为leader，这些日志条目可能不可用。
代码语言：javascript复制class ReplicationModule…
public WALEntry readEntry(long index) {
if (index > replicationState.getHighWaterMark()) {
throw new IllegalArgumentException("Log entry not available");
}
return wal.readAt(index);
}
日志截取
当服务器在崩溃/重启后加入集群时，总是有可能在其日志中有一些冲突条目。因此，每当服务器加入集群时，它都会与集群的领导者进行检查，以了解日志中的哪些条目可能存在冲突。然后，它将日志截取到与leader匹配的条目位置，然后使用后续条目更新日志，以确保其日志与集群的其余部分匹配。
考虑下面的例子。客户端发送请求以在日志中添加四个条目。leader成功地复制了三个条目，但是在将entry4添加到自己的日志后复制失败。其中一个追随者被选为新的领导者，并从客户端那里接受更多的条目。当故障的leader再次加入集群时，它的entry4发生冲突。因此，它需要将其日志截取到entry3，然后添加entry5使日志与集群的其他服务器匹配。
Figure 2: Leader Failure
Figure 3: New Leader
Figure 4: Log Truncation
任何在暂停后重启或重新加入集群的服务器都会找到新的leader。然后，它显式地请求当前的High-Water Mark，将其日志截取到High-Water Mark处，然后从leader获取超过High-Water Mark的所有条目。像RAFT这样的复制算法可以通过检查自己日志中的日志项和请求的日志项来找出冲突项。删除具有相同日志索引但处于较低Generation Clock的条目。
代码语言：javascript复制class ReplicationModule…
private void maybeTruncate(ReplicationRequest replicationRequest) throws IOException {
if (replicationRequest.hasNoEntries() || wal.isEmpty()) {
return;
}
List<WALEntry> entries = replicationRequest.getEntries();
for (WALEntry entry : entries) {
if (wal.getLastLogEntryId() >= entry.getEntryId()) {
if (entry.getGeneration() == wal.readAt(entry.getEntryId()).getGeneration()) {
continue;
}
wal.truncate(entry.getEntryId());
}
}
}支持日志截取的一个简单实现是保存日志索引和文件位置的映射。然后在给定索引处截取日志，如下所示:
代码语言：javascript复制class WALSegment…
public void truncate(Long logIndex) throws IOException {
var filePosition = entryOffsets.get(logIndex);
if (filePosition == null) throw new IllegalArgumentException("No file position available for logIndex=" logIndex);
fileChannel.truncate(filePosition);
}例子
• 所有共识算法都使用High-Water Mark的概念来知道何时应用提议的状态变化。例如 在RAFT共识算法中，High-Water Mark称为“CommitIndex”。• 在Kafka复制协议中，有一个单独的索引被称为“High-Water Mark”。消费者只能看到High-Water Mark之前的条目。• Apache BookKeeper具有“最后确认添加”的概念，该条目已成功复制到quorum。
领导者选举可能会出现一个微妙的问题。在任意服务器向客户端传送数据之前，我们要确保集群中的所有服务器都有最新的日志。 这个场景有一个微妙的问题是，现有的领导者在向所有追随者传播High-Water Mark之前就失败了。在领导者选举成功后，RAFT会在领导者的日志中附加一个no-op无操作条目，并且只有在被它的追随者确认后才会为客户端服务。在ZAB中，在开始服务客户端之前，新领导者显式地尝试将其所有条目推送给所有追随者。
