Atom  是一个开箱即用却又可以充分拓展的的编辑器,不如来精子的  Atom 中文社区  瞧瞧?

Docker 与容器化技术实践

这篇文章由我 7 月末在 Connext 2016 进行的一次技术分享整理而来。

RP 主机

我在高一的时候开始尝试搭建自己的网站,当时市面上的「虚拟主机」基本上只提供 PHP 环境,限制也比较多。于是我在 Linode 以每月 20 美元的价格买了一台 Linux VPS 用来搭建网站,但当时我的零花钱无法负担这个开销,于是尝试性地公开出售服务器资源,为此我编写了一套叫 RootPanel 的虚拟主机管理系统。

和其他虚拟主机不同的是,RP 主机的用户可以有非常大的权限 —— 可以登录 SSH, 运行 Node.js、Python 之类的程序;而 RootPanel 则通过 Web 的界面允许用户使用 MySQL、MongoDB 数据库,并且通过 Nginx 共享 80 端口,RootPanel 会检查用户的请求是否符合权限要求,然后去与 Nginx 这些系统服务交互。

当时 Docker 还没有出现,我用了一些比较「传统」的方式来隔离 RP 主机上用户的权限:

  • 文件系统:Unix users(文件权限)、quota-tools(磁盘空间)
  • CPU 和内存:自行编写脚本来调整进程优先级(CPU 超限时)和杀进程(内存超限时)
  • 进程和网络:因为 Unix 本身的权限,无权向其他进程发送信号

在运行 Web 服务时,后端程序(例如 PHP-FPM、Python 的 uwsgi、Node.js 应用进程)本身由用户运行,以 Unix Socket 的方式提供服务(Unix Socket 会遵守 Unix 的文件权限机制),然后可以在 RootPanel 的 Web 界面上配置从域名到 Unix Socket 的映射(RootPanel 会检查你配置的 Unix Socket 是否在你的 home 目录中等),由 Nginx 完成反向代理,实现共享 80 端口。

Redis 和 Memache 这种轻量级数据库也是由用户自行运行的,通过 Unix Socket 提供服务来避免被其他用户访问到。出于性能考虑,所有用户会共同使用同一个 MySQL 和 MongoDB,用户可以在 RootPanel 的 Web 上创建和管理数据库,RootPanel 会为每个用户分配一个用户名和密码,使用这些数据库本身的用户机制进行权限控制。

当然 RP 主机现在已经被关掉了,详见 RP 主机和 GreenShadow 关闭计划

「隔离」和「资源控制」

到后来 2014 年初的时候我发现了 Docker, 它是一个基于 Linux 的轻量级虚拟化技术,可以以非常低的成本来创建与主机隔离的、可以独立进行资源控制的「容器」。

在前面 RP 主机的例子中,我们虽然一定程度地解决了这两个问题,但并不完美。隔离方面 RP 主机只做到了权限的隔离,但用户依然可以看到其他用户和它们的进程、网络链接;资源控制方面,CPU 和内存都依赖于脚本进行控制,控制的粒度和准确性显然不如利用内核本身的特性。

Docker 使用 Linux 2.6 提供的 namespaces 特性来隔离容器之间的文件系统(mount namespace)、主机名(UTS namespace)、进程(PID & IPC namespace)、网络(network namespace)、用户(user namespace)。使容器中的进程只能看到与自己有关的系统资源,完全感觉不到主机上其他的容器的存在。

Docker 还使用了 Linux 2.6 提供的 cgroups 特性来统计和限制容器的系统资源,包括 CPU(cpuset & cpu & cpuacct cgroup)、内存(memory cgroup)、磁盘 IO(blkio cgroup)等。在资源控制方面,因为是由内核执行的,因此可以进行非常细粒度的控制,例如在 CPU 上,既可以为容器设置权重,也可以直接设置最大使用率。

联合文件系统

在解决了隔离和资源控制之后,我们可以允许容器自由地修改容器内的文件系统,每个容器可以使用不同的发行版、运行不同版本的系统服务。但为了允许容器去自定义它们的文件系统,我们必须要为每个容器挂载一个单独的根目录,这样将会占用大量的磁盘空间。

