Netium's software technology space

0%

发表于 更新于 阅读次数：

Keycloak是一个比较流行的OAuth/OIDC服务器和IAM系统， 本文将介绍如何在Linux上配置Keycloak以standalone模式运行，并且使用MariaDB作为后端数据库存储。

这里假设：

  • 安装Keycloak的Linux机器的IP地址是: 192.168.0.152;
  • 安装MariaDB的Linux机器的IP地址是: 192.168.0.151;
  • Keycloak的数据库的名称是keycloak_db;
  • Keycloak将使用用户名 keycloak 和密码 123456 连接数据库;
  • 所有的Linux系统都是Ubuntu Linux Server 20.04;
  • Keycloak版本是10.0.1.

MariaDB安装与配置

  1. 首先需要安装MariaDB，这里就不作介绍了，网上有很多教程可以参考;

  2. 使用root用户登入MariaDB:

    1
    $ sudo mysql -u root -u

  3. 在MariaDB中创建名为keycloak_db的数据库:

    1
    > CREATE DATABASE keycloak_db;

  4. 在MariaDB中创建名为keycloak的用户并赋予它操作keycloak_db的权限：

    1
    2
    3
    4
    5
    > create user 'keycloak'@'192.168.0.152' identified by '123456';

    > grant all on keycloak_db.* to 'keycloak'@'192.168.0.152' with grant option;

    > flush privileges;

Keycloak安装与配置

  1. 下载keycloak:

    1
    $ wget https://downloads.jboss.org/keycloak/10.0.1/keycloak-10.0.1.tar.gz

  2. 解压keycloak:

    1
    $ tar zxvf keycloak-10.0.1.tar.gz

  3. 下载MariaDB client JAR:

    1
    $ wget https://downloads.mariadb.com/Connectors/java/connector-java-2.6.0/mariadb-java-client-2.6.0.jar

  4. 在keycloak中给MariaDB client创建对应的文件夹并将MariaDB client拷贝入文件夹:

    1
    2
    3
    $ mkdir -p keycloak-10.0.1/modules/system/layers/keycloak/com/mariadb/main/

    $ cp mariadb-java-client-2.6.0.jar keycloak-10.0.1/modules/system/layers/keycloak/com/mariadb/main/

  5. 为MariaDB client创建module.xml文件:

    1
    $ vi keycloak-10.0.1/modules/system/layers/keycloak/com/mariadb/main/module.xml

    文件内容如下:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    <?xml version="1.0" ?>

    <module xmlns="urn:jboss:module:1.3" name="com.mariadb">
        <resources>
            <resource-root path="mariadb-java-client-2.6.0.jar"/>
        </resources>
        <dependencies>
            <module name="javax.api"/>
            <module name="javax.transaction.api"/>
        </dependencies>
    </module>

  6. 编辑keycloak的standalone.xml文件, 配置数据库驱动和数据库连接相关信息:

    1
    $ vi keycloak-10.0.1/standalone/configuration/standalone.xml

    把datasource部分替换成:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    <datasource jndi-name="java:/jboss/datasources/KeycloakDS" pool-name="KeycloakDS" enabled="true">
        <connection-url>jdbc:mariadb://192.168.0.151:3306/keycloak_db?characterEncoding=utf8&amp;useSSL=false</connection-url>
        <driver>mariadb</driver>
        <pool>
            <min-pool-size>5</min-pool-size>
            <max-pool-size>15</max-pool-size>
        </pool>
        <security>
            <user-name>keycloak</user-name>
            <password>123456</password>
        </security>
    </datasource>

    然后在drivers里加上MariaDB相关的driver信息:

    1
    2
    3
    <driver name="mariadb" module="com.mariadb">
        <driver-class>org.mariadb.jdbc.Driver</driver-class>
     </driver>

  7. 缺省配置下，keycloak只绑定到了127.0.0.1的端口，所以从其他机器上是访问不了keycloak的admin界面的，为了可以从其他机器上访问keycloak的admin界面，需要编辑standalone.xml文件：

    1
    $ vi keycloak-10.0.1/standalone/configuration/standalone.xml

    然后找到以下内容:

    1
    2
    3
    <interface name="public">
        <inet-address value="${jboss.bind.address:127.0.0.1}"/>
    </interface>

    把它改成:

    1
    2
    3
    <interface name="public">
        <inet-address value="${jboss.bind.address:0.0.0.0}"/>
    </interface>

  1. 配置完成后，尝试运行keycloak:

    1
    $ ./keycloak-10.0.1/bin/standalone.sh

