DBSCAN（Density-Based Spatial Clustering of Applications with Noise）聚类算法，它是一种基于高密度连通区域的、基于密度的聚类算法，能够将具有足够高密度的区域划分为簇，并在具有噪声的数据中发现任意形状的簇。我们总结一下DBSCAN聚类算法原理的基本要点：DBSCAN算法需要选择一种距离度量，对于待聚类的数据集中，任意两个点之间的距离，反映了点之间的密度，说明了点与点是否能够聚到同一类中。由于DBSCAN算法对高维数据定义密度很困难，所以对于二维空间中的点，可以使用欧几里德距离来进行度量。DBSCAN算法需要用户输入2个参数：一个参数是半径（Eps），表示以给定点P为中心的圆形邻域的范围；另一个参数是以点P为中心的邻域内最少点的数量（MinPts）。如果满足：以点P为中心、半径为Eps的邻域内的点的个数不少于MinPts，则称点P为核心点。DBSCAN聚类使用到一个k-距离的概念，k-距离是指：给定数据集P={p(i); i=0,1,…n}，对于任意点P(i)，计算点P(i)到集合D的子集S={p(1), p(2), …, p(i-1), p(i+1), …, p(n)}中所有点之间的距离，距离按照从小到大的顺序排序，假设排序后的距离集合为D={d(1), d(2), …, ...继续阅读 (97)

我们基于Hadoop 1.2.1源码分析MapReduce V1的处理流程。在MapReduce程序运行的过程中，JobTracker端会在内存中维护一些与Job/Task运行相关的信息，了解这些内容对分析MapReduce程序执行流程的源码会非常有帮助。在编写MapReduce程序时，我们是以Job为单位进行编程处理，一个应用程序可能由一组Job组成，而MapReduce框架给我们暴露的只是一些Map和Reduce的函数接口，在运行期它会构建对应MapTask和ReduceTask，所以我们知道一个Job是由一个或多个MapTask，以及0个或1个ReduceTask组成。而对于MapTask，它是根据输入的数据文件的的逻辑分片（InputSplit）而定的，通常有多少个分片就会有多少个MapTask；而对于ReduceTask，它会根据我们编写的MapReduce程序配置的个数来运行。有了这些信息，我们能够预想到，在Job运行过程中，无非也需要维护与这些Job/Task相关的一些状态信息，通过一定的调度策略来管理Job/Task的运行。这里，我们主要关注JobTracker端的一些非常有用的数据结构：JobTracker、JobInProgress、TaskInProgress，来熟悉各种数据结构的定义及作用。数据结构总体抽象MapReduce框架就为了运行Job，所以我们基于 ...继续阅读 (92)

我们基于Hadoop 1.2.1源码分析MapReduce V1的处理流程。MapReduce V1实现中，主要存在3个主要的分布式进程（角色）：JobClient、JobTracker和TaskTracker，我们主要是以这三个角色的实际处理活动为主线，并结合源码，分析实际处理流程。上一篇我们分析了Job提交过程中JobClient端的处理流程（详见文章MapReduce V1：Job提交流程之JobClient端分析），这里我们继续详细分析Job提交在JobTracker端的具体流程。通过阅读源码可以发现，这部分的处理逻辑还是有点复杂，经过我们梳理，更加细化清晰的流程，如下图所示：上图中主要分为两大部分：一部分是JobClient基于RPC调用提交Job到JobTracker后，在JobTracker端触发TaskScheduler所注册的一系列Listener进行Job信息初始化；另一部分是JobTracker端监听Job队列的线程，监听到Job状态发生变更触发一系列Listener更新状态。我们从这两个方面展开分析：JobTracker接收Job提交JobTracker接收到JobClient提交的Job，在JobTracker端具体执行流程，描述如下：JobClient基于JobSubmissionProtocol协议远程调用JobTracker的submitJob方法提 ...继续阅读 (80)

我们基于Hadoop 1.2.1源码分析MapReduce V1的处理流程。MapReduce V1实现中，主要存在3个主要的分布式进程（角色）：JobClient、JobTracker和TaskTracker，我们主要是以这三个角色的实际处理活动为主线，并结合源码，分析实际处理流程。下图是《Hadoop权威指南》一书给出的MapReduce V1处理Job的抽象流程图：如上图，我们展开阴影部分的处理逻辑，详细分析Job提交在JobClient端的具体流程。在编写好MapReduce程序以后，需要将Job提交给JobTracker，那么我们就需要了解在提交Job的过程中，在JobClient端都做了哪些工作，或者说执行了哪些处理。在JobClient端提交Job的处理流程，如下图所示：上图所描述的Job的提交流程，说明如下所示：在MR程序中创建一个Job实例，设置Job状态创建一个JobClient实例，准备将创建的Job实例提交到JobTracker在创建JobClient的过程中，首先必须保证建立到JobTracker的RPC连接基于JobSubmissionProtocol协议远程调用JobTracker获取一个新的Job ID根据MR程序中配置的Job，在HDFS上创建Job相关目录，并将配置的tmpfiles、tmpjars、tmparchives，以及Job对应jar文 ...继续阅读 (163)

Akka集群原理Akka集群支持去中心化的基于P2P的集群服务，没有单点故障（SPOF）问题，它主要是通过Gossip协议来实现。对于集群成员的状态，Akka提供了一种故障检测机制，能够自动发现出现故障而离开集群的成员节点，通过事件驱动的方式，将状态传播到整个集群的其它成员节点。状态转移与故障检测Akka内部为集群成员定义了一组有限状态（6种状态），并给出了一个状态转移矩阵，代码如下代码所示：private[cluster] val allowedTransitions: Map[MemberStatus, Set[MemberStatus]] = Map( Joining -> Set(Up, Down, Removed), Up -> Set(Leaving, Down, Removed), Leaving -> Set(Exiting, Down, Removed), Down -> Set(Removed), Exiting -> Set(Removed, Down), Removed -> Set.empty[MemberStatus]) }Akka集群中的每个成员节点，都有可能处于上面的一种状态，在发生某些事件以后，会发生状态转移。需要注意的是，除了Dow ...继续阅读 (106)