为了解决这个问题,Docker 基于「联合文件系统(AUFS、OverlayFS)」实现了一个「镜像」的功能。联合文件系统是一种可以将不同的目录,以分层「叠加」的方式挂载为一个文件系统的文件系统。Docker 会将不同容器间共同的部分作为一个共用的只读层(例如发行版就是一个层),然后为每个容器再叠加一个可写的层,容器对文件系统的修改会写入到这个可写的层,而不是共享的层,在容器运行结束后,这个可写的层也可以固化为一个只读的层,被其他容器复用(这就是 docker build 的过程)。

将应用封装为镜像

Docker 的容器实际上都是从 Docker 镜像创建出来的,可以说镜像是容器的模板,这个概念类似于进程是由可执行文件创建出来的,但镜像不仅仅包含可执行文件,而是包含了一个程序允许所需要的所有环境。

我们可以通过 Dockerfile 来创建镜像,Dockerfile 中包含了若干指令,这些指令会在容器中被执行,而这些指令对文件系统的修改,会作为构建出的镜像中的一个「层」。

Docker 镜像让应用的「交付」变得简单了,在理想的情况下,Dockerfile 中包含了构建应用所需要的运行环境的指令,而镜像则是一次构建的结果,Docker 为镜像提供了二进制级别的兼容性,镜像可以被传输到其他 Linux 主机上直接运行,交付一个应用就像发送一个可执行文件那么简单。基于我们前面提到的联合文件系统,Docker 镜像在传输时只会传输新的层,如果不同的镜像基于同一个基础的镜像(层)来构建,那么并不会产生额外的传输和存储开销。

无状态的容器

在一个服务器端系统中,包含了大量业务逻辑、需要频繁修改的「应用进程」是最不稳定的部分,它可能会出错、会崩溃重启、会占用大量的计算资源,因此我们必须要能够快速地对包含应用的容器进行调整。为了做到这一点,一个得到了广泛认同的实践就是将应用实现为「无状态」的,即不在内存中持久性地保存数据,而是将这些状态存储到专门的数据库(Redis 等)中,这些数据库会有自己的分布式解决方案,而不必我们操心。

这样我们便可以随时停止和启动一个应用容器,而不必担心数据丢失或状态不同步,同时无状态的应用对容器数量也毫不关心,我们可以根据业务的负载情况随时调整容器数量进而增加业务的负载能力,应用也不关心这些进程运行在哪台服务器上(Docker 的镜像为容器提供了一致的运行环境),只要前端的负载均衡(Nginx)可以发现它即可,因此我们还需要一种「服务发现」的机制让负载均衡服务能够感知到新容器的加入和已有容器的退出。

分布式的容器调度

在一个公有云的场景中,我们往往需要管理运行在几十台服务器上的几千个容器,物理设备总是可能出现故障的,随着集群规模的增长,出现故障的频率将会越来越高,我们必须能够自动地发现和恢复这些故障,我们将这种程序称为「集群管理器」,它需要关注的问题包括:

  • 容器崩溃:应用进程因错误或内存超限退出,可以简单通过设置 Docker 的重启策略来解决。
  • 容器僵死:负载均衡器应该能够将应用容器无响应的情况通知给集群管理器来重启容器。
  • 服务器崩溃或失联:集群管理需要将崩溃的服务器上的容器移动到其他的服务器并从负载均衡中移除。

在一些计划中的维护任务也需要保证服务不中断:

  • 部署新版本:应逐个启动新版本的容器并加入负载均衡,确认新容器工作正常后再将旧容器从负载均衡中移除并停止。
  • 调度到资源充足的服务器:集群管理器应该能够感知到各个服务器的负载情况,将负载较高的服务器的容器移动到负载较低的服务器。

集群管理器需要决定将容器部署到哪台服务器,需要考虑的因素包括:

  • 服务器实际负载。
  • 有时容器会声明自己需要多少资源,虽然实际并没有占用这么多,但一段时间之后可能会有变化。
  • 将容器分散到不同的服务器以应对单个服务器失效。

集群管理器还应该能够应对自身或所依赖的服务失效的情况,通过反复地重试保证实际运行的容器与计划中的一致。

在集群管理器方面社区已经有了很多成熟的解决方案,例如 Docker Swarm、Kubernetes、Marathon,作为私有云来说都基本够用,但在公有云的场景下经常还是需要自己开发一部分功能来和现有系统(例如计费)整合的。

