Chronicle-----流计算中避免FullGC

背景

最近在Jstorm中遇到一个问题,在一个流量很大的Jstorm集群中,其中一个Spout会定期从mysql中同步一些元信息并广播到下游的相关Bolt。当元数据信息不大时,这种广播的方式并不会造成太大的影响。

然而,当元数据信息愈发庞大时,广播元数据带来了各种各样的负面影响。

  1. 首先,当Spout读元数据广播时,大量元数据信息被序列化后,发送给下游Bolt,当下游Bolt收到时,元信息又被反序列化为一个大的对象,并更新。这时候对GC产生了很大的压力。
  2. 其次,每个Bolt作为Worker的一个线程去分别持有一份元数据信息,会占用很大的内存。

解决FGC引起的流量异常

从我们流计算的业务监控中,看到流量突然下跌。几分钟后重新恢复流量。立马看了一下Jstorm日志,发现没有发生系统调度,所以说在Jstorm层面应该没有引起流量的下跌。

那么既然不是Jstorm的原因的话,那只能从Topology层面找找原因。这时候在@简离的指导下,用Jstat看了对应Worker的GC情况。 发现FGC 4->5 的时候,old区增长了近10%,同时触发了FGC。这时候就要结合业务日志来看,这个时间点系统到底在做什么导致old区的迅速增长,由于有近10%的内存增长,应该是一个很大的对象分配。 从业务log中发现,发生FGC的时候,Spout从我们的元数据库读了一份元信息,并广播给下游Bolt。这份元信息是一个有近200W+ entry的HashMap。 为了验证这一猜想,我去看了其他集群运行较久的Job。 可以看到这个Job运行了9天,发生了5000+次FGC,平均下来5分钟发生近两次FGC。正好是我们Spout同步元数据的频率。

小插曲

在部署某个集群时,发现Job总是运行个五分钟就挂了,当时也是“百思不得骑姐”。放大worker的内存,以及适当降低并发数就正常了,当时只是简单的觉得是因为OOM,机器资源不足导致的。后面想到并发数特别高时,每个线程持有元数据相当占用内存空间,比较容易引起OOM。

怎么解决?

又是@简离的一番教育,介绍了我什么是堆外内存,什么是FreeGC编程-。- 主角登场chronicle-map,这个是开源的堆外内存实现的ConcurrentHashMap。原本应用在高频交易的场景下,在高频交易中FGC也是灾难性的。

ChronicleMap is a ConcurrentMap implementation which stores the entries off-heap, serializing/deserializing key and value objects to/from off-heap memory transparently. Chronicle Map supports

Key and value objects caching/reusing for making zero allocations (garbage) on queries. Flyweight values for eliminating serialization/deserialization cost and allowing direct read/write access to off-heap memory.

堆存储 VS 非堆存储

堆存储的优势
  • 常见的,写普通的Java代码。所有有经验的Java开发人员都可以做到。
  • 访问内存的安全性问题。
  • 自动的GC服务——无需自身管理的malloc()/free()操作。
  • 完整的 Java Lock API和JMM相结合。
  • 添加无序列化/复制数据到一个结构中去。
非堆存储的优势
  • 控制"停止一切(Stop the World)"的GC事件到你比较满意的层次。
  • 可以超越在规模上的堆存储结构(当使用堆存储的时候会变得很高)
  • 可以作为一个本地的IPC传输(无需java.net.Socket的IP回送)
  • NIO DirectByteBuffer到/dev/shm (tmpfs)的map 或者直接sun.misc.Unsafe.malloc()

什么才是非堆存储

上图介绍了两个使用ShardHashMap(SHM)作为进程间通信(IPC)的Java VM过程(PID1和PID2)。图表底部的水平轴代表的是完全SHM操作系统的所在域。当OpenHFT对象被操作时,它就会在操作系统中物理内存的用户地址空间或者内核地址空间的某处。往深一层思考,我们知道他们以“关于进程”的局部开始着手。从Linux操作系统来看,JVM是一个a.out (通过调用 gcc呈现的)。当a.out在运行的时候会有一个PID。一个 PID的 a.out (在运行时)包含以下三个方面:

  • 文档(低地址……执行代码的地方)
  • 数据(通过sbrk(2)从低地址升级到高地址来掌管)
  • 栈(从高地址到低地址来掌管)

这是PID在操作系统中的表现形式。也就是说,PID是一个执行的JVM,JVM有它自己操作对象潜在的局部性。

