视频云源站的资源调度系统设计与实现

杨继伟

（乐视云计算有限公司，北京 100025）

0 引言

视频云服务是基于云计算、大数据等技术提供视频服务的网络应用模式。视频云服务需要消耗大量的基础设施资源，主要包括计算资源、存储资源、网络资源等[1]。基于视频市场的海量需求，云计算厂商为企业用户提供了便捷、低成本、高质量的视频云服务，但随着业务的发展，集群规模不断扩大，随之也带来很多问题，如集群管理、集群利用率偏低等[2]，因此如何管理这些资源，如何合理并高效的使用这些资源，从而降低成本，是云计算厂商关心的一个主要问题。

在视频云源站生产控制系统存在如下几个问题：一是生产任务的获取采用拉取模式，生产机器需要定时访问生产控制系统来获取任务，当没有任务时，机器仍然要访问生产控制系统，这造成了机器资源、网络资源的浪费。二是任务调度方式只是简单的区域调度，没有考虑资源情况，调度不均匀，导致节点利用率不均衡。三是调度模块与生产控制系统耦合在一起，随着业务发展以及调度策略的复杂性，使得生产控制系统越来越臃肿。

为解决上述问题，提出视频云源站的资源调度系统，将调度功能与生产控制系统解耦，完成生产层机器的统一管理和动态调度，均衡的使用机器资源，从而达到提高机器利用率的目的。

1 研究进展

视频云服务包括视频生产和终端播放两个环节，如图1所示。视频云生产是指源站不同协议、不同码率视频的生产。在这些任务环节中，需要合理的为任务分配机器，如分配转码机进行转码任务、分配RTMP服务器进行推流或拉流，分配录制机器对HLS切片进行录制等。

在云计算开源平台中，具有资源管理与调度功能的软件有OpenStack、Docker、Hadoop YARN。

OpenStack的作用是整合各种底层硬件资源对外提供虚拟机服务[3]，它的调度功能主要是用来决策虚拟机创建在哪个主机上。生产层机器一般为物理机，可以使用 OpenStack对物理机进行管理，提供虚拟机来部署生产服务。如果虚拟机性能满足点播、直播需求，那么替换掉物理机将大大提高机器利用率。

Docker是一个基于 Linux容器的高级容器引擎[4]，可以快速实现服务器扩容和自动化部署。当Docker技术应用在视频云源站服务中时，如果每个容器实例执行一个生产任务，随着任务数的增加容器实例也将不断增多，与生产控制系统间交互的量级也将急剧增多，为系统带来了负担。如果每个容器仍然执行多个生产任务，这种方式需要由上层业务方来管理每个容器上可执行的任务数量，还需要决策每个任务在哪个容器中执行，因此需要搭建资源调度系统对容器IP进行管理。

图1 视频云生产环节Fig.1 Production process of video cloud

Hadoop YARN[5]主要应用在大数据领域，调度的实时性以及与业务系统交互方式的缺失，并不适合应用在视频云源站的资源调度中。

综上所述，无论视频云源站生产过程中使用的是物理机、虚拟机还是容器，都需要对其进行管理，因此需要搭建视频云源站的资源调度系统实现生产任务调度功能。

2 需求分析

基于业务现状，资源调度系统应该满足如下功能：

第一，由于资源复用，同一台机器上每个服务可执行的任务数是不相同的，因此需要进行差别调度和管理。

第二，在特殊业务场景中，需要对机器调度进行个性化配置，如将某个用户的请求固定发送到某一台机器上。

第三，需要返回当前资源最优的机器，例如当需要转码时，需要找到一台资源最充足、离源站距离最近、网络链路较好的机器来进行转码。

由于需要对资源进行管理和配置，同时还需要向业务方提供调度接口，因此资源调度系统的用户有如下两类：

（1）系统管理员。系统管理员是资源调度系统的使用者，可以管理生产环节用到的节点、机器等信息；可以为业务方分配资源池，设置资源使用权限；可以灵活配置资源调度策略，屏蔽某个机器的资源调度；可以实时监控资源使用情况；对调度情况、资源情况进行统计分析。

（2）业务方系统。业务方一般是点播、直播生产控制系统，所以需要为其提供一个实时的、稳定的资源调度接口。

3 系统总体设计

3.1 系统架构设计