小结

因为随着需要处理的数据量越来越大,我们必须将系统设计成分布式的,这需要我们将计算资源进行一个抽象,不去考虑有关运行环境的细节问题,所以虚拟化是一个大的趋势。基于 Docker 的容器是虚拟化解决方案中的一种,也是目前受到了非常多关注的一种,这大概是因为内核级别的虚拟化有着非常好的性能,同时 Docker 作为一个开源的产品也有着非常活跃的社区。我今天主要介绍的是我在部署环节对 Docker 的实践,但 Docker 的应用并不止于此,在开发和测试环节同样有 Docker 的身影。

参考链接

给初入门程序员的建议

我们经常看到网络上有很多黑程序员的段子,但那不过是一群居心叵测的人散布的谣言,企图通过给新人们留下负面的印象,进而阻止更多人进入这个行业的方式,来保证不思进取的自己不会被行业淘汰。

解决问题的途径比得到结果更重要

解决问题是一个通用的能力,本应在学生时代习得,若是不擅长解决问题,怕是短时间内很难提升,但在一个具体的领域里,往往「途径」更加重要。

当你在一个论坛或社区提出一个问题时,有些惜字如金的大牛会直接丢给你一个链接,不会多留下哪怕半个字,不要小看一个链接,它可能比直接告诉你答案更有价值。

当你进入一个新的领域,遇到问题时往往不知道应该去哪寻找答案,这时候你会想如果有一个网站,列出了作为新手可能遇到的一切问题该多好。但世上没有这么好的事情,往往这些问题和解答分散在不同的网站上 —— 从这个链接就可以点过去。

不要相信一句话就可以描述的真理

网络上的大牛经常提出提出一些简洁有力的口号,例如「抽象可以解决计算机领域的一切问题」、「好的代码不需要注释去解释」、「动态类型语言才能提高编码效率」、「PHP 是世界上最好的编程语言」等等。

并不是说这些观点是错误的,但它们就像「苹果总是会落到地上」这种简单的理论一样,描述的情况是片面的,而非普适的。有些结论是前辈们花了大量的时间和精力探索出来的,但光知道一个结论对你的编程是没有太多指导意义的,更多的细节隐藏在得出这个结论的过程中。

所以如果提出这些观点的人没有深入介绍、你也不打算自行了解,索性不如忘掉这些话。

深入了解你使用的工具

在编程的过程中,我们需要借助大量的工具来完成版本控制、调试、重构、构建和部署等工作。包括你的编辑器(IDE)和操作系统都是必不可少的工具,选择一组好用的工具,并且不断地学习和配置它们,这样才能逐渐提高工作效率。

每个人在选择工具的过程中都会掺杂大量的个人喜好,但我建议大家在选择工具时考虑下面几个因素:是否是免费软件或开源软件、是否有公司在维护、是否有大量用户和活跃的社区、是否支持插件或拓展、是否支持多种平台。

写出可以运行的代码只是最基本的要求

当一个程序可以运行起来了,不要高兴得太早,这只是一个开始。例如你是否考虑到了各种边界情况;当程序收到非预期的输入会发生什么;所依赖的外部服务出现异常会怎样,发生错误时是否能从日志中还原出现场;如果程序处理的数据量或运行时间提高几个数量级会发生什么;构建、测试和部署过程是否做到了自动化;代码是否为将来的修改做好了准备等等。

先精通一种语言,再广泛涉猎

很多新手会各种编程语言搞得头晕目眩,不知道先从哪个学起,索性不如左右开弓,同时学习。

一旦你这样做了就会发现很难将同时学习的两种语言的知识区分开,因为它们实在太像了。但如果你先精通一门语言,了解了它每个语法的工作方式之后再学习其他语言就很轻松了,因为你对已掌握的语言已经足够了解,不会和新语言混淆。而且你会不由自主地用已掌握的语言去和新语言比较,更容易发现它们之间的差异,发现各自语法的内在逻辑。

WizardChess: 一个国际象棋 AI 的实现

这篇文章由我 6 月末在 LeanCloud 进行的一次技术分享整理而来。

