Hadoop MapReduce中的负载均衡问题二 详细分析及现有方案 Analyzing Load Balancing on Hadoop

上一篇文章中,简要介绍了负载均衡问题,及其在Hadoop MapReduce平台中的表现。本文将进行详细分析,并介绍一些解决方案。

一、倾斜类型

  1. 数据倾斜

    输入数据分布不均,有些节点处理的数据远大于其他节点。可能会出现下面的情况,有个Join操作(reduce端join)输出数据量的大小

reduce side join output

  1. 计算倾斜

    运算的复杂度与输入的数据量关系不大,而取决于输入数据的特性。例如,PageRank这样的算法,一个节点的计算复杂度是于这个节点的出度有关,即使分配到一个计算节点上的数据相等,它们的实际运算时间由于度数的差别,还是会出现类似下图这样的情况。

compute unbalance

二、解决方案

两种倾斜方式中数据倾斜看起来会比较容易理解些,其实也是较易解决的。而计算倾斜发生得也很频繁,且情况更严重,解决起来也比较麻烦。解决方法整体上有两种分类:静态负载均衡,动态负载均衡。

2.1 静态负载均衡

严格意义上讲,静态负载均衡大多是进行算法优化,改变用户程序,使得整个作业的执行时间尽可能降低。这样的负载均衡一般都是需要对于当前的作业任务、输入数据特征和各个机器节点资源有先验知识。作业开始运行前,哪块数据在哪里进行计算都是可预测的,或者说是确定的,不管运行多少次都是这样一个状态。Hadoop提供的Partition接口就可以看做是一种静态负载均衡。下图展示了一个静态负载均衡的效果。

static load banlance

静态均衡很难用来解决计算倾斜的情形。大量的输入数据,想对每个分块的数据做计算量的估计是一个十分繁复且巨大的工作,而且没有通用性。

2.2 动态负载均衡

Hadoop平台中以Slot作为计算资源的分配单位,map任务和reduce任务都是运行在Slot上。Slot可以理解为单位计算资源,与cpu对应。由于存在数据倾斜或者计算倾斜每个任务的运行时间不同,可能会出现某个Slot已经完成任务空闲了,其他的Slot上还有大量的任务没有完成。显而易见,如果此时能够把其他Slot的任务放到这个Slot上来运行会大大提高系统的资源使用率,同时能够提升任务的处理效率及系统的吞吐量。相比于静态负载均衡,动态的均衡有多个优点。它不需要改变用户自己的应用代码,也不要针对不同的输入数据做算法定制优化,系统能够自动地完成均衡工作。

动态均衡还有个优点,它可以用来解决计算倾斜的问题。动态均衡关注的是Slot的空闲与否,可以在运行时根据当前运行状况做出负载分配决策。

相对而言动态均衡比静态均衡更难实现些,为了实现任务间的数据迁移工作需要增加任务间的数据传输模块及其他辅助功能。

2.3 关键技术

负载均衡过程中涉及到三个基本问题:Which,Where,How。

Which– 目前系统中哪个节点的任务被当做Straggler,谁的任务重,需要被迁移。

Where– 系统中哪个节点任务轻,可以多承担些工作,将重的任务迁移到这里。

How– Straggler节点的任务如何迁移到空闲节点中去,而且保证系统的一致性、正确性。

静态

静态Which:对输入数据进行采样,分析作业,估算每个部分的代价(归约到时间运行值)超出均值的那些块为Straggler。

静态Where:估值低于均值的块为要迁移任务到的空闲点。

静态How:类似背包问题,但分配目标是各个背包的估计代价方差最小。

动态

动态Which:目前系统中出现空Slot时,正在运行的task都可以作为Straggler。从其中挑选一个作为Straggler,如何挑选也是通过代价估计。

动态Where:即当前空闲的Slot,将任务迁移到这个Slot。

动态How: A. 直接法:选择当前系统运行中task剩余时间最长的为Straggler,考虑迁移时间,使Straggler和空闲节点处理迁移任务的时间一致。 B. 迭代法:考虑系统I/O问题,选择当前在同一个机器上的剩余时间最长的task为straggler,切分一半计算量到空闲节点;本地不够分再向其他机器请求切分。

dynamic demo

大概就像这样。

三、代价估计模型

上面提到的两种方案都需要有个代价估计,一半都是以计算时间作为标量。我们一般使用代价估计模型将不同的应用及对应的数据来将具体的作业情况做代价估计。

3.1 Map task估计

3.2 Reduce task估计

3.3 具体设计

Hadoop MapReduce中的负载均衡问题 Load Balancing on Hadoop MapReduce

做了一段时间的Hadoop中的负载均衡问题,此文谨当做对那段时间的总结。

一、负载均衡 – 一个广泛而普遍存在的问题