Akka是使用Scala语言开发一个编程库，基于事件驱动的架构实现异步处理，它能够简化编写分布式应用程序。Akka中最核心的概念是Actor模型，它为编写分布式/并行计算应用程序提供了高层次抽象，在实际编程实践中，开发人员可以从对复杂网络通信细节的处理、多线程应用场景下对锁的管理中解脱出来。Akka能够给应用程序带来的几个重要的特性是：容错性可伸缩性异步性事件驱动架构（EDA）远程透明性Actor是Akka中最核心的组件，以至于我们在编写基于Akka的应用程序时，大部分时间都会和Actor打交道，那么Actor到底是怎样的一种抽象呢？一个Actor对象封装了状态和行为，但是它不和外界其它的Actor共享状态，如果一个Actor想要和另一个Actor交互，能且只能通过发送消息来达到信息交换的目的。可见，一个Actor能够很好地保护其内部状态的安全。与本地Actor通信下面，我们从最简单的Actor编程来体验Akka的功能。首先，先定义几种类型的消息，后面会基于这些消息来进行通信，代码如下所示：package org.shirdrn.scala.akka object Start extends Serializable object Stop extends Serializable trait Message { val id: String } case class S ...继续阅读 (83)

Akka基于Actor模型，提供了一个用于构建可扩展的（Scalable）、弹性的（Resilient）、快速响应的（Responsive）应用程序的平台。本文基本上是基于Akka的官方文档（版本是2.3.12），通过自己的理解，来阐述Akka提供的一些组件或概念，另外总结了Akka的一些使用场景。Actor维基百科这样定义Actor模型：在计算科学领域，Actor模型是一个并行计算（Concurrent Computation）模型，它把actor作为并行计算的基本元素来对待：为响应一个接收到的消息，一个actor能够自己做出一些决策，如创建更多的actor，或发送更多的消息，或者确定如何去响应接收到的下一个消息。Actor是Akka中最核心的概念，它是一个封装了状态和行为的对象，Actor之间可以通过交换消息的方式进行通信，每个Actor都有自己的收件箱（Mailbox）。通过Actor能够简化锁及线程管理，可以非常容易地开发出正确地并发程序和并行系统，Actor具有如下特性：提供了一种高级抽象，能够简化在并发（Concurrency）/并行（Parallelism）应用场景下的编程开发提供了异步非阻塞的、高性能的事件驱动编程模型超级轻量级事件处理（每GB堆内存几百万Actor）实现一个Actor，可以继承特质akka.actor.Actor，实现一个receive方法，应该在 ...继续阅读 (102)

