分散KVS etcdの CAP/PACELC 定理における立ち位置と合意アルゴリズムRaft

2024-03-11 kubernetes algorithm

etcd は Kubernetes でも使われている分散KVS。

Raspberry PiでおうちKubernetesクラスタを構築する - sambaiz-net

Kubernetes のドキュメントには etcd is a consistent and highly-available key value store と書いてあり、であれば CAP 定理の P (Partition tolerance) を妥協しているのかと考えてしまうが、分散システムのネットワークが分断された場合 CA を維持するのは難しい気がする。

Daniel Abadi 氏はネットワークの分断時に可用性を放棄する CP システムと、分断耐性がない CA システムは本質的に同じなので CP/CA と AP の2種類しかないと述べていて、2010年に CAP 定理における C と A のトレードオフを明確にして発展させた PACELC 定理を発表している。これは Partition の問題が発生したとき Availability と Consistency のどちらを取るか、そうでないとき (Else) は Latency と Consistency のどちらを取るかというもの。

etcd が用いている合意アルゴリズム Raft ではいずれかのノードがリーダーとなり、書き込まれたデータをフォロワーに複製して過半数のフォロワーからのレスポンスをもってコミットされたとみなす。リーダーは定期的にハートビートを送り、これが送られてこないことで機能停止したと判断したフォロワーは自身が候補者となって他のノードに投票をリクエストし、自身を含めて過半数の票を得ると次の term のリーダーとなる。

Kubernetes で etcd を動かして確認してみる。

apiVersion: v1
kind: Service
metadata:
  name: etcd
  labels:
    app: etcd
spec:
  clusterIP: None
  selector:
    app: etcd
  ports:
  - port: 2379
    name: client
  - port: 2380
    name: peer

---

apiVersion: apps/v1
kind: StatefulSet
metadata:
  name: etcd
spec:
  serviceName: "etcd"
  replicas: 3
  selector:
    matchLabels:
      app: etcd
  template:
    metadata:
      labels:
        app: etcd
    spec:
      containers:
      - name: etcd
        image: quay.io/coreos/etcd:v3.5.0
        ports:
        - containerPort: 2379
          name: client
        - containerPort: 2380
          name: peer
        volumeMounts:
        - name: etcd-data
          mountPath: /etcd-data
        command:
        - /bin/sh
        - -c
        - | 
          /usr/local/bin/etcd \
          --name \
          ${HOSTNAME} \
          --initial-advertise-peer-urls \
          http://${HOSTNAME}.etcd:2380 \
          --listen-peer-urls \
          http://0.0.0.0:2380 \
          --advertise-client-urls \
          http://${HOSTNAME}.etcd:2379 \
          --listen-client-urls \
          http://0.0.0.0:2379 \
          --initial-cluster \
          etcd-0=http://etcd-0.etcd:2380,etcd-1=http://etcd-1.etcd:2380,etcd-2=http://etcd-2.etcd:2380 \
          --initial-cluster-state \
          new \
          --data-dir \
          /etcd-data
  volumeClaimTemplates:
  - metadata:
      name: etcd-data
    spec:
      accessModes: [ "ReadWriteOnce" ]
      resources:
        requests:
          storage: 1Gi

etcd-0 がリーダーとなった。

$ export ETCDCTL_ENDPOINTS="http://etcd-0.etcd:2379,http://etcd-1.etcd:2379,http://etcd-2.etcd:2379"
$ etcdctl endpoint status --write-out=table
+-------------------------+------------------+---------+---------+-----------+------------+-----------+------------+--------------------+--------+
|        ENDPOINT         |        ID        | VERSION | DB SIZE | IS LEADER | IS LEARNER | RAFT TERM | RAFT INDEX | RAFT APPLIED INDEX | ERRORS |
+-------------------------+------------------+---------+---------+-----------+------------+-----------+------------+--------------------+--------+
| http://etcd-0.etcd:2379 | 69691ed70da97612 |   3.5.0 |   25 kB |      true |      false |        30 |         35 |                 35 |        |
| http://etcd-1.etcd:2379 | 7e44220b60d58d6a |   3.5.0 |   25 kB |     false |      false |        30 |         35 |                 35 |        |
| http://etcd-2.etcd:2379 | 63cdb3774b98cc2e |   3.5.0 |   20 kB |     false |      false |        30 |         35 |                 35 |        |
+-------------------------+------------------+---------+---------+-----------+------------+-----------+------------+--------------------+--------+

$ etcdctl put aaa bbb
OK
$ etcdctl get aaa
aaa
bbb

