阅读视图

发现新文章,点击刷新页面。
🔲 ☆

Cilium 的 Host Firewall 功能

Cilium CNI 之前一直看文档,功能大概了解,eBPF也大略看过。但一直没有深入从代码角度去研究。它的 bpf 相关代码做的比较全,而且比较老,跟现在网上的 BCC, CO-RW 还不太一样,而且代码量又大,所以读起来并不容易。这次借着 Host Firewall 功能的探究,深入看下。不可能面面俱到,但尽量多涉及一些。这篇文章在后面可能会继续更新,如果有新的发现的话。

一些基本概念

  • Endpoint: 可以理解为跟 device 挂钩的概念(host, pod 等等),还有特殊的 health endpoint等等。Endpoint有ID,也有对应的 Identity 和自己的 Policy. Endpoint 是 Node Scope 的概念。
  • Identity: 跟 label 挂钩。同一个deploy的两个Pod, 有不同的endpoint,但有同样的 identity. K8s Node共用同样的 Identity. Cilium 的 NetworkPolicy 即是针对于 Identity的。这个很好理解,二者主要都是使用 label 来做 filter. 跟 Endpoint 不同, Identity 是 Cluster Scope 的概念(label当然跟node无关)。
  • KV Store: 用来存储一些映射关系。Labels, Identity, Address, Node等这些元素之间的各种映射关系。Cilium 要实现 NetworkPolicy, 那么就需要这些映射关系。比如 Address -> Identity 等等。

不同的 CNI 在架构方面的差别还是挺大的。比如 KV Store 的需求,有的 CNI 就完全不需要。对 Cilium 来说,当有新的 NetworkPolicy时, agent 来计算 NetworkPolicy,如果发现自己所在的 Node 上有 Endpoint 受影响,那么就需要对此 Endpoint 做一些 Update (Regenerate BPF Programs等等),其他的 Node 则不需要。不同的 agent 则依赖于 KV Store 来互相交换一些数据。 引用一篇架构图所示:

(图片来自于: https://arthurchiao.art)

Cilium 选择使用 Identity 跟它的架构有关。因为使用 agent 来计算 NetworkPolicy. 如果没有 Identity, 那么每次新增加一个 Pod, 所有的 Pod 都需要计算一下 Policy. Identity 是基于 Labels, 相同的 Labels 的 Pod(比如一个 Workload 下的)共享一个 Identity, 那么在很多新增 Pod 的场景下 Policy 没有变更,减少了 agent 的工作量。那么如果从 Identity 获取 Pod 的 address 呢?就要用到上面所说的 KVStore.。所以上面图中的每个 Node 都需要 watch kvstore 中的数据。

Host Firewall 是什么

K8s 的 Network Policy 以及各个 CNI 的 Network Policy, 主要都是针对于 Pod/Service/Remote 的,最开始都不涉及到 Host相关的。我理解一般这块都有现成的其他工具在做。但将其纳入 NetworkPolicy 之内,也是自然发展趋势。这样方便用户。我们看一个 Cilium NetworkPolicy 的例子:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
apiVersion: "cilium.io/v2"
kind: CiliumClusterwideNetworkPolicy
metadata:
 name: "demo-host-policy"
spec:
 description: ""
 nodeSelector:
 matchLabels:
 node-access: ssh
 ingress:
 - fromEntities:
 - cluster
 - toPorts:
 - ports:
 - port: "22"
 protocol: TCP

nodeSelector 即指定了此 Policy 所涉及到的 Node. 其他部分跟一般的 Pod NetworkPolicy 差别并不大。其他的 fromEntities 字段没考证过是否是 Host Policy 所独有,其取值取值范围如下:

  • cluster: 当前集群的所有 Endpoint (Endpoint的概念需另外细讲)
  • host: local host 以及当前 host 上所有使用 host network 的 pod
  • remote-node: cluster 减去 host 的内容
  • health: cilium 管理的 health endpoint

可以看到,其 target 是针对 Endpoint 这个概念的。Endpoint 可以理解包含了 Pod, Host, 以及一些特殊的 Endpoint 的概念。我们可以通过下面的 Output 看下。这是一个 2 Nodes 的 Cilium 集群:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
# exec it in worker node's cilium pod:
# cilium endpoint list

ENDPOINT POLICY (ingress) POLICY (egress) IDENTITY LABELS (source:key[=value]) IPv6 IPv4 STATUS
 ENFORCEMENT ENFORCEMENT
456 Disabled Disabled 4 reserved:health 10.0.0.68 ready
972 Disabled Disabled 63615 k8s:io.cilium.k8s.namespace.labels.kubernetes.io/metadata.name=kube-system 10.0.0.69 ready
 k8s:io.cilium.k8s.policy.cluster=default
 k8s:io.cilium.k8s.policy.serviceaccount=coredns
 k8s:io.kubernetes.pod.namespace=kube-system
 k8s:k8s-app=kube-dns
1307 Disabled Disabled 63615 k8s:io.cilium.k8s.namespace.labels.kubernetes.io/metadata.name=kube-system 10.0.0.135 ready
 k8s:io.cilium.k8s.policy.cluster=default
 k8s:io.cilium.k8s.policy.serviceaccount=coredns
 k8s:io.kubernetes.pod.namespace=kube-system
 k8s:k8s-app=kube-dns
1723 Disabled Disabled 1380 k8s:io.cilium.k8s.namespace.labels.kubernetes.io/metadata.name=default 10.0.0.220 ready
 k8s:io.cilium.k8s.policy.cluster=default
 k8s:io.cilium.k8s.policy.serviceaccount=default
 k8s:io.kubernetes.pod.namespace=default
 k8s:run=nginx
3015 Disabled Disabled 1 reserved:host ready

这是 Worker Node 上的输出,可以看到如下内容:

  1. 包含了Pod,Host,Health. 其中Host,Health都是reserverd的label
  2. 每个 Endpoint 都有一个 ID, 并且都有一个 ID. 这个 ID 如其名,在很多地方用来做 Policy 决策。

Master Node 上的数据如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
# exec it on master node's cilium pod

ENDPOINT POLICY (ingress) POLICY (egress) IDENTITY LABELS (source:key[=value]) IPv6 IPv4 STATUS
 ENFORCEMENT ENFORCEMENT
386 Disabled (Audit) Disabled 1 k8s:node-access=ssh ready
 k8s:node-role.kubernetes.io/control-plane
 k8s:node-role.kubernetes.io/master
 k8s:node.kubernetes.io/exclude-from-external-load-balancers
 reserved:host
565 Disabled Disabled 4 reserved:health 10.0.1.230 ready

Master Node 上一般没有 Workload, 所以只有 health 和 node 两个 Endpoint.

Cilium 主要通过 TC bpf 来实现其 datapath, 我们可以在 host 上的 device 里看到 tc bpf prog list:

1
2
3
# cmd: tc filter show dev eth0 ingress
filter protocol all pref 1 bpf chain 0
filter protocol all pref 1 bpf chain 0 handle 0x1 bpf_netdev_eth0.o:[from-netdev] direct-action not_in_hw id 510 tag ec099af6e42d92d6 jited

from-netdev 就是这个 bpf object 的 entrypoint. 实现 Host Firewall 这个功能,对 Cilium 来说,相当于只是在 Policy 决断的时候加了一些规则,整体的 datapth 还是不变的。下面将对 golang code 以及 bpf code 做一个简要的 walkthrough.

Golang 相关代码

注: 参考的代码版本为 v1.11

Golang 部分的代码会比 BPF 相关的代码多很多,此处尽量挑最相关的说。真正在阅读此类代码时,结合着 DEBUG LOG 是比较好的策略。我们的场景是:Add NetworkPolicy, 这部分最开始的处理跟其他的 Operator 方式一样,Controller Watch CRD + Handler.

policyAdd

File: daemon/cmd/policy.go

Cilium 中大量地用到了 EventQueue. Add NetworkPolicy 的事件,最终在 RepositoryChangeQueue 里增加了一个 Event, 并且交由 policyAdd 处理。其工作如下:

  • 处理 CIDR 相关的 Rule. 本例中没有用到
  • 根据 Rules 选出需要 Update 的 Endpoint.代码中一般叫 Regeneration (其中涉及到重新生成 eBPF 程序).

选出相应的 Endpoints 之后,生成另一个 Event 中,并 Push 到 RuleReactionQueue 中。

reactToRuleUpdates

File: daemon/cmd/policy.go

此函数便是 RuleReactionQueue 的最终 Handler. 主要任务就是 Regenerat 相关的 Endpoint. 方法仍然是通过 EventQueue.

EndpointRegenerationEvent.Handle

File: pkg/endpoint/events.go

regenerate endpoint. 涉及到一些本地文件操作(/var/run/cilium),生成新的 BPF Program 并 attch 上去。这部分涵盖的内容很多,最好结合DEBUG日志看下,此处不再细说。

相关 BPF 代码

注: 参考的代码版本为 v1.11. 比较短的函数就直接全贴出来了。

from-netdev

入口即是 from-net-dev:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// FIle: bpf/bpf_host.c
/*
 * from-netdev is attached as a tc ingress filter to one or more physical devices
 * managed by Cilium (e.g., eth0). This program is only attached when:
 * - the host firewall is enabled, or
 * - BPF NodePort is enabled
 */
__section("from-netdev")
int from_netdev(struct __ctx_buff *ctx)
{
 __u32 __maybe_unused vlan_id;

 /* Filter allowed vlan id's and pass them back to kernel.
 */
 if (ctx->vlan_present) {
 vlan_id = ctx->vlan_tci & 0xfff;
 if (vlan_id) {
 if (allow_vlan(ctx->ifindex, vlan_id))
 return CTX_ACT_OK;
 else
 return send_drop_notify_error(ctx, 0, DROP_VLAN_FILTERED,
 CTX_ACT_DROP, METRIC_INGRESS);
 }
 }

 return handle_netdev(ctx, false);
}

注释里解释的比较清楚,这个只应用于 TC 的 Ingress. 开启条件是 Host Firewall 功能或者 NodePort 功能打开。本例中打开了 Host Firewall 功能。所以能看到上面的 bpf object.

handle_netdev

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * handle_netdev
 * @ctx The packet context for this program
 * @from_host True if the packet is from the local host
 *
 * Handle netdev traffic coming towards the Cilium-managed network.
 */
static __always_inline int
handle_netdev(struct __ctx_buff *ctx, const bool from_host)
{
 __u16 proto;

 if (!validate_ethertype(ctx, &proto)) {
#ifdef ENABLE_HOST_FIREWALL
 int ret = DROP_UNSUPPORTED_L2;

 return send_drop_notify(ctx, SECLABEL, WORLD_ID, 0, ret,
 CTX_ACT_DROP, METRIC_EGRESS);
#else
 send_trace_notify(ctx, TRACE_TO_STACK, HOST_ID, 0, 0, 0,
 REASON_FORWARDED, 0);
 /* Pass unknown traffic to the stack */
 return CTX_ACT_OK;
#endif /* ENABLE_HOST_FIREWALL */
 }

 return do_netdev(ctx, proto, from_host);
}

这里主要的代码是处理ethertype不合法的情况,如果开启了 audit 之类的功能的话可以上报一些事件。我们假定 ethertype 合法,跳过这部分。这里也获取了 proto (v4,v6)的值。

do_netdev

do_netdev 比较长,部分原因是需要根据上层的 feature gate 来定义 marco (bpf程序里很常见)。其中包括了是否开启 IPSEC, IPV6等等功能以及相应的处理代码。这里我们简单起见,只看 IPV4 及 HOST_FIREWALL 相关的情况:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#ifdef ENABLE_IPV4
 case bpf_htons(ETH_P_IP):
 identity = resolve_srcid_ipv4(ctx, identity, &ipcache_srcid,
 from_host);
 ctx_store_meta(ctx, CB_SRC_IDENTITY, identity);
 if (from_host) {
# if defined(ENABLE_HOST_FIREWALL) && !defined(ENABLE_MASQUERADE)
 /* If we don't rely on BPF-based masquerading, we need
 * to pass the srcid from ipcache to host firewall. See
 * comment in ipv4_host_policy_egress() for details.
 */
 ctx_store_meta(ctx, CB_IPCACHE_SRC_LABEL, ipcache_srcid);
# endif
 ep_tail_call(ctx, CILIUM_CALL_IPV4_FROM_HOST);
 } else {
 ep_tail_call(ctx, CILIUM_CALL_IPV4_FROM_LXC);
 }
 /* We are not returning an error here to always allow traffic to
 * the stack in case maps have become unavailable.
 *
 * Note: Since drop notification requires a tail call as well,
 * this notification is unlikely to succeed.
 */
 return send_drop_notify_error(ctx, identity, DROP_MISSED_TAIL_CALL,
 CTX_ACT_OK, METRIC_INGRESS);
#endif

这里面需要关注的是:

  1. 取出了 Identity, 这个在上面的 Endpoint 里提到。具体涉及到的逻辑比较多,有机会再细说。
  2. 通过 eBPF 的 tail call 继续往下走。

tail_handle_ipv4

tail call 调用了此函数。然后继续走到 handle_ipv4

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
static __always_inline int
tail_handle_ipv4(struct __ctx_buff *ctx, __u32 ipcache_srcid, const bool from_host)
{
 __u32 proxy_identity = ctx_load_meta(ctx, CB_SRC_IDENTITY);
 int ret;

 ctx_store_meta(ctx, CB_SRC_IDENTITY, 0);

 ret = handle_ipv4(ctx, proxy_identity, ipcache_srcid, from_host);
 if (IS_ERR(ret))
 return send_drop_notify_error(ctx, proxy_identity,
 ret, CTX_ACT_DROP, METRIC_INGRESS);
 return ret;
}

handle_ipv4

比较长,截取相关部分

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
#ifdef ENABLE_HOST_FIREWALL
 if (from_host) {
 /* We're on the egress path of cilium_host. */
 ret = ipv4_host_policy_egress(ctx, secctx, ipcache_srcid, &monitor);
 if (IS_ERR(ret))
 return ret;
 } else if (!ctx_skip_host_fw(ctx)) {
 /* We're on the ingress path of the native device. */
 ret = ipv4_host_policy_ingress(ctx, &remote_id);
 if (IS_ERR(ret))
 return ret;
 }
#endif /* ENABLE_HOST_FIREWALL */

后面就是实际计算 Policy 的地方了。

Links

  1. https://docs.cilium.io/en/v1.9/gettingstarted/host-firewall/
  2. Layer 3 Examples
  3. Cilium Code Walk Through: Agent Start
  4. Cilium PR: Network policies for the host endpoint
  5. Endpoint Lifecycle
  6. Cilium Code Walk Through: Cilium Operator
  7. Cilium Code Walk Through: Restore Endpoints and Identities
  8. Cilium Code Walk Through: CNI Create Network
🔲 ☆

eBPF Loop

eBPF Loop 是个老大难问题,只要实际开发大概率都会遇到。Kernel 版本越高,loop 的支持也越多。最近在 LWN 上又看到一篇关于 bpf loop 的新实现,如果能合并进去,那么就有三种 loop 得方式了:

  1. bounded loop: 跟传统编程模式很像,但loop的count必须是已知的
  2. map iterator: 针对 bpf map 的迭代器,可以用来遍历 map
  3. bpf_loop 函数: 最新的提议,能让 verifier 处理的更快

目前的 verifier 的策略是比较激进的,因为它没法验证所有的场景,所以有可能会对一些实际正确的程序验证不通过。bpf_loop 主要就是从这个角度来考虑问题,相当于对最开始的 bounded loop 做的一个优化。下面将详细介绍。

Bounded Loop

Kernel 5.3 之前, eBPF 不支持 loop. 要想实现类似功能,而且前提是明确 loop 的次数,那么基本上只能靠 unroll 来实现。示例如下:

1
2
3
4
#pragma clang loop unroll(full)
 for (i = 0; i < 4; i++) {
 /* Do stuff ... */
 }

相当于把 loop 展开。5.3 及之后,就不用这样了。

MAP Iterator

Bounded Loop 只能解决一部分的问题。总会有 unbounded loop 的场景。5.13 引入了 map iterator, 支持对 bpf map做遍历。考虑到 bpf map 在 eBPF 程序中的普遍性,算是一个比较好的解决方案了.

具体可参考: https://lwn.net/Articles/826058/

bpf_loop

bpf_loop 仍然是 bounded loop 范畴。但从 verifier 的角度考虑,大大简化了 verify 的逻辑。相当于把 loop 从普通的函数流程里抽取了出来,单独用一个 bpf 函数来实现:

1
2
 long bpf_loop(u32 iterations, long (*loop_fn)(u32 index, void *ctx),
 void *ctx, u64 flags);

这个 patch 还没合并。

Links:

  1. Are loops allowed in Linux’s BPF programs?
  2. A different approach to BPF loops
🔲 ⭐

eBPF Timeline

bcc 的文档已经做了很多详细的介绍,关于 kernel 中 eBPF 的变化: https://github.com/iovisor/bcc/blob/master/docs/kernel-versions.md. 本文记录的是我在测试过程中发现的几个比较重要的节点。

5.2

这块没找到详细描述,是根据程序实测出来的。在运行包含 map 的 eBPF 程序时,有如下错误:

1
failed to load objects: field Ingress: program _ingress: map .rodata: map create: read- and write-only maps not supported (requires >= v5.2)

错误信息提示的比较清楚,5.2内核及以上的就可以。不太确定为啥用上了 read/write only的 maps, 猜测是 libbpf 内部的实现机制导致的。因为这个问题,我目前将我测试的 eBPF 程序支撑的最低内核设定为 5.2 了。这点挺可惜的,因为 4.x 的内核对 eBPF 的很多支持已经很完善了, ubuntu 18.04 就是 4.18 的内核。

5.8

kernel 默认带了 BTF 文件。这个 5.8 是不准确的,但确实没查到具体在哪个 kernel 版本默认带的。ubuntu 20.04 没有, 20.10 有了,暂且将其作为开始版本。kernel 对 BTF 的支持从 4.x 就有了,只不过最开始不是默认带的,如果需要,需要自己 打开开关并重新编译内核。如果考虑生产环境,这个其实挺麻烦的。如果设定为只支持自带 BTF 文件的版本,那就省事多了。

5.13

5.13 开始支持 map 的遍历了。最开始的 eBPF 是不支持 loop 之类的操作的,防止 crash kernel等等。但是因为程序开发离不了这个,后面又加入了 bounded loop, 但仍然是不够用的。因为很多复杂程序是没法提前知道需要 loop 多少次的。5.13 才开始支持了 map iterator. 不过要注意以下两点:

  • 这里所说的支持只是指 kernel space. 用户态的很早就支持了
  • 因为 libbpf 有了自己单独 sync 出来的代码库。所以也是可以在较老的 kernel 是链接 5.13+ 的 libbpf 来使用此功能。

Links:

  1. Crash because of TUN/TAP do not support ebpf
🔲 ☆

Kubernetes 的 Server-Side Apply

从 Kubernetes 1.18 开始,可以看到一个明显的变化就是资源的 YAML 在 metadata 部分多了很多信息:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
apiVersion: v1
kind: Namespace
metadata:
 creationTimestamp: "2021-02-18T03:03:40Z"
 managedFields:
 - apiVersion: v1
 fieldsType: FieldsV1
 fieldsV1:
 f:status:
 f:phase: {}
 manager: kube-apiserver
 operation: Update
 time: "2021-02-18T03:03:40Z"
 name: default
 resourceVersion: "199"
 uid: 2f4536b5-7302-4dc1-9620-052a567c917c
spec:
 finalizers:
 - kubernetes
status:
 phase: Active

比如这个 NS 的例子, 其中大部分都是 mangedFields部分.简单来讲,managedFields 字段是用来声明一个资源的各个字段的具体的管理者是谁.我们可以参考一个有点类似的案例, Node 的 conditions 字段:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
 conditions:
 - lastHeartbeatTime: "2021-02-18T03:05:25Z"
 lastTransitionTime: "2021-02-18T03:05:25Z"
 message: Flannel is running on this node
 reason: FlannelIsUp
 status: "False"
 type: NetworkUnavailable
 - lastHeartbeatTime: "2021-02-18T07:34:05Z"
 lastTransitionTime: "2021-02-18T03:03:36Z"
 message: kubelet has sufficient memory available
 reason: KubeletHasSufficientMemory
 status: "False"
 type: MemoryPressure

Contaions 是一个列表,不同的 Component 负责上报自己所观察到的信息,最终汇总到 Node 的 Status 下面.然后再合并汇总出一个整体的 Ready 状态. mangedFieds 也是有点类似的思路, 一个资源的不同部分是由不同组件/人负责维护的,显式的声明这种维护关系有助于各方协同地维护一个资源完整的状态.更直观的,我们可以看一个 Deployment 的例子. 首先,我们使用如下的 deployment 文件来创建

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
apiVersion: apps/v1
kind: Deployment
metadata:
 name: nginx-deployment
 labels:
 app: nginx
spec:
 replicas: 3
 selector:
 matchLabels:
 app: nginx
 template:
 metadata:
 labels:
 app: nginx
 spec:
 containers:
 - name: nginx
 image: nginx:1.14.2

创建命令是:

1
2
# -n 后面是希望使用的 namespace, 非关键信息
kubectl apply -f d.yaml -n ssa

最终生成的 deployment 如下所示(部分信息):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
apiVersion: apps/v1
kind: Deployment
metadata:
 annotations:
 deployment.kubernetes.io/revision: "1"
 kubectl.kubernetes.io/last-applied-configuration: |
  {"apiVersion":"apps/v1","kind":"Deployment","metadata":{"annotations":{},"labels":{"app":"nginx"},"name":"nginx-deployment","namespace":"ssa"},"spec":{"replicas":3,"selector":{"matchLabels":{"app":"nginx"}},"template":{"metadata":{"labels":{"app":"nginx"}},"spec":{"containers":[{"image":"nginx:1.14.2","name":"nginx"}]}}}}
 creationTimestamp: "2021-02-18T07:41:40Z"
 generation: 1
 labels:
 app: nginx
 managedFields:
 - apiVersion: apps/v1
 fieldsType: FieldsV1
 fieldsV1:
 f:metadata:
 f:annotations:
 .: {}
 f:kubectl.kubernetes.io/last-applied-configuration: {}
 f:labels:
 .: {}
 f:app: {}
 f:spec:
 f:progressDeadlineSeconds: {}
 f:replicas: {}
 f:revisionHistoryLimit: {}
 f:selector: {}
 f:strategy:
 f:rollingUpdate:
 .: {}
 f:maxSurge: {}
 f:maxUnavailable: {}
 f:type: {}
 f:template:
 f:metadata:
 f:labels:
 .: {}
 f:app: {}
 f:spec:
 f:containers:
 k:{"name":"nginx"}:
 .: {}
 f:image: {}
 f:imagePullPolicy: {}
 f:name: {}
 f:resources: {}
 f:terminationMessagePath: {}
 f:terminationMessagePolicy: {}
 f:dnsPolicy: {}
 f:restartPolicy: {}
 f:schedulerName: {}
 f:securityContext: {}
 f:terminationGracePeriodSeconds: {}
 manager: kubectl-client-side-apply
 operation: Update
 time: "2021-02-18T07:41:40Z"
 - apiVersion: apps/v1
 fieldsType: FieldsV1
 fieldsV1:
 f:metadata:
 f:annotations:
 f:deployment.kubernetes.io/revision: {}
 f:status:
 f:availableReplicas: {}
 f:conditions:
 .: {}
 k:{"type":"Available"}:
 .: {}
 f:lastTransitionTime: {}
 f:lastUpdateTime: {}
 f:message: {}
 f:reason: {}
 f:status: {}
 f:type: {}
 k:{"type":"Progressing"}:
 .: {}
 f:lastTransitionTime: {}
 f:lastUpdateTime: {}
 f:message: {}
 f:reason: {}
 f:status: {}
 f:type: {}
 f:observedGeneration: {}
 f:readyReplicas: {}
 f:replicas: {}
 f:updatedReplicas: {}
 manager: kube-controller-manager
 operation: Update
 time: "2021-02-18T07:41:42Z"
 name: nginx-deployment

其中 f 后面跟的是 field 的名字,其他部分都比较直观.可以看到 managedFieds 包含两个 item:

  • 第一个manager 是 kubectl-client-side-apply.因为这个 deploy 是我直接用 kubectl apply 创建的. 默认 kubectl apply 使用的是 Client-Side Apply 而不是 Server-Side Apply.
  • 第二个manager 是 kube-controller-manager, 比较直观.对比两个 manager 所管理的字段列表来看, kube-controller-manager管理的都是我们通常看到的由 系统 自动填充的信息, 比如 conditions, .status.repliacs等.而kubectl-client-side-apply 则是管理那些用户自己输入的信息.

如上所展示的 manager 机制即是 Server-Side Apply的核心, 下面将详述细节.

kubectl apply

首先我们需要大概了解 kubectl apply做了什么,分为如下几步:

  1. GET 查询目标 Object
  2. 如果 Object 不存在,则提交到API创建,并且将用户提供的 input 信息放到 新创建的 Object 的 annotations里(key 为 kubectl.kubernetes.io/last-applied-configuration)
  3. 如果 Object 已存在, 先读取到旧的 Object 的 kubectl.kubernetes.io/last-applied-configuration 的值, 然后与当前的做对比, 生成一个 diff (strategic merge patch), 用 PATCH 发给 API Server. 其中 diff 里面也会附带上最新的 kubectl.kubernetes.io/last-applied-configuration.

其中, strategic merge patch 需要单独提一下,它的主要特点就是对于 list 的 update 提供了 patchStrategy 以便对不同的字段做不同的处理.比如我们常见的 Pod 的 containers 列表:

1
2
3
type PodSpec struct {
 ...
 Containers []Container `json:"containers" patchStrategy:"merge" patchMergeKey:"name" ...`

举个例子.最初始的 Pod Template 如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
apiVersion: apps/v1
kind: Deployment
metadata:
 name: patch-demo
spec:
 replicas: 2
 selector:
 matchLabels:
 app: nginx
 template:
 metadata:
 labels:
 app: nginx
 spec:
 containers:
 - name: patch-demo-ctr
 image: nginx
 tolerations:
 - effect: NoSchedule
 key: dedicated
 value: test-team

假设想用如下的 yaml PATCH 这个 deploy

1
2
3
4
5
6
spec:
 template:
 spec:
 containers:
 - name: patch-demo-ctr-2
 image: redis
1
kubectl patch deployment patch-demo --patch "$(cat patch-file.yaml)"

依赖于上面的 containers patch 策略的声明,我们能得到如下的最终结果:

1
2
3
4
5
6
7
8
9
containers:
- image: redis
 imagePullPolicy: Always
 name: patch-demo-ctr-2
 ...
- image: nginx
 imagePullPolicy: Always
 name: patch-demo-ctr
 ...

这样更符合用户的期望.而其他的一些字段,如果没有声明 patchStrategy, 那么默认操作是 replace.

何为 Service-Side Apply

Server-Side Apply 可以字面地理解为将 kubectl apply的工作迁移到 Server 端来进行, 准确地可以定义为一种新的Merge算法.它的好处如下:

  • --dry-run如果是在 client 端进行,那么因为 Server 端存在各种 webhook以及 injector,很难模拟真实的情况.如果 –dry-run 放在服务端, 如果出错了,可以通过新加的 mangedFields 机制给用户更明确的提示
  • 如果不用 kubectl 而是 API 开发则很难利用到 kubectl 提供的功能
  • kubectl apply 使用的 kubectl.kubernetes.io/last-applied-configuration 更加声明式一些.用户发送一个资源的manifest,其中包含了自己关心的字段的期待状态.
  • 防止用户误修改一些字段
  • 多个组件/用户对资源的协作管理
  • 其他一些在 Server 端实现起来更简单的地方

Server-Side Apply 利用 managedFields 字段,追踪了各个字段的归属,并且能在更新的时候提供冲突检测(manager不匹配),并提供更为准确的提示.

managedFields 详解

现在我们可以详细看下 managedFields的内容:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 - apiVersion: apps/v1
 fieldsType: FieldsV1
 fieldsV1:
 f:metadata:
 f:annotations:
 .: {}
 f:deployment.kubernetes.io/revision: {}
 f:status:
 f:availableReplicas: {}
 f:conditions:
 .: {}
 k:{"type":"Available"}:
 .: {}
 f:lastTransitionTime: {}
 f:lastUpdateTime: {}
 f:message: {}
 f:reason: {}
 f:status: {}
 f:type: {}
 k:{"type":"Progressing"}:
 .: {}
 f:lastTransitionTime: {}
 f:lastUpdateTime: {}
 f:message: {}
 f:reason: {}
 f:status: {}
 f:type: {}
 f:observedGeneration: {}
 f:readyReplicas: {}
 f:replicas: {}
 f:updatedReplicas: {}
 manager: kube-controller-manager
 operation: Update
 time: "2021-02-18T04:58:50Z"

其中:

  • f: 代表字段名
  • v: 代表 value, 字段的值
  • k: 代表 key, map object, 包含 f/v
  • i: index, 数组的索引

k 不太好理解, 对应的资源字段示例如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
status:
 availableReplicas: 3
 conditions:
 - lastTransitionTime: "2021-02-18T04:58:50Z"
 lastUpdateTime: "2021-02-18T04:58:50Z"
 message: Deployment has minimum availability.
 reason: MinimumReplicasAvailable
 status: "True"
 type: Available
 - lastTransitionTime: "2021-02-18T04:56:00Z"
 lastUpdateTime: "2021-02-18T04:58:50Z"
 message: ReplicaSet "nginx-deployment-877f48f6d" has successfully progressed.
 reason: NewReplicaSetAvailable
 status: "True"
 type: Progressing
 observedGeneration: 1
 readyReplicas: 3
 replicas: 3
 updatedReplicas: 3

另外:

  • manager: 操作主体
  • operator: 动作
  • time: 操作时间

如下所示,我们将上面用到的 deployment 修改一下,然后用不同的 manager 去 apply 一下试试:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
➜ server-side-apply git:(master) ✗ kubectl apply -f d.yaml --server-side --field-manager='test1'
error: Apply failed with 1 conflict: conflict with "kubectl-client-side-apply" using apps/v1: .spec.replicas
Please review the fields above--they currently have other managers. Here
are the ways you can resolve this warning:
* If you intend to manage all of these fields, please re-run the apply
 command with the `--force-conflicts` flag.
* If you do not intend to manage all of the fields, please edit your
 manifest to remove references to the fields that should keep their
 current managers.
* You may co-own fields by updating your manifest to match the existing
 value; in this case, you'll become the manager if the other manager(s)
 stop managing the field (remove it from their configuration).
See http://k8s.io/docs/reference/using-api/api-concepts/#conflicts

上面的错误提示也展示了在冲突时可能的几种解决办法:

  • 覆盖: 如果确定是要修改,可以使用foce参数,强制覆盖,并且将其manager变更为自己
  • 忽略: 如果本身并不关心这个字段的值,可以将其从自己的 manifest 中移除然后重试
  • 共享: 将冲突字段改为原来的值,这种情况下更新后将与原来的manager共享管理.

同时需要注意的时,通常的两种更新操作对 manager 的处理也不同:

  1. PATCH: content type 为 application/apply-patch+yaml, 冲突逻辑如上所示
  2. UPDATE: 其他更新方式,完全忽略冲突

Controller 的使用

目前常用的对 resource 的操作基本上都遵循一个 READ-UPDATE 的步骤,因为 resourceVersion 的冲突问题. Service-Side Apply 有望能去掉 READ 这步,直接进行 UPDATE 操作.

一般也推荐 controller 在遇到冲突的时候执行 force 操作.

现状

功能仍有缺陷, 接口复杂,未到 stable 状态,尽量不用使用.

Links

  1. Kubernetes 1.18 Feature Server-side Apply Beta 2
  2. Understanding OpenKruise Kubernetes Resource Update Mechanisms
  3. Strategic Merge Patch
  4. Update API Objects in Place Using kubectl patch
  5. Break Down Kubernetes Server-Side Apply
🔲 ☆

算法笔记(1): 链表及其应用

最近准备系统的过一遍算法。一是因为看的很多项目最终多多少少都会涉及到算法,如果提前了解好会理解的更深入。二是之前也没有系统的看过,最近想定一个比较长久的学习计划。看文章的话网上质量参差不齐,有些东西只能这样弄,自己花时间慢慢找,总结,记录。算法这类前两天想看 LevelDB, 然后又得先看 LSM Tree, 然后发现还是得看红黑树。然后在网上找,发现文章一大堆,但写的都不行。我觉得想要了解红黑树的基本上肯定都会有一个疑惑“为啥要两种颜色”,可惜基本上没几篇文章能把这个东西讲清楚,知其然而不知其所以然。所以最终决定第一次在网上买了一个电子课,因为发现能讲的清楚的一篇文章是从这门课里摘录的。

所以后面会尝试更新一个持续的算法系列,笔记性质的。记录一些感兴趣的点。然后才是其他的一些感兴趣的项目和技术。本身作为第一篇,跳过了一些更基础的,直接从链表开始了。

链表本身也比较简单,基本原理都清楚。我觉得从应用层来看更有意思一点。主要就是两个

  • 约瑟夫问题
  • LRU等算法

约瑟夫问题

阿橋问题(有时也称为约瑟夫斯置换),是一个出现在计算机科学数学中的问题。在计算机编程的算法中,类似问题又称为约瑟夫环

人们站在一个等待被处决的圈子里。 计数从圆圈中的指定点开始,并沿指定方向围绕圆圈进行。 在跳过指定数量的人之后,处刑下一个人。 对剩下的人重复该过程,从下一个人开始,朝同一方向跳过相同数量的人,直到只剩下一个人,并被释放。

问题即,给定人数、起点、方向和要跳过的数字,选择初始圆圈中的位置以避免被处决。

或者更加数学的问法: 已知 n 个人(以编号1,2,3…n分别表示)围坐在一张圆桌周围。从编号为 k 的人开始报数,数到 m 的那个人出圈;他的下一个人又从 1 开始报数,数到 m 的那个人又出圈;依此规律重复下去,直到剩余最后一个胜利者。

这个问题可能是与单项循环链表最贴近的一个问题模型了。每个人都是一个节点,然后出局的人可以用操作指针的方法将其从链表中移除即可,最后剩下一个人的时候就是答案。下面是C代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <stdio.h>
#include <stdlib.h>

/*声明一个链表节点*/
typedef struct node
{
 int number;//数据域,存储编号数值
 struct node *next;//指针域,指向下一个节点
}Node;

/*创建链表节点的函数*/
Node* CreatNode(int x)
{
 Node *p;
 p = (Node*)malloc(sizeof(Node));
 p->number = x;//将链表节点的数据域赋值为编号
 p->next = NULL;
 return p;
}

/*创建环形链表,存放整数1到n*/
Node* CreatJoseph(int n)
{
 Node *head,*p,*q;
 int i;
 for(i = 1; i <= n; i++)
 {
 p = CreatNode(i);//创建链表节点,并完成赋值
 if(i == 1)//如果是头结点
 head = p;
 else//不是头结点,则指向下一个节点
 q->next = p;
 q = p;
 }
 q->next = head;//末尾节点指向头结点,构成循环链表
 return head;
}

/*模拟运行约瑟夫环,每数到一个数,将它从环形链表中删除,并打印出来*/
void RunJoseph(int n,int m)
{
 Node *p,*q;
 p = CreatJoseph(n);//创建循环链表形式的约瑟夫环
 int i;
 while(p->next != p)//循环条件,当前链表数目大于1
 {
 for(i = 1; i < m-1; i++)//开始计数
 {
 p = p->next;
 }
 //第m个人出圈
 q = p->next;
 p->next = q->next;
 p = p->next;
 printf("%d--",q->number);//输出出圈的序号
 free(q);
 }
 printf("n最后剩下的数为:%dn",p->number);
}

int main()
{
 int n,m;
 scanf("%d %d",&n,&m);
 RunJoseph(n,m);
 return 0;
}

LRU算法

不考虑各种优化算法的话,LRU场景本身也是很适合用来链表实现。需求描述如下:

  1. 如果此数据之前已经在缓存中,需要找到它,并且把它挪到表头
  2. 如果数据尚不在缓存中
    1. 缓存未满,直接插入表头即可
    2. 缓存已满,将表尾节点删除,将新数据插入表头

当然如果基于单向链表来实现的话,访问的时间复杂度都是O(n)。不过本文暂不涉及优化方式,后续再说。下面是一个示例的 go 实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
package main

import "fmt"

// LRU缓存淘汰策略的demo

// 这是一个单向链表的节点
type Node struct {
 Next *Node
 Value interface{}
}


// 缓存模型
type Memory struct {
 Head *Node // 头节点
 Max int32 // 链表的最大长度
}

// 向内存中插入变量的指针,若链表为空,则插入头节点
func (m *Memory) Insert(newNode interface{}) {
 if m.Head == nil {
 m.Head = &Node {
 Next: nil,
 Value: newNode,
 }
 return
 }

 var pre *Node // 前节点的指针
 current := m.Head // 当前节点位置
 var i int32 = 1 // 计数,第一个节点

 n := &Node {
 Next: m.Head,
 Value: newNode,
 }

 for {
 // 若该记录在内存中存在,则将其在链表相应位置删除,并插入链表的头部,若已在头部,则不变
 if current.Value == newNode {
 if pre != nil {
 pre.Next = current.Next
 m.Head = n
 }
 break
 }

 // 若当前节点是尾节点,则将变量指针插入链表头部,若长度超出了链表长度,则将链表最后一个节点删除
 if current.Next == nil {
 if i >= m.Max {
 pre.Next = nil
 m.Head = n
 } else {
 m.Head = n
 }
 break
 }

 pre = current
 current = current.Next
 i++
 }
}

func main() {
 m := &Memory{
 Max: 10,
 }
 for i := 0; i <= 11; i ++ {
 v := i
 m.Insert(&v)
 fmt.Printf("==========\n")
 fmt.Printf("head is %+v\n", m.Head)
 fmt.Printf("head value is %v\n", *m.Head.Value.(*int))
 fmt.Printf("==========\n")
 }
}

Links

  1. 算法科普:什么是约瑟夫环
  2. Go基于单向链表实现LRU缓存淘汰算法
🔲 ☆

Rick and Morty

我给很多人推荐过这部动画片。可能也是唯一一个我一直在不遗余力地给很多人推荐的艺术作品。

曾经我也跟很多人一样,在追《马男》,看似颓废却又奋进,真是一部优秀的剧集。后来偶然接触到了《Rick and Morty》,再去回看《马男》,不是它不好了,只是相比来说,它太平庸了。

很多喜好的东西都太过个人化了,即使你再爱,也知道你没法总给别人讲。但《Rick and Morty》不同,它是一个流行于全世界的东西,是文化本身,也是文化的反面本身。

很多美国的青少年如此痴迷,以至于在现实中做出种种奇怪的举动。川香酱的疯狂正是一个绝妙的对于这个剧的呼应。而对于中国的青少年来说,这个美国文化里衍生出来的动画片,包含了太多反美国文化的东西,以至于每一个大洋彼岸的年轻人都被它深刻地吸引,感同身受。它成了一个跨域东方与西方,跨越资本主义与社会主义,跨域文化的东西。

从内容上来说,抛开表面的光怪陆离,看似蹩脚的宇宙设定,下面隐藏的是每一个人一生都要遇到的问题:父母,子女,家庭,婚姻,种族,文化,梦想,自我的哲学思考等等。同样是表面的虚无主义,底层的复杂深刻。不同的人看会有不同的感受,但每个人都会沉浸其中。

《马男》的失败在于,同样是在探讨这些问题,但是太根植于美国文化,让其他地方的人总觉得有隔阂,且太过肤浅,没有悲剧式的深刻。《Rick and Morty》里最为痛苦的设定在于,Rick 知晓自己是一个动画角色,这种痛苦一直伴随着他,自杀而不能。

同样无法摆脱这种可能的我们,可能为了规避这样的痛苦而不敢去想这个问题。

🔲 ⭐

Sinfonia: a new paradigm for building scalable distributed systems

论文链接: Sinfonia: a new paradigm for building scalable distributed systems

Sinfornia 像是一个构建分布式系统的 SDK 。目前的市面上分布式系统已经非常多了,比如 etcd, zookeeper, ceph 等等。但他们都是分别实现的,彼此之间的代码并无太多借鉴。Sinfonia 的实践是很难得的,可以说比大部分的分布式软件都更有指导价值一些。

这个图中展示了 Sinfonia 中关键的几部分

  • user library: SDK 部分,隐藏了分布式系统处理内部细节的 SDK。用户基于 user library 来开发分布式应用
  • minitranscations: Sinfonia 的核心概念。一个分布式的事物机制
  • application node: 应用节点
  • memory node: 维持分布式系统内部状态的节点。

图中没有画出的有

  • 管理节点: 用于执行一些定期的 recover 任务
  • directory node: Application Node 访问 Memory Node 使用的是逻辑 id, directory node 记录了逻辑 id 与 真实地址的映射。

Memory Node

Memory Node 存储了应用的状态数据,根据不同情况,可能是存在 RAM 中,也可能是在磁盘上。 user library 封装了操作 Memory Node 中数据的方式。Application Node 可以与 Memory Node 是同台机器也可以是不同机器(有些 Application 出于性能考虑会需要 Applicaiton Node 与 Memory Node 为同台机器,Sinfonia 会告知 Application 此种情况以便让其尽量把数据写在本机)。

Sinfonia 的一个特点是,它的数据结构可以理解为都是字节数组,目的是为了解耦。每个 Memory Node 都只负责管理字节数组,并且可以通过 (memory-node-id, address) 这样的序列来定位具体的数据。user library 即封装了操纵 Memory Node 上这些字节数组的细节。

Memory Node是多个,出于数据 locality 的考虑,Sinafonia 并不提供负责均衡策略,而是让 Application 自己选择 Memory Node。Sinfonia 给 Application 提供了 Memory Node 的 load 信息供其参考。

Minitranscation

Minitranscation 可以说是 Sinfonia 的核心了。Application 可以通过它来访问和修改 Memory Node,并且保证一致性,持久性,隔离性以及可靠性。 它有如下优点:

  1. 允许用户将多次操作放到一个 batch 里面
  2. 可以直接在 commit protocol 里执行?
  3. minitransactions can execute in parallel with a replication scheme ?

一个 Minitranscation 包含三类操作, 按执行顺序如下所示:

  • compare items: 对比发送的数据与已经存储的数据。如果对比不相等,或者出错,那么整个 transcation 中断。
  • read items: 比较成功(相等), 读取数据
  • write items: 比较成功(相等), 写入数据

这几个 items 的组合能够实现我们普遍需要的一些原子语义:

  • swap: read -> write
  • compare-and-swap: compare -> write
  • acquire-lease: compare 0 -> write id

两阶段提交

标准的 two-phase commit 里,如果 coordinator 崩溃,整个系统需等待其恢复后才可用。在 Sinfonia 中,coodinator 就在 application node, 如果它不可用,系统并不会阻塞。而是阻塞在出问题的 Meomory Node 上(因为 Memory Node 保存了系统的核心数据,并且 Memory Node 有 replicate 机制来保证高可用性coodinator 的作用减轻了,它并不需要维持状态。只要在 Meomory Node 处理失败时重试即可。

需要注意的是, 在 phase 1, participant 在获取锁后,首先对 compare items 进行比较,如果成功,vote commit, 然后读取 read items ,记录 transcations(redo-log,只包含 write items).否则就 vote abort,释放锁并反悔了。

在 phase 2, coordinator 汇总结果,告知 participants 是 commit 还是 abort。如果是 commit, partcipants 开始写入 write items。

Cache

cache 放置在 Application 层,而不是在 Memory Node 上。这样做的好处有:

  • 灵活性更好
  • Application 对于 cache 的利用率比较高
  • Sinfonia 的架构更为简单,从 Sinfonia 获取到的数据永远都是最新的

Minitranscations 提供的 compare 机制可以让 Application 方便地校验其本地的 cache 是否有效。

容错

Sinfonia 使用四种机制来提供 Meomory Node 容错功能:

  • disk images: 保存 memory node 的数据的 copy。异步写,数据可能会比较老。reply repo-log 可以再 memory 数据丢失的时候进行恢复。
  • logging: 同步写,保存最近的数据更新
  • replication: 一个 stand-by 的 node。同步更新
  • backup: 数据备份。如果 disk images 数据丢失,可以尝试从 backup 恢复。

上面说到 coordinator 的作用在 two-phase commit 中的作用被削弱,因为其不保存状态。在其 crash 时,会使一些 transcation 陷入不确定状态。 Sinfonia 引入了一个 recovery coordinator 来解决这个问题。首先,每个 Momory Node 会记录其处理的一些 transcations 的状态,如下图所示:

recovery coordinator 会循环执行,读取 Memory Node 的记录,从 in-doubt list 中读取那些未提交的 transcations 并尝试恢复。首先,在 phase 1, recovery coordinator 要求所有的 participants vote abort。如果一个 participants 已经 vote 过了,那么就使用之前的 vote ,否则就 vote abort。phase 2 就跟普通的流程一样。 所以假设之前的 participants 都 vote 了 commit ,然后 coordinator 不可用,那么 recovery coordinator 就能将这个 transcations commit 了。否则就是 abort 。

如果一个 Memory Node crash, 上图中的 decided list 可以辅助 disk-image 用来恢复 Meomory Node 的内存数据。因为它也是异步写的,会有一些 transcations 存在于 redo-log 但不在 decided 中。这种情况下需要联系其他 particants 看他们的 vote 结果来判定这个 transcations 是否需要 replay。(参与某个 transcations 的particants都记录在 redo-log 中)

如果大部分或者所有 Memory Node crash, 管理节点会启动程序来尝试恢复。关于管理节点,论文中并未着重介绍。目前提到的就两个地方,一个是用于recovery coordinator,一个便是恢复整个系统的。所以看起来更像是一个救火的,并不是常驻服务。在此种情况下,每个 Meomory Node 都会用上面所说的方式进行自我恢复。但是可以通过主动向其他 Meomory Node 发送自己的最近的 transcations 来避免像上面那样的主动询问(交互量上的优化)。

垃圾回收

redo-log以及其他 log 随着时间的增长肯定是不断增加的,所以需要进行定期的垃圾回收。对于已经 aborted 的 transcation, 可以直接回收。对于已经 commited 的 transcation, 需要确保每个参与的 momory node 都将数据落地了。(因为会有 Node crash 的情况)。其他的 list 也会随着 redo-log 的清理同步回收一些 transcations。

forced-abort list 的回收要复杂些。因为 Sinfonia 允许 origin 和 recovery 两个 coordinator 同时运行。如果直接回收,会导致正在运行的 coordinator 出错(它仍想处理这个 transcation)。 Sinfornia 加了一个 epoch number 来处理这种情况。epoch number 与时间相关,由participants 定义并返回给 coordinator。每个 transcation 都与一个 epoch number 绑定。partipants 可以拒绝 stale 的 epoch(大于等于两个 epoch 的差距)。那么 forced-abort 中早期的 trancations 都可以被回收掉,因为如果要重试肯定会被 abort 掉。

数据备份

transication -> redo-log -> disk-image -> backup 。当然 disk-image 只会更新已经 commited 的 transcations, backup 可以从 disk-image 做整个 copy 或者 snapshot。

评论

这个论文引用次数还挺多。但是感觉设计的还是挺零碎的,一些核心概念可以借鉴,但作为一个整体还是感觉不太可靠。另外,不是很懂它是如何做到小部分 Memory Node 不可用时仍然保证系统可用的?

链接

  1. 论文笔记:[SOSP 2007] Sinfonia: a new paradigm for building scalable distributed systems
🔲 ☆

Golang FAQ

Golang FAQ 是一篇比较好的关于 Golang 设计的文档。比较琐碎,但是解释了很多 Golang 设计的权衡之处。没有语言是完美的,从工业界来看,Golang 是一种流行的,成功的编程语言。从语言设计来看,当然仍有欠缺与不足之处。许式伟是前者的角度,王垠是后者的角度。当然除了宏观层面,FAQ 文档仍然提供了很多有趣的细节。

文档的可得性

所有的语言都知道支持文档。但可得性是一个更重要的维度。 Python 有 PEP 系列详细解释了语言设计的细节, 有 read the docs 系统为各种 library 提供用户文档。 Golang有 godoc 工具以及 Golang blog, 还有像 FAQ 这样的设计 detail 解释。二者在此方面都是做的比较优秀的,也在一定程度上促进了语言的流行。

语言设计细节

可读性

可读性一方面是要考虑尽量贴近大部分程序员的背景以及知识结构,另一个方面语言的设定要尽量 common, 不会让人需要额外思考来确定一个语法的语义。Golang 对于大部分具有 c / python 等背景的程序员来说非常易懂,也尽量控制新的语法的数量,所以能够迅速的大范围的流行起来。

另一方面,为了语言的可维护性,去掉一些便捷的语法糖也是一个重要的考量。Golang 去掉了 ?: , 隐式类型转换,指针操作,Goroutine 的内部结构不对外暴露等等。虽然代码不会像 python 那样简短,但在可维护性以及稳定性上都有了改善。

Generic types

泛型的缺乏是 Golang 广受批评的一个点。Golang 在初期为了语言的可读性以及可维护性舍弃了泛型,而且从使用角度来看,范型并不是缺少了就无法写出拥有良好结构的代码。当然现在语言发展到成熟期,泛型的加入仍是值得考虑的。

Error 与 Exception

这两个东西只能说目前都没有完美的实现,各有各的问题。 Golang 选择了贴近于 C 语言的 error 形态,也一定程度上是为了语言结构的清晰性。

assertions

在语言层面去掉 assert 是比较好的,因为它的使用场景主要是程序员的偷懒。但是在 test 部分仍然不提供 assert 有点说不过去。目前有很多第三方的实现。

static link

虽然产生的 binary size 比较大,但是却正好和 Docker 成了好搭档。什么依赖都不需要 os 干涉,甚至直接从一个空的 base image 添加 go binary 也是可以执行的。

Tips

unused imports

尤其是在使用 Goland 的 auto-format 之类的特性时,再加上 import 时, 因为名称冲突必须使用 alias 的场景下,有时候加入一个 import 语句是一件挺麻烦的事。这种情况下,在代码修改或者重构时保留那些 unused imports 还是挺有用的,用如下的代码可以保留住这些 imports:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
import "unused"

// This declaration marks the import as used by referencing an
// item from the package.
var _ = unused.Item // TODO: Delete before committing!

func main() {
 debugData := debug.Profile()
 _ = debugData // Used only during debugging.
 ....
}

Links

  1. Golang FAQ
  2. 对 Go 语言的综合评价
🔲 ⭐

Common Index

这几天在重温 《疑犯追踪》,作为一个近科幻的代表作,其描绘的社会是如此地贴近现实,让人想到时都会有一种无力感。在技术社区的种种讨论中,总会有零星的关于此话题的讨论以及解决之道。去中心化网络作为其中一个核心概念,已经有很多落地的实验性产品,虽然仍然无法撼动如今的网络结构,但总是一些希望之火。另外一个最近引起热门讨论的技术便是 Common Index。搜索引擎发展了这么多年,在给人们带来了很多便利的同时,也带来了无数的负面影响。Common Index 是一种解决途径,虽然如去中心化网络一样,看起来都很遥不可及,但仍然是值得期待的。

搜索引擎是一种商业产品,其背后的公司依靠大部分依靠广告牟利。这是一种非常容易理解的商业模式,但是却造成了以下后果:

  1. Too Big To Fail: 搜索引擎技术随着互联网规模的发展,会形成越来越高的技术壁垒。没有任何新公司能进入到这个市场。Google 目前占据着绝对主流,其他几家只占有微量的比例:
  2. 搜索引擎公司可以通过一些看似 公平的策略来调整不同网页的权重,从而来影响互联网的发展。比如 Google 一直在提高支持移动互联网网页的比重。这样的行为不能说是很坏,但是否应该由一家公司来做这些决定呢?
  3. 搜索引擎公司可以通过人为调整搜索结果顺序来牟利。比如毫无底线的百度。

信息时代人们对于信息检索的需求是非常庞大的,而且或许正如某些人所说,它不再是一个普通的商品,而是成为类似于水电一样的基础设施,每个人的生存都依赖于这些东西。在这种情况下,搜索技术再由某些垄断公司提供是不合适的,尤其是公司容易受到地缘政治的影响。Common Index 对此的提议是将搜索技术分为两层: 底层是通用的 index 技术,上层是各个公司的定制部分。

这里OWIOpen Web Index, 即本文一直说的 Common Index。Common Index 作为基础设施,提供基本的互联网索引,不同的商业机构可以基于此添加自己的特定的索引,并提供不同的界面以及功能。比如我可以实现一个专门搜书的搜索引擎,或者一个专门用来搜索特定某个人的公开信息的搜索引擎等等。Common Index 让新公司加入搜索引擎这个市场变得可能,并且可以通过差异化的服务来获取用户。有了这个基础,搜索引擎市场便有可能成为一个良性竞争的市场。

要想这个设想变成可能, 操作起来是很麻烦的,所以很多类似的设想都只停留在设想阶段。我能想到两个问题便是:

  1. 谁来承担 Common Index 的成本? 理论上可以应该让参与这个市场的公司来共同承担,想扶持本国在此方面有所发展的国家可以资助本国公司去参与这个市场。
  2. 如何打破现有市场的格局? 最理想的情况是,在未来的某一个天,通过反垄断法将 Google 拆分, 分离出其 部分index 技术作为 Common Index 的基础。

当然,希望在未来讨论这些问题的时候,百度已经不在了。

相关链接:

  1. Can an Open Web Index break Google’s stranglehold over the search engine market?
  2. The Web is missing an essential part of infrastructure: an Open Web Index
🔲 ⭐

代码与注释

代码应该拥有良好的注释一直是业界共识,毕竟,在可预见的未来里,阅读代码的主要还是人。所有的语言都支持注释,有的拥有额外的注释提取工具及格式规范。但总体来说,大部分语言在这块做的都比较一般。Python有一些约定俗称的规范以及 Sphinx 这样的工具, Golang 的规范比较简单,但内置了 godoc 工具。Lisp 算是做的比较好的,示例如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
(defun small-prime-number-p (n)
 "Return T if N, an integer, is a prime number. Otherwise, return NIL."
 (cond ((or (< n 2))
 nil)
 ((= n 2)
 t)
 ((divisorp 2 n)
 nil)
 (t
 (loop for i from 3 upto (sqrt n) by 2
 never (divisorp i n)))))

其独特之处在于,不同于一般语言注释位于函数体之外,而是将其放置于函数 body 开始处。这样开发者更容易将其当作函数定义的一部分,也有助于养成良好的注释习惯。

Golang 虽然 在注释方面做的普通,但是在官方 library 以及最佳实践方面成功地鼓励了人们尽可能地写非常详细的注释,具体到一个 struct 的各个字段上。尤其是在 kubernetes 社区里面, 其Space Shuttle style 的 Code 对于社区的蓬勃发展可以说是一个极大的背后功臣,从如下的代码便可一窥其风格:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
// Adapts a ConfigMap into a projected volume.
//
// The contents of the target ConfigMap's Data field will be presented in a
// projected volume as files using the keys in the Data field as the file names,
// unless the items element is populated with specific mappings of keys to paths.
// Note that this is identical to a configmap volume source without the default
// mode.
type ConfigMapProjection struct {
 LocalObjectReference
 // If unspecified, each key-value pair in the Data field of the referenced
 // ConfigMap will be projected into the volume as a file whose name is the
 // key and content is the value. If specified, the listed keys will be
 // projected into the specified paths, and unlisted keys will not be
 // present. If a key is specified which is not present in the ConfigMap,
 // the volume setup will error unless it is marked optional. Paths must be
 // relative and may not contain the '..' path or start with '..'.
 // +optional
 Items []KeyToPath
 // Specify whether the ConfigMap or it's keys must be defined
 // +optional
 Optional *bool
}

可读性越好的代码越容易流行。Golang 在这方面做的很好。

Knuth 曾经发明过一种将注释发挥到极致的语言风格: Literate Programming。结构很类似于 Tex 和 Markdown, 代码穿插于文档之中,工具可以分别提取出其中的文档与源代码。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
\section{Hello world}

Today I awoke and decided to write
some code, so I started to write Hello World in \textsf C.

<<hello.c>>=
/*
 <<license>>
*/
#include <stdio.h>

int main(int argc, char *argv[]) {
 printf("Hello World!\n");
 return 0;
}
@
\noindent \ldots then I did the same in PHP.

<<hello.php>>=
<?php
 /*
 <<license>>
 */
 echo "Hello world!\n";
?>
@
\section{License}
Later the same day some lawyer reminded me about licenses.
So, here it is:

<<license>>=
This work is placed in the public domain.

虽然听起来跟普通语言差别不大,但是从如上的示例上看,其观感与普通的语言的差别非常之大。文档与代码拥有了同样的重要性。整个文件更像是作者一个思路的记录与阐释。这样的好处自然是在代码的可读性性上有一些独特的优势。但缺点也同样明显,已经有无数的人从各种角度对其进行了批评。最为显著的一个问题便是,作者选定了一种顺序方式来书写代码,但是人们阅读代码的顺序与习惯则是多种多样的。有的人想要完整地阅读代码,有的只想阅读某一个片段,不同的阅读顺序,频繁地跳转,都需要语言本身的支持。而 lierateing programming 并没有在这些方面有很好的方案。也许作为简短的代码说明是一个比较适合的场景。

🔲 ⭐

jekyll 的问题

考虑良久,决定将 Blog 迁移到 hexo。整个过程比想象的简单很多,也看了下二者的异同。相对于来讲,我觉得 hexo 在设计上比 jekyll 更为优良一些,更适合作为一个静态博客生成器。 那么,jekyll 的问题在哪?

目录结构

jekyll 的目录结构是 posts/themes/settings 等杂糅在一起,初看起来更好理解,但使用起来是很痛苦的。尤其是在更换 theme 的时候,需要小心翼翼地甄别哪些目录需要更换而哪些不需要。而 hexo 的目录结构更加清晰,每个 themes 的内容都包含在一个单独的目录中,与其他部分互不干扰。想要更换 theme 直接 clone 一个新的改一个配置参数即可。

更换 theme 的次数越多,jekyll 的目录结构会越来越乱,分不清哪些文件是当前必须的。而 hexo 没这个问题。

默认主题

jekyll 没有默认主题。或者说有,但大家不这样用。通常的用法都是找一个现成的第三方 blog clone 下来,然后按自己的需求改。这样有个问题就是,总会有一种不适配的感觉。因为主题都是别人为自己的使用配置的。而 hexo 提供了默认的主题,它是这个软件自带的一部分,是理所应当的属于我们自身的。而且这个默认的主题已经足够好用,同时第三方的next主题也占据了相当大的份额。不是说选择少,而是在 hexo 上能够更快地完成theme配置这一环而专注于内容。

功能

jekyll 各个 theme 的功能丰富程度差别很大,分页、评论、TAG 等等。不同主题想要添加新功能的方式不同,遇到问题处理的简易程度也不一样。而这种情况也往往导致用户会选择更换主题,然后继续恶性循环。hexo 的默认主题提供了对大多数常用功能的支持,而扩充起来也比较方便,不同主题在这块的差别也比较小。

内容发布

这块 jekyll 完全没做,必须得自己手动创建 md,添加头部的 attribute,之前还借鉴了其他人的 shell 脚本来根据模板自动生成这些内容。而 hexo 提供了new命令来创建新的 post,自动补上头部的内容,这样学习成本基本上就只剩 markdown 了。

目前静态博客软件的内容发布还是太偏程序员化了,可以参考 wordpress 的地方还有很多。目前已经有一些 admin 页面的项目流行起来,但还没有达到能让普通用户无学习成本使用的程度。

其他

目前静态博客的分化是好事,但有点像 linux distros 那样,最终也带来了很多恶性循环。大家不关注易用性去普及用户,而更关注彼此设计理念的不同。一堆程序员圈地自嗨,最终可能只是落得自娱自乐罢了。

🔲 ⭐

JFFS3 文件系统

看完了闪存,继续看文件系统。网上搜了一圈,发现都是讲 Andriod 的目录结构的,讲文件系统本身的少。目前能确认的是历史上曾经用过 ext4,yaffs,yaffs2 等。 估计目前主流的应该是 ext4。不过在搜索的时候先发现了一篇讲 jffs3 的,它在嵌入式系统上应用比较广泛,也是针对 Flash 存储特定设计的文件系统。不太确定现在的使用范围,但是拿出来研究下还是不错的。

闪存对文件系统的影响

闪存跟磁盘有很多不同的地方,在设计文件系统的时候,二者有很多不同的考量。简单的对比表格如下

闪存 磁盘
最小寻址单位(读) 字节 扇区
最小寻址单位(写) NOR FLASH 是字节,NAND FLASH 是页,擦除是块 扇区
寿命 由擦写块的最大可擦写次数 机械故障

闪存的这些特性,导致我们在设计文件系统的时候,必须考虑以下的问题:

  1. out of place update: 对于磁盘来讲,我们更新数据可以直接原地更新。但是闪存不行,因为无法将 bit 位从 0 -> 1。所以对于闪存的数据更新只能是在另外一个地方写入数据,然后将原数据标记为 dirty,再通过 GC 来定期回收.
  2. wear leveling: 磨损平衡。闪存的使用寿命是由擦写块的最大可擦写次数来决定的。超过了最大可擦写次数,这个擦写块就成为坏块(bad block)了。因此为了避免某个擦写块被过度擦写,以至于它先于其他的擦写块达到最大可擦写次数,我们应该在尽量小的影响性能的前提下,使擦写操作均匀的分布在每个擦写块上

闪存转换层

为了能让普通的文件系统(磁盘上的)能够在闪存上正常运行,需要有一个转换层:Flash Translation Layer(FTL)。它的功能就是将底层的闪存模拟成一个具有 512 字节扇区大小的标准块设备(block device)。对于文件系统来说,就像工作在一个普通的块设备上一样,没有任何的差别。

基本的实现思路就是对磁盘的扇区和闪存的块做映射。当上层的文件系统要写一个块设备的扇区时,闪存转换层要做下面的操作来完成这个写请求:

  1. 将这个扇区所在擦写块地数据读到内存中,放在缓存(buffer)中

  2. 将缓存中与这个扇区对应的内容用新的内容替换掉

  3. 对该擦写块执行擦写操作

  4. 将缓冲中的数据写回该擦写块

这种实现方式的缺点是很明显的:

  1. 效率低,对一个扇区的更新要重写整个擦写块上的数据,造成数据带宽很大的浪费。
  2. 没有提供磨损平衡,那些被频繁更新的数据所在擦写块将首先变成坏块。
  3. 非常不安全,很容易引起数据的丢失。如果在上面的第三步和第四步之间发生了突然掉电(power loss),那么整个擦写块中的数据就全部丢失了。这在突然掉电经常发生的嵌入式系统中是不能接受的。

当然,实际的 FTL 肯定不是这么简单,需要对这种模式做很多的优化。但不论怎么优化,性能以及可靠性上都不算很好。最终还是需要专门针对闪存的文件系统。

JFFS3

JFFS 的全称是Journalling Flash File System,有 JFFS3 肯定也有 JFFS2 以及 JFFS,只不过不是本文关注的重点。JFFS3 的存在本来也是为了解决 JFFS2 的一些问题,所以肯定也会附带介绍到。 从其名字可以看出,重点是journal。JFFS 文件系统整体可以看作一个大的日志(跟 LSM 有点像),根源就是上面所说的out of place update, 更新和新加数据都是不断地 append -> mark dirty -> gc 的过程。

JFFS2 的问题

对于文件系统来说,index都是非常重要的一环。index 能让我们更快地定位到文件和数据,其维护和更新也是文件系统设计的核心。JFFS2 将 index 放在了 RAM 中,很特殊,有很多优势,也是它很多问题的根源。 在比较小的闪存上,它的吞度量和性能很好,因为 index 的更新都是在内存中。但是闪存的容量越来越大,问题也就越来越凸显了:

  1. 挂载时,JFFS2 需要扫描整个闪存来建立 index, O(S)的复杂度,闪存容量越大,挂载越慢
  2. 同样的,闪存越大,index 越大,内存占用越大。同样是 O(S)

除开这些缺点,其优势也是很多的

  1. index 不占用闪存空间
  2. 吞吐量高
  3. 磨损平衡好,因为更新比较频繁的 index 都在内存中了

Index 的存储

JFFS3 的解决方式将 index 从 RAM 放回到闪存上,相当于基本上是重新设计了。这样就解决了 JFFS2 挂载慢的问题,因为不用每次重新在内存中 build index 了。index 放到闪存上面临的第一个问题就是更新数据时引起的 index 的连锁更新,如下图所示:

index 以一个树的结构存在,leaf node 存储最终的数据。假设我们要更新 H,需要在一个新地方写一个 H1,那么指向 H 的 F 以及指向 F 的 A(root)都需要更新,他们的更新也是在一个新地方写数据。JFFS2 因为是在 RAM 中存储了 index,可以原地更新,所以没有这个问题。一旦放到闪存中,这种连锁更新就很难避免了。这种实现方式有个名字叫Wandering tree

显而易见,树的 level 越多,这种方式的效果就越不好。用 B+树来实现是一个非常自然的选择。JFFS3 中所有的对象都是存在一个大 B+树上,index、数据、文件、目录、属性等等。每一个对象都有一个 key,查询的时候就用这个 key 来查询。

leaf node 存储了真正的数据,其他的 index node 存储的都是 index 信息。

The Journal

Wandering tree 的代价还是挺大的。JFFS3 在设计时参考了 JFFS2 的思路在内存中实现了一种cache来尽量避免这种高频次的更新。这种方式叫做journal(名字起的很不好)

在闪存上预留一些 block 作为 journal eraseblock,当有数据更新时,数据更新到这些 block 上,但是 index 在内存中更新,暂时不修改闪存上的 index。当有读取请求时,先看下内存中的 index(叫The journal tree),如果有那就用,没有的话就去闪存的 index 查。the journal tree 可以在合适的时机同步到闪存的 index 中。这样做的好处很多:

  1. 避免了 wandering tree 的昂贵开销,因为可以合并很多 index update
  2. 平衡损耗也很好。JFFS3 可以用比较好的算法来自己挑选 journal eraseblock

坏处也有,跟 JFFS2 一样,挂载的时候,如果想提前尽可能多的生成 the journal tree 来提升性能, 势必会增加挂载时间,一个权衡的问题。

Garbage collection

跟 JFFS2 一样,整体思路都是将有效数据挪到别的地方,然后更新 index。JFFS3 因为 index 在闪存上,实现起来更为复杂些。而且会碰到一个尴尬的问题, 因为更新 index 也需要写新的数据,有可能在 GC 的过程中产生的垃圾数据比回收的更多。。。

如上图所示,为了回收 1 中的一块数据,最终产生了 2 中三倍的垃圾数据。原论文直接跳过了这个问题,说是仍在开发中,没有特别好的解决方案。暂时也没有找到引用比较高的研究这个问题的论文。

Superblock

superblock 也是文件系统很重要的一环,可以说是 metadata 的 metadata。JFFS3 将 superblock 分为了两部分:

  1. static superblock: 固定不变的基本信息,放在第一个 eraseblock 中
  2. superblock: 经常更新的信息

superblock 的位置是不固定的,原因也是因为不能原地更新。JFFS3 在这块的设计也是相当的复杂:

anchor area 的位置是固定的,就是 JFFS3 的第 2,3 个 earseblock,其他的 chain earblock 和 super eraseblock 都是会一直更新的。通过这个链条可以就可以找到 superblock。 真正的 superblock 数据只占一个 sector,所有的指针也只占一个 sector,每个 eraseblock 包含 N 个 sector,每一次的闪存数据更新,superblock 都会更新, N 次 superblock 更新会导致上一个 chain eraseblock 更新,依次类推一直到 anchor area 的更新。

这里就有一个必须解决的问题: 在可擦除的次数用尽之前,ancher area 必须比 data area 能用的时间更长。不然到某个时刻数据更新时会发现 ancher area 已经无法更新了。这个问题涉及到了几个变量:

  1. 每个 eraseblock 包含的 selector 数量 N
  2. chain 的长度 m
  3. 闪存可用的 eraseblock 的数量 M

具体这几个参数怎么设置来保证这个基本原则论文中已经有详细介绍,本文不再赘述。但可能简单推理这几个变量的变化对于结果的影响。

  1. N 越大,这样 ancher area 的变动频率越低
  2. m 越大,ancher area 的变动频率越低

举个例子,目前 N=64, m=3 已经能支撑 128G 的闪存了。更大的容量需要更大的 N,m 参数。

Links

  1. IBM Developer: JFFS2 文件系统及新特性介绍
  2. JFFS3 design issues - MTD
  3. LWN: Wandering Tree?
❌