负载均衡问题是一个广泛而普遍存在的问题。在所有的分布式系统中几乎都会提及到“长尾问题(Long Tail Problem)”,其实也就是大家常说的“短板理论”,系统的整体表现取决于表现最差的一部分。常见的分布式系统如分布式缓存,分布式存储,分布式计算,分布式数据库等等,都存在这个问题。分布式缓存中可能会遇到短时间内集中访问同一个缓存的情况;分布式存储可能单机磁盘使用过度;分布式计算可能会有单点的计算负担过重;分布式数据库可能会有单机访问量过大。如此总总,只要是分布的,想完全端平一碗水几乎是不大可能的。

在此,总结我对负载均衡的定义:在多点协作的系统中由于不合理的任务分配导致某个或者少量的某些节点处理负担过重,最终拖延整个系统对外的响应效率。

负载均衡的解决思路主要有:

1. 被动解决,发现负载倾斜后,将负载迁移到空闲节点
2. 主动预防,防止倾斜的发生
    2.1 系统任务分配方式主动预防
        2.1.1 静态负载均衡
        2.1.2 动态负载均衡
    2.2 用户先验知识的介入

负载均衡问题的解决在大多数情况下是存在一个极限的,这取决于具体问题的可划分性(2.2中对此有讨论)。 分布式系统的负载均衡问题已经研究了多年了,有些问题早有了较成熟的解决方案,像分布式缓存系统中常见的一致性哈希算法等。在这里主要讨论的是分布式计算平台Hadoop里的负载均衡问题。

后文会对这几种方式一一讨论,下面先对本文的主要讨论对象Hadoop的背景做个简要介绍。

Read on →

Java(JVM)内存类型详解 Java(JVM) Memory Types

Java为何不支持多继承 Why Multiple Inheritance Is Not Supported in Java

原文:http://javapapers.com/core-java/why-multiple-inheritance-is-not-supported-in-java/

James Gosling 在95年二月发表的名为“Java: an Overview”的白皮书中给出了为什么Java不支持多继承的思量。

Java略去了好多C++中很少用到的,很难理解的,令人困惑的特性,根据我们的经验这些特性带来的麻烦比它们带来的好处更多。这些去掉的特征主要包括操作符重载(但是Java有方法重载),多继承,广泛的自动强制类型转换。

还有谁比James Gosling更有资格来对此作评论。这段话给了我们一个概要,并提起了不支持多继承的话题。

Java不支持多继承


首先让我们来盖棺定论。Java到底支不支持多继承本身就是一个争议点。有人说Java支持多继承。不,Java中没有对多继承的支持。如果你不相信我的话,把上面Java之父的那段话再读一下。

用接口支持多继承的说法是我们这些开发人员自己编造出来的。接口比实体类提供了更高的灵活性,我们可以选择用单个类去实现多个接口。这样我们通过继承两个模板来构建一个类。

这样做是在尝试向多继承靠近。其实我们做的是实现多个接口,却没有继承任何东西。实现一个类的接口的工作是向其中添加属性和方法,而不能直接从父类中获取具体实现。简单地说,Java中没有堆多继承的支持。

Read on →

接口和抽象类的区别 Diference Between Interface and Abstract Class

面试过程中经常会被问道Java中接口和抽象类有什么区别,总觉得自己总结不好,也不全面。正好这里有篇文章感觉写得很好。下面是内容。

  1. 接口最主要的不同是,接口默认是抽象的,本身不能有任何实现。抽象类可以有为子类提供的默认实例方法。

  2. 接口中的变量默认是final的。抽象类可以包含非final的变量。

  3. 接口的成员默认是public的。抽象类可以有任意类型的成员,private,protected都可以。

  4. 实现接口需要用implements关键字。继承抽象类用extends关键字。

  5. 接口继承一个或者多个接口,但是不能继承或实现任意抽象抑或者实体类。抽象类可以继承另外一个Java类同时还可以实现多个Java接口。

  6. 一个Java类可以实现多个接口,但是只能继承一个抽象类。

  7. 接口是完全抽象的,不能够实例化。抽象类也是不能被实例化的,但是如果其中有main()方法时,还是可以调用。

  8. 和抽象类相比,接口定义的引用在具体执行时由于需要做额外的间接寻址工作因此会慢些。(执行时需要通过搜索具体类的实现方法)

深入理解重载和重写及与之相关的多态性 Overloading and Overriding

本文分割线之前非原创,翻译自Overloading and overriding.

重载和重写除了在名称上有些相似之外,其实是完全不同的两个东西。

重载的目的是使得我们能够用用一个统一的接口名称来调用一系列方法。这些方法的目的也许是一样的,但是它们的实现方式会根据传入的参数不同而不同。

重写涉及到继承这个概念中的问题。子类继承了父类的方法,但是它可能需要有不同的操作行为,这时候就需要在子类中重写这个父类方法。

重载本身并不是多态,同时运行时绑定重载方法也不是多态的表现。它们以及一些其他的东西都是其面向对象多态性的使用(原文:All these and more are used to exercise the object oriented property polymorphism.总感觉翻译不要,故贴上来)。