Apache Pig是一个用来分析大数据集的平台，它由两部分组成：一部分是用于表达数据分析程序的高级脚本语言，另一部分是用于评估分析程序的基本工具。目前来看，Pig主要用于离线数据的批量处理应用场景，但是随着Pig的发展处理数据的速度会不断地提升，这可能依赖于Pig底层的执行引擎。比如，Pig通过指定执行模式，可以使用Hadoop的MapReduce计算引擎来实现数据处理，也可以使用基于Tez的计算引擎来实现（Tez是为了绕开MapReduce多阶段Job写磁盘而设计的DAG计算引擎，性能应该比MapReduce要快），看到Pig未来的发展路线图，以后可能会基于Storm或Spark计算平台实现底层计算引擎，那样速度会有极大地提升。我们基于最新的0.15.0版本的Pig（Hadoop使用的是2.2.0版本），通过编写一些例子脚本来实践Pig的语言特性。Pig安装与执行Pig安装非常简单，只需要下载Pig包，然后解压缩即可：wget http://mirror.bit.edu.cn/apache/pig/pig-0.15.0/pig-0.15.0.tar.gz tar xvzf pig-0.15.0.tar.gz sudo ln -s /usr/local/pig-0.15.0 /usr/local/pig cd /usr/local/pig bin/pig -x mapreduce ...继续阅读 (92)

YARN是开源项目Hadoop的一个资源管理系统，最初设计是为了解决Hadoop中MapReduce计算框架中的资源管理问题，但是现在它已经是一个更加通用的资源管理系统，可以把MapReduce计算框架作为一个应用程序运行在YARN系统之上，通过YARN来管理资源。如果你的应用程序也需要借助YARN的资源管理功能，你也可以实现YARN提供的编程API，将你的应用程序运行于YARN之上，将资源的分配与回收统一交给YARN去管理，可以大大简化资源管理功能的开发。当前，也有很多应用程序已经可以构建于YARN之上，如Storm、Spark等计算框架。YARN整体架构YARN是基于Master/Slave模式的分布式架构，我们先看一下，YARN的架构设计，如图所示（来自官网文档）：上图，从逻辑上定义了YARN系统的核心组件和主要交互流程，各个组件说明如下：YARN ClientYARN Client提交Application到RM，它会首先创建一个Application上下文件对象，并设置AM必需的资源请求信息，然后提交到RM。YARN Client也可以与RM通信，获取到一个已经提交并运行的Application的状态信息等，具体详见后面ApplicationClientProtocol协议的分析说明。ResourceManager（RM）RM是YARN集群的Master，负责管理整个集群 ...继续阅读 (83)

在大数据应用场景下，使用过Hive做查询统计分析的应该知道，计算的延迟性非常大，可能一个非常复杂的统计分析需求，需要运行1个小时以上，但是比之于使用MySQL之类关系数据库做分析，执行速度快很多很多。使用HiveQL写类似SQL的查询分析语句，最终经过Hive查询解析器，翻译成Hadoop平台上的MapReduce程序进行运行，这也是MapReduce计算引擎的特点带来的延迟问题：Map中间结果写文件。如果一个HiveQL语句非常复杂，会被翻译成多个MapReduce Job，那么就会有很多的Map输出中间结果数据到文件中，基本没有数据的共享。如果使用Spark计算平台，基于Spark RDD数据集模型计算，可以减少计算过程中产生中间结果数据写文件的开销，Spark会把数据直接放到内存中供后续操作共享数据，减少了读写磁盘I/O操作带来的延时。另外，如果基于Spark on YARN部署模式，可以充分利用数据在Hadoop集群DataNode节点的本地性（Locality）特点，减少数据传输的通信开销。软件准备我把使用的相关软件的版本在这里列出来，以便测试验证，如下所示：CentOS-6.6 (Final)JDK-1.7.0_25Maven-3.2.1Hadoop-2.2.0Spark-1.3.1Hive-0.12.0MySQL-Server-5.5.8另外还要搭建好Hadoop集群 ...继续阅读 (90)

基于Spark通用计算平台，可以很好地扩展各种计算类型的应用，尤其是Spark提供了内建的计算库支持，像Spark Streaming、Spark SQL、MLlib、GraphX，这些内建库都提供了高级抽象，可以用非常简洁的代码实现复杂的计算逻辑、这也得益于Scala编程语言的简洁性。这里，我们基于1.3.0版本的Spark搭建了计算平台，实现基于Spark Streaming的实时计算。我们的应用场景是分析用户使用手机App的行为，描述如下所示：手机客户端会收集用户的行为事件（我们以点击事件为例），将数据发送到数据服务器，我们假设这里直接进入到Kafka消息队列后端的实时服务会从Kafka消费数据，将数据读出来并进行实时分析，这里选择Spark Streaming，因为Spark Streaming提供了与Kafka整合的内置支持经过Spark Streaming实时计算程序分析，将结果写入Redis，可以实时获取用户的行为数据，并可以导出进行离线综合统计分析Spark Streaming介绍Spark Streaming提供了一个叫做DStream（Discretized Stream）的高级抽象，DStream表示一个持续不断输入的数据流，可以基于Kafka、TCP Socket、Flume等输入数据流创建。在内部，一个DStream实际上是由一个RDD序列组成的。Spar ...继续阅读 (110)

