gfs论文题目

gfs论文题目

GFS的诞生来源于google日益增长的数据量的处理需求，它是一个可扩展的分布式文件系统，用于大型分布式数据密集型应用，在廉价的通用硬件上运行时提供容错机制，并且可以为大量客户端提供较高的聚合性能。 它的设计由当前和预期的应用负载(当时的)和技术环境驱动，与以前的文件系统的假设有着明显不同，因此gfs在设计上有几个不同的points：

当前已部署多个集群用于不同目的，最大的拥有1000多个存储节点，超过300TB的存储服务，并且有数百个客户端连续不断地高负载请求。

前面提到一些对应用负载和技术环境的观察，现在更详细地进行阐述：

虽然GFS不能提供像POSIX标准的API，但它提供一个相似的文件系统接口。文件在目录中按层次结构组织，并以路径名作为标识。支持create、delete、open、close、read and write files。

gfs支持快照和record append操作。快照以低代价创建文件副本或者目录树，record append支持多个客户端并发地写文件，保证每个独立客户端append的原子性。

一个gfs集群包含一个master和多个chunkservers，chunkserver被多个客户端访问，如图1所示。每一个都是普通linux机器上运行的用户态服务进程。资源允许的情况下，客户端可以和chunkserver部署在同一台机器上。

文件被划分为固定大小的块。每个chunk由一个独一无二的64位大小的chunk handle所标识，chunk handle在chunk被创建时由master分配。每个chunk的副本分布在多个机器上，系统默认为三副本模式，用户也可以为不同namespace的文件指定不同级别的副本。

master包含文件系统的所有元信息。包含namespace、访问控制权限信息、文件到chunks的映射、当前chunks的位置信息。也控制着全局的活动，像chunk租约管理、gc、chunk迁移等。master通过心跳的方式与每个chunkserver交流来发送它的指令和收集状态。

客户端与master的交互涉及元信息操作，所有数据操作直接与chunkserver交互。gfs不提供POSIX标准API，因此不需要挂接到linux的vnode层。

客户端和chunkserver都不缓存文件数据。大多数应用传输大文件，客户端缓存收益很低。chunks作为本地的文件存储，linux系统有自己的buffer cache，chunkserver不需要再增加缓存。

单master简化了系统的设计，但是会有单点的瓶颈问题，这是必须要解决的。客户端不会从master读写数据文件，客户端请求master它需要的交互的chunkserver信息，并且将其缓存一段时间，后续的操作直接与chunkservers交互。

客户端会发送请求给离它最近的一个副本。实际上，客户端通常会向master请求多个chunk的信息，以减少未来与maser交互的代价。

chunk size定为64MB，相比普通的文件系统的block size更大。每个chunk副本以linux文件的形式存在chunkserver上，仅根据需要来扩展。使用lazy space allocation的方式避免空间浪费。

large chunk size有以下几个优点：

但是large chunk size with lazy space allocation也有其缺点：单个文件可能包含很少数量的chunks，或许只有一个，当许多客户端访问相同文件时这些chunks成为热点。但由于目标应用大多是顺序的读多个large chunk文件，热点并不是主要的问题。 然而GFS第一次用于批处理队列系统时确实出现了热点问题，数百个客户端同时访问一个单chunk文件，存储这个文件的几个chunkserver超负荷运转，当时通过错开应用的启动时间避免了这个问题，一个潜在、长期的解决方法是允许客户端从其它客户端读取数据。

master保存三种类型的元数据：

所有元数据都保存在内存中 。对于元数据的内存操作是很快的，后台任务周期巡检整个状态也是比较简单高效的。周期巡检用于实现chunk gc、在chunkserver故障时重新构造副本、chunk迁移以平衡多个chunkserver的负载和disk usage。 虽然系统的容量受master内存大小的限制，但这并不是一个严重的问题，64MB的chunk只需要不到64byte大小的元信息，如果一定需要更大的文件系统，那么增加内存的代价相比为可靠性、性能和灵活性等付出的代价是较小的。

前两种类型的元数据通过写日志来保证持久化，并且会复制日志到远程机器上。master不需要将chunks的位置信息持久化，而是在master启动和新的chunkserver加入集群时向每个chunkserver询问它的位置信息，之后通过心跳信息监控chunk位置变更信息。chunkserver作为最后一关是确切知道自己本地有没有哪些chunk的，因此维护一个一致性的视图是没有必要的。