考虑到系统的健壮性、模块化、调度接口的性能以及便于管理，将系统设计分为两个子系统，一是资源管理子系统，二是资源调度子系统，系统架构如图2所示。

3.1.1 资源管理子系统

资源管理子系统为系统管理员提供各种资源创建和配置服务，同时需要和外部数据平台、报警系统交互。系统功能主要分为五个模块。

（1）基础数据管理

管理生产环节用到的机器、节点、网络信息，以及国家、省份、城市、运营商、IP库等基本信息，对数据进行修改和维护。

（2）资源池管理

主要用于业务资源池创建、资源分配、业务角色的配置和修改。将节点和机器划分成不同的业务资源池，多个机器可以同时分配给不同的业务方。

（3）调度管理

资源调度子系统需要依赖基础的调度配置实现调度功能，调度管理包括路由调度配置和定制调度配置。路由调度配置指配置节点间的调度方向，定制调度配置指根据用户 ID、请求来源 IP、节点 ID等进行定向配置。

（4）资源监控

指对资源池中的资源总量、利用率进行监控和预警，当资源使用量超过某一阈值时，与报警系统进行交互，发送邮件、短信或电话报警。

（5）统计报表

提供各类统计报表，如资源利用率统计、机器资源利用率等。报表的数据来源主要是对资源池中的资源进行定期采集，生成不同时间下的资源使用情况报表。

3.1.2 资源调度子系统

图2 系统架构设计Fig. 2 The design of system architecture

资源调度子系统主要是基于资源量、地域、运营商等因素实现实时的动态调度，为业务系统返回最优的生产机器。业务方包括点播生产控制系统、直播生产控制系统、轮播生产控制系统等。资源调度子系统功能分为3个模块。

（1）调度API

向业务系统提供资源调度接口，对业务方进行身份认证和接入鉴权，系统提供的调度服务包括转码调度、流媒体生产调度、切片生产调度、录制调度、截图调度等。

（2）调度策略

资源调度是建立在调度模型基础上，通过资源适配器，适配出合适的业务资源池，再根据不同的调度算法，如定制调度、路由调度、机器调度等查找合适的机器资源。

（3）三级存储结构

三级存储结构指数据库、分布式缓存、内存。资源调度子系统与资源管理子系统共用数据库，管理子系统对数据进行添加、修改后将数据保存到数据库中等，调度子系统从数据库中查询数据。为了提高调度接口的响应时间，减轻数据库的压力，调度子系统采用 Redis缓存资源量数据，并进行数据一致性处理；采用内存存储使用频率高且不存在数据一致性问题的数据，如调度策略的配置、节点基本信息、机器基本信息等。

3.2 系统交互流程

业务系统、生产层与资源调度系统间的交互流程如图3所示。具体流程如下：

（1）资源调度系统为业务系统预分配资源池，指定初始资源池大小。

（2）生产层机器定时向心跳平台上报资源量、机器负载等信息。

（3）资源调度子系统访问心跳平台的接口，获取机器资源量信息并将资源量保存到Redis缓存中。

（4）业务系统向资源调度子系统发起资源申请。

（5）资源调度子系统为业务匹配资源池，根据调度策略查找节点列表。

（6）资源调度子系统根据节点列表，从节点下查找满足资源需求的最优的机器，并对机器资源量进行减法操作，更新到分布式缓存中。

（7）业务系统获取到机器后，向生产层机器下发任务，机器收到任务后执行，同时机器上报本机的剩余资源至心跳平台。

4 系统实现的关键技术

4.1 资源模型设计

由于生产层机器会出现业务复用的情况，因此本文采用基于角色模式建立资源模型。在机房建设时，每个机房是一个独立的集群节点，一个机房的机器会同时向多个业务提供服务。因此需要将同一机房的机器资源按照业务需求划分为多个子节点，每个子节点形成一个业务角色，最后将资源划分为以角色为单位的资源池。资源模型如图4所示。

图3 系统架构设计Fig.3 S ystem interaction process

图4 资源模型Fig.4 Resouce model

角色资源池由不同节点的不同机器组成，一个角色可以包含多个机器，同一个机器也可以拥有多个角色。对于拥有多个角色的机器而言，角色之间共享硬件资源，但在业务上，角色之间是独立的。一个业务资源池由多个角色资源池组成，一个角色资源只能属于一个业务资源。资源类数据结构及关系如图5所示。