Dubbo是Alibaba开源的分布式服务框架，我们可以非常容易地通过Dubbo来构建分布式服务，并根据自己实际业务应用场景来选择合适的集群容错模式，这个对于很多应用都是迫切希望的，只需要通过简单的配置就能够实现分布式服务调用，也就是说服务提供方（Provider）发布的服务可以天然就是集群服务，比如，在实时性要求很高的应用场景下，可能希望来自消费方（Consumer）的调用响应时间最短，只需要选择Dubbo的Forking Cluster模式配置，就可以对一个调用请求并行发送到多台对等的提供方（Provider）服务所在的节点上，只选择最快一个返回响应的，然后将调用结果返回给服务消费方（Consumer），显然这种方式是以冗余服务为基础的，需要消耗更多的资源，但是能够满足高实时应用的需求。有关Dubbo服务框架的简单使用，可以参考我的其他两篇文章（《基于Dubbo的Hessian协议实现远程调用》，《基于Dubbo的Hessian协议实现远程调用》，后面参考链接中已给出链接），这里主要围绕Dubbo分布式服务相关配置的使用来说明与实践。Dubbo服务集群容错假设我们使用的是单机模式的Dubbo服务，如果在服务提供方（Provider）发布服务以后，服务消费方（Consumer）发出一次调用请求，恰好这次由于网络问题调用失败，那么我们可以配置服务消费方重试策略，可能消费方第二次重试 ...继续阅读 (101)

Apache Crunch提供了一套Java API，能够简化编写、测试、运行MapReduce Pipeline程序。Crunch的基本思想是隐藏编写MapReduce程序的细节，基于函数式编程的思想，定义了一套函数式编程接口，因为Java并不支持函数式编程，只能通过回调的方式来实现，虽然写起来代码不够美观简洁，但是编写MapReduce程序的思路是非常清晰的，而且比编写原生的MapReduce程序要容易地多。如果直接使用MapReduce API编写一个复杂的Pipeline程序，可能需要考虑好每个Job的细节（Map和Reduce的实现内容），而使用Crunch变成库来编写，只需要清晰地控制好要实现的业务逻辑处理的操作流程，调用Crunch提供的接口（类似函数操作的算子、如union、join、filter、groupBy、sort等等）。下面，我们简单说明一下Crunch提供的一些功能或内容：Crunch集合及操作我们看一下Crunch提供的用来在处理分布式数据集的集合类型的抽象定义，如下面类图所示：上面，我给出了集合类对应的方法签名，其中具有相同名称签名的方法还具有重载的其他方法签名（参数列表不同），Crunch集合类型的高层抽象就包含这3个接口，相关集合子类的实现可以参考Crunch源码。连接操作（Join）上面类图中，PTable接口中有个一个join方法，这个默认是 ...继续阅读 (83)

JStorm是由Alibaba开源的实时计算系统，它使用Java重写了Apache Storm（使用Clojure+Java混编），而且在原来的基础上做了很多改进的地方。使用Java重写，对于使用Java的开发人员来说，可以通过阅读源码来了解JStorm内部的原理和实现，而且可以根据运行错误日志来排查错误。下面通过安装配置，以及简单使用的验证，来说明JStorm宏观上与Apache Storm的不同之处。安装配置JStorm Server首先，要保证JDK成功安装配置，然后在一个节点上下载、安装、配置JStorm。例如，我在hadoop1节点上，下载并解压缩：wget http://42.121.19.155/jstorm/jstorm-0.9.6.2.zip unzip jstorm-0.9.6.2.zip cd jstorm-0.9.6.2修改配置文件conf/storm.yaml，内容修改如下：########### These MUST be filled in for a storm configuration storm.zookeeper.servers: - "10.10.4.128" - "10.10.4.129" - "10.10.4.130" storm.zookeeper.root: "/jstorm" # %JSTOR ...继续阅读 (102)