operation log 包含元数据的变更记录， 它是GFS的核心 ，它不仅仅是唯一的元数据持久化记录，也表明了并发操作的逻辑时间线。文件、chunks和它们的版本都是由逻辑时间线唯一标识。元数据变更记录在持久化之前对客户端是不可见的，而且日志被复制到多个远程的机器，只有相应的记录在本地和远程都持久化到硬盘了才可以回复客户端。master使用批处理log的方式提高系统的吞吐。

master通过回放日志来恢复文件系统的状态，为提高恢复速度需要保持log量足够小。当log增长超过特定大小时，master会checkpoint它的状态，以加速恢复提高可用性。构建checkpoint可能需要花费一段时间，因此master以一种不delay后续变化的方式来组织内部状态，先switch到一个新的日志文件，使用独立的线程创建checkpoint，新的checkpoint包含了所有switch之前的变化。几百万个文件的集群在一分钟内可以完成，完成后将同时被写入本地和远程。恢复只需要最新的checkpoint和之后的日志文件，旧的checkpoints和日志文件可以完全删除。

GFS使用一个宽松的一致性模型，这种模型可以很好地支持分布式应用程序，而且实现起来简单有效。 file namesapce变化(例如文件创建)是原子的，使用namespace锁。 master的operation log定义了这些操作的全局顺序。

数据变化后文件region的状态取决于变化的类型，是否成功、失败或者是并发的。Table1做了总结。如果所有客户端都能看到相同的数据，无论它们读的是哪个副本，则这个file region是一致的。

数据变化有两种：writes或者record appends。write是指从应用指定offset处开始写数据，record append指即使存在并发冲突，数据也要被原子地append到文件至少一次，但offset是由GFS选定。

GFS保证在一系列成功的mutations后，file region是defined，通过下面两点来保证：

过期的副本将不会再涉及到任何mutation，master也不会将其位置信息回应给客户端，不久后将会被gc。但客户端缓存的信息可能包含过期的副本，缓存失效存在一个时间窗口，文件再次打开也会清除该文件的所有chunk信息。由于大多数文件是append-only，过期的副本通常返回的是过早的结尾???而不是过期的数据。

介绍客户端、master和chunkserver之间如何交互来实现数据变化、原子追加写和快照的。

使用租约的方式维护多个副本间一致的mutation order。master授权租约给副本中的一个，称之为primary。primary为chunk的mutaions选择一个顺序，所有副本都按照这个顺序apply。 租约机制最小化了master的管理overhead。租约初始的超时时间是60s，如果chunk一直在变化过程中，primary可以申请续租。这些授权和续租请求由master和chunkserver之间的心跳信息携带。master也可以尝试撤销租约，即使它与primary失去了联系，也可以等租约过期后安全地授权给另外一个副本。

在Figure2中，跟随着写入控制流展示了处理过程：

如果一个写请求比较大或者超出了chunk边界，GFS客户端将它拆为多个写操作，但是多个操作可能与其它客户端并发交叉写入，因此共享的fie region最终可能包含多个不同客户端的碎片，这会造成 一致性模型 中所描述的file region处于consistent but undefined状态。

数据以pipline的机制在chunkserver链上线性传输，而控制流是从客户端到primary再到所有的其它副本。分离数据流和控制流可以更高效地使用网络。可以带来以下好处：

GFS提供原子的append operaton叫作 record append 。传统的write中，客户端指定offset，并发写相同region时不是serializable，最终region可能包含多个客户端的碎片数据。而对于record append，客户端仅指定数据，GFS保证至少一次成功的原子append，offset由GFS选定，与Unix的O_APPEND模式相似。

多个客户端并发操作相同文件是比较重的。如果处理传统的write，客户端需要额外复杂和昂贵的同步逻辑，像分布式锁。而record append仅需要primary增加一点额外的逻辑：primary检查是否并发append数据的chunk会超出max size，如果会超出则将chunk填充到max size，并且告诉所有二级副本同样操作，然后回应客户端指出这个操作应该选择另一个chunk重试；大多数情况下记录是在max size内的，primary将数据append到自己的副本，并告诉所有二级副本按照确切的offset写数据，最后回应给客户端。