检查keycloak是否正常启动，一般第一次启动keycloak需要在数据库中创建和初始化需要的表，所以要花一些时间。启动完成后访问: http://127.0.0.1:8080/auth 看看是否可以正常显示keycloak的admin界面。

至此，keycloak的standalone模式配置完成。

发表于 更新于 阅读次数：

The following are the steps on how to deploy Keycloak helm on Ubuntu Server 19.10 from Scretch:

  1. Install microk8s from snap:

    1
    sudo snap install microk8s --classic

  2. Enable the Helm3 for microk8s:

    1
    microk8s.enable helm3

  3. Add codecentric helm repo:

    1
    microk8s.helm3 repo add codecentric https://codecentric.github.io/helm-charts

  4. Update Helm repo:

    1
    microk8s.helm3 repo update

  5. Install Keycloak helm:

    1
    microk8s.helm3 install keycloak codecentric/keycloak

Reference:

发表于 更新于 阅读次数：

分布式快照（Snapshot）的作用

作为软件工程师的我们深有体会，能够抓取一个程序运行状态的快照是很重要的一个功能，通过对快照的分析，我们可以定位软件在某个运行时刻上的状态，从而可以发现软件是否按照预定的逻辑运行，是否存在内存泄漏，是否存在死锁等一系列的问题，从而可以定位出软件代码上的bug。

同样的，对于一个分布式系统，如果我们能对整个分布式系统抓取快照，那么这个快照也可以帮我们分析分布式系统出现的问题，比如，进程之间的死锁，状态异常等等。

对于单应用进程的快照，快照一般包含CPU状态以及内存状态，对于一个分布式系统，它的快照除了包含系统中每一个进程的快照外，还要包含进程间通信信道上的信息。

分布式快照的难点

对于一个分布式系统，如果我们想对它做快照，那么一个最简单的思路就是希望在做快照的时候能让整个系统停下来，然后记录每一个进程的信息，再记录每一个信道上的所有信息，这样一个全局快照就生成了，但是这个思路却有以下问题：

  1. 一般我们使用分布式系统是希望达成某种程度的高可用性，所以让整个分布式系统暂时停止下来比较难以接受；
  2. 一般我们的分布式系统都是构建在一个异步网络之上的（消息传输时间不确定），所以想让一个快照控制进程给整个系统发送快照消息，消息并不会即时到达所有节点，而且消息到达不同节点的时间是不一样的，所以做出来的快照状态会不一致。一个简单的例子就是假设节点i往节点j上发送了一条消息m，m已经从i发出，但是还在信道Ci->j上而没有被j接收到，这时候假设节点k向整个系统发出来快照请求（这要求往节点i进程，信道C进程，节点j进程上发消息通知快照），根据消息抵达速度，节点i在发出了m以后收到了快照消息，做了本地快照，信道C进程在m在它里面的时候收到了快照消息，做了信道消息的快照，但是节点j因为快照消息延时的原因，是在m被它消费了以后才收到了快照消息做了本地快照，这种情况下生成的全局快照就是不一致的，因为如果用这个全局快照重建系统，那么m会被节点j消费两次。

Chandy-Lamport算法

谈到分布式系统的快照算法，比较著名的一个就是Chandy-Lamport算法。它是由K. Mani Chandy和Leslie Lamport共同发明的算法。

先决条件

Chandy-Lamport算法对于能应用此算法的系统做出了以下假设：

  1. 系统中的任意两个节点之间都可以进行通信；
  2. 通信信道中的消息满足先进先出（FIFO）的顺序。

算法描述

Chandy-Lamport算法如下：

  1. 系统中的任何一个节点都可以发起快照操作；
  2. 对于发起快照操作的节点（假设此节点为Node i）：
    1. 节点对本地进程生成快照，然后给所有其他节点发送一条<Marker>消息，然后；
    1. 对于所有从其他节点发送过来的消息，和本地快照一并记录下来；
    1. 如果此节点收到了从Node j (j != i)发送过来的一条<Marker>消息，则停止记录信道Node j->Node i上的消息。
  6. 对于其他节点Node j (j != i):
    1. 如果Node j第一次从信道Ck->j (k != j)上收到了<Marker>消息，则对本地进程生成快照，然后给所有其他节点发送一条<Marker>消息；
    1. 对于所有从其他节点l (l != k)发送过来的消息，和本地快照一并记录下来；
    1. 如果此节点上收到了从Node l (l != k)发送过来的一条<Marker>消息，则停止记录信道Node l->Node j上的消息。
  10. 当所有的节点都从其他节点收到了<Marker>以后，算法停止，分布式系统的快照生成完成。
  11. 在一个系统中可以有多个快照同时进行，发起节点也可以不同，只要在发起快照时给它赋予一个全局唯一的ID，然后发起节点把这个ID附在<Marker>消息上，同时每个节点在做本地快照时在快照副本上记录这是对于哪一个ID生成的副本，然后也把ID附在发送出的<Marker>消息上。