从JVM来看,操作对象作为On-PID-on-heap(一般的Java)或者On-PID-off-heap(通过Unsafe或者NIO到Linux mmap(2)的桥梁)。无论在On-PID-on-heap还是在On-PID-off-heap,所有的操作对象仍然存活在用户的地址空间。在C/C++中,API(操作系统调用的)提供了允许C++操作对象有 Off-PID-off-heap的地方,这些操作对象都寄存在内核地址空间内。

小插曲

在使用chronicle-map的过程中,因为Jstorm只支持java 1.7的缘故,我们只能使用chronicle-map 2.x的版本,在使用过程中,我的测试起了10个进程,每个进程500个线程去创建chronicle-map,发现了其builder源码的bug,源码中,当指定的共享文件存在时并且文件内容长度不为0时,它会通过创建一个ObjectStream 8个bytes地读取文件,然而当并发足够大时,会出现第一个线程开始向文件中写入meta信息,而其他的线程读文件时,恰巧8个bytes中读到了EOF引发EOFERROR,在公司内部版本中我已经修复了这个bug。

使用效果

从图中可以看出,FGC时,内存并不像之前那样出现了old区跳跃式增长;同时从业务监控中,也没有再出现断崖式地流量下跌。然而,我们Job每秒大概处理接近200W+的sql信息,db写入接近每秒600Mb,由于大量的YGC,整个Job并没有能够完全避免FGC。

路漫漫其修远兮,吾将上下而求索。

记阿里人工智能研讨会

题外话

之前没有了解过知识图谱,同样也是第一次参加研讨会。 总体而言,研讨会能够快速,高效地了解到学术界目前的研究方向。

Background

知识图谱,简而言之,就是以三元组代表(HeadEntity, Relationship, TailEntity)头实体,尾实体以及它们之间的关系。

知识图谱(Mapping Knowledge Domain)也被称为科学知识图谱,在图书情报界称为知识域可视化或知识领域映射地图,是显示知识发展进程与结构关系的一系列各种不同的图形,用可视化技术描述知识资源及其载体,挖掘、分析、构建、绘制和显示知识及它们之间的相互联系。

具体来说,知识图谱是通过将应用数学、图形学、信息可视化技术、信息科学等学科的理论与方法与计量学引文分析、共现分析等方法结合,并利用可视化的图谱形象地展示学科的核心结构、发展历史、前沿领域以及整体知识架构达到多学科融合目的的现代理论。它把复杂的知识领域通过数据挖掘、信息处理、知识计量和图形绘制而显示出来,揭示知识领域的动态发展规律,为学科研究提供切实的、有价值的参考。

Google知识图谱Wiki

其他代表知识库:

  1. WordNet
  2. Freebase

目前研究方向

分布式表示学习(distributed representation, embeddings)

主要研究思路: 将知识图谱嵌入到低维向量空间
  • 实体和关系都表示为低维向量
  • 有效表示和度量实体、关系间的语义关联

知识表示代表模型:

对每个事实(head, relation, tail),将relation看做从head到tail的翻译操作。

训练的优化目标为: h + r = t

此外还有Neural Tensor Network(NTN)以及Energy Model。 NTN Energy Model

表示学习在处理一对多、多对一、多对多的关系时,不能较好的处理。当出现多个结果时,每个结果的权重相当。

在TransE的基础上考虑关系对实体的影响

有以下两个典型的算法:

  • TransH
  • TransR

TransH TransR

Path Ranking

关系路径的表示学习: Recursive Neural Network(RNN)

考虑了关系路径的TransE算法为PTransE:

relation之间的组合语义,通常包括 ADD, MULTIPLY, RNN

通常关系之间的每个组合,需要单独训练一个目标函数。 在大规模复杂的知识图谱中,目标函数也会呈现指数级增长。

Probabilistic Graphical Models

这个算法,由于落地难的问题,大家都没有讲=.=

王志春-讲解了规则学习的几个方法:

  • 归纳逻辑程序设计 ILP
  • 类似数据挖掘中的关联规则
  • 关系路径
  • 分布式表示

韩先培-介绍了相关无监督语义关系抽取:

  • bootstrapping
  • distant supervision
  • Open IE(Stanford OpenIE)

写在最后

刘知远讲解的TransE非常的Solid,而且开源了算法实现https://github.com/thunlp/KG2E

王泉研究员,我只能献上我的膝盖了,语速很快,思路无敌清晰。简简单单的一个slide就能把当前知识图谱的研究方向洋洋洒洒的讲出来。

最后附上 刘知远的 ppt 大规模知识图谱的表示学习