我高一的时候曾读过一本「代码的力量:C/C++ 中国象棋程序入门与提高」,也想自己试着实现一个,连名字都想好了,就叫 Wizard Chess —— 哈利波特中的「巫师棋」。然而直到最近借着 AlphaGo 的热度,我才真正动起手来,代码开源在 GitHub,因为是纯前端程序,所以你可以直接访问托管在云引擎上的 Demo http://wizard-chess.leanapp.cn.

国际象棋是一种「透明」的、「没有随机元素」的博弈游戏,所谓「透明」是说在任一时间,博弈双方对局面的了解都是一致的(而不像牌类游戏看不到对方的手牌),大部分棋类游戏,例如五子棋、围棋都是如此,这类游戏需要的是非常强的逻辑推理能力去遇见若干回合之后的局面,本文介绍的方法也大体适用于这些棋类游戏。

在技术选型上,我选择了用 TypeScript 来编写核心代码以便可以同时运行于浏览器和 Node.js, 借助 TypeScript 的编译期类型检查,可以让我们更早地发现和类型有关的错误,同时 Chrome 本身也有着非常好用的调试器和性能分析器来查找性能瓶颈。前端方面我选择用 React 来编写 UI, Web Worker 来运行计算 —— 毕竟如果在主线程进行 CPU 密集的运算会阻塞事件循环。

最近一段时间,我发现在这种偏重于数据结构的程序中,「不可变」的数据类型将会极大地减少复杂度并且提高性能,但在我调研了 Immutable.js 后并没有直接使用它,因为我觉得可能我不需要它提供的那么复杂的数据结构,而是自己在编码时注意不要修改参数、函数总是返回新的对象。

建模

第一步是将国际象的规则建模到代码中,首先是定义一些数据结构来表示国际象棋中的元素(阵营、棋子、棋盘):

enum ChessType {
  king, queen, rook, bishop, knight, pawn
}

enum Camp {
  black, white
}

interface Piece {
  type: ChessType;
  camp: Camp;
}

interface Board {
  /* from 0 to 63 */
  pieces: Array<Piece>;
}

然后需要为每一种棋子编写一个「生成走法」的函数,以便我们的程序知道一个棋子有哪些走法可走,在此以国王为例:

function generateMovesForKing(board, piece, camp) {
  for target in ([-1, -1], [0, -1], [1, -1], [-1, 0],
                 [1, 0], [-1, 1], [0, 1], [1, 1]) {
    if (target on the board and (target is empty or target.camp != piece.camp)) {
      yield target
    }
  }
}

按照国际象棋的规则,国王可以以直线或斜线的方式移动一格,因此上面的代码会检查相邻一格的位置是否在棋盘范围内、是否是空的或者有对面的棋子(吃子)。

然后还需要考虑到我们的程序和外部的输入输出,在国际象棋领域已有一个叫 FEN 的标准来表示当前的局势(各个棋子在棋盘上的位置),下面是一段表示开局状态的 FEN:

rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR

FEN 为每种棋子规定了一个字母、用大小写表示黑棋或者白棋、用斜线分割不同的行、用数字表示空白。在我们的程序的 Web 界面中有一个填写 FEN 的文本框,当你填入一个新的 FEN 时,棋盘上的棋子会随之改变;反过来当你移动棋子时,FEN 也会跟着改变,这将会让我们后续的调试变得非常简单。

局面评估

我们的程序会在每个回合中,从众多可能的走法中选择一个对自己而言最优的走法,所以我们需要一个函数去评估和量化一个走法对我们而言的优势。

function evaluate(board: Board, camp: camp): number {
  var ourScore = 0;

  for piece on board {
    if (piece.camp == camp) {
      ourScore += getScode(board, piece)
    } else {
      ourScore -= getScode(board, piece)
    }
  }

  return ourScore;
}

这个函数会接受一个棋盘(board)和一个阵营(camp)作为参数,这个棋盘其实就是应用了某个走法之后,各个棋子的位置。这个函数会检查棋盘上每个棋子,如果这个棋子是我方的,就将其代表的分数加到「我方的优势分数」上;如果是对方的,就从我方的优势分数中减去对应的分数。

每个棋子所代表的分数则按照下表来计算:

棋子 基础分数 每多一种走法的额外分数
10000 2
皇后 1000 2
500 2
400 2
300 2
100 2