Hue是一个开源的Apache Hadoop UI系统，最早是由Cloudera Desktop演化而来，由Cloudera贡献给开源社区，它是基于Python Web框架Django实现的。通过使用Hue我们可以在浏览器端的Web控制台上与Hadoop集群进行交互来分析处理数据，例如操作HDFS上的数据，运行MapReduce Job等等。很早以前就听说过Hue的便利与强大，一直没能亲自尝试使用，下面先通过官网给出的特性，通过翻译原文简单了解一下Hue所支持的功能特性集合：默认基于轻量级sqlite数据库管理会话数据，用户认证和授权，可以自定义为MySQL、Postgresql，以及Oracle基于文件浏览器（File Browser）访问HDFS基于Hive编辑器来开发和运行Hive查询支持基于Solr进行搜索的应用，并提供可视化的数据视图，以及仪表板（Dashboard）支持基于Impala的应用进行交互式查询支持Spark编辑器和仪表板（Dashboard）支持Pig编辑器，并能够提交脚本任务支持Oozie编辑器，可以通过仪表板提交和监控Workflow、Coordinator和Bundle支持HBase浏览器，能够可视化数据、查询数据、修改HBase表支持Metastore浏览器，可以访问Hive的元数据，以及HCatalog支持Job浏览器，能够访问MapReduce ...继续阅读 (91)

Hadoop集群上存储数据，同时基于MapReduce计算框架可以实现计算任务，那么无论是从数据保护的角度，还是从提交计算任务占用资源的角度来看，都需要存在一种权限管理与分配机制，能够很好地限制哪些人可以在HDFS上存储数据，哪些人可以利用集群的资源来处理特定的计算任务。当然，如果能够非常完美地解决这些问题是最好的。当前Hadoop本身提供的权限管理功能还不能满足普遍的需要，或者我们从Hadoop已有的一些简单或复杂的认证机制选择适合自己所在组织机构需要的，或者我们在外围开发一些权限管理系统与Hadoop整合作为补充。对比Kerberos认证（Authentication）配置方式与SLA授权（Service Level Authorization）方式，Kerberos配置相当复杂，而且还要依赖于外部的密钥分发中心KDC（Key Distribution Center）服务器，如果KDC出现问题，那么就会导致依赖于KDC认证的整个Hadoop集群无法使用，鉴于此，对于一些相对小的开发团队来说还是更倾向于粗粒度的Hadoop SLA授权机制。Hadoop SLA基于Hadoop的各种服务（基于协议来划分）与Linux系统的用户、用户组来实现。Hadoop通过制定接口协议的方式来实现节点之间服务调用的逻辑，这样每一个协议所指定的一组服务就是一个认证单元，再基于底层Linux系统的用户 ...继续阅读 (73)

Storm是一个分布式是实时计算系统，它设计了一种对流和计算的抽象，概念比较简单，实际编程开发起来相对容易。下面，简单介绍编程实践过程中需要理解的Storm中的几个概念：TopologyStorm中Topology的概念类似于Hadoop中的MapReduce Job，是一个用来编排、容纳一组计算逻辑组件（Spout、Bolt）的对象（Hadoop MapReduce中一个Job包含一组Map Task、Reduce Task），这一组计算组件可以按照DAG图的方式编排起来（通过选择Stream Groupings来控制数据流分发流向），从而组合成一个计算逻辑更加负责的对象，那就是Topology。一个Topology运行以后就不能停止，它会无限地运行下去，除非手动干预（显式执行bin/storm kill ）或意外故障（如停机、整个Storm集群挂掉）让它终止。SpoutStorm中Spout是一个Topology的消息生产的源头，Spout应该是一个持续不断生产消息的组件，例如，它可以是一个Socket Server在监听外部Client连接并发送消息，可以是一个消息队列（MQ）的消费者、可以是用来接收Flume Agent的Sink所发送消息的服务，等等。Spout生产的消息在Storm中被抽象为Tuple，在整个Topology的多个计算组件之间都是根据需要抽象构建的Tup ...继续阅读 (77)

我们可以从java.io.InputStream类中看到，抽象出一个read方法，用来读取已经打开的InputStream实例中的字节，每次调用read方法，会读取一个字节数据，该方法抽象定义，如下所示：public abstract int read() throws IOException;Hadoop的DFSClient.DFSInputStream类实现了该抽象逻辑，如果我们清楚了如何从HDFS中读取一个文件的一个block的一个字节的原理，更加抽象的顶层只需要迭代即可获取到该文件的全部数据。从HDFS读文件过程分析：获取文件对应的Block列表（http://shiyanjun.cn/archives/925.html）中，我们已经获取到一个文件对应的Block列表信息，打开一个文件，接下来就要读取实际的物理块数据，我们从下面的几个方面来详细说明读取数据的过程。Client从Datanode读取文件的一个字节下面，我们通过分析DFSClient.DFSInputStream中实现的代码，读取HDFS上文件的内容。首先从下面的方法开始：@Override public synchronized int read() throws IOException { int ret = read( oneByteBuf, 0, 1 ); return ...继续阅读 (80)