如果中间出现错误，客户端重试，相同chunk的副本可能包含不同的数据，可能包含相同的记录或者一部分相同，GFS不保证bytewise identical，仅仅保证数据至少有一次被成功地原子写入。从report success逻辑可以容易得出，数据必须是在某个chunk的所有副本上以相同的offset写入。在此之后，所有副本都与记录end一样长，即使后面不同的副本成为primary，任何将来的记录也将分配到更高的offset或者不同的chunk。根据上述的一致性保证，成功的record append的region是defined和一致的，而中间的region是不一致的(undefined)。GFS的应用可以处理这种不一致的region(2.7.2)。

snapshot 操作拷贝一份文件或者目录树，几乎是实时的，同时最大程度减少对正在进行中的mutation的干扰。 像AFS一样，使用标准的COW技术实现snapshot。当master接收到一个snapshot请求，首先将所有涉及到chunks的租约撤销，这保证了这些chunks后续的write将会先请求master查找租约持有者，master会创建一个新的副本来回应。

租约被撤销或者过期后，master将这个操作记录日志到disk。新创建的snapshot引用元数据相同的chunks。 当snapshot操作完成后，客户端第一次要写chunk C，发送请求给master查询持有租约者，master察觉到chunk C的引用大于1，则让每个含有当前chunk副本的chunkserver创建一个新的chunk叫作C'，所有创建都使用本地的副本，相比100Mb的网络本地速度大约是三倍速度。master授权租约给新的chunk C'中的一个并且回复给客户端，之后正常地写chunk。整个过程对客户端是透明的。

master执行所有的namespace操作。另外，它管理整个系统的chunk副本：

接下来，详细探讨这些细节。

许多master操作可能花费较长一段时间，比如snapshot操作需要撤销相关的所有chunks的租约。因此为了不delay其它master操作，在namesapce的regions上使用locks来确保串行化。 GFS没有按目录列出该目录中所有文件的结构，也不支持文件和目录的别名(unix中的硬链和软链)。GFS将完整的路径名到元数据的映射表作为它的逻辑namespace。使用前缀压缩，这个表可以有效保存在内存中。namespace tree中的每个节点都有一个关联的读写锁。 每个master操作在运行前都会获取一组锁。如果涉及到/d1/d2/../dn/leaf，它将获取目录名称/d1、/d1/d2、...、/d1/d2/.../dn上的读锁，完整路径/d1/d2/../dn/leaf的读锁或者写锁。leaf可以是文件或者目录。

创建文件不需要对父级目录加锁，因为没有"目录"的概念不会修改它，而加读锁是防止它被删除、重命名或者snapshot。这种锁机制的好处是允许相同目录下并发的mutations。

一个GFS集群通常具有分布在多个机架上的数百个chunkserver，这些chunkserver也会被相同或者不同机架的数百个客户端访问。不同机架上的两台计算机之间的通信可能会跨越一个或者多个网络交换机。另外进出机架的带宽可能小于机架内所有计算机的总带宽。多级分布式对如何分发数据以实现可伸缩性、可靠性和可用性提出了独特的挑战。 副本放置策略有两个目的：最大化数据可靠性和可用性，最大化网络带宽利用率。不仅要在多台机器上放置，还要在多个racks上，即使整个racks损坏也可以确保部分副本保持可用。也可以利用多个racks的总带宽。

chunk副本创建有三个原因：

当master创建新的chunk时，根据几个因素考虑如何放置新的副本：

当chunk可用副本的数量低于用户指定时，master会重新复制。可能发生在几种情况：

需要重新复制的chunk根据以下几个因素确定优先级：

master限制集群和每一个chunkserver内的活跃的clone数量，另外chunkserver通过限制其对源chunkserver的读请求来限制在每个clone操作上花费的带宽。

master会定期重新平衡副本：检查当前副本的分布，迁移副本以获得更好的磁盘空间利用率和负载平衡。同样通过此过程，master逐渐填充一个新的chunkserver。另外，master通常更倾向于移除具有低磁盘利用率chunkservers上的副本，以平衡空间使用。