リーダーを一時的に落とすと選挙が始まり etcd-1 が新たなリーダーとなった。

7e44220b60d58d6a is starting a new election at term 30
7e44220b60d58d6a became pre-candidate at term 30
7e44220b60d58d6a received MsgPreVoteResp from 7e44220b60d58d6a at term 30
7e44220b60d58d6a [logterm: 30, index: 36] sent MsgPreVote request to 63cdb3774b98cc2e at term 30
7e44220b60d58d6a [logterm: 30, index: 36] sent MsgPreVote request to 69691ed70da97612 at term 30
raft.node: 7e44220b60d58d6a lost leader 69691ed70da97612 at term 30
7e44220b60d58d6a received MsgPreVoteResp from 63cdb3774b98cc2e at term 30
7e44220b60d58d6a has received 2 MsgPreVoteResp votes and 0 vote rejections
7e44220b60d58d6a became candidate at term 31
7e44220b60d58d6a received MsgVoteResp from 7e44220b60d58d6a at term 31
7e44220b60d58d6a [logterm: 30, index: 36] sent MsgVote request to 63cdb3774b98cc2e at term 31
7e44220b60d58d6a [logterm: 30, index: 36] sent MsgVote request to 69691ed70da97612 at term 31
7e44220b60d58d6a received MsgVoteResp from 63cdb3774b98cc2e at term 31
7e44220b60d58d6a has received 2 MsgVoteResp votes and 0 vote rejections
7e44220b60d58d6a became leader at term 31

$ etcdctl endpoint status --write-out=table
+-------------------------+------------------+---------+---------+-----------+------------+-----------+------------+--------------------+--------+
|        ENDPOINT         |        ID        | VERSION | DB SIZE | IS LEADER | IS LEARNER | RAFT TERM | RAFT INDEX | RAFT APPLIED INDEX | ERRORS |
+-------------------------+------------------+---------+---------+-----------+------------+-----------+------------+--------------------+--------+
| http://etcd-0.etcd:2379 | 69691ed70da97612 |   3.5.0 |   25 kB |     false |      false |        31 |         38 |                 38 |        |
| http://etcd-1.etcd:2379 | 7e44220b60d58d6a |   3.5.0 |   25 kB |      true |      false |        31 |         38 |                 38 |        |
| http://etcd-2.etcd:2379 | 63cdb3774b98cc2e |   3.5.0 |   20 kB |     false |      false |        31 |         38 |                 38 |        |
+-------------------------+------------------+---------+---------+-----------+------------+-----------+------------+--------------------+--------+

$ etcdctl get aaa
aaa
bbb

次に StatefulSet の replicas を 1 に減らすと同様に選挙が始まるが、過半数の票が集まらないのでリーダーが決まらずデータも取得できなくなり、2 に増やすとリーダーが決まって再度取得できるようになった。つまり etcd は過半数のノードが機能停止しない限り動き続ける高い可用性(A)はありつつも、一貫性(C)を優先する PC(/EC) システムということになる。対照的にネットワーク分断時には可用性を、平時はレイテンシを優先する PA/EL の例としては Cassandra が挙げられている。

69691ed70da97612 is starting a new election at term 35
69691ed70da97612 became pre-candidate at term 35
69691ed70da97612 received MsgPreVoteResp from 69691ed70da97612 at term 35
69691ed70da97612 [logterm: 35, index: 45] sent MsgPreVote request to 63cdb3774b98cc2e at term 35
69691ed70da97612 [logterm: 35, index: 45] sent MsgPreVote request to 7e44220b60d58d6a at term 35

$ etcdctl endpoint status --write-out=table
...
+-------------------------+------------------+---------+---------+-----------+------------+-----------+------------+--------------------+-----------------------+
|        ENDPOINT         |        ID        | VERSION | DB SIZE | IS LEADER | IS LEARNER | RAFT TERM | RAFT INDEX | RAFT APPLIED INDEX |        ERRORS         |
+-------------------------+------------------+---------+---------+-----------+------------+-----------+------------+--------------------+-----------------------+
| http://etcd-0.etcd:2379 | 69691ed70da97612 |   3.5.0 |   25 kB |     false |      false |        35 |         45 |                 45 | etcdserver: no leader |
+-------------------------+------------------+---------+---------+-----------+------------+-----------+------------+--------------------+-----------------------+

$ etcdctl get aaa
...
Error: rpc error: code = Unknown desc = context deadline exceeded

参考

システムの高可用性の担保と etcd, Raft について

How is ETCD a highly available system, even though it uses Raft which is a CP algorithm?

PACELCで理解するCAPの定理(2)