摘要

Bigtable 是一个分布式的结构化数据存储系统,它被设计用来处理海量数据:通常是分布在数千台普通服务器上的 PB 级的数据。

Google 的很多项目使用 Bigtable 存储数据,包括 Web 索引、Google Earth、Google Finance。这些应用对 Bigtable 提出的要求差异非常大,无论是在数据量上(从 URL 到网页到卫星图像)还是在响应速度上(从后端的批量处理到实时数据服务)。尽管应用需求差异很大,但是,针对 Google 的这些产品,Bigtable 还是成功的提供了一个灵活的、高性能的解决方案。

本论文描述了 Bigtable 提供的简单的数据模型。利用这个模型,用户可以动态的控制数据的分布和格式。 我们还将描述 Bigtable 的设计和实现。

介绍

在过去两年半时间里,我们设计、实现并部署了一个分布式的结构化数据存储系统 —— 在 Google,我们 称之为 Bigtable。Bigtable 的设计目的是可靠的处理 PB 级别的数据,并且能够部署到上千台机器上。Bigtable 已经实现了下面的几个目标:适用性广泛、可扩展、高性能和高可用性。

阅读全文 »

摘要

MapReduce 是一个编程模型,也是一个处理和生成超大数据集的算法模型的相关实现。用户首先创建一个 Map 函数处理一个基于 key/value pair 的数据集合,输出中间的基于 key/value pair 的数据集合;然后再创建一个 Reduce 函数用来合并所有的具有相同中间 key 值的中间 value 值。现实世界中有很多满足上述处理模型的例子,本论文将详细描述这个模型。

MapReduce 架构的程序能够在大量的普通配置的计算机上实现并行化处理。这个系统在运行时只关心:如何分割输入数据,在大量计算机组成的集群上的调度,集群中计算机的错误处理,管理集群中计算机之间必要的通信。采用 MapReduce 架构可以使那些没有并行计算和分布式处理系统开发经验的程序员有效利用分布式系统的丰富资源。

我们的 MapReduce 实现运行在规模可以灵活调整的由普通机器组成的集群上:一个典型的 MapReduce 计算往往由几千台机器组成、处理以 TB 计算的数据。程序员发现这个系统非常好用:已经实现了数以百计的 MapReduce 程序,在 Google 的集群上,每天都有 1000 多个 MapReduce 程序在执行。

阅读全文 »

摘要

我们设计并实现了 Google GFS 文件系统,一个面向大规模数据密集型应用的、可伸缩的分布式文件系统。 GFS 虽然运行在廉价的普遍硬件设备上,但是它依然了提供灾难冗余的能力,为大量客户机提供了高性能的服务。

虽然 GFS 的设计目标与许多传统的分布式文件系统有很多相同之处,但是,我们的设计还是以我们对自己的应用的负载情况和技术环境的分析为基础的,不管现在还是将来,GFS 和早期的分布式文件系统的设想都有明显的不同。所以我们重新审视了传统文件系统在设计上的折衷选择,衍生出了完全不同的设计思路。

GFS 完全满足了我们对存储的需求。GFS 作为存储平台已经被广泛的部署在 Google 内部,存储我们的服务产生和处理的数据,同时还用于那些需要大规模数据集的研究和开发工作。目前为止,最大的一个集群利用数千台机器的数千个硬盘,提供了数百 TB 的存储空间,同时为数百个客户机服务。

在本论文中,我们展示了能够支持分布式应用的文件系统接口的扩展,讨论我们设计的许多方面,最后列出了小规模性能测试以及真实生产系统中性能相关数据。

阅读全文 »

同步IO和异步IO,阻塞IO和非阻塞IO分别是什么,到底有什么区别?不同的人在不同的上下文下给出的答案是不同的。所以先限定一下本文的上下文。

本文讨论的背景是Linux环境下的network IO。

一 概念说明

在进行解释之前,首先要说明几个概念:

  • 用户空间和内核空间
  • 进程切换
  • 进程的阻塞
  • 文件描述符
  • 缓存 I/O

用户空间与内核空间

现在操作系统都是采用虚拟存储器,那么对32位操作系统而言,它的寻址空间(虚拟存储空间)为4G(2的32次方)。操作系统的核心是内核,独立于普通的应用程序,可以访问受保护的内存空间,也有访问底层硬件设备的所有权限。为了保证用户进程不能直接操作内核(kernel),保证内核的安全,操心系统将虚拟空间划分为两部分,一部分为内核空间,一部分为用户空间。针对linux操作系统而言,将最高的1G字节(从虚拟地址0xC0000000到0xFFFFFFFF),供内核使用,称为内核空间,而将较低的3G字节(从虚拟地址0x00000000到0xBFFFFFFF),供各个进程使用,称为用户空间。

进程切换

为了控制进程的执行,内核必须有能力挂起正在CPU上运行的进程,并恢复以前挂起的某个进程的执行。这种行为被称为进程切换1。因此可以说,任何进程都是在操作系统内核的支持下运行的,是与内核紧密相关的。

从一个进程的运行转到另一个进程上运行,这个过程中经过下面这些变化:

  1. 保存处理机上下文,包括程序计数器和其他寄存器。
  2. 更新PCB信息。
  3. 把进程的PCB移入相应的队列,如就绪、在某事件阻塞等队列。
  4. 选择另一个进程执行,并更新其PCB。
  5. 更新内存管理的数据结构。
  6. 恢复处理机上下文。
    阅读全文 »

今天在看厕所专刊(编程珠玑)的时候看到了粗略估算,有点感悟,所以写下关于粗略估算的笔记。

粗略估算

粗略估算在工程角度来说是非常重要的,对于个人的能力评估也是很重要的,粗略估算不是说和仔细的数学的计算正确结果相悖,而是在某些情况下,在得到正确的结果之前,能够给我们一个很准确的方向,例如下面这道题。

题目:从N个数中取M个最大值。N是无序的,不连续的。

当然,在做上面这道题的时候,大家都可以很容易的做出来,例如快速排序,取前M个数,用二叉排序树,后序遍历M个数,堆排序,等等,不是很复杂。当然,这个题还可以变形一下,如下。

题目:从100万个数中取最大的10个数。

好吧,我想大部分的人都会犯这样一个错误,100万?这么大,那么我怎么组织空间才能性能最好,速度最快呢?其实,这个肯定是有一定问题的,100万,不是小数目,但是我们不妨计算一下,在各个系统中占用的内存最坏是多少,我们可以大约估算一下,在16位的机器里,一个指针和一个整数大约占4个字节,32位,那么就是8字节,那么64位就是16字节。那么100万个32位的整数和指针,大约会占用8M的内存,也就是说,在现在的计算机里,就算你将100万个数全部放到内存中,也才8M,那么,最坏最坏才8M,你就可以为你的程序计算出最坏的情况,比如这个程序需要10M内存,CPUx%以及进程数n,那么最后的程序应该在这个预期之内或更好。为了追求速度,可以牺牲一点空间,可以全部读入,如果要求空间有限,那就要优化一下,只用4M或2M内存或者更少。

阅读全文 »