资源模型中，useful_count表示可用的资源量。以计算资源为例，CPU、IO等资源在资源调度时不能直接使用，需要转换成可以计算的指标。不同于虚拟机或容器的资源量化方式，本文使用一个整数值来表示该类机器的可用资源量。计算资源量化的方法是根据机器机型、CPU配置等信息得出最大可执行任务数或代表机器计算能力，例如一台转码机上可以并行执行 12个转码任务，12就表示该台转码机的计算资源总量。存储资源的量化是将磁盘容量作为机器资源总量，如存储容量为 500 G。带宽资源量化是将本机带宽资源作为资源总量，如本机当前带宽为1000 Mbps。

4.2 资源池创建与分配

图5 资源数据结构Fig.5 Res ource data structure

业务方在使用调度子系统的资源申请功能前，系统管理员必须要通过资源管理页面给业务方系统创建资源池。创建成功后该资源池中的资源为 0，必须经过资源分配，绑定节点和机器信息时该资源才可用。资源创建与分配流程如图6所示。

为每一类资源分配节点以及节点下的机器资源，页面功能如图7所示。

例如在分配实时转码资源时，先选择节点类型为实时转码节点，系统查出所有的实时转码节点后，勾选某一节点，然后单击对应的“选择机器”按钮，系统查出该节点下的机器列表，勾选要分配的机器，提交表单，资源分配完成。

4.3 资源调度流程

资源调度从整体上可以分为三步：

第一，节点调度，按照调度策略得到节点列表；

第二，角色调度，将节点列表与业务资源池相匹配，最后得到排序的角色列表。

第三，机器调度，遍历角色列表，从中查找符合需求的最优的机器。

资源调度整体工作流程如图8所示。

具体步骤如下：

（1）对用户申请的资源进行适配，按申请的资源类别biz匹配资源池，得到资源ID。

（2）根据IP库的数据，解析用户的请求IP，获取用户的归属地信息，包括国家、省份、城市、运营商信息。

（3）采用定制调度查找节点，查找成功则跳转到（6），失败跳转到（4）。

（4）采用路由调度查找节点，查找成功则跳转到（6），失败跳转到（5）。

（5）采用经纬度调度查找节点，查找成功则跳转到（6），失败则返回未申请到资源。

（6）节点ID与资源ID相关联，得到角色ID。

（7）依次遍历角色 ID，过滤掉不可用机器，将机器按照资源量排序，得到资源量最高的机器。

（8）对资源进行减法操作，更新机器资源量缓存，返回机器IP。

4.4 资源调度模型

4.4.1 节点路由调度模型

路由调度是将运营商、地域和资源量3个因素作为筛选节点的条件，根据实际IDC机房的建设情况，可将节点按地域进行分层划分，全网节点可以看成是一个有向图，如图9所示。该模型主要应用在节点机房较多的国家中。

图6 资源分配流程Fig.6 Resour ce allocation process

图7 资源分配页面Fig.7 Resour ce allocation process

图8 资源调度流程Fig.8 Re source schedule process

图9 路由调度模型Fig.9 Routing scheduling model

路由调度模型的生成分成两步：

首先生成世界地图，由图中的节点和直线箭头组成。按照国家、省份、地市建立树形结构，即每个国家用一棵树表示，根节点是国家信息，第二层是省份或州信息，第三层是地市信息，第四层是叶子节点，为该地区的机房信息。多个国家之间形成森林，以上形成一个四层的世界地图结构。

其次定义路由调度方向，即节点之间的调度方向，为图中的弧形箭头。系统维护调度路由表，该路由表采用地理上相邻的国家、省份或州作为基础数据。例如省份 A与省份B、C、D相邻，则系统生成一条记录，表示到达A省的请求可以往B、C、D调度。

（1）世界地图

为了方便快速查找，Java中使用HashMap嵌套的结构实现世界地图的存储，HashMap实际上是链表散列，即数组和链表的结合体。数组中每一个元素包含一个key-value键值对，此种模式在查找数据时时间复杂度为O(1)，可以快速实现查找。Java中创建名称为WORLD_MAP_NODE的数据结构，定义如下：

Map>>>>

初始化时，首先生成国家Map结构，key为国家ID，value为该国家的所有省份Map结构；省份Map结构中key为每个省份ID，value为该省份所有的城市 Map结构；依次类推，城市 Map中 key为城市ID，value为节点Map，节点Map中key为节点ID，value为机房节点信息。