示例

以下图示展示了一个基于3个节点的Chandy-Lamport算法 （示例摘自于本人以前一个一份英文讲义）：

发表于 更新于 阅读次数：

分布式系统的一致性模型

在一个分布式系统里面，按照数据的一致性从强到弱排序，我们有以下的一致性模型：

  • 严格一致 （Strict Consistency）
  • 线性一致 （Linearizability)
  • 序列一致 （Sequential Consistency）
  • 因果一致 （Causal Consistency）
  • FIFO一致 （FIFO Consistency）

严格一致 （Strict Consistency）

严格一致性（Strict Consistency）要求对于一个分布式系统的读写交错序列（按照实时时钟排序），如果在某一时刻t对变量x做了一个写操作write(x:=10),那么对于在这个t之后的t’时刻 (t’>t) 的对于此变量x的读操作（并且在下一次的对于x的写操作之前），都会有结果read(x)=10。严格一致性保证了一个集群系统对任何客户端来说看起来都像是一个单机系统。严格一致性在单机单线程程序上是可以满足的，但是在一个分布式系统上却非常难以实现，因为它要求对于所有的节点，一旦x发生了更改，那么此更改可以即时同步到所有的节点上面，但是我们知道，节点之间通过网络进行通信，而且网络通信是有延时的，要做到所有节点即时同步是做不到的。

线性一致 （Linearizability)

线性一致性（Linearizability）要求对于一个分布式系统的读写交错的序列（按照实时时钟排序），如果对于任何一个变量x的读操作read(x)，读到的值都是在此读操作之前最后一次写操作write(x)更新的值。
严格一致性和线性一致性的区别是严格一致性要求对于一个变量x的写操作在所有的节点副本上是实时更新的，而线性一致性并不要求实时更新这一点。
要实现线性一致性，所有的读写操作都要使用一个全序多播（Total ordering multicast）来完成。

对于以下图1：

图1

按照线性一致性，则有：

  1. ReadA1(x)=10
  2. ReadA2(x)=20
  3. ReadA3(x)=20
  4. ReadB(x)=20
  5. ReadC1(x)=20
  6. ReadC2(x)=20

序列一致 （Sequential Consistency）

序列一致性（Sequential Consistency）要求对于一个分布式系统的读写交错序列（按照实时时钟排序），必须满足：

  1. 对于同一个节点发起的读写序列，对于任何一个变量x的读操作read(x)，读到的值都是在此读操作之前最后一次此进程发起的写操作write(x)更新的值；
  2. 对于整个读写交错序列，所有节点看到的写操作序列必须保证一致。

要实现序列一致性：

  • 对于写操作，使用一个全序多播（Total ordering multicast);
  • 对于读操作，立即返回本节点上对应变量的值。

对于图1，除了线性一致性中的返回值情况，以下返回值也满足序列一致：

  1. ReadA1(x)=10
  2. ReadA2(x)=10
  3. ReadA3(x)=20
  4. ReadB(x)=20
  5. ReadC1(x)=10
  6. ReadC2(x)=10

但是以下的ReadC1(x)和ReadC2(x)却不满住序列一致性:

  1. ReadC1(x)=20
  2. ReadC2(x)=10

因果一致 （Causal Consistency）

因果一致性（Causal Consitency）要求对于分布式系统里的每一个节点，对于所有的有因果关系的写操作，进程都以相同的顺序执行这些写操作，而读操作读出来的值必须反应出这个更新顺序，所以对于读操作：

  1. 对于同一个节点发起的读写序列，对于任何一个变量x的读操作read(x)，读到的值都是在此读操作之前最后一次此进程发起的写操作write(x)更新的值；
  2. 对于没有因果关系的写操作，其他节点的读操作可以按任意顺序返回值。