在这里我们凭「直觉」,按照棋子的重要性,给了每个棋子一个基础分数。但如果只有基础分数的话就会出现这样的情况:我们只能区分出出现吃子行为时的优势,如果不发生吃子,那么所有局面的优势都是一样的。为了解决这个问题,我们可以为「每一个可能的走法」再增加两点分数,因为在象棋中,我们可以走到一个格子,就说明我们对这个格子有一定的控制能力(如果对方的棋子走到这个格子我们就可以吃掉它),引入这个代表「灵活性」的分数后,我们会认为有更多走法的局面是更具有优势的局面。

关于局面评估函数应该考虑什么、不应该考虑什么是一个值得思考的话题。因为我们的 AI 主要是靠下文介绍的「搜索」算法来找到最优的走法的,搜索函数会模拟双方的走棋,如果棋子之间存在守护关系,会在搜索中得到体现,有时过于「自作聪明」的评估函数反而会影响到搜索。在五子棋这样简单(搜索树小)的游戏中,我们甚至可以将评估函数精简为一个「判断胜负」的函数,因为按照目前的计算力,是有可能直接在搜索中找到获胜的局面的,而在象棋这种搜索树庞大的游戏中,我们还是需要评估函数的。

在我们的程序中,我将「灵活性分数」做成了一个默认不开启的选项,默认只计算棋子的基础分数,这是因为计算走法是一个相对开销较大的运算,会比较明显地减少搜索层数(减少一层)。

极大极小搜索法

棋类游戏的博弈 AI, 最核心的就是搜索算法,即通过轮流模拟双方走棋,找到最优的走法。搜索的层数就是模拟走棋的回合数,搜索层数越深代表博弈程序可以考虑得越远,能力也就越强,响应地消耗的计算资源也越多。

我们首先介绍一个非常简单的搜索算法 —— 极大极小搜索法,这个算法平淡无奇,只是深度优先地轮流模拟双方走棋:

function negaMaxSearch(depth: number, board: Board, camp: Camp): number {
  if (depth <= 0) {
    return evaluate(board, camp);
  } else {
    return getAllMoves(board, camp).reduce( (best, move) => {
      return Math.max(best, -negaMaxSearch(depth - 1, board.move(move), anotherCamp(camp)));
    }, -Infinity);
  }
}

我将这个算法实现为了递归的形式,参数 depth 用于控制搜索的深度,每递归一层便减少 1, 当减少到 0 的时候结束递归,使用评估函数评估这个局面的优势值;depth 大于 0 时则递归地搜索当前所有可能的走法(getAllMoves),返回其中优势值最大的局面。

注意在进行递归时,我们需要用 anotherCamp 来切换阵营,同时对结果取负值。这是因为在象棋中,博弈双方是轮流走棋的,我们需要先模拟自己走棋,再模拟对方走棋。在模拟对方走棋时,我们需要站在对方的角度来考虑 —— 我们需要找到对我方最不利的走法,因为我们需要假设对方是聪明的,是会尽一切可能针对我方的,所以在递归时我们需要对 negaMaxSearch 的结果取负。

wizard-chess-negamaxsearch.jpg

在我的电脑上,这个算法可以在使用单核心的情况下,花费 1 分钟来搜索 4 层。在开局状态下,搜索树有 9341 个节点,最终评估了 220211 个局面:

White {search: 9341, evaluate: 220211}
Black {search: 9341, evaluate: 220211}

Alpha/Beta 剪支

但其实在前面的搜索树中,有很大一部分节点是「没有意义」的,即无论是否搜索这些节点,对最终的结果都不会有影响,我们可以通过接下来介绍的 Alpha/Beta 剪支算法来跳过对这些无意义的节点的搜索。

wizard-chess-alphabetasearch.jpg

例如在上图中,如果我们从左到右深度优先地搜索走法树,那么右侧灰色的节点就是我们需要跳过的节点。depth=1 最右标有 5 的节点的左侧子树(5 - 5 - 5)被搜索出之后,depth=1 最右标有 5 的节点的最小值就已经被确定为了 5 —— 因为在 depth=2 时我们需要站在对手的角度找到对我方估值最低的走法,既然左侧子树已经找到了 5, 那么无论其他子树的值是多少,这个节点估值都不可能比 5 更大了。