大规模分布式系统

背景:

Google发表了MapReduce计算范型及其框架的论文。MapReduce和并行数据库系统(MPP)各有优劣并且两者有一定的互补和学习。与传统MPP架构相比,MapReduce更适合非结构化数据的ETL处理类操作,并且可扩展性和容错性占优,但是单机处理效率较低。
DAG计算模型是MapReduce计算机制的一种扩展。MapReduce对于子任务之间复杂的交互和依赖关系缺乏表达能力,DAG计算模型可以表达复杂的并发任务之间的依赖关系。
Spark本质上是DAG批处理系统,其最能发挥特长的领域是迭代式机器学习。

MapReduce计算模型与架构

计算模型

MapReduce计算任务的输入是Key/Value数据对,输出也以Key/Value数据对方式表示。开发者要根据业务逻辑实现Map和Reduce两个接口函数内的具体操作内容,即可完成大规模数据的并行批处理任务。

实例一:单词统计

map(String key, String value):  
    //key: 文档名
    //value: 文档内容
    for each word in value:
        Emit Intermedia(w, "1");

reduce(String key, Iterator values):  
    //key: 单词
    //value: 出现次数列表
    int result = 0;
    for each v in values:
        result += ParseInt(v);//累加values值
    Emit(AsString(result));

实例二: 链表反转

map(String source_url, Iterator outlinks):  
    //key: 网页url
    //value: 出链列表
    for each outlink o in outlinks:
        Emit Intermedia(o, source_url)

reduce(String target_url, Iterator source_urls):  
    //key: target网页url
    //values: source网页url
    list result = [];
    for each v in source_urls:
        Result.append(v);
    Emit(AsString(result));

实例三: 页面点击统计

map(String tuple_id, String tuple):  
    Emit Intermedia(url, "1");

reduce(String url, Iterator list_tuples):  
    int result = 0;
    for each v in list_tuples:
        result += ParseInt(v);
    Emit(AsString(result));

系统架构

MapReduce计算框架架构

处理流程:

  1. MapReduce框架将应用的输入数据切分成M个模块,典型的数据块大小为64MB,然后可以启动位于集群中不同机器上若干程序。
  2. 全局唯一的主控Master以及若干个Worker,Master负责为Worker分配具体的Map任务或Reduce任务并做一些全局管理。
  3. Map任务的Worker读取对应的数据块内容,从数据块中解析一个个Key/Value记录数据并将其传给用户自定义的Map函数,Map函数输出的中间结果Key/Value数据在内存中缓存
  4. 缓存的Map函数产生的中间结果周期性写入磁盘,每个Map函数中间结果在写入磁盘前被分割函数切割成R份,R是Reduce个数。一般用key对R进行哈希取模。Map函数完成对应数据块处理后将R个临时文件位置通知Master,Master再转交给Reduce任务的Worker
  5. Reduce任务Worker接到通知时,通过RPC远程调用将Map产生的M份数据文件pull到本地。(只有所有Map函数完成,Reduce才能执行)。Reduce任务根据中间数据的Key对记录进行排序,相同key的记录聚合在一起
  6. Reduce任务Worker遍历有序数据,将同一个Key及其对应的多个Value传递给用户定义的Reduce函数,reduce函数执行业务逻辑后将结果追加到Reduce对应的结果文件末尾
  7. 所有Map、Reduce任务完成,Master唤醒用户应用程序

为了优化执行效率,MapReduce计算框架在Map阶段还可以执行Combiner操作。

hadoop的MapReduce运行机制基本与google的类似。
hadoop的MapReduce运行机制 不同的是,hadoop采用https协议来进行数据传输,并采用归并排序对中间结果进行排序。
Google的MapReduce框架支持细粒度的容错机制。Master周期性Ping各个Worker,如果Worker没有响应,则认为其已经发生故障。
如果Master故障则单点失效,重新提交任务。

MapReduce不足

  1. 无高层抽象数据操作语言
  2. 数据无Schema及索引
  3. 单节点效率低下
  4. 任务流描述方法单一

优势:

  1. 数据吞吐量高
  2. 支持海量数据处理的大规模并行处理
  3. 细粒度容错
    但是不适合对时效性高的应用场景,比如交互查询或流处理,也不适合迭代计算类的机器学习及数据挖掘类应用。

由于:

  1. 启动时间长
  2. 多处读写磁盘及网络传输

DAG计算模型