要实现因果一致性：

  • 对于写操作，使用基于矢量时钟的多播（Vector clock multicast）来完成所有节点的更新操作；
  • 对于读操作，立即返回本节点上对应变量的值。

对于图1，如果WriteA(x=10)和WriteB(x=20)之间有因果关系，以下返回值满足因果一致：

  1. ReadA1(x)=10
  2. ReadA2(x)=10
  3. ReadA3(x)=20
  4. ReadB(x)=20
  5. ReadC1(x)=10
  6. ReadC2(x)=20

但是以下的ReadC1(x)和ReadC2(x)却不满住因果一致性:

  1. ReadC1(x)=20
  2. ReadC2(x)=10

如果WriteA(x=10)和WriteB(x=20)之间没有因果关系，以下返回值满足也因果一致：

  1. ReadA1(x)=10
  2. ReadA2(x)=10
  3. ReadA3(x)=20
  4. ReadB(x)=20
  5. ReadC1(x)=20
  6. ReadC2(x)=10

FIFO一致 （FIFO Consistency）

FIFO一致性（FIFO Consistency）是最弱的一致性，它仅仅要求：对于同一个进程执行的读写序列，对于任何一个变量x的读操作read(x)，读到的值都是在此读操作之前最后一次此进程发出的写操作write(x)更新的值。而对于不同节点发出的写序列，其他节点的读操作可以按任意顺序返回值。

发表于 更新于 阅读次数：

以下列表是在高可用软件项目中经常用到的容错模式：

1. 架构类
  • Units of Mitigation
  • Correcting Audits
  • Redundancy
  • Recovery Blocks
  • Minimize Human Intervention
  • Maximize Human Participation
  • Maintenance Interface
  • Someone in Charge
  • Escalation
  • Fault Observer
  • Software Update
2. 检测类
  • Fault Correlation
  • Error Containment Barrier
  • System Monitor
  • Heartbeat
  • Acknowledgement
  • Watchdog
  • Realistic Threshold
  • Exisiting Metrics
  • Voting
  • Routine Maintenance
  • Routine Exercises
  • Routine Audits
  • Checksum
  • Riding Over Transients
  • Leaky Bucket Counter
3. 错误恢复类
  • Quarantine
  • Concentrated Recovery
  • Error Handler
  • Restart
  • Rollback
  • Rollforward
  • Return to Reference Point
  • Limit Retries
  • Failover
  • Checkpoint
  • What to Save
  • Remote Storage
  • Individuals Decide Timing
  • Data Reset
4. 错误缓解/消除类
  • Overload Toolboxes
  • Deferrable Work
  • Reassess Overload Decision
  • Equitable Resource Allocation
  • Queue for Resources
  • Expansive Automatic Controls
  • Protective Automatic Controls
  • Shed Load
  • Final Handling
  • Share the Load
  • Shed Work at Periphery
  • Slow it Down
  • Finish Work in Progress
  • Fresh Work Before Stale
  • Marked Data
  • Error Correcting Code
5. 错误处理类
  • Let Sleeping Dogs Lie
  • Reintegration
  • Reproducible Error
  • Small Patches
  • Root Cause Analysis
  • Revise Procedure

发表于 更新于 分类于 阅读次数：

概述

前两天家里台式机的Windows 10专业版提示我有更新，需要重新启动系统，结果在点击<重启>按钮让系统重启后，Windows 10无法正常引导，现象为过了主板启动画面后，不再显示Windows 10的视窗启动画面，而是一个光标在黑屏左上角闪烁了几次以后就直接进入了BIOS设置界面。由于BIOS设置界面中依旧可以找到硬盘，所以根据现象初步怀疑是引导区损坏。但麻烦的是，我的台式机启用了UEFI, 所以系统遵从的是UEFI引导模式，硬盘用的也是GPT格式，所以基于Legacy BIOS和MBR方式的修复方法并不适用于我的台式机。在网上遍查资料后，我终于把引导区重新修复，现在就把修复步骤整理一下写出来，希望对遇到同样问题的同学有帮助。

准备

首先，要准备一张Windows 8/10的安装光盘或者U盘（用Windows 8的安装盘也能修复Windows 10，这个本人亲测，网上有说Windows 7的安装光盘也可以，但是本人没有试过）；
然后，要设置引导设备的顺序为优先从光驱或者USB引导系统。

修复步骤

以下是修复步骤，一些屏幕上的选项文章里会写英文，因为我的Windows 8的安装光盘启动后使用了英文版选项：

