Hadoop提供了一个可靠、可扩展的存储和分析平台，是一个由多个项目组成的生态系统，这些项目都属于分布式计算和大规模数据处理范畴。

寻址速度的提升远远跟不上传输速度的提升，寻址是将磁头移动到特定磁盘位置进行读写操作的过程，它是导致硬盘操作延迟的主要原因，而传输速度取决于硬盘的带宽。如果数据访问中包含大量硬盘寻址，那么读取大量数据集就需要花费更长时间。如果只更新少量数据，传统的基于B树的数据库更有优势，如果需要更新大量数据，B树的速度将明显落后于MapReduce，因为需要使用排序/合并来重建数据库。

Hadoop尽量在计算节点上存储数据，以实现数据的本地快速访问，数据本地化（data locality）特性是Hadoop数据处理的核心。

MapReduce是对大量分布式处理问题的总结和抽象，核心思想是分而治之。主要由两部分组成：编程模型和运行时环境，编程模型为用户提供了非常易用的编程接口，用户只需要像编写串行程序一样实现几个简单的函数即可实现分布式程序，其它复杂的工作，如节点间通信、节点失效、数据切分等都由MapReduce运行时环境完成。

一个分布式计算过程可以拆解成两个阶段：

第一阶段：Map阶段，由多个可并行的Map Task构成，主要功能是将待处理数据集按照数据量大小切分成等大的数据分片，每个分片交由一个任务处理。

第二阶段：Reduce阶段，由多个可并行的Reduce Task构成，主要功能是对前一阶段中各任务产生的结果进行规约，得到最终结果。

Hadoop自带一个分布式文件系统——HDFS（Hadoop Distributed Filesystem），有时也简称DFS。

数据块

构建于单个磁盘的文件系统通过磁盘块来管理该文件系统的块，该文件系统块的大小可以是磁盘块的整数倍。文件系统块一般是几千字节，而磁盘块一般是512字节。HDFS的块（block）作为独立的存储单元默认是128MB，HDFS上的文件也被划分为多个分块（chunk）。与单一磁盘文件系统不同，HDFS小于一个块大小的文件不会占据整个块空间。

namenode和datanode

HDFS集群以一个管理节点（namenode）和多个工作节点（datanode）模式运行，namenode管理文件系统的命名空间，它维护着文件系统树及整颗树内所有的文件和目录。这些信息以两个文件形式永久保存在本地磁盘上：命名空间镜像文件和编辑日志文件。namenode也记录着每个文件中各个块所在数据节点信息，但它并不永久保存块的位置信息，因为这些信息会在系统启动时根据数据节点信息重建。datanode是HDFS的工作节点，用于存储和检索数据块，并定期向namenode发送所存储块的列表。

客户端（client）提供一个类似POSIX（可移植操作系统界面）的文件系统接口，用户访问HDFS时无需感知namenode和datanode。

参考资料

《Java编程思想》

RDD

RDD，弹性分布式数据集（Resilient Distributed Dataset）是spark的核心概念，它是集群中跨多个机器分区存储的一个只读对象集合，弹性指spark可以通过重新安排计算来自动重建丢失的分区。在spark程序中，一般加载一个或多个RDD作为输入，通过一系列转换得到一组目标RDD，然后将这些RDD计算出结果或者写入持久存储器。

加载RDD或执行转换并不会立即触发任何数据处理的操作，只是创建一个计算计划。只有对RDD执行某个动作（如foreach）时，才会触发真正的计算。通过rdd的map()方法可以对RDD的每个元素应用某个函数，filter()方法的输入是一个过滤谓词，即返回布尔值的函数。

RDD 具有以下几个特点：

1. 分布在集群中的只读对象集合，由多个 partition 构成，这些 partition 可能存储在不同机器上

2. RDD 可以存储在磁盘或内存中（多种存储级别），partition 可以全部存储在内存或磁盘上，也可以部分在内存中，部分在磁盘上

3. Spark 提供了大量 API 通过并行的方式构造和生成 RDD

4. 失效后自动重构：Spark 通过记录 RDD 的血统，了解每个 RDD 的产生方式（包括父 RDD 以及计算方式），进而能够通过重算的方式构造因机器故障或磁盘损坏导致丢失的 RDD 数据

   HDFS 的任何一个文件也可以认为是分布式数据集，但从一定程度上，HDFS 并不具有弹性，因为所有数据都存储在磁盘上。RDD 则可以将 Partition 部分存储在磁盘部分存储在内存。

转换和动作

转换（transformation）是从现有RDD生成新的RDD，动作（Action）触发对RDD的计算并对计算结果执行某种操作，要么返回给用户，要么保存到外部存储器中。动作的效果是立竿见影的，但转换不是，转换是惰性的，在对RDD执行一个动作之前不会为该RDD的任何转换操作采取实际行动。判断一个操作是转换还是动作，可以观察返回类型，如果返回的类型是RDD，那么它是一个转换，否则就是一个动作。

作业

Spark作业由任意多阶段（stages）有向无环图构成，有的阶段又被spark运行环境分解为多个任务（task），任务并行运行在分布于集群中的RDD分区上。作业始终运行在应用（application）上下文（SparkContext实例表示）中，它提供了RDD分组以及共享变量。一个应用可以串行或并行地运行多个作业，并为这些作业提供访问由同一应用的先前作业所缓存的RDD的机制。

Task：具体执行的任务，Task 分为 ShuffleMapTask 和 ResultTask 两种，分别类似于 Hadoop 中的 Map、Reduce

