0%

发表于
本文字数： 2k 阅读时长 ≈ 4 分钟

说明

了解Yarn架构之前，先要了解两个概念。

  • 作业。也可称为应用程序，包含一个或多个任务。
  • 任务。在运行MapReduce时，一个任务可以使一个Mapper或一个Reducer。

Yarn关键组件

ResourceManager

ResourceManager由两个关键组件Scheduler和ApplicationsManager组成。

Scheduler

Scheduler在容量和队列限制范围内负责为运行的容器分配资源。Scheduler是一个纯调度器（pure scheduler），只负责调度，它不会监视或跟踪应用程序的状态，也不负责重启失败任务，这些全都交给ApplicationMaster完成。Scheduler根据各个应用程序的资源需求进行资源分配。

ApplicationsManager

ApplicationManager负责接收作业的提交，然后启动一个ApplicationMaster容器负责该应用。它也会在ApplicationMaster容器失败时，重新启动ApplicationMaster容器。

NodeManager

Hadoop 2集群中的每个DataNode都会运行一个NodeManager来执行Yarn的功能。每个节点上的NodeManager执行以下功能：

  • 定时向ResourceManager汇报本节点资源使用情况和各个Container的运行状况
  • 监督应用程序容器的生命周期
  • （监控资源）监控、管理和提供容器消耗的有关资源（CPU/内存）的信息（监控资源使用情况）
  • （监控容器）监控容器的资源使用情况，杀死失去控制的程序
  • (启动/停止容器）接受并处理来自ApplicationMaster的Container启动/停止等各种请求。

ApplicationMaster

提交到Yarn上的每一个应用都有一个专用的ApplicationMaster(注意，ApplicationMaster需要和ApplicationManager区分）。ApplicationMaster运行在应用程序启动时的第一个容器内。ApplicationMaster会与ResourceManager协商获取容器来执行应用中的mappers和reducers，之后会将ResourceManager分配的容器资源呈现给运行在每个DataNode上的NodeManager。ApplicationMaster请求的资源是具体的。包括：

  • 处理作业需要的文件块
  • 为应用程序创建的以容器为单位的资源
  • 容器大小（例如，1GB内存和一个虚拟核心）
  • 资源在何处分配，这个依据从NameNode获取的块存储位置信息（如机器1的节点10上分配4个容器，机器2的节点20上分配8个容器）
  • 资源请求的优先级

ApplicationMaster是一个特定的框架。例如，MapReduce程序是MRAppMaster，spark是SparkAppMaster。

Container

Container是对于资源的抽象, 它封装了某个节点上的多维度资源，如内存、CPU等。

Yarn工作流程

  1. 客户端向ResourceManager提交应用程序。
  2. ResourceManager的ApplicationManager组件指示NodeManager（运行在每一个工作节点的其中一个）为应用程序启动一个新的ApplicationMaster容器。
  3. ApplicationMaster首先向ResourceManager注册，这样用户可以直接通过NodeManager查看应用程序的运行状态。
  4. ApplicationMaster计算应用完成所需要的资源，然后向ResourceManager申请需要的资源（容器）。ApplicationMaster在应用程序的整个生命周期内与ResourceManager保持联系，确保其所需要资源的列表被ResourceManager严格遵守，并且发送一些必要的Kill请求杀死任务。
  5. 申请到资源后，ApplicationMaster指示NodeManager在对应的节点上创建容器。
  6. NodeManager创建容器，设置好运行环境，然后启动容器。
  7. 各个容器定时向ApplicationMaster发送任务的运行状态和进度，这样ApplicationMaster随时掌握各个任务的运行状态，从而可以在任务失败时重新启动任务。
  8. 应用程序完成后，ApplicationMaster会通知ResourceManager该作业已经完成并注销关闭自己。

这里要注意几点。第一，NodeManager会将节点状态和健康状况发送到ResourceManager，ResourceManager拥有全局资源视图才能分配资源。第二，ResourceManager的Scheduler组件决定容器在哪个节点上运行。

发表于 更新于
本文字数： 1.1k 阅读时长 ≈ 2 分钟

哈希

Java8中HashMap的hash()方法：

1
static final int hash(Object key) {
2
        int h;
3
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
4
    }

可以看到hash方法返回一个int类型的散列值。这个散列值与对象初始hashcode相比：

  • 高16位不变
  • 低16位与高16位做异或运算，得到新的低16位
    这样得到一个32位的int类型新散列值。为什么不直接使用key的hashcode的呢？

在HashMap的putVal方法中，可以看到插入值的index算法：

1
if ((p = tab[i = (n - 1) & hash]) == null)
2
            tab[i] = newNode(hash, key, value, null);

也就是说实际上的插入地址为（n-1)&hash，这里的n为哈希表长度。Hashmap习惯将表的大小设为2的幂，这样n-1相当于一个低位掩码，(n-1)&hash 的结果实际上就是hash的低位。因为n-1是低位掩码，所以(n-1)&hash的结果总是小于n，用&运算来代替%运算，效率提高了好几倍。这也是为什么我们在使用HashMap时，其长度应该取2的整次幂。

但是只取后几位的话，无疑会提高碰撞率。再回过头来看hash()方法，这样产生的散列值打乱了参与运算的低16位，此时的低位混合了原来的高位和低位，加大了低位的随机性，降低了哈希冲突的概率。

查找

JDK1.8中引入了红黑树来提升链表的查询效率。链表查找的平均时间为复杂度O(n)， 红黑树则为O(logn)。为链表的长度超过8以后，红黑树的查找速度比链表高。所以链表长度超过8后，HashMap会将链表转化为红黑树。当然小于6时，HashMap也会将红黑树转换为链表。

扩容

JDK1.8中扩容不需要再rehash，转而使用了一种很巧妙的方法。扩容数组的长度是两倍的关系。比如大小为4，那么扩容大小就会变成8。也就是0100变成1000，那么n-1由0011变为0111。根据上面讲过的（n-1)&hash算法，也就是说，扩容后key的新地址，实际上就是hash方法算出来的值多取了一个高位bit。如果高位是0，那么索引不变。如果高位是1，索引就变成原来索引加上原来的表大小。下图是hashmap大小由16扩充为32的示意图，来自美团点评技术博客。