（2）路由调度方向

如图10所示，为路由调度方向的存储结构，采用邻接表实现。例如一共有5个节点P0、P1、P2、P3、P4。P0的邻接点有P1，P1的邻接点有P0、P2、P3、P4。图中每个顶点的所有邻接点构成一个线性表。

图10 路由调度方向存储结构Fig.10 Storage structure of routing scheduling direction

实现时，每个顶点的所有邻接点也采用HashMap嵌套的结构，不同层级的key值包括国家ID、省份ID，依次递进。Java中创建名称ROUTE_SCHEDULE_RULE的数据结构用来表示调度方向，定义如下：

Map>>

使用该数据结构，表示可以根据国家ID找到其拥有的省份ID,再根据省份ID可以找到可调度到的国家-省份列表。其中ScheduleTargetCountry元数据的结构包含两个字段，国家ID和省份ID。

4.4.2 节点经纬度调度模型

由于世界上国家较多，而且不是所有国家都有机房节点信息，因此将存在节点信息的国家使用路由调度模型方式，没有节点的国家使用经纬度调度模型。

经纬度调度是根据用户所在地的经纬度信息，与全网节点的经纬度分别做差值，节点间距离最小的离用户最近，视为较优节点。与路由调度策略相比，该策略比较单一，但同时可以减少遍历节点的次数，提高查找效率。如图11所示，为经纬度调度模型。

图11 经纬度调度模型Fig.11 Schedule model of longitude and latitude

图中A、B、C、D、E、F共6个节点，如在A节点，与其他5个节点的距离分别为s1、s2、s3、s4、s5，对这 5个距离按照从小到大排序，得出距离最小的节点。经纬度模型在内存中的存储结构为：

Map>

该结构表示根据节点类型可以查找出所有节点，每个节点中配置了经纬度信息。

4.5 资源调度算法实现

4.5.1 IP查找算法

当业务方传递了IP这个参数时，调度系统需要根据IP库中的信息，对参数IP进行解析，得出IP所在的地域信息用来进行路由调度。由于IP库中存储的是IP段所在的国家、省份、城市和运营商信息，直接查找数据库很难定位IP的地域信息，且调度接口需要满足实时性，因此将IP库数据加载到内存中，在内存中判断IP的地域信息，并由定时任务每天定时更新IP库到内存。

IP库在内存中，采用List集合进行存储，即数组结构。每一条记录包含了IP的起始地址段、结束地址段，起始地址长整型，结束地址长整型和地域归属信息。首先从数据库查询IP时，按照起始地址长整型从小到大排序，再保存到内存中，即内存中的数据是有序的。将请求来源IP转换成长整型，利用二分查找算法，定位IP所在的IP段信息，IP段信息的数据结构包括IP归属国家ID、省份ID、运营商ID。

使用二分查找IP归属信息算法如下：

（1）定义变量low=最小数下标，hign=最大数下标，mid为中间数下标；

（2）初始化low=0，hign=集合大小；

（3）while(low <= high)

（a）中间数下标mid = (low + high)/2

（b）if ( Long IP >= 中间数List[mid])return 中间数

（c）else if (Long IP > 中间数)

low = mid + 1

（d）else

high = mid – 1

二分查找代码实现如图12所示。

4.5.2 节点路由调度算法

路由调度算法流程分为四步：

第一步按照图的广度优先遍历，遍历所有节点，按照相邻省份之间的步长对节点分组，相邻省份间的步长为1，当前节点到其邻省的邻省步长为2，依此类推。

第二步分别对步长相同的节点按照运营商进行分组，相同运营商的节点为一组，不同运营商的节点为另外一组。

第三步对分组后的节点与业务资源ID关联，得到角色列表。

第四步对每一层的角色使用合并排序算法排序，最终得到排序的角色列表。

图12 二分查找实现Fig.12 The implementation of Two point lookup

路由调度算法具体步骤如下：

（1）设请求所在地的省份为 P0，定义如下变量并初始化。

v：ScheduleTargetCountry数据对象，Q：待访问的省份队列，VisitQ：已访问过的省份队列，TempQ：临时节点队列，ReturnList：返回的节点集合，结构为List>。