当文件被删除时，master记录日志，但不会立即回收资源，而是将文件重命名为包含删除时间戳标记的隐藏名称。如果这些文件存在时间超过三天(时间可配置)，master巡检时会将其删除。在此之前，仍然可以用特殊名称来读取文件，并且可以重命名为正常名称来取消删除。当从namesapce中删除隐藏文件时，其内存元数据将被删除，这有效切断了所有chunk的连接，在对chunk namespace的扫描中，master识别出孤立的chunk并清除元数据。在心跳信息中，每个chunkserver报告其拥有的chunks子集，而master将回应不在存在于master元数据中的所有的chunk的标识。chunkserver可以自由删除此类chunk的副本。

这种gc机制相比立即删除有以下几个优点：

这种机制主要的缺点是当存储空间紧张时，延迟有时会影响用户的使用，重复创建和删除临时文件的应用可能无法立即重用存储。如果删除的文件再次被明确删除，GFS将通过加快存储回收来解决这些问题。还允许用户将不同的复制和回收策略应用于不同的namespace的不同部分中。

如果一个chunkserver故障或者chunk丢失了mutations，这个chunk副本可能是过期的。对于每个chunk，master都维护了一个chunk版本号。

当master授权租约给一个chunk时，这个chunk的版本号增加1，如果一个副本当前不可用了，则其版本号将不会领先。当chunkserver重新启动并报告其chunks集合和相关联的版本号时，master将检测到该chunkserver上具有过期的副本。如果master看到的版本号大于它记录的版本号，则认为在授权租约时失败了，因此将较高的版本号更新。

master在常规gc中删除旧的副本。另一个保护措施，在master回应客户端哪个chunk持有租约或者clone操作中chunkserver从另一个chunkserver读取chunk时会包含chunk的最新版本号。客户端或者chunkserver在执行操作时会验证版本号。

这个系统最大的挑战之一是处理经常故障的组件。组件的质量和数量造成的问题会超出预期，组件故障可能造成系统不可能，甚至数据错误。接下来讨论GFS如何应对这些挑战，还有系统如何诊断不可避免问题。

使用两个简单有效的方式保证系统的高可用：快速恢复和复制。 master和chunkserver的恢复都是秒级别的。 master维护每个chunk的副本数量，当chunkserver下线或者checksum检测出错误副本时，master会通过已有副本来复制。尽管复制提供了很好的解决方式，但仍在探索其它形式的跨服务器冗余方案，例如奇偶校验或者纠删码，以适应不断增长的只读存储需求。在非常松耦合的系统中实现这些更复杂的冗余方案更具有挑战性。

master的操作日志和checkpoint会被复制到多台机器上，状态的变化只有在本地和所有副本上都持久化以后才可以commit。master进程负责所有的mutations以及后台任务，当它宕机时可以很快重启，如果机器或者磁盘故障，GFS的外部监控将使用日志在其它节点重启新的master进程。在master宕机时，master的备节点只提供只读服务，它们不与master保持强一致，可能会落后于master，通常在1/4秒内。它们保证了那些不介意读到过期数据的应用的高可用读。类似于chunk的primary机制，master的备按照相同的序列应用日志。与master一样，在启动时从每个chunkserver拉取chunks的位置信息，与它们频繁交换握手消息来监控其状态。

每个chunkserver使用checksum来检测存储数据的损坏。数据损坏的chunk可以通过其它的副本来恢复，但是通过副本间比较来检验数据是不切实际的。正常的副本也不是完全一样的，如前文所讲，原子的append并不能保证完全一样的副本。因此每个chunkserver会维护自己的checksum。 每个chunk分为多个64kb的blocks，每个block包含一个32位的checksum，与其它元数据一样，checksum保存在内存中，依靠log持久化，与用户数据分离。

对于读，chunkserver在返回数据给请求者前先检测checksum，确保不会将出错的数据传输给其它chunkservers或者客户端。如果数据是坏的，chunkserver将错误返回给请求者并报告给master，请求者将会去读其它副本， master将会根据其它副本重新克隆一份。当新的副本创建以后，master指示chunkserver将错误的副本删除。checksum的计算不涉及I/O，对读的影响比较小，客户端通常尝试使用对齐block边界读来减少overhead。