2.

Linux内核把所有管理的资源，如网卡、磁盘驱动器、打印机、输入输出设备、普通文件或目录都当作一个文件。对文件的读写操作会调用内核提供的命令，返回一个文件描述符。文件描述符是一个非负整数索引值，指向内核为每个进程所维护的该进程打开的文件记录表，表中的项是一个结构体（包含文件路径、数据区等属性）。套接字是通信端点的抽象，套接字描述符是一种用来访问套接字的文件描述符，很多处理文件描述符的函数（如read和write）都可以用来处理套接字描述符。

一次IO过程可以分为两个阶段：

1. 等待数据准备（数据先读到内核的缓冲区）
2. 将数据从内核拷贝到进程中

Unix提供了五种IO模型，分别是阻塞IO、非阻塞IO、IO复用、信号驱动IO和异步IO。IO编程中，当需要处理多个客户端接入时，可以利用多线程或IO多路复用技术。IO多路复用是把多个IO的阻塞复用到同一个select的阻塞上，从而使得系统在单线程的情况下可以同时处理多个客户端请求。模型使用一个进程监视多个描述符，一旦某个描述符就绪（一般是读就绪或写就绪），能够通知程序进行相应的读写操作。

Linux支持IO多路复用的系统调用有select、pselect、poll和epoll，IO多路复用需要使用两个系统调用（select/pselect/poll/epoll和recvfrom），而阻塞IO只需要一个系统调用（recvfrom）。但多路复用的优势是可以同时处理多个connection，系统开销小，不需要创建和维护新的额外进程或线程。适用于需要同时处理多个（可以是不同状态或协议）套接字。如果处理连接数不是很高的情况下，IO多路复用不一定比阻塞IO+多线程性能好。这两种IO模型都是进程主动等待并向内核检查状态，所以都是同步阻塞模型。

select

调用select后进程阻塞，直到有fd就绪（可读、可写或except）或超时后返回。select几乎支持所有的平台，具有良好的跨平台性，但最大的缺陷是单个进程对监控的fd有数量限制。这个限制由FD_SETSIZE定义，32位默认值是1024，64位默认值2048.

poll

poll和select没有本质区别，它基于链表存储fd，没有最大数限制。与select一样，监控到描述符就绪并返回后，通过遍历文件描述符获取已经就绪的scoket。

同步与异步

同步是发起一个调用后，被调用者未处理完请求前，调用不返回，调用者不继续执行

异步是发起一个调用后，可以马上收到被调用者已接到请求的回应，但并没有立即返回结果。调用者可以继续执行其它操作，被调用者通过事件、回调等机制通知调用者返回结果

阻塞与非阻塞

操作系统I/O分为两个阶段：等待就绪和操作。读函数分为等待系统可读和真正的读；写函数分为等待网卡可写和真正的写。等待就绪的阻塞不使用 CPU，是在“空等”；真正的读写操作的阻塞是在使用 CPU，真正在“干活”，这个memory copy 的过程很快（如宽带 1GB/s）。

传统的BIO里面socket.read()，如果TCP RecvBuffer里没有数据，函数会一直阻塞，直到收到数据，返回读到的数据。

对于NIO，如果TCP RecvBuffer有数据，就把数据从网卡读到内存，并且返回给用户；反之则直接返回0，永远不会阻塞。

最新的AIO(Async I/O)里面会更进一步：不但等待就绪是非阻塞的，就连数据从网卡到内存的过程也是异步的。

换句话说，BIO里用户最关心“我要读”，NIO里用户最关心”我可以读了”，在AIO模型里用户更需要关注的是“读完了”。

NIO一个重要的特点是：socket主要的读、写、注册和接收函数，在等待就绪阶段都是非阻塞的，真正的I/O操作是同步阻塞的（消耗CPU但性能非常高）。

• 分布式系统
• 理论

从ACID到CAP/BASE

事务（Transaction）是由一系列对系统中数据进行访问和更新的操作所组成的一个程序执行逻辑单元（Unit），狭义上的事务指数据库事务。事务需要满足ACID特性，即原子性（Atomicity）、一致性（Consistency）、隔离性（Isolation）和持久性（Durability）。

分布式事务可以看作由多个分布式操作组成的序列，每个操作称为子事务。在高并发的互联网应用中，如果实现要实现严格满足ACID特性的分布式事务，会出现可用性与一致性之间的冲突。

CAP理论

一个分布式系统不可能同时满足一致性（Consistency）、可用性（Availability）和分区容错性（Partitiontolerance）这三个特性，最多只能同时满足其中的两项。由于分区容错性是分布式系统最基本的需求，所以往往需要把精力花在如何根据业务特点在一致性和可用性之间需求平衡。

一致性

分布式环境中，一致性是指数据在多个副本之间是否能保持一致的特性。如果能够做到针对一个数据项的更新操作执行成功后，所有的用户都可以读取到最新的值，即可认为该系统具有强一致性。

可用性

PriorityQueue

PriqorityQueue（优先队列）基于二叉小顶堆实现，可以用一颗完全二叉树来表示，底层采用数组来实现

假设树中父节点和左右子节点在数组中的下标分别为parent、left、right，树中任一节点对应数组下标为node，则有：

left=parent * 2 + 1

right=parent * 2 + 2

parent=(node - 1) / 2

PriorityQueue不允许插入null元素，否则将抛出npe异常，

参考资料

1. PriorityQueue
2. 用PriorityQueue实现最大最小堆