这个设计非常巧妙，省去了重新计算哈希的时间。同时由于新增的0bit和1bit可以认为是随机的，这样扩容后就把之前的节点均匀的散列到哈希表中。扩容后，节点链表的前后关系不会变。

发表于 更新于
本文字数： 569 阅读时长 ≈ 1 分钟

centos7官方镜像是没有ssh的，需要自己安装配置。
首先安装：

1
yum install openssh* -y

启动：

1
usr/sbin/sshd

发现报错如下：

1
[root@78812d8146a9 /]# /usr/sbin/sshd
2
Could not load host key: /etc/ssh/ssh_host_rsa_key
3
Could not load host key: /etc/ssh/ssh_host_ecdsa_key
4
Could not load host key: /etc/ssh/ssh_host_ed25519_key
5
sshd: no hostkeys available -- exiting.

所以生成秘钥：

1
ssh-keygen -t rsa -f /etc/ssh/ssh_host_rsa_key -P ''
2
ssh-keygen -t rsa -f /etc/ssh/ssh_host_ecdsa_key -P ''
3
ssh-keygen -t rsa -f /etc/ssh/ssh_host_ed25519_key -P ''

配置localhost免密：

1
ssh-keygen -t rsa -P ''
2
cat ~/.ssh/id_rsa.pub >> ~/.ssh/authorized_keys

重新启动：

1
usr/sbin/sshd

ssh 127.0.0.1，连接成功。

发表于
本文字数： 271 阅读时长 ≈ 1 分钟

非中文系统下安装微信会出现乱码，中文变成小方框。
官方README给出的办法是在/opt/deepinwine/tools/run.sh 中将 WINE_CMD 那一行修改为

1
WINE_CMD="LC_ALL=zh_CN.UTF-8 deepin-wine"

但是在我的系统上(Mint 19)没有用，在issues里翻到一个方法(安装字体)，问题得到解决。

1
sudo apt-get install ttf-wqy-microhei
2
3
sudo apt-get install ttf-wqy-zenhei
4
5
sudo apt-get install xfonts-wqy

发表于 更新于
本文字数： 1.8k 阅读时长 ≈ 3 分钟

这篇论文来自NSDI 2019，作者是来自斯坦福的博士生Seo Jin Park和John Ousterhout教授，John Ousterhout教授也是raft算法的作者。论文提出了一种无序复制算法，将基于Primary-Backup的复制时延降低到了1个RTT。


如图，在没有复制的系统中，客户端向服务器发起一个写操作（x=1)，服务器接收到客户端请求后，将x=1写入到存储中并返回一个ok回复，这个过程耗时1个RTT。