为append写是做了checksum计算上的优化的，因为append写是主要的负载(相比于overwrite)。GFS只增量地更新最后部分block的checksum，为新的block的计算新的checksum。这样即使block已经损坏，新的checksum将与存储的数据不会匹配，下次读时将会与正常一样被检测出来。 如果一个写请求要写一个chunk中已存在的region，必要要先检验region的第一个和最后一个block的checksum，然后再重写，最后计算新的checksums。因为第一个和最后一个block可能含有不被重写的内容，如果这部分数据是损坏的，则新的checksum将包含错误的数据。

在idle时，checkserver可以扫描并检查不活跃的chunks，可以检测到冷chunks的错误，一旦错误被检测到，master可以创建一个新的副本。

GFS在设计上与传统文件系统有很多不同，这些点是基于对当时应用负载和技术环境的观察所重新设计，将组件故障看作平常的事件而非异常，为大文件的读取和追加写做优化，扩展和放宽了标准的文件系统接口以改善整个系统。通过监控、复制以及快速恢复能力提供容错能力，使用checksum机制来校验数据的正确性。通过将控制流和数据流分离，数据直接在chunkservers、客户端之间传输，为许多并发的各种任务的读取和写入提供了高吞吐量。大chunk size和租约机制使得master的操作足够轻量化，使得这样一个简单中心化的master不会成为瓶颈。

GFS成功地满足了google的存储需求，作为研究、开发和数据处理的存储平台广泛地应用于google内部。

分布式系统领域有哪些经典论文

分布式领域论文译序
sql&nosql年代记
SMAQ：海量数据的存储计算和查询
一．google论文系列
1. google系列论文译序
2. The anatomy of a large-scale hypertextual Web search engine (译 zz)
3. web search for a planet :the google cluster architecture(译)
4. GFS：google文件系统 (译)
5. MapReduce: Simplied Data Processing on Large Clusters (译)
6. Bigtable: A Distributed Storage System for Structured Data (译)
7. Chubby: The Chubby lock service for loosely-coupled distributed systems (译)
8. Sawzall:Interpreting the Data--Parallel Analysis with Sawzall (译 zz)
9. Pregel: A System for Large-Scale Graph Processing (译)
10. Dremel: Interactive Analysis of WebScale Datasets(译zz)
11. Percolator: Large-scale Incremental Processing Using Distributed Transactions and Notifications(译zz)
12. MegaStore: Providing Scalable, Highly Available Storage for Interactive Services(译zz)
13. Case Study GFS: Evolution on Fast-forward (译)
14. Google File System II: Dawn of the Multiplying Master Nodes
15. Tenzing - A SQL Implementation on the MapReduce Framework (译)
16. F1-The Fault-Tolerant Distributed RDBMS Supporting Google's Ad Business
17. Elmo: Building a Globally Distributed, Highly Available Database
18. PowerDrill：Processing a Trillion Cells per Mouse Click
19. Google-Wide Profiling:A Continuous Profiling Infrastructure for Data Centers
20. Spanner: Google’s Globally-Distributed Database(译zz)
21. Dapper, a Large-Scale Distributed Systems Tracing Infrastructure(笔记)
22. Omega: flexible, scalable schedulers for large compute clusters
23. CPI2: CPU performance isolation for shared compute clusters
24. Photon: Fault-tolerant and Scalable Joining of Continuous Data Streams(译)
25. F1: A Distributed SQL Database That Scales
26. MillWheel: Fault-Tolerant Stream Processing at Internet Scale(译)
27. B4: Experience with a Globally-Deployed Software Defined WAN
28. The Datacenter as a Computer
29. Google brain-Building High-level Features Using Large Scale Unsupervised Learning
30. Mesa: Geo-Replicated, Near Real-Time, Scalable Data Warehousing(译zz)
31. Large-scale cluster management at Google with Borg
google系列论文翻译集(合集)
二．分布式理论系列
00. Appraising Two Decades of Distributed Computing Theory Research
0. 分布式理论系列译序