步骤1：引导系统并通过安装盘进入控制台界面

  1. 从Windows 8/10的安装光盘或者U盘引导系统；
  2. 在Install now界面上选择Repair your computer；
  3. 在Choose an option界面上点击Troubleshoot；
  4. 在Trouleshoot界面上点击Advanced options；
  5. 然后再Advanced options界面上点击Command Prompt；

这时候Windows控制台界面就会显示出来，然后就可以进行步骤2。

步骤2：让UEFI分区可以通过控制台访问

  1. 在控制台里面输入DISKPART启动分区工具：
    X:> DISKPART
    然后控制台提示符应该会变成DISKPART>；
  2. 输入以下命令：：
    DISKPART> list vol
    DISKPART会把所有的卷（分区）给列出来，在这个列表里，你要找到UEFI分区，它一般处于主物理盘上，FS是FAT32，容量是100MB；记下它的卷号 *<vol#>*；
  3. 输入以下命令：
    DISKPART> sel vol **
    DISKPART会把卷号为 *<vol#>*的卷作为后面操作的默认卷；
  4. 这时候需要使用以下命令给卷设置一个唯一的ID：
    DISKPART> set ID=<GUID>
  5. 然后给卷设置一个驱动器符（我使用的是M:）：
    DISKPART> assign letter=M:
  6. 至此，UEFI分区就可以在控制台里使用M:来访问，DISKPART里的操作完成，我们可以使用exit命令退出DISKPART：
    DISKPART> exit

步骤3：修复引导记录

  1. 在控制台提示符下输入命令：cd /d M:\EFI\Microsoft\Boot，如果这一步执行报错，说目录找不到，那么就是步骤2里找到的卷（分区）不是UEFI分区，需要回到步骤2里重新找UEFI分区；
  2. 输入以下命令：
    M:\EFI\Microsoft\Boot> bootrec /fixboot

步骤4：修复BCD

  1. 输入以下命令：
    M:\EFI\Microsoft\Boot> ren BCD BCD.old
  2. 然后输入以下命令：
    M:\EFI\Microsoft\Boot> bcdboot c:\windows /s M: /f ALL
    注意，这个命令执行起来需要花费一些时间。

至此，UEFI引导应该已经被修复，可以退出控制台，选择关机，然后启动电脑，Windows 10系统就可以被正常引导了。

发表于 更新于 阅读次数：

简介

本人这段时间基于LSM(Log Structure Merge)技术和RAFT算法实现了一个分布式键值对存储系统项目，现在决定将该项目开源。项目工程位于：https://gitlab.com/netium/distkvstore

项目技术架构

该项目从整体上分为数据库引擎本身和共识引擎两部分。

数据库引擎是基于LSM的实现。
共识引擎使用了jgroups-raft库，该库提供了一个RAFT算法的实现。

该数据库可以根据配置文件的设定运行于单机模式和集群模式。当运行在单机模式下，共识引擎将不会启动，所有来自于客户端的请求将直接进入数据库引擎处理。当运行在集群模式下，共识引擎将会启动，集群里任何一个节点都能接收来自于客户端的请求，但是请求将会全部重定向到主节点，然后在共识引擎达成共识后将请求提交到数据库引擎处理。