但是在分布式系统中,数据存储通常有多个备份。如果继续使用之前的复制方法，就会导致节点数据的顺序不一致（由于网络等原因，客户端请求到达的顺序发生变化）。因此，为了多节点数据的一致性，大部分分布式系统采用了Primary-Backup模型。

如图，客户端发送一个写操作（x=1）到Primary节点，Primary节点先将x=1写到本地，然后将其同步到所有的Backup节点。当所有Backup节点成功保存数据后，Primary节点返回ok给客户端。这样一个过程耗时2个RTT。

CURP的大致结构如图：

CURP引入了witness节点，client不仅需要发送request到主服务器同时也需要发送到所有的witness节点，witness中的记录是无序的。主服务器在接受到request后，将数据写到本地后立即返回OK无需等待同步到Backups。当客户端收到primary和所有witness的OK回复后，写操作完成，client确认这个操作已经持久化，这个过程耗时1个RTT。

这个过程中如果witness拒绝了client的请求，此时witness需要向primary发送同步请求并等待primary把所有数据同步到backups后返回OK，才能确认数据完成持久化。这个过程大部分情况下耗时2个RTT（client发送同步请求时primary已经同步完成）,最坏情况下耗时3个RTT。

witness接收到request时需要对其进行交换性（commutativity)检查。如图中所示，z <- 7和y <- 5这两个记录就是可交换的，不论以什么顺序执行，不影响最后的结果。但是z < -7和z <- 2就不满足交换性，这两条记录必须严格按client发起的顺序执行。witness如果检查到request不满足交换性就会拒绝这个请求。

CURP分两个阶段恢复。第一步从Backup里恢复，第二步从Witness里回复。首先新Primay从一个Backup里恢复数据，然后选择一个可用的witness，要求它停止接受更多的operation。新primary在检查了witness中的所有记录都满足可交换性后，进行恢复。通过这两步，新Primary节点恢复看所有的数据。replay过程有3个潜在的问题：

第一，从witness中恢复的数据是乱序的。由于witness中的数据满足交换性，所以无论以何种顺序执行，都不影响最终的结果。


第二，operation的重复执行。primary节点将operation同步到Backups后，会向witness发送垃圾回收请求，witness中已经完成同步的op就会被垃圾回收。如果Primary节点在发送垃圾回收请求前宕机，此时witness和Backup中就会存在两条相同的op。如图所示，这时从witness中恢复的op就会覆盖掉Backup中的op，破坏了数据的一致性。作者使用了自己发表在SOSP 15的一篇论文《Implementing linearizability at large scale and low latency》中的方案解决了这个问题。


第三，Primaries May Reveal Not-yet-durable Data。如图所示，首先client A发送一个 x <- 3操作，几乎同时client B来读取x的值，此时x并没有被同步到Backup中。x <- 3此时可能没有被记录到witness中。primary返回x=3给client B后宕机了，这个时候新primary恢复数据后，x<-3就没了。在Client B看来，数据的一致性遭到了破坏。因此，在CURP中，如果client的op基于primary中未同步的op，此时client必须等待同步完成。

以上就是CURP的大致实现，更多的细节如垃圾回收、数据迁移, backup crash, witness crash等，请看论文。

发表于 更新于
本文字数： 362 阅读时长 ≈ 1 分钟

分布式协调与同步

分布式互斥

集中式算法

分布式算法

令牌环算法

分布式选举

Bully算法

Raft算法

ZAB算法

分布式共识

PoW

PoS

DPoS

分布式事务

基于XA协议的二段提交方法

三阶段提交方法

基于分布式消息的最终一致性方案

分布式锁

基于分布式实现分布式锁

基于缓存实现分布式锁

基于Zookeeper实现分布式锁

分布式资源管理与负载调度

分布式结构：集中式结构

Google Borg

Kubernetes

Mesos

分布式结构：非集中式结构

Akka

Redis

Cassandra

分布式调度：单体调度

分布式调度：两层调度

分布式调度：共享状态调度

分布式计算

MapReduce

Stream

Actor

流水线

分布式通信

远程调用RPC

发布订阅

消息队列

分布式存储

CAP定理

哈希与一致性哈希

数据复制技术

数据缓存技术

分布式高可靠

负载均衡

流量控制

##故障隔离
##故障恢复

发表于
本文字数： 357 阅读时长 ≈ 1 分钟

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