其中队列均采用链表 LinkedList结构，队列中的元素为ScheduleTargetCountry数据对象，队列Q的初值为请求所在地的ScheduleTargetCountry信息。

（2）while（队列Q非空）

（3）队列Q的队头元素出队,v入队列VisitQ，根据国家 ID、省份 ID从 ROUTE_SCHEDULE_RULE结构中获取邻接省份节点，即可调度到的ScheduleTargetCountry列表，该列表与VisitQ比较，将v的未被访问过的邻接点列表入队列Q，同时记录v与P0的步长。

（4）访问省份v，从世界地图中查找v的节点信息，如果v存在机器节点且节点满足可用性等条件，则v的节点ID入队列TempQ。否则重复步骤（2）、（3）、（4），直到全部省份被遍历完。

（5）遍历结束后，对TempQ按步长分组，形成List>形式的数据结构ReturnList。外层List表示步长序号，内层List表示节点列表。

（6）按照运营商对ReturnList分组，与用户相同运营商的节点为一组，其它为另一组，返回ReturnList。

通过以上步骤，得到分组后的节点如图13所示：

图13 节点路由调度分组Fig.13 Node routing scheduling group

4.5.3 节点经纬度调度算法

经纬度调度算法如下：

（1）系统保存所有节点所在省份的经纬度信息。

（2）根据用户所在省份信息，得出用户的经纬度。

（3）计算用户所在地经纬度与各节点的经纬度的距离。

（4）根据 Java中自带的集合排序算法 Collections.sort，对所有距离排序，找出距离用户最近的节点。

计算用户所在地与各节点的距离，采用计算球面上任意两点距离的方法。假设球面上两点A、B，A点坐标为A(j1, w1),B点坐标为B(j2, w2)，其中j1、w1、j2、w2是经纬度信息。

图14 球面距离模型Fig.14 S pherical distance model

球面距离公式如下：