有向无环图的简称。在大数据处理领域,DAG计算模型是将计算任务在内部分解成若干子任务,这些子任务之间由逻辑关系或运行先后顺序等因素被构建成有向无环图结构。

DAG计算系统三层结构

  • 最上层是应用表达层,通过一定手段将计算任务分解成若干子任务形成的DAG结构
  • 最下层是物理机集群,由大量物理机器搭建的分布式计算环境
  • 中间层是DAG执行引擎层,将上层以特殊方式表达的DAG计算任务通过转换和映射,将其部署到下层的物理机集群中运行

Dryad

微软DAG计算系统,dryad在实现时以共享内存、TCP连接以及临时文件的方式进行数据传输

Dryad整体架构

Dryad整体架构

job manager负责将逻辑形式存在的DAG描述映射到物理机。NS负责维护集群中当前可以的机器资源。Daemon守护进程作为JM在计算节点上的代理,具体负责子任务的执行和监控。

FlumeJava和Tez

  • FlumeJava构建了java库,本质上是在MapReduce基础上的DAG计算系统,图中每个节点可以看作单个MapReduce子任务。
  • Tez使用Map任务或者Reduce任务作为DAG的图节点,图节点的有向边是数据传输通道。Tez消除Map阶段中间文件输出到磁盘过程以及引入Reduce-Reduce结构改进措施提升执行效率

分布式系统算法

中间件在分布式系统中的地位和角色

为了使种类各异的计算机和网络都呈现为单个的系统,分布式系统常常通过一个“软件层”组织起来,该层在逻辑上位于由用户和应用程序组成的高层与由操作系统组成的低层之间,这样的分布式系统又称为中间件。中间件层延伸到了多台机器上,且为每个应用程序提供了相同的接口。它的重要的目的是提供一定程度的透明性,也就是一定程度上向应用程序隐藏数据处理的分布性。中间件集分布式操作系统与网络操作系统的优点于一身,既能够具有网络操作系统的可扩展性和开放性,又能够具有分布式操作系统的透明性和与之相关的易用性。

分布式系统进程通信,rpc基本原理步骤

  1. 客户过程以正常方式调用客户存根
  2. 客户存根生成一个消息,然后调用本地操作系统
  3. 客户端操作系统将消息发送给远程操作系统,并阻塞客户过程
  4. 远程操作系统将消息交给服务器存根
  5. 服务器存根将参数提取出来,然后调用服务器
  6. 服务器执行要求的操作,操作完成后将结果返回给服务器存根
  7. 服务器存根将结果打成消息包,然后调用本地操作系统
  8. 服务器操作系统将消息发送回客户端操作系统
  9. 客户端操作系统将消息交给客户存根
  10. 客户存根将结果从消息中提取出来,返回给调用进程

移动agent特点

自主性;反应性;主动/面向目标;推理/学习/自适应能力;可移动性;社会性。

命名服务(优缺点)

移动实体定位

  1. 广播和多播
  2. 转发指针
  3. 给实体指定一个起始位置
  4. 创建一颗搜索树

并发,petri网建模

哲学家进餐

哲学家进餐

图解:

h-hunger k-thinking f –fork/chopstick e-eating

  1. 圆圈:hi,ki,ei,fi为库所
    h:表示为哲学家饥饿状态库所 : k表示为哲学家思考状态的库所 e:表示为哲学家吃饭状态的库所 f:表示筷子处于备用状态的库所
  2. 黑色实心点为token。初始状态时:f0-f4中的是筷子,k0-k4中的是哲学家
  3. 方框为变迁
    初始状态:筷子备用状态,处于f0-f4库所中。哲学家是思考状态,处于k0-k4中。

以哲学家0为例 - T1 变迁1(感到饥饿):哲学家在思考中感到饿了,从库所k0经过T1到达库所h0。哲学家从思考状态进入饥饿状态。 - T2变迁2(获得筷子):哲学家和筷子分别从h0,f4,f0库所经过T2迁移到库所e0。哲学家从饥饿状态进入吃饭状态。 - T3变迁3(释放筷子):吃完饭后,哲学家经过T3迁移到k0库所中,从吃饭状态转入思考状态。两只筷子经过T3,分别迁移到库所f0,f4,从使用状态进入备用状态。

生产者消费者