1. A brief history of Consensus_ 2PC and Transaction Commit (译)
2. 拜占庭将军问题 (译) --Leslie Lamport
3. Impossibility of distributed consensus with one faulty process (译)
4. Leases：租约机制 (译)
5. Time Clocks and the Ordering of Events in a Distributed System(译) --Leslie Lamport
6. 关于Paxos的历史
7. The Part Time Parliament (译 zz) --Leslie Lamport
8. How to Build a Highly Available System Using Consensus(译)
9. Paxos Made Simple (译) --Leslie Lamport
10. Paxos Made Live - An Engineering Perspective(译)
11. 2 Phase Commit(译)
12. Consensus on Transaction Commit(译) --Jim Gray & Leslie Lamport
13. Why Do Computers Stop and What Can Be Done About It?(译) --Jim Gray
14. On Designing and Deploying Internet-Scale Services(译) --James Hamilton
15. Single-Message Communication(译)
16. Implementing fault-tolerant services using the state machine approach
17. Problems, Unsolved Problems and Problems in Concurrency
18. Hints for Computer System Design
19. Self-stabilizing systems in spite of distributed control
20. Wait-Free Synchronization
21. White Paper Introduction to IEEE 1588 & Transparent Clocks

22. Unreliable Failure Detectors for Reliable Distributed Systems
23. Life beyond Distributed Transactions:an Apostate’s Opinion(译zz)
24. Distributed Snapshots: Determining Global States of a Distributed System --Leslie Lamport
25. Virtual Time and Global States of Distributed Systems
26. Timestamps in Message-Passing Systems That Preserve the Partial Ordering
27. Fundamentals of Distributed Computing:A Practical Tour of Vector Clock Systems
28. Knowledge and Common Knowledge in a Distributed Environment
29. Understanding Failures in Petascale Computers
30. Why Do Internet services fail, and What Can Be Done About It?
31. End-To-End Arguments in System Design
32. Rethinking the Design of the Internet: The End-to-End Arguments vs. the Brave New World
33. The Design Philosophy of the DARPA Internet Protocols(译zz)
34. Uniform consensus is harder than consensus
35. Paxos made code - Implementing a high throughput Atomic Broadcast
36. RAFT:In Search of an Understandable Consensus Algorithm
分布式理论系列论文翻译集(合集)
三．数据库理论系列
0. A Relational Model of Data for Large Shared Data Banks -- 1970
1. SEQUEL：A Structured English Query Language 1974
2. Implentation of a Structured English Query Language 1975
3. A System R: Relational Approach to Database Management 1976
4. Granularity of Locks and Degrees of Consistency in a Shared DataBase --Jim Gray 1976
5. Access Path Selection in a RDBMS 1979
6. The Transaction Concept:Virtues and Limitations --Jim Gray
7. 2pc-2阶段提交：Notes on Data Base Operating Systems --Jim Gray
8. 3pc-3阶段提交：NONBLOCKING COMMIT PROTOCOLS
9. MVCC：Multiversion Concurrency Control-Theory and Algorithms --1983
10. ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging-1992
11. A Comparison of the Byzantine Agreement Problem and the Transaction Commit Problem --Jim Gray
12. A Formal Model of Crash Recovery in a Distributed System - Skeen, D. Stonebraker
13. What Goes Around Comes Around - Michael Stonebraker, Joseph M. Hellerstein
14. Anatomy of a Database System -Joseph M. Hellerstein, Michael Stonebraker
15. Architecture of a Database System(译zz) -Joseph M. Hellerstein, Michael Stonebraker, James Hamilton
四．大规模存储与计算(NoSql理论系列)
0. Towards Robust Distributed Systems：Brewer's 2000 PODC key notes
1. CAP理论
2. Harvest, Yield, and Scalable Tolerant Systems
3. 关于CAP
4. BASE模型：BASE an Acid Alternative
5. 最终一致性
6. 可扩展性设计模式
7. 可伸缩性原则
8. NoSql生态系统
9. scalability-availability-stability-patterns
10. The 5 Minute Rule and the 5 Byte Rule (译)
11. The Five-Minute Rule Ten Years Later and Other Computer Storage Rules of Thumb
12. The Five-Minute Rule 20 Years Later(and How Flash Memory Changes the Rules)
13. 关于MapReduce的争论
14. MapReduce：一个巨大的倒退
15. MapReduce：一个巨大的倒退(II)
16. MapReduce和并行数据库，朋友还是敌人？(zz)
17. MapReduce and Parallel DBMSs-Friends or Foes (译)
18. MapReduce:A Flexible Data Processing Tool (译)
19. A Comparision of Approaches to Large-Scale Data Analysis (译)
20. MapReduce Hold不住？(zz)
21. Beyond MapReduce：图计算概览
22. Map-Reduce-Merge: simplified relational data processing on large clusters
23. MapReduce Online
24. Graph Twiddling in a MapReduce World
25. Spark: Cluster Computing with Working Sets
26. Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing
27. Big Data Lambda Architecture
28. The 8 Requirements of Real-Time Stream Processing
29. The Log: What every software engineer should know about real-time data's unifying abstraction
30. Lessons from Giant-Scale Services
五．基本算法和数据结构
1. 大数据量，海量数据处理方法总结
2. 大数据量，海量数据处理方法总结(续)
3. Consistent Hashing And Random Trees
4. Merkle Trees
5. Scalable Bloom Filters
6. Introduction to Distributed Hash Tables
7. B-Trees and Relational Database Systems
8. The log-structured merge-tree (译)
9. lock free data structure
10. Data Structures for Spatial Database
11. Gossip
12. lock free algorithm
13. The Graph Traversal Pattern
六．基本系统和实践经验
1. MySQL索引背后的数据结构及算法原理
2. Dynamo: Amazon’s Highly Available Key-value Store (译zz)
3. Cassandra - A Decentralized Structured Storage System (译zz)
4. PNUTS: Yahoo!’s Hosted Data Serving Platform (译zz)
5. Yahoo!的分布式数据平台PNUTS简介及感悟(zz)
6. LevelDB：一个快速轻量级的key-value存储库(译)
7. LevelDB理论基础
8. LevelDB：实现(译)
9. LevelDB SSTable格式详解
10. LevelDB Bloom Filter实现
11. Sawzall原理与应用
12. Storm原理与实现
13. Designs, Lessons and Advice from Building Large Distributed Systems --Jeff Dean
14. Challenges in Building Large-Scale Information Retrieval Systems --Jeff Dean
15. Experiences with MapReduce, an Abstraction for Large-Scale Computation --Jeff Dean
16. Taming Service Variability,Building Worldwide Systems,and Scaling Deep Learning --Jeff Dean
17. Large-Scale Data and Computation:Challenges and Opportunitis --Jeff Dean
18. Achieving Rapid Response Times in Large Online Services --Jeff Dean
19. The Tail at Scale(译) --Jeff Dean & Luiz André Barroso
20. How To Design A Good API and Why it Matters
21. Event-Based Systems:Architect's Dream or Developer's Nightmare?
22. Autopilot: Automatic Data Center Management
七．其他辅助系统
1. The ganglia distributed monitoring system:design, implementation, and experience
2. Chukwa: A large-scale monitoring system
3. Scribe : a way to aggregate data and why not, to directly fill the HDFS?
4. Benchmarking Cloud Serving Systems with YCSB
5. Dynamo Dremel ZooKeeper Hive 简述
八. Hadoop相关
0. Hadoop Reading List
1. The Hadoop Distributed File System(译)
2. HDFS scalability:the limits to growth(译)
3. Name-node memory size estimates and optimization proposal.
4. HBase Architecture(译)
5. HFile：A Block-Indexed File Format to Store Sorted Key-Value Pairs
6. HFile V2
7. Hive - A Warehousing Solution Over a Map-Reduce Framework
8. Hive – A Petabyte Scale Data Warehouse Using Hadoop