L=R arccos (cosw1 cos w2 cos(j2-j1) + sin w1 sin w2

计算球面距离代码实现如图15所示。

图15 球面距离实现Fig.15 The implementation of spherical distance

4.5.4 器调度算法

机器调度算法是根据角色信息查找该角色下的机器，返回资源量最高的机器，具体步骤如下：

（1）设用户申请的资源量为 count，角色集合为L，大小为s，定义临时变量i=0。

（2）遍历角色，对角色下的机器按照资源总量从大到小排序

（3）while ( i < s)

（4）if（机器 L[i]的剩余资源>最小剩余阈值 and机器剩余资源>count），对该机器开启 Redis事务。

（a）机器资源量减 count，更新缓存，如果更新成功，表示申请机器资源成功，接口返回机器IP。

（b）如果更新缓存失败，对i加1，跳转到步骤（3）。

（5）else资源不满足，对i加 1，跳转到步骤（3）。

4.6 分布式缓存与数据一致性

在响应业务方的申请资源请求或者调度子系统从心跳平台查询资源信息时，都要更新调度子系统的 Redis缓存。资源调度在查找机器时，需要根据角色ID先查找到机器信息，然后对缓存中该机器的资源量进行更新，因此内存中需要定义如下结构：

Map>

该结构表示某一角色下的机器 IP列表，其中BIZ_IP是业务类型和机器 IP的拼接，ServerCache存储在缓存中，包括的字段如表1所示。

表1 名称资源缓存数据结构Tab.1 Data struct of resouce cache

当申请资源进行资源量扣除时，对可用资源量字段进行事务操作。Java中 Redis的事务操作通过以下步骤实现：

（1）使用 Redis的 watch()方法对缓存中 key为BIZ_IP的字段进行监控。

（2）使用multi()方法开启事务。

（3）使用 decrBy()方法将资源量减去申请的数值。

（4）使用exec()方法提交事务，如果执行成功，表示申请资源成功。否则申请失败，返回。

5 系统测试

测试的主要内容是测试路由调度的准确性和灵活性，即运营商、省份区域和资源量对调度的影响。

测试环境服务器采用Linux系统，8 G内存，4核CPU，2.4 GHZ。Web容器采用Tomcat7.0，使用JDK1.7，Redis采用 3.2.9版本，Mysql采用 5.5版本，MongoDB采用3.0.3版本。

模拟多用户并发请求资源调度接口，调度系统记录请求日志，从日志中分析调度到的机器IP。测试前需预置数据，提前创建多个资源节点，如表 2所示。

表2 预置节点数据Tab.2 P repared node data

用户请求来源可以分为两类，一是节点中包含与用户运营商相同的节点，二是节点中不包含与用户运营商相同的节点，测试用例如表3所示。

表3 测试用例Tab.3 Te st case

（1）测试用例1

请求来源为杭州电信，调度的节点顺序为东莞电信、长沙联通、北京联通，调度到的IP顺序如图16所示，X轴为请求个数，Y轴为IP序号。

（2）测试用例2

请求来源为安徽歌华有线，由于已知服务器的节点中没有和请求所在地运营商相同的节点，且 3个节点距离请求所在地步长都相同，因此节点调度只按照资源量进行均匀调度，调度到的机器IP也是按照资源量均匀调度，如图17所示，X轴为请求个数，Y轴为IP序号。

图16 相同运营商请求Fig.16 The request from same ISP

测试结果表明：

（1）当节点中包含与请求所在地运营商相同的节点时,会最先匹配相同运营商节点，其次按照距离从近到远，即调度配置的临省关系，依次匹配不同运营商的节点，最后按照资源量从大到小匹配节点。

图17 不同运营商请求Fig.17 The Request from different ISP

（2）当节点中不包含与用户运营商相同的节点时，只会按照距离从近到远、资源量从大到小匹配节点。

（3）无论哪类请求，当某节点内有多台机器时，该节点内的机器资源是均衡使用的，保证了各个节点内资源利用率的均衡。设置节点剩余资源量的最低阈值解决资源不均衡问题，同时防止节点被全部打满。

资源管理问题一直是云计算厂商关心的主要问题，通过各种虚拟化、资源整合复用等技术，提高机器资源利用率，降低企业成本。在未来云计算的资源管理还会投入更多的研究，使得各种资源进行融合，发挥出巨大的价值。

6 结论

本论文设计并实现了视频云源站生产环节的资源调度系统，系统整合了视频云生产层的所有机器，使得之前零散的机器管理得到统一，方便后续的资源复用；系统提供了基于资源量、地域、运营商的动态调度算法，解决了原有系统中调度不准确、不灵活的问题，提高了机器利用率，促进了各生产环节交互的稳定性。

通过实际的应用，资源调度系统解决了原调度系统中调度不准确、不灵活的问题，但同时也存在着不足：

（1）随着任务逐渐增多，机器资源利用率也逐渐升高，在节点利用率达到较高值时，每台机器会产生一定的资源碎片不能被利用。

（2）节点间网络链路情况也是影响调度的一个因素，当按照距离和资源量进行节点调度时，会优先打满距离请求所在地最近的节点，但此种方法在网络链路好的情况下，节点间资源利用率出现了不均衡。由于资源池中资源一般较为充足，可以通过

[1] 陈国良, 明仲. 云计算工程[M]. 北京: 人民邮电出版社,2016: 160-183.

[2] 易观智库. 2016中国视频云专题研究报告[R/OL].(2016-06-20). [2018-01-05]. http://www.useit.com.cn/thread-12482-1-1.html.

[3] 潘虎. 云计算理论与实践[M]. 北京: 电子工业出版社,2016: 142-162.

[4] 刘志成, 林东升, 彭勇. 云计算技术与应用基础[M]. 北京:人民邮电出版社, 2017: 178-181.

[5] Arun C. Murthy, Vinod Kumar Vavilapalli. Hadoop YARN权威指南[M]. 罗韩梅,译.第1版. 北京: 机械工业出版社,2015: 27-45.

[6] 武凯, 勾学荣, 朱永刚. 云计算资源管理浅析[J]. 软件,2015, 36(2): 97-101.

[7] 李华清. 云计算技术及应用服务模式探讨[J]. 软件, 2014,35(2): 127-128.

[8] 段忠祥. 基于云计算的网络平台共享资源模型的建设[J].软件, 2013, 34(5): 119-121.

[9] 张栋梁, 谭永杰. 云计算中负载均衡优化模型及算法研究[J]. 软件, 2013, 34(8): 52-55.

[10] Ellis Horowitz, Sartaj Sahni, Sanguthevar Rajasekeran. 计算机算法[M]. 赵颖, 武永卫, 等译. 2版. 北京: 清华大学出版社, 2015: 96-115, 219-225.