移动mogent通信失效(本地和异地)的解决方案

  • 分析
    • 无论本地通信还是异地通信,其通信模型是一致的
    • 通信失效本质上都是因为在路由信件和实际信件传输过程中,目标agent发生了物理位置的变化,而这种变化是随机的,不可预计的。
  • 结论
    • 通信失效现象并不是mogent系统特有的现象.它是一个因agent的移动而带来的可能会出现在任意一个移动agent系统中的普遍现象
  • 其它系统的处理
    • Aglets:未见
    • Mole:
      • 将失效信件扔弃;
      • 扔弃的同时回送错误信息
      • 将失效信件就地保存,待被通信agent在回送时交付
  • 根本原因:
    • 移动:随机改变位置信息
    • 通信:要求位置信息“暂时”不变
    • 通信和移动所共享的“位置”信息未进行同步控制是造成通信失效的根本原因
    • 从OS进程互斥考虑,接收者的“位置”在通信失效问题中具有决定性的意义,当通信和移动相矛盾时,该“位置”就成为了一个必须互斥使用的“资源”
  • “位置”的互斥 =》 “状态”的互斥
  • 在一个能够避免通信失效的移动agent系统中,必须且只要做到以下三条 :
    • 准确纪录agent的状态信息
    • 只能向一个处于“静止态”的agent发送信件
    • 信件发送过程中必须限制接收者从“静止态”向“移动态”的状态转换

同步:逻辑时间算法,向量时间戳(将每个时间的向量时间戳标出)

Lamport算法:不能反应因果关系。

向量时钟 :要求能计算出每个进程中的事件,标出向量的时间戳,不同事件之间的向量时间的大小关系,依赖关系与并发关系。

逻辑时钟

  • 为了同步逻辑时钟,Lamport定义了一个称作 “先发生” (happens-before) 的关系。表达式ab读作 “a在b之前发生”,意思是所有进程一致认为事件a先发生,然后事件b才发生。这种先发生关系有两种情况。
    • 如果a和b是同一个进程中的两个事件,且a在之前发生,则ab为真。
    • 如果a是一个进程发送消息的事件,而b为另一个进程接收消息的事件,则ab也为真。消息不可能在发送之前被修改,也不能在发送的同时被接收,这是因为消息需要一定时间才能到达接收端。
    • Lamport逻辑时间钟具有传递性和并发性;
  • 对这个算法稍作补充就可以满足全局时间的需要。即在每两个事件之间,时钟必须至少滴答一次。如果一个进程以相当快的速度发送或者接受两个消息,那么它的时钟必须在这之间至少滴答一次。
  • 在某些情况下还需要一个附加条件,即两个事件不会精确地同时发生。为了达到这个目标,我们可以将事件发生所在的进程号附加在时间的低位后,并用小数点分开。这样,如果进程1和进程2中的事件都发生在时刻40,那么前者记为40.1后者记为40.2。
  • 使用这种方法,我们现在有了一个为分布式系统中的所有事件分配时间的方法,它遵循下面的规则:
    • 若同一进程中a在b之前发生,则C(a)
    • 若a和b分别代表发送一个消息和接收该消息的事件,则C(a)
    • 对于所有不同的事件a和b,C(a) ≠ C(b)。
  • 这个算法为我们提供了一种对系统中所有事件进行完全排序的方法。许多其他的分布式算法都需要这种排序以避免混淆,所以文献中广泛引用此算法。
  • 使用Lamport时间戳后,只通过比较事件a和b各自的时间值C(a)和C(b),无法说明它们之间的关系。换句话所,C(a)

向量事件戳

为什么采用向量时间戳可以表示事件因果关系? - 因果关系可以通过向量时间戳来捕获。分配给事件a的向量时间戳VT(a)具有下列性质:如果对某一事件b,有VT(a)

  • 现在假设进程Pj张贴了一个该文章的回复。回复是通过该进程广播一个消息r实现的,消息r携带值等于Vj的时间戳vt(r)。注意vt(r)[i]> vt(a)[i]。假设通信是可靠的,包含文章的消息a和包含回复的消息r最终都到达了另一个进程Pk。因为我们没有对消息的顺序关系做出假设,所以消息r可能在消息a之前到达进程Pk。进程Pk接收到消息r时检查时间戳,并决定推迟提交消息r,直到因果关系上位于r之前的消息都接收到了才提交。消息r只有下列条件满足时才得到交付: vt(r)[j]=vk[j]+1;
    对于所有满足i¹j的i和j,vt(r)[i]< Vk[i] 第一个条件说明r是进程Pk正在等待的下一条来自进程Pj的消息。 第二个条件说明当进程Pj发送消息r时,进程Pk只看到被进程Pj看到的消息。这意味着进程Pk已经看到了消息。