发表于 更新于 阅读次数：
autoauto- [1. 概述](#1-概述)auto- [2. 基础Paxos算法特性](#2-基础paxos算法特性)auto- [3. 基础Paxos算法流程](#3-基础paxos算法流程)auto - [3.1 算法目的](#31-算法目的)auto - [3.2 前提假设](#32-前提假设)auto - [3.3 角色](#33-角色)auto - [3.4 算法流程](#34-算法流程)auto- [4. 使用场景](#4-使用场景)auto- [5. 活锁](#5-活锁)auto- [6. 注意事项](#6-注意事项)autoauto

1. 概述

    大家在讨论分布式系统的时候，一个经常要碰到的问题就是分布式系统里的一致性问题，也就是CAP理论中的C (Consistency)。让网络中各个节点达成一致性的一种方法，就是上一遍博客中提到的状态机复制 (State Machine Replication)，状态机复制的基础协议就是所谓的共识协议，而Paxos算法，就是为了让多个节点达成共识而发明出来的算法。
    虽然我们经常说Paxos算法，但是严格说来，Paxos是一整个协议族，里面包含：基础Paxos，Multi-Paxos，Fast Paxos和Egalitarian Paxos。而我们今天要讨论的，就是其中的基本Paxos（Basic Paxos）算法。

2. 基础Paxos算法特性

    基础Paxos算法具有以下特性：

  1. 最后达成共识的值只能从被提议的候选值中产生；
  2. 仲裁节点（Quorum）一旦就某个值达成共识，后面就不能就另外的值达成共识；
  3. 仲裁节点（quorum）一旦就某个值达成共识，那么最终所有的节点都将学习到这个值；
  4. 算法保证了安全性，但是理论上并不能保证活性；
  5. 算法能在不可靠的消息传输协议下（消息可以被丢失，重传，乱序）正常工作，但是消息要保证正确和完整；
  6. 如果有2N+1个节点参与算法，那么算法可以在N个节点失效的情况下依旧保证正常工作；

3. 基础Paxos算法流程

3.1 算法目的

    基础Paxos算法要解决的问题是：如果有2N+1个节点都有一个寄存器文件，并且针对这个寄存器文件提交了m个候选值，那么这2N+1个节点需要最终决定这个寄存器文件需要写入哪一个候选值，并且一旦至少N+1个节点对这个决定达成了共识，那么此决定将不可再更改。

3.2 前提假设

  1. 系统不存在拜占庭将军问题，即所有的节点不存在欺骗，消息在传输过程中要保证内容的正确和完整；
  2. 任意一个节点都可以发送消息到另外一个节点；
  3. 任何一个节点都可能失效；
  4. 网络协议本身并不可靠。

3.3 角色

    基础Paxos算法定义了如下角色：

  1. 客户端（Client）：向分布式集群系统发起请求（对值作出提议），并且等待集群系统的响应结果；
  2. 提议者（Proposer）：也可以叫做协调者（coordinator），提议者负责接受客户端发起的提议，然后尝试让接受者接受该提议，同时保证即使多个提议者的提议之间产生了冲突，那么算法都能进行下去；
  3. 接受者（Acceptor）：也可以叫做投票员（voter），负责对提议者的提议投票，同时需要记住自己的投票历史；
  4. 学习者（Learner）：如果有超过半数接受者就某个提议达成了共识，那么学习者就需要接受这个提议，并就该提议作出运算，然后将运算结果返回给客户端。

    这里给出的角色定义是算法层面的逻辑定义。在实际应用中，往往一个系统具有一个或者多个角色的功能。下图给出了各个角色的逻辑关系图：
角色关系图
注1：图中给出的示例有两个客户同时提交了请求，但是基础Paxos算法保证只有其中一个客户端的请求会被共识系统接受，而另一个客户端的请求将会被拒绝。

3.4 算法流程

    基础Paxos算法的核心思想是：多轮选举；超半数节点响应；响应结果传递。

    在基础Paxos算法中，任何一个Proposer都能发起新一轮的选举，即使上一轮的选举还没有完成。而且一旦Acceptor收到了新一轮选举的消息，那么它就要拒绝所有之前选举的消息。为了实现这个目的，Proposer在开始新一轮选举的时候都要给这轮选举付一个全局唯一的ID（Pro poseNum），而且此ID必须比之前所有进行过的选举的ID都要大。那么问题来了，要让所有的节点都能生成一个全局唯一ID，这本身就是一个共识问题，就变成了用一个共识问题去解决另一个共识问题。怎么办？一个比较简单的方法就是使用分布式ID生成算法：我们让Proposer所在的节点都有一个唯一的Server ID，然后每一个节点都维持一个本地的最大选举轮数计数器maxLocalRound，当我们需要ProposeNum的时候，我们可以通过如下算法生成它：

1
2
localRoundNum = ++maxLocalRound
ProposeNum = (localRoundNum << (bits of serverID)) | serverID

    我们可以重复执行以上算法直到ProposeNum大于当前正在进行的选举的ProposeNum。

    每一轮的选举都分为两个阶段：

  • 阶段一(Phase 1)：准备/承诺 (Prepare/Promise)

        目的：
        1. 停止所有之前还没有完成的选举；
        2. 尝试发现是否已经有提议被接受。

        流程：
        Prepare（Phase 1a）: proposer生成一个比它之间见到过的ProposeNum都要大的新ProposeNum，然后把这个新的ProposeNum通过prepare消息发送给所有的acceptor。
        Promise（Phase 1b）: acceptor内部维护着一个变量minProposeNum，当acceptor收到了一个prepare消息，并且消息包含的ProposeNum > minProposeNum, 则让minProposeNum = ProposeNum，并向proposer返回包含minProposeNum和<acceptedProposeNum, acceptedValue>的确认消息（如果acceptor在之前没有接受过任何proposal，则acdeptedProposeNum/acceptedValue可以设置为null）。然后，acceptor对于后面收到的任何消息，只要消息里的ProposeNum <= minProposeNum, 则将返回reject或者忽略。

  • 阶段二(Phase 2)：接受请求/请求被接受（Accepting/Accpeted)

        目的：
        1. 让acceptor接受某个提议。

        流程：
        Accepting（Phase 2a）: 当proposer在Phase 1b里收到了超过半数acceptor返回的确认消息，它将扫描所有返回的<acceptedProposeNum, acceptedValue>, 如果所有的acceptedValue都为null，则proposer可以自行决定接下来将要发送的value，否则，它必须将最大的acceptedProposeNum对应的acceptedValue作为接下来将要发送的value的值。然后proposer将向所有的acceptors发送附带有<ProposeNum, value>的accepting消息；
        Accepted（Phase 2b）: 当acceptor收到了带有<ProposeNum, value>的accepting消息后，如果ProposeNum < minProposeNum, 则返回reject消息或者忽略，否则，设置minProposeNum = acceptedProposeNum = ProposeNum, accptedValue = value. 然后向proposer和learner发送附带有minProposeNum的accepted消息。