重载和重写的关键点

  • private: 一个私有的java方法是不能被重写的,因为它对子类压根就不可见
  • final:重载一个final的方法是可以的,但是不能重写它,因此父类如果将方法声明为final的就可保证所有子类的调用此方法时调用的都是父类的方法。
  • final:如果两个方法有同样的参数列表,而其中一个的参数被声明为final的这种情况下这两个方法完全一样,因此不可重载。编译都通不过,因为这两个方法被视为完全一样。
  • static:可以重载一个静态的Java方法但是不能重写静态的Java方法,因为静态方法在方法区中只有一个。
  • static:重载是关于对象(实例)和继承而言的。一个声明为静态的方法属于整个类(对于这个的所有对象都是一样的)。因此重写它没有任何意义。
  • static:对于重载,两个静态方法的重载没有什么特别的,只不过是修饰符多了个static修饰符。参数列表依然必须不同。
Read on →

Java垃圾回收机制四 Monitoring and Analyzing Java Garbage Collection

在这篇Java垃圾回收系列文章中,让我们看下一些监控和分析垃圾回收的工具。然后用工具尝试监控和分析一个例子。初学者最好先看下此系列,从Java 垃圾回收简介开始吧。

Java垃圾回收监控和分析工具

下面是一些监控工具,它们有各自的优缺点。我们可以通过选择恰当的工具做一些有序的分析工作来提升应用性能。这篇文章将从Java VisualVM开始讲起。

  • Java VisualVM
  • Naarad
  • GCViewer
  • IBM Pattern Modeling and Analysis Tool for Java Garbage Collector
  • HPjmeter
  • IBM Monitoring and Diagnostic Tools for Java – Garbage Collection and Memory
  • Visualizer
  • Verbose GC Analyzer

Java VisualVM

Java VisualVM是在Java SE SDK安装时免费提供的。看下你的Java JDK安装目录下的/bin目录,\Java\jdk1.8.0\bin。此目录下有许多其他工具包括javac和java工具,jvisualvm就是其中一个。

Read on →

Java垃圾回收机制三 Types of Java Garbage Collectors

本文是Java垃圾回收系列的第三篇,非原创,翻译自Types of Java Garbage Collectors。如果没有相应基础的话,阅读本文前建议先阅读前两篇Java Garbage Collection Introduction(介绍了JVM的架构,堆内存模型和周边相关的Java术语)和How Java Garbage Collection Works?(概况介绍了GC是如何工作的)

本文将会介绍各种不同类型的Java垃圾回收器。垃圾回收是Java用来将程序员从分配和释放内存的琐事中解放出来的自动过程。

Java有四种类型的垃圾回收器,

  1. Serial Garbage Collector
  2. Parallel Garbage Collector
  3. CMS Garbage Collector
  4. G1 Garbage Collector

各种类型的Java垃圾回收器

Read on →

Java垃圾回收机制一 简介–Java Garbage Collection Introduction

本文非原创,翻译自Java Garbage Collection introduction 在Java中为对象分配和释放内存空间都是由垃圾回收线程自动执行完成的。和C语言不一样的是Java程序员不需要手动写垃圾回收相关的代码。这是使得Java如此流行,同时也是Java能帮助程序员写出更好的Java应用的优点之一。

计划写一个介绍Java垃圾回收基础的系列文章,共分四部分:

  1. Java垃圾回收简介
  2. Java垃圾回收器是如何工作的?
  3. 各种类型的Java垃圾回收器
  4. Java垃圾回收的监控和分析

本文是这个系列的第一篇文章,这篇文章将会介绍一些基本术语,如:JDK,JVM,JRE,HotSpot VM,以及理解JVM的架构和Java堆内存结构。在开始学习Java垃圾回收机制之前确实有必要了解一下这些基本东西。

关键的Java术语

  • Java API–一个帮助程序员创建Java应用的打包好的库集合
  • Java Development Kit(JDK)–一个使得程序员能够开发Java应用的工具集合
  • Java Virtual Machine(JVM)–JVM是一个抽象的计算机。Java程序是针对JVM规范写的。JVM是根据不同的操作系统平台实现的,它将Java指令翻译成对应平台上的指令,并执行。这样Java程序能够达到平台独立性。
  • Java Runtime Environment(JRE)–JRE由一个JVM的实现和Java API组成。

Java HotSpot虚拟机

每个JVM的实现在对垃圾回收的原理的实现方式上会有一些不同。在收购SUN之前Oracle有JRockit JVM,收购SUN之后有了HotSpot虚拟机。目前Oracle同时维护了这两个虚拟机,并宣称将来会将两个虚拟机合并。

Read on →

Do Not Say These Words When Debuging

there is some interesting saying, when problems came out

Bushit, that’s impossible!

It’s okay on my mechine!

It shouldn’t…

It must be someone else’s problem!

Why it’s ok previously?

HHHHHaaaa!

返回顶部