0%

引言

最近仔细看了下 Elasticsearch Operator,感觉它的设计有点别出心裁,在集群更新方面,比我所知道的 TiDB Operator 和 Prometheus Operator 做的更好。所以在这里做一个 Elasticsearch Operator 和 TiDB Operator 的对比。

ES Operator 滚动更新

ES 作为搜索存储组件,也是一种有状态应用。ES Operator 在19年的有一个 issue #1173 ,确定了基于Statefulset 做 ES 的部署。最近阅读完 ES Operator的代码,我发现它虽然基于Statefulset做集群管理,但是节点更新的逻辑脱离了 Statefulset 的倒序更新。ES Operator 将需要部署的Statefulset更新策略设置为OnDelete 策略,然后自定义了一套 节点更新 策略,这套更新策略简化为:

ES Operator 自定义了一套 Pod 预选机制,预选机制是可扩展的,当前已有多个预选规则,我总结了一下。

预选规则:

  1. 不得重启大于 MaxUnAvailable 的节点数。
  2. 只有当集群是 green 或者 yellow 的时候,才可以重启节点。
  3. 跳过正在重启的Pod。
  4. 在集群是 yellow 状态的时候,如果重启这个点,必须满足 shard 不会出现无 started 状态分片的情况。
  5. 一次只重启一个 master。
  6. 如果 data 节点没有更新完,不会更新 master 节点。
  7. 不会同时更新两个Pod 包含相同的 shard。

ES Operator 在更新 Pod 之前,会经过一系列的验证才会去操作集群,我觉得更加稳定。举个例子,[0,1,2] 三个 data 节点,如果 0 节点损坏宕机了,这个时候Operator 更新集群,如果按照Statefulset 的倒序策略,需要先重启 2 号节点,这个时候会让集群陷入更糟糕的场景。我们应该先重启 0 号节点,让它先恢复。所以 ES Operator 虽然脱离于Statefulset 重新写了一套更新策略,但是这套机制更灵活,让应用更稳定。

我画了一张更详细的流程图,描述 ES Operator 的滚动更新逻辑。

TiDB Operator 滚动更新

TiDB Operator 采用 Statefulset Partition 的方式滚动更新,这种方式可以控制节点依次更新,但是必须按照倒序的方式,在极端情况下,由于中间节点的损坏,倒序更新的方式会让集群陷入更加糟糕的地步。TiDB Operator 更新集群的时候,没有考虑到集群层面的可用性,只是对当前更新节点进行驱逐 region。这一点我们可以从TiDB Operator 更新 TiKV 的一段核心代码看出来。

代码如下:

画个图描述下依次更新的过程:

基于 TiDB Operator 当前的实现,我也提出来了自定义一套更新策略,增强在发布过程中的稳定性。参考 issue 4130

总结

从 ES Operator 的实现可以看出,有状态存储用Statefulset还是有很多问题点,所以大家会对它做很多增强,比如 AdvanceStatefulset。但是我觉得或许我们需要一款新的基于 Pod 重新组装的CRD,他需要更加灵活可扩展,来应对 TiDB ,ES 等复杂类型的组件。

双数组前缀树(Double array Trie)

引言

前缀树通常用在字符串查询和模糊匹配中,今天讨论前缀树的相关实现,着重了解双数组前缀树的优势。

  • 什么是前缀树
  • 三数组前缀树
  • 双数组前缀树

什么是前缀树 Trie (Retrieval)

Trie 是一种字符搜索树,是一种有效的索引方法,也是一种有穷自动机 DFA( deterministic finite automaton),DFA 就是一种有终止状态的状态转移。

如下图:

查询一个字符串,按字符从根节点搜索,像状态转移一样。

Trie 的算法复杂度依赖于搜索Key的大小,而不依赖于数据的大小,即算法复杂度是O(m),所以它一般比B Tree这种基于比较的索引方法快很多。

如何实现一个前缀树

二维数组存储

比如存储单词,每一层用数组a[第i层][26个字符+1(终止符号)]来存储。

因为数组长度不可变,每一层字符比较稀疏的话,就会造成空间的浪费。

链表存储