如果 depth=1 最右标有 5 的节点的估值小于等于 5, 那么它对于父节点也是没有意义的,因为在 depth=1 的层我们需要找到估值最高的走法,既然在 depth=1 这层我们已经找到了一个估值为 6 的走法,那么我们就对估值小于等于 5 的走法不感兴趣了,因此图中灰色的节点我们都可以跳过。

function alphaBetaSearch(depth: number, board: Board, camp: Camp, currentCamp: Camp, alpha: number, beta: number): number {
  if (depth <= 0) {
    return evaluate(board, camp);
  } else {
    for move in getAllMoves(board, camp) {
      if (camp == currentCamp) {
        alpha = Math.max(alpha,
          alphaBetaSearch(depth - 1, board.move(move), camp, anotherCamp(currentCamp), alpha, beta)
        );
      } else {
        beta = Math.min(beta,
          alphaBetaSearch(depth - 1, board.move(move), camp, anotherCamp(currentCamp), alpha, beta)
        );
      }

      if (beta <= alpha) {
        break;
      }
    }

    if (camp == currentCamp) {
      return alpha;
    } else {
      return beta;
    }
  }
}

我们在极大极小搜索法的基础上进行了修改,得到了带有剪支(跳过图中灰色节点)功能的 alphaBetaSearch, 它多了 currentCamp, alpha, beta 三个参数。alpha 表示在当前搜索路径中,我方至少可以得到 alpha 的分数,任何低于 alpha 的局面都不考虑(剪支);beta 表示在当前搜索路径中,对方至少可以拿到 beta 的分数,任何高于 beta 的局面都不考虑(剪支),因对方不会放任你拿到更高的分数的;而 currentCamp 和 camp 将用于在搜索中区分「我方」和「对方」。

在递归时,我们会区分当前是「我方」还是「对方」。我方走棋时,将最好的估值保存到 alpha, 对方走棋时,我们将最差的估值保存到 beta, 如果某个局面的估值在 beta 和 alpha 之间则进行剪支(break)。

depth worst case best case
n b^n b^⌈n/2⌉+b^⌊n/2⌋−1
0 1 1
1 40 40
2 1,600 79
3 64,000 1,639
4 2,560,000 3,199
5 102,400,000 65,569
6 4,096,000,000 127,999
7 163,840,000,000 2,623,999
8 6,553,600,000,000 5,119,999

这个表格列出了 Alpha/Beta 剪支搜索在最好和最差的情况下搜索的局面数量级,所谓最好的情况就是每个最左子树都是最理想的估值,其余子树都被剪掉了,最差的情况就是每个子树都有着比左侧子树更理想的估值,因此我们需要搜索所有子树来找到最理想的估值。当然实际情况肯定是会介于最好和最坏的情况之间,在开局状态下,我们的程序表现如下,相比于前面的极大极小搜索,我们剪掉了 95% 的局面,只评估了 15k - 34k 的局面。

White {search: 1748, evaluate: 15854, cut: 1136}
Black {search: 2071, evaluate: 34740, cut: 1547}

从上面的数据可以看到很有趣的一点,开局状态下明明黑白双方的棋子位置差不多,但搜索的局面数量却差了一倍。这是因为 Alpha/Beta 搜索会比较严重地依赖搜索每个走法的顺序 —— 如果先搜索的是估值理想的走法,那么就会触发更多的剪支,搜索更少的节点,反之则会搜索更多的节点。而我们完全没有对走法做排序,所以搜索的顺序会取决于棋子在棋盘上出现的顺序 —— 没错,差别就是这么大。

因此在搜索子树的时候,对子树(走法)做一个预先的排序就显得很重要了,可以很大程度地提高剪支的效率。但同时这又是一个很矛盾的事情 —— 我们搜索就是为了找到最好的走法,但在搜之前却又需要先对走法进行一个排序。所以这个排序必须直观而简单,例如优先搜索皇后、车这类重要的棋子,

写在后

说实话,因为我数学基础比较差,也没有进行太多的性能优化,最后实现出来的 AI 非常地弱,基本每一步棋都很「蠢」,但至少实现了一个棋类 AI 应有的骨架。我今后可能不会继续维护这个代码了,所以相比于代码,可能这篇文章对读者的帮助会更大。

参考链接

国际象棋规则:

FEN:

Alpha/Beta 搜索:

测试数据:

12366