当learner收到了超过半数acceptor针对于某个ProposeNum的accepted消息后，认为共识已经达成，它可以开始执行提议并向client返回最终结果。

4. 使用场景

     Paxos算法可以使用到一下场景里面：

  1. Leader选举，proposer把server id作为提议运行paxos算法，最后就哪个server id达成了共识，对应的server就能成为leader；
  2. 分布式锁，请求分布式锁的client把自己的client id作为提议发送给proposer运行paxos算法，最后就哪个server id达成了共识，对应的client就能获得分布式锁。
  3. 就状态机复制中节点replication log中的log entry达成一致。

5. 活锁

基础Paxos算法存在活锁的场景，如下图所示：
基础Paxos活锁

6. 注意事项

  1. 基础Paxos是一个Leaderless算法，也就是说，它的运行不依赖于系统选举出一个leader （基础Paxos本身就可以拿来做leader选举）；
  2. 虽然对于整个系统来说，一旦系统就某个提议达成共识，那么这个提议就是最终结果并且不能再改变，但是对于每一个acceptor来说，它们能在不同的选举轮中接受不同的值；
  3. Acceptor只负责投票和记录投票历史，它并不实际执行达成共识的提议，实际的执行操作是由learner来完成，其实我本人不是很赞成使用接受者(Acceptor)这个名词，因为给人的第一感觉就好像一旦接受了就可以开始执行提议了，但实际上它仅仅起到一个投票的作用，所以我觉得叫voter更好一些。

发表于 更新于 分类于 阅读次数：

    在分布式环境中，如果我们要让一个服务具有容错能力，那么最常用最直接的办法就是让一个服务的多个副本同时运行在不同的节点上。但是，当一个服务的多个副本都在运行的时候，我们如何保证它们的状态都是同步的呢，或者说，如果让客户端看起来无论请求发送到哪一个服务副本，最后都能得到相同的结果？实现这种同步方法就是所谓的状态机复制（State Machine Replication）。
    状态机复制的理论基础是：如果集群里的每一个节点上都运行着相同的确定性状态机S，并且所有的状态机刚开始都处于同样的初始状态s0，那么给予这些状态机相同的输入序列: {i1, i2, i3, i4, i5, i6, …, in}, 这些状态机必然会经过相同的状态转换路径: s0->s1->s2->s3->…->sn最终达到相同的状态sn, 同时生成相同的输出序列 {o1(s1), o2(s2), o3(s3), …, on(sn)}。
状态机复制在实际应用中的一个例子就是MySQL集群。我们知道，MySQL集群中的master会把所有的操作记录到binlog中，这里的操作就是输入序列I, 然后slave会把master上的binlog复制到自己的relaylog中，然后把把relaylog里的操作回放一遍（相当于执行了一遍输入序列I）。所以，如果master和slave里的状态机是完全相同的，并且在执行序列I之前都处于相同的状态下，那么执行完序列I后，它们的状态依旧是相同的（一致性）。
    在执行输入序列I的过程中，根据同步方式的不同，系统就有了强一致性和最终一致性。如果我们要求对于序列I中的每一个in, 都需要所有的服务副本确认成功执行了in，才能执行in+1，那么这个系统就是强一致性的系统。如果我们取消掉这个限制，仅仅要求所有的服务副本执行相同的输入序列I，但是完全各自独立执行，而不需要在中间同步，那么就有了最终一致性（各服务都会达到相同的最终状态，但是达到的时间不确定）。