使用链表来存储每一层,空间可控制,但是状态转移的时候,必须遍历链表,算法复杂度就变成了O(m*n)(n是每层节点中的数量),降低了查询效率。

如下图:

Hash 存储

Hash 表每层搜索的算法复杂度在O(1),算是一种比较好的实现。但是算hash值,解决hash冲突,实际搜索效率还是比不上二维数组。

三数组前缀树(tripple-array)

使用 base next check 三个数组来存储.

参照上面的图我们理解一下: s->t,输入c字符。

  • base:base数组中每一个元素代表一个节点,base[s]的值是next和check数组的起始索引.
  • next:存储base[s]节点,在输入某个状态c,得到的下一个状态。即 next[base[c]+c]=t
  • check:存储转换过程中的的上一状态。check[base[s] + c] = s

通过三个数组,next维护转换的结果,check维护转换的上一状态,构造一个前缀树。这个做法做到空间节省,但是还不够,我们看下面的双数组前缀树。

双数组前缀树(Double-Array Trie)

双数组前缀树是对三数组前缀树的压缩优化,将next数组和base数组合并,check数组保留。

如下图:

  • check[base[s] + c] = s
  • base[s] + c = t

用check保存状态转移过程中的上一个状态,base[s]保存上一状态的偏移量。

双数组前缀树构造例子

  • 假定输入两个前缀为’ab’, ‘ad’,将字母a-z映射为数字1,2,3,…, 26.

  • 这里用-1代表数组元素为空,-2代表叶子节点, -3代表根节点

    • 初始状态

      对于索引0,check[0]=-3代表根节点, base[0]表示偏移基地址为1,其他元素为-1表示为空

  • 输入前缀ab

    • 输入a

      base[0]+a,由状态0跳转到状态2. check[2]为-1,说明为空,更新为父状态0;base[2]更新为跳转过来的base, 即base[0]的值1

    • 输入b

      base[2]+b,由状态2跳转到状态3,check[3]为-1,说明为空,更新为父状态2;由于字符串结束,将base[3]更新为-2,代表叶节点。

  • 输入前缀ad

    • 输入a

    图中base和check的状态不会变化。 根据base[0]+a,从状态0跳转到2。 check[2]不为空,但check[2]的值0与其父状态S=0相等,则无需更新,进入状态2,等待输入下一个字符。这个过程相当于一个查询过程

    • 输入d

    base[2]+d,由状态2跳转到状态5,check[5]为-1,说明为空,更新为父状态2;由于字符串结束,将base[5]更新为-2,代表叶节点。

  • 输入字符串ca,解决冲突问题

    • 输入c

    状态由0跳转到状态4,check[4]空闲,将check[4]赋值为0,base[4]赋值为1.

    • 输入a, 发生冲突

    根据base[4]+4 状态从4跳转到2, 但是check[2]非空,并且check[2]=0不等于父状态4,此时发生冲突

    • 解决冲突
      • 重新查找base 和 check数组新的空闲位置,我们找到base[6]和check[6]。我们将base[4]改为6-a=5。check[6]=4。如下图:

双数组前缀树优势和应用

Trie 树的双数组实现基本可以达到单数组实现的性能,同时能够大幅降低空间开销;但是其难以做到词典的实时更新。

BYVoid写的opencc,简繁翻译就是用的双数组前缀树。双数组前缀树在nlp中应用比较广泛。

libdatrie 是C语言版本的双数组前缀树。

hanlp hanlp中实现了java版本的双数组前缀树。还基于双数组前缀树实现了 Aho Corasick自动机 版本。

参考

#数据结构 #nlp #Trie

Kafka-exactly-once-设计思想

(备注: 不显示声明就是基于V1版本来讲解的)

  1. 什么是 cgroups.
  2. 为什么我们需要 cgroups.
  3. crgoups 是如何实现的.
  4. 如何使用 Cgroups
  5. Cgroup V2 版本有什么不一样
  6. 总结

什么是 cgroups

cgroup 基本概念

cgroups 机制是用来限制一个进程或者多个进程的资源。

概念:

  1. Subsystem(子系统): 每种可以控制的资源都被定义成一个子系统,比如CPU子系统,Memory子系统。
  2. Control Group: cgroup 是用来对一个 subsystem(子系统)或者多个子系统的资源进行控制。
  3. 层级(Hierarchy): Control group 使用层次结构 (Tree) 对资源做划分。参考下图:

每个层级都会有一个根节点, 子节点是根节点的比重划分。

关系:

  1. 一个子系统最多附加到一个层级(Hierarchy) 上。
  2. 一个 层级(Hierarchy) 可以附加多个子系统

进程和Cgroup的关系

一个进程限制内存和CPU资源,就会绑定到CPU Cgroup和Memory Cgroup的节点上,Cpu cgroup 节点和Memory cgroup节点 属于两个不同的Hierarchy 层级。进程和 cgroup 节点是多对多的关系,因为一个进程涉及多个子系统,每个子系统可能属于不同的层次结构(Hierarchy)。

如图:

上图 P 代表进程,因为多个进程可能共享相同的资源,所以会抽象出一个 CSS_SET, 每个进程会属于一个CSS_SET 链表中,同一个 CSS_SET 下的进程都被其管理。一个 CSS_SET 关联多个 Cgroup节点,也就是关联多个子系统的资源控制,那么 CSS_SETCgroup节点就是多对多的关系。

参考下 CSS_SET 结构定义:

1
2
3
4
5
6
#ifdef CONFIG_CGROUPS
/* Control Group info protected by css_set_lock */
struct css_set __rcu *cgroups; 关联的cgroup 节点
/* cg_list protected by css_set_lXock and tsk->alloc_lock */
struct list_head cg_list; // 关联所有的进程
#endif

为什么我们需要 cgroups

我们希望能够细粒度的控制资源,我们可以为一个系统的不同用户提供不同的资源使用量,比如一个学校的校园服务器,老师用户可以使用15%的资源,学生用户可以使用5%的资源。我们可以用 cgroups 机制做到。

crgoups 是如何实现的

cgroups 数据结构

  • 每个进程都会指向一个 CSS_SET 数据结构.(上文 进程和cgroups关系已经提供过)

    参考源码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    struct task_struct { //进程的数据结构
    ...
    #ifdef CONFIG_CGROUPS
    /* Control Group info protected by css_set_lock */
    struct css_set __rcu *cgroups; 关联的cgroup 节点
    /* cg_list protected by css_set_lXock and tsk->alloc_lock */
    struct list_head cg_list; // 关联所有的进程
    #endif
    ...
    }
  • 一个 CSS_SET 关联多个 cgroup_subsys_state 对象,cgroup_subsys_state 指向一个 cgroup 子系统。所以进程和 cgroup 是不直接关联的,需要通过 cgroup_subsys_state 对象确定属于哪个层级,属于哪个 Cgroup 节点。

    参考下 CSS_SET源码:

  • 一个 Cgroup Hierarchy(层次)其实是一个文件系统, 可以挂载在用户空间查看和操作。

  • 我们可以查看 绑定任何一个cgroup节点下的所有进程Id(PID).

    • 实现原理: 通过进程的fork和退出,从 CSS_SET attach 或者 detach 进程。

cgroups 文件系统

上面我们了解到进程和Cgroup的关系,那么在用户空间内的进程是如何使用 Cgroup功能的呢?

Cgroup 通过 VFS 文件系统将功能暴露给用户,用户创建一些文件,写入一些参数即可使用,那么用户使用Crgoup功能会创建哪些文件?

文件如下:

  • tasks 文件: 列举绑定到某个 cgroup的 所有进程ID(PID).
  • cgroup.procs 文件: 列举 一个Cgroup节点下的所有 线程组Id.
  • notify_on_release flag 文件: :填 0 或 1,表示是否在 cgroup 中最后一个 task 退出时通知运行release agent,默认情况下是 0,表示不运行。
  • release_agent 文件: 指定 release agent 执行脚本的文件路径(该文件在最顶层 cgroup 目录中存在),在这个脚本通常用于自动化umount无用的 cgroup
  • 每个子系统也会创建一些特有的文件。

什么是 VFS 文件系统