一致性模型,要能写出以客户为中心的四个模型(条件描述)以数据为中心的三种类别(了解))

  1. 每一个以客户为中心的一致性模型是单调读的一致性模型。如果数据存储满足以下条件,那么称该数据存储提供单调读一致性(monotonic-read consistency):

    • 如果一个进程读取数据x的值,那么该进程对执行任何后续读操作将总是得到第一次读取的那个值或更新的值。

    也就是说,单调读一致性保证,如果一个进程已经在t时刻看到x的值,那么以后他不再会看到较老的版本的x的值。

  2. 在很多情况下,写操作以正确的顺序传播到数据存储的所有拷贝是非常重要的。这种性质被描述为单调写一致性。单调写一致性(monotonic-write consistency)的数据存储应该满足以下条件:

    • 一个进程对数据项x执行的写操作必须在该进程对x执行任何后续写操作之前完成。
  3. 下面介绍一种与单调写一致性有密切关系的以客户为中心的一致性模型。如果数据存储满足以下条件,那么称该数据存储提供写后读一致性(read-your-writes consistency)。

    • 一个进程对数据项x执行一次写操作的结果总是会被该进程对x执行的后续读操作看见。

    也就是说,一个写操作总是在同一进程执行的后续读操作之前完成,而不管这个后续的读操作发生在什么位置。

  4. 最后一种以客户为中心的一致性模型是这样的模型,即更新是作为前一个读操作的结果传播的。如果数据存储满足以下条件,那么称该数据存储提供读后写一致性(writes-follow-reads consistency)。

    • 同一个进程对数据项x执行的读操作之后的写操作,保证发生在与x读取值相同或比之更新的值上。

    也就是说,进程对数据项上x所执行的任何后续的写操作都会在x的拷贝上执行,而该拷贝是用该进程最近读取的值更新的。

代码迁移(基础、分类)

分布式系统中的代码迁移是以进程迁移(process migration)的形式进行的,在这种形式下整个进程被从一台机器搬到另一台机器上去。其基本的思想是:如果把进程由负载较重的机器上转移到负载较轻的机器上去,就可以提升系统的整体性能。(迁移的是计算程序本身,而非数据)

分类

  • 弱可迁移性:在这种模型中,可以只传输代码段以及某些初始化数据。弱可移动性的典型特征是,传输过来的程序总是以初始状态重新开始执行的。
  • 强可移动性(strong mobility):它还可以迁移执行段。强可移动性的典型特征是,可以先停止运行中的进程,然后将它搬到另一台机器上去,再从刚才中断的位置继续执行。

分类(主动方): - 发送者启动(sender-initiated)迁移:在这种模型中,代码当前驻留在哪台机器上或者正在哪台机器上执行,就由该机器来启动迁移。一般来说,在向计算服务器上载程序时进行的就是发送者启动的迁移。 - 接收者启动(receiver-initiated)迁移:代码迁移的主动权掌握在目标机器手中。Java小程序是这种迁移的一个例子。

事务提交:2pc\3pc

  1. 两阶段提交协议(2PC):考虑一个分布式事务中有很多进程作为参与者,每个进程都运行在不同的机器上。假定没有故障发生,协议就由以下两个阶段组成,每个阶段又由两步组成。

    • 协调者向所有的参与者发送一个Vote_Request消息。
    • 当参与者接收到VoteRequest消息时,就向协调者返回一个VoteCommit消息通知协调者它已经准备好本地提交事务中属于它的部分,否则就返回一个Vote_Abort消息。
    • 协调者收集来自参与者的所有选票。如果所有的参与者都表决要提交事务,那么协调者就进行提交。在这种情况下它向所有的参与者发送一个GlobalCommit消息。但是,如果有一个参与者表决要取消事务,那么协调者就决定取消事务并多播一个GlobalAbort消息。
    • 每个提交表决的参与者都等待协调者的最后反应。如果参与者接收到一个GlobalCommit消息,那么它就在本地提交事务,否则接收到一个GlobalAbort消息时,就在本地取消事务。
      • The finite state machine for the coordinator in 2PC.(协调者)
      • The finite state machine for a participant.(参与者)

    两阶段提交的一个问题在于当协调者崩溃时,参与者不能做出最后的决定。因此参与者可能在协调者恢复之前保持阻塞。三阶段提交协议(3PC),避免了在出现故障停机时的阻塞过程。

  2. 三阶段提交(3PC)

    3PC的本质在于协调者和每个参与者都满足以下两个条件:

    • 没有一个可以直接转换到Commit或者Abort状态的单独状态。
    • 没有一个这样的状态:它不能做出最后决定,而且可以从它直接转换到Commit状态。

    三阶段提交协议(3PC)的基本原理为:在2PC的参与者投票和协调者决策之间增加了“预提交”阶段。协调者在接收到所有参与者的提交票后发送一个全局预提交命令,当参与者接收到全局预提交命令之后,它就得知其他的参与者都投了提交票,从而确定自己在稍后肯定会执行提交操作,除非它失败了。每个参与者都对全局预提交发出确认消息,协调者一旦接收到所有参与者的确认消息就再发出“全局性提交”。3PC协议在站点失败,甚至是所有的站点都失败的情况下也不会带来阻塞。

    它们各自的状态机如图所示。(a 协调者,b 参与者)

  3. 二者比较:

与2PC相比,3PC的主要不同点在于以下情况:崩溃的参与者可能恢复到了Commit状态而所有参与者还处于Ready状态。在这种情况下,其余的可能操作进程不能做出最后的决定,不得不在崩溃的进程恢复之前阻塞。在3PC中,只要有可操作的进程处于Ready状态,就没有崩溃的进程可以恢复到Init、Abort或Precommit之外的状态。因此存活进程总是可以做出的最后决定。

复制和一致性(四个经典模型(不带同步变量的))

  1. 严格一致性

    条件定义:对于数据项x的任何读操作将返回最近一次对x进行的写操作的结果所对应的值。

    严格一致性中存在的问题是它依赖于绝对的全局时间(注意由于技术的限制,我们需要处理同一时间间隔内所发生的多个操作)

    (a)严格的一致性存储; (b) 非严格的一致性存储

    总之,当数据存储是严格一致的时候,对于所有的进程来说,所有写 操作是瞬间可见的,系统维持着一个绝对的全局时间顺序。(如果一 个数据项被改变了,那么无论数据项改变之后多久执行读操作,无论 哪些进程执行读操作,无论这些进程的位置如何,所有在该数据项上 执行的后续读操作都将得到新数值。同样,如果执行了读操作,那么 无论多快地执行下一个写操作,该读操作都将得到当前的值。 )

  2. 顺序一致性

    条件定义:

    任何执行结果都是相同的,就好像所有进程对数据存储的读、写操作 时按照某种序列顺序执行的,并且每个进程的操作按照程序所制定的 顺序出现在这个序列中。

    (a) 顺序一致的数据存储; (b)非顺序一致的数据存储

  3. 线性一致性

    条件定义:当数据存储上的每个操作都具有时间戳并满足以下条件时,称这个数据存储是可线性化的。任何执行结果都是相同的,就好像所有进程对数据存储的读、写操作是按某种顺序执行的,并且每个进程的操作按照顺序所执行的顺序出现在这个顺序中。另外,如果tsop1(x)

  4. 因果一致性

    因果关系理解:考虑一个存储器的实例。假设进程P1对变量x执行了写操作。然后进程P2先读取x,然后对y执行写操作。这里,对x的读操作和对y的写操作具有潜在的因果关系,因为y的计算可能依赖于P2所读取的x值。没有因果关系的操作被称为并发的。

    条件定义:所有进程必须以相同的顺序看到具有潜在因果关系的写操作。不同机器上的进程可以以不同的顺序被看到并发的写操作。 实现因果一致性要求跟踪哪些进程看到了哪些写操作。这意味着必须构建和维护一张记录哪些操作依赖于哪些操作的依赖关系图。一种实现方法是使用上一章所讨论的向量时间戳。

分布式系统算法(选举算法(欺负算法)、互斥算法(集中式带协调者的、分布式不带协调者的、recut、令牌环(不一定考)))

选举算法

欺负算法

1.1 当任何一个进程发现协调者不再响应请求时,它就发起一个选举。进程P按如下过程主持一次选举:
- 1.1.1 P向所有编号比它大的进程发送一个election消息; - 1.1.2 如果无人响应,P获胜成为协调者; - 1.1.3 如果有编号比它大的进程响应,则响应者接管选举工作。P的工作完成。

  • (a) 进程4主持一个选举;
  • (b) 进程5和6进行响应,告诉进程4停止选举;
  • (c) 进程5和6此时各自主持一个选举;
  • (d) 进程6通知进程5停止选举;
  • (e) 进程6获胜,并通知每个进程。

互斥算法

集中式算法

只有一个协调者,无论何时一个进程要进入临界区,它都要向协调者发送一个请求消息,说明它想要进入哪个临界区并请求允许。如果当前没有其他进程在该临界区内,协调者就发送允许进入的应答消息。