发表于 更新于 分类于 阅读次数：

基于LSM的键值对数据库

THE SIMPLEST LOG

STRUCTURE BASED KEY-VALUE

STORAGE

  • Just one backend file;^
  • For any update operation, just append a new <K,V>
    record at the end of the backend file;
  • For any delete operation, append an tombstone record to
    the end of the backend file;
  • For any read operation, read from last record of the file
    back to the beginning, if a key is found, then return the
    <K,V>, if the tombstone is found or not key found, then
    the <K,V> doesn’t existed.

PERFORMANCE

  • Update Key: O(1);^
  • Delete Key: O(1) if not checking key existence;^
  • Read Key:^
    • For most recently updated key or delete key: O(1);^
    • For least frequently updated key: O(n) (n: all log items in the backend log);^
    • For average: O(n/2) (n: all log items in the backend log).^
  • Conclusion:^
    • Update/Delete friendly;^
    • Read unfriendly.

UNBOUNDED FILE SIZE

  • The original approach only append content to the file, so:^
    • Unbounded file size, and eventually run out of disk
      space;
    • Make the read performance even poor.^
  • Solution: Compaction.^
    • Compaction means throwing away duplicate keys in
      the log, and keeping only the most recent update for
      each key.

COMPACTION

  • Now we don’t have just one backend file, we have a set
    of backend segment files.

With compaction, we control the storage file size,

and removing duplicate item make lookup/read

faster, but, it’s still no fast enough…

1
Seg File
1
Memory

IN-MEMORY HASH INDEX

1
2
3
4
Key Offset
Alias 0
Charm 8
Tom 16
1
2
3
Alias 101
Charm 356
Tom 123
1
2
Each segment file will has its own
in-memory hash index

But, if the index table is too big to fit its whole into

the memory…

LSM (Log Structured

Merged) Tree

MEMTABLE

  • When a write comes in, add it to an in-memory balanced
    tree data structure. This tree is called a memtable;
  • When the memtable gets bigger than some threshold,
    flush it to a new segment file on the disk (which is called
    SSTable file);
  • This new SSTable file becomes the most recent segment
    of the database;
  • When a memtable is starting to flush to the SSTable file,
    all new incoming writes shall go into a new memtable.

SSTABLE

  • A segment file is the file that all <K,V> in it are sorted by
    the key;
  • This can be done because the SSTable is generated from
    the memtable, which is already a sorted structure;
  • The SSTable is immutable after created, which means that
    when it’s created from the memtable, no any update will
    apply to it.

SPARSE IN-MEMORY INDEX

  • With the SSTable, we don’t need to put very key into index table in memory;^
  • We just need to put a sub set of the keys into the index table;^
  • For searching a key:^
    • If key is in the in-memory index table, hit, fetch value and return;^
    • If key not hit in the in-memory index table but falls into some range between the two keys in the table, scan the content from the segment file between the two keys to see whether key existed, if hit, then
      fetch value and return.
1
2
3
4
Memory Seg File
Key Offset
Alias^0
Tom 16
1
2
3
Alias 101
Charm 356
Tom 123

COMPACT AND MERGE

  • For compact and merge of the SSTable files:^
    • Apply merge-sort to the SSTable files, so that the new
      segment file will still be sorted (a new SSTable file);
    • When multiple segments contain the same key, we keep
      the value from the most recent segment and discard the
      values in older segments;
    • Create new in-memory index table for the new SSTable;^
    • Delete the obsolete SSTable files and discard their in-
      memory index table.

FIGHT AGAINST TO LOSING

DATA

  • For updating data, the data flow is: request -> memtable -> SSTable;^
  • And memtable is only flushed to the SSTable (persistent storage) after a threshold is met;^
  • So if crash happens, then the data will get lost;^
  • Solution:^
    • Has a separate log on disk;^
    • Every time write request is coming, then immediately appended to this log;^
    • This log is not sorted;^
    • When recover from crashing, can replay this log to build up the memtable again;^
    • When memtable is flushed to the SSTable, then discard the corresponding item in the
      log.

REFERENCE

  • Design Data-Intensive Applications, by Martin
    Kleppmann, 2017.