VFS 是一个内核抽象层,能够隐藏具体文件系统的实现细节,从而给用户态进程提供一套统一的 API 接口。VFS 使用了一种通用文件系统的设计,具体的文件系统只要实现了 VFS 的设计接口,就能够注册到 VFS 中,从而使内核可以读写这种文件系统。 这很像面向对象设计中的抽象类与子类之间的关系,抽象类负责对外接口的设计,子类负责具体的实现。其实,VFS本身就是用 c 语言实现的一套面向对象的接口。

clone_children flag 是干什么的

这个标志只会影响 cpuset 子系统,如果这个标志在 cgroup 中开启,一个新的 cpuset 子系统 cgroup节点 的配置会继承它的父级cgroup节点配置。

如何使用 Cgroups

我们创建一个 Cgroup,使用到 “cpuset” cgroup子系统,可以按照下面的步骤:

  1. mount -t tmpfs cgroup_root /sys/fs/cgroup
  2. mkdir /sys/fs/cgroup/cpuset
  3. mount -t cgroup -ocpuset cpuset /sys/fs/cgroup/cpuset
  4. 通过创建和写入新的配置到 /sys/fs/cgroup/cpuset 虚拟文件系统,创建新的 cgroup
  5. 启动一个 父进程任务
  6. 得到进程PID,写入到 /sys/fs/cgroup/cpuset tasks 文件中
  7. fork,exec 或者 clone 父进程任务。

举个例子,我们可以创建一个cgroup名字叫 “Charlie”,包含CPU资源 2到3核,memory 节点为1,操作如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 mount -t tmpfs cgroup_root /sys/fs/cgroup
mkdir /sys/fs/cgroup/cpuset
mount -t cgroup cpuset -ocpuset /sys/fs/cgroup/cpuset
cd /sys/fs/cgroup/cpuset
mkdir Charlie
cd Charlie
/bin/echo 2-3 > cpuset.cpus
/bin/echo 1 > cpuset.mems
/bin/echo $$ > tasks

## 查看cgroup信息
sh
# sh 是进入当前cgroup
cat /proc/self/cgroup

Cgroup V2 版本有什么不一样

不同于 v1 版本, cgroup v2 版本只有一个层级 Hierarchy(层级).

cgroup v2 的层级可以通过下面的命令进行挂载:

# mount -t cgroup2 none $MOUNT_POINT

cgroup2 文件系统有一个根 Cgroup ,以 0x63677270数字来标识,所有支持v2版本的子系统控制器会自动绑定到 v2的唯一层级上并绑定到根 Cgroup.没有使用 cgroup v2版本的进程,也可以绑定到 v1版本的层级上,保证了前后版本的兼容性。

在V2 版本中,因为只有一个层级,所有进程只绑定到cgroup的叶子节点。

如图:

节点说明:

  • 父节点开启的子系统控制器控制到儿子节点,比如 A节点开启了memory controller,那么 C节点cgroup就可以控制进程的memory.
  • 叶子节点不能控制开启哪些子系统的controller,因为叶子节点关联进程Id.所以非叶子节点不能控制进程的使用资源。

cgroup v2的cgroup目录下文件说明:

  • cgroup.procs文件,用来关联 进程Id。这个文件在V1版本使用列举线程组Id的。
  • cgroup.controllers文件(只读)和cgroup.subtree_control文件 是用来控制 子 Cgroup 节点可以使用的 子系统控制器。
  • tasks文件用来 关联进程信息,只有叶子节点有此文件。

    为什么这么改造?

    v1 版本为了灵活一个进程可能绑定多个层级(Hierarchy),但是通常是每个层级对应一个子系统,多层级就显得没有必要。所以一个层级包含所有的子系统就比较简单容易管理。

线程模式

Cgroup v2 版本支持线程模式,将 threaded 写入到 cgroup.type 就会开启 Thread模式。当开始线程模式后,一个进程的所有线程属于同一个cgroup,会采用Tree结构进行管理。

总结

通过对 Cgroup的学习,大致了解 Linux Crgoup 的数据结构,V2 版本层级结构的优化和 支持线程模式的功能。

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1
$ hexo new "My New Post"

More info: Writing

Run server

1
$ hexo server

More info: Server

Generate static files

1
$ hexo generate

More info: Generating

Deploy to remote sites

1
$ hexo deploy

More info: Deployment