转载请注明作者：phylips@bmy 2011-4-30

分布式系统领域有哪些经典论文

分布式系统在互联网时代，尤其是大数据时代到来之后，成为了每个程序员的必备技能之一。分布式系统从上个世纪80年代就开始有了不少出色的研究和论文，我在这里只列举最近15年范围以内我觉得有重大影响意义的15篇论文（15 within 15）。

1. The Google File System: 这是分布式文件系统领域划时代意义的论文，文中的多副本机制、控制流与数据流隔离和追加写模式等概念几乎成为了分布式文件系统领域的标准，其影响之深远通过其5000+的引用就可见一斑了，Apache Hadoop鼎鼎大名的HDFS就是GFS的模仿之作；
2. MapReduce: Simplified Data Processing on Large Clusters：这篇也是Google的大作，通过Map和Reduce两个操作，大大简化了分布式计算的复杂度，使得任何需要的程序员都可以编写分布式计算程序，其中使用到的技术值得我们好好学习：简约而不简单！Hadoop也根据这篇论文做了一个开源的MapReduce；
3. Bigtable: A Distributed Storage System for Structured Data：Google在NoSQL领域的分布式表格系统，LSM树的最好使用范例，广泛使用到了网页索引存储、YouTube数据管理等业务，Hadoop对应的开源系统叫HBase（我在前公司任职时也开发过一个相应的系统叫BladeCube，性能较HBase有数倍提升）；
4. The Chubby lock service for loosely-coupled distributed systems：Google的分布式锁服务，基于Paxos协议，这篇文章相比于前三篇可能知道的人就少了，但是其对应的开源系统zookeeper几乎是每个后端同学都接触过，其影响力其实不亚于前三篇；
5. Finding a Needle in Haystack: Facebook's Photo Storage：facebook的在线图片存储系统，目前来看是对小文件存储的最好解决方案之一，facebook目前通过该系统存储了超过300PB的数据，一个师兄就在这个团队工作，听过很多有意思的事情（我在前公司的时候开发过一个类似的系统pallas，不仅支持副本，还支持Reed Solomon-LRC，性能也有较多优化）；
6. Windows Azure Storage: a highly available cloud storage service with strong consistency：windows azure的总体介绍文章，是一篇很好的描述云存储架构的论文，其中通过分层来同时保证可用性和一致性的思路在现实工作中也给了我很多启发；
7. GraphLab: A New Framework for Parallel Machine Learning：CMU基于图计算的分布式机器学习框架，目前已经成立了专门的商业公司，在分布式机器学习上很有两把刷子，其单机版的GraphChi在百万维度的矩阵分解都只需要2~3分钟；
8. Resilient Distributed Datasets: A Fault-Tolerant Abstraction for
In-Memory Cluster Computing：其实就是 Spark，目前这两年最流行的内存计算模式，通过RDD和lineage大大简化了分布式计算框架，通常几行scala代码就可以搞定原来上千行MapReduce代码才能搞定的问题，大有取代MapReduce的趋势；
9. Scaling Distributed Machine Learning with the Parameter Server：百度少帅李沐大作，目前大规模分布式学习各家公司主要都是使用ps，ps具备良好的可扩展性，使得大数据时代的大规模分布式学习成为可能，包括Google的深度学习模型也是通过ps训练实现，是目前最流行的分布式学习框架，豆瓣的开源系统paracell也是ps的一个实现；
10. Dremel: Interactive Analysis of Web-Scale Datasets：Google的大规模（近）实时数据分析系统，号称可以在3秒相应1PB数据的分析请求，内部使用到了查询树来优化分析速度，其开源实现为Drill，在工业界对实时数据分析也是比价有影响力；
11. Pregel: a system for large-scale graph processing: Google的大规模图计算系统，相当长一段时间是Google PageRank的主要计算系统，对开源的影响也很大（包括GraphLab和GraphChi）；
12. Spanner: Google's Globally-Distributed Database：这是第一个全球意义上的分布式数据库，Google的出品。其中介绍了很多一致性方面的设计考虑，简单起见，还采用了GPS和原子钟确保时间最大误差在20ns以内，保证了事务的时间序，同样在分布式系统方面具有很强的借鉴意义；
13. Dynamo: Amazon’s Highly Available Key-value Store：Amazon的分布式NoSQL数据库，意义相当于BigTable对于Google，于BigTable不同的是，Dynamo保证CAP中的AP，C通过vector clock做弱保证，对应的开源系统为Cassandra；
14. S4: Distributed Stream Computing Platform：Yahoo出品的流式计算系统，目前最流行的两大流式计算系统之一（另一个是storm），Yahoo的主要广告计算平台；
15. Storm @Twitter：这个系统不多说，开启了流式计算的新纪元，几乎是所有公司流式计算的首选，绝对值得关注；