- (a) 进程1请求协调者允许它进入一个临界区。请求得到了批准; - (b) 进程2也请求进入同一个临界区。协调者不应答;进程2进入等待队列 - (c) 进程1在退出临界区时通知协调者,协调者然后做出应答。协调者再通知等待队列中的排在最前面的进程2进入临界区 - 优点:没有进程会处于永远等待状态(不会出现饿死的情况);易于实现,每使用一次临界区只需3条消息(请求、允许和释放);不仅能用于管理临界区,也可以用于更一般的资源分配。 - 缺点:协调者是一个单个故障点,所以如果它崩溃了,整个系统就可能瘫痪。在一般情况下,如果进程在发出请求之后被阻塞,那么请求者就不能区分“拒绝进入”和协调者已经崩溃这两种情况,因为上述两种情况都没有消息返回。此外,在规模较大的系统中,单个协调者会成为性能的瓶颈。

分布式算法

该算法的工作过程如下:当一个进程想进入一个临界区时,它构造一个消息,其中包含它要进入的临界区的名字、它的进程号和当前时间。然后它将消息发送给所有其他的进程,理论上讲也包括它自己。
当一个进程接收到来自另一个进程的请求消息时,它根据自己与消息中的临界区相关的状态来决定它要采取的动作。可以分为三种情况: - 2.1 若接收者不再临界区也不想进入临界区,它就向发送者发送一个OK消息。 - 2.2 若接收者已经在临界区,它不进行应答,而是将该请求放入队列中。 - 2.3 如果接收者想进入临界区但尚未进入时,它将对收到的消息的时间戳和包含在它发送给其余进程的消息中的时间戳进行比较。时间戳最早的那个进程获胜。如果收到的消息的时间戳比较早,那么接收者向发送者发回一个OK消息。如果它自己的消息的时间戳比较早,那么接收者将接收到的请求放入队列中,并且不发送任何消息。

在发送了请求进入临界区的请求消息后,进程进行等待,直到其他所有进程都发回允许进入消息为止。一旦得到所有进程的允许,它就可以进入临界区了。当它退出临界区时,它向其他队列中的所有进程发送OK消息,并将它们从队列中删除。

- (a) 两个进程同时希望进入同一个临界区; - (b) 进程0具有最早的时间戳,所以它获胜; - (c) 当进程0退出临界区时,它发送一个OK消息,所以进程2现在可以进入临界区 - 优点:不会发生死锁或者饿死现象;最大的优点是不存在单个故障点。 - 缺点:单个故障点被n个故障点所取代;要求更多网络通信的算法;要么必须使用组通信原语,要么每个进程都必须自己维护组成员的清单,清单中包括进入组的进程、离开组的进程以及崩溃的进程。

令牌环

当环初始化时,进程0得到一个令牌token。该令牌绕着环运行,用点对点发送消息的方式把它从进程k传递到进程k+1(以环大小为模)。进程从它邻近的进程得到令牌后,检查自己是否要进入临界区。如果自己要进入临界区,那么它就进入临界区,做它要做的工作,然后离开临界区。在该进程退出临界区后,它沿着环继续传递令牌。不允许使用同一个令牌进入另一个临界区。如果一个进程得到了邻近进程传来的令牌,但是它并不想进入临界区,那么它只是将令牌沿环往下传递。 - 优点:不会发生饿死现象,那么最差的情况是等待其他所有进程都进入这个临界区然后再从中退出后它再进去。 - 缺点:如果令牌丢失了,那么它必须重新生成令牌,检测令牌丢失是很困难的;如果有进程崩溃,该算法也会出现麻烦,但是恢复起来比其他算法容易。

TF-IDF

词频因此(tf)

Tf计算因子代表了词频,即一个单词在文档中出现的次数。

变体1: $W_{tf} = 1 + log(Tf)$

变体2: $W_{tf} = a + (1-a)\times{Tf\over Max(Tf)}$

(a=0.4)
同一个文档内单词之间的相对重要性。

逆文档频率因子(IDF)

表示文档集合范围的一种全局因子。给定一个文档集合,那么每个单词的IDF值就唯一确定,跟具体的文档无关。所以IDF考虑的不是文档本身的特性,而是特征单词之间的相对重要性。
$IDF_k = log{N \over n_k}$
N: 文档数目
$n_k$: 文档频率

TF-IDF框架

$Weight_{word} = TF \times IDF$