分布式领域论文译序
专注于为中小企业提供成都网站设计、网站建设、外贸网站建设服务,电脑端+手机端+微信端的三站合一,更高效的管理,为中小企业隰县免费做网站提供优质的服务。我们立足成都，凝聚了一批互联网行业人才，有力地推动了上千余家企业的稳健成长，帮助中小企业通过网站建设实现规模扩充和转变。
sqlnosql年代记
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 --E.F.Codd 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
大数据时代数据管理方式研究
1数据管理技术的回顾
数据管理技术主要经历了人工管理阶段、文件系统阶段和数据库系统阶段。随着数据应用领域的不断扩展，数据管理所处的环境也越来越复杂，目前广泛流行的数据库技术开始暴露出许多弱点，面临着许多新的挑战。
1.1 人工管理阶段
20 世纪 50 年代中期，计算机主要用于科学计算。当时没有磁盘等直接存取设备，只有纸带、卡片、磁带等外存，也没有操作系统和管理数据的专门软件。该阶段管理的数据不保存、由应用程序管理数据、数据不共享和数据不具有独立性等特点。
1.2 文件系统阶段
20 世纪 50 年代后期到 60 年代中期，随着计算机硬件和软件的发展，磁盘、磁鼓等直接存取设备开始普及，这一时期的数据处理系统是把计算机中的数据组织成相互独立的被命名的数据文件，并可按文件的名字来进行访问，对文件中的记录进行存取的数据管理技术。数据可以长期保存在计算机外存上，可以对数据进行反复处理，并支持文件的查询、修改、插入和删除等操作。其数据面向特定的应用程序，因此，数据共享性、独立性差，且冗余度大，管理和维护的代价也很大。
1.3数据库阶段
20 世纪 60 年代后期以来，计算机性能得到进一步提高，更重要的是出现了大容量磁盘，存储容量大大增加且价格下降。在此基础上，才有可能克服文件系统管理数据时的不足，而满足和解决实际应用中多个用户、多个应用程序共享数据的要求，从而使数据能为尽可能多的应用程序服务，这就出现了数据库这样的数据管理技术。数据库的特点是数据不再只针对某一个特定的应用，而是面向全组织，具有整体的结构性，共享性高，冗余度减小，具有一定的程序与数据之间的独立性，并且对数据进行统一的控制。
2大数据时代的数据管理技术
大数据（big data），或称巨量资料，指的是所涉及的资料量规模巨大到无法透过目前主流软件工具，在合理时间内达到撷取、管理、处理、并整理成为帮助企业经营决策更积极目的的资讯。大数据有 3 个 V,一是大量化（Volume），数据量是持续快速增加的，从 TB级别，跃升到 PB 级别；二是多样化（Variety），数据类型多样化，结构化数据已被视为小菜一碟，图片、音频、视频等非结构化数据正以传统结构化数据增长的两倍速快速创建；三是快速化 （Velocity），数据生成速度快，也就需要快速的处理能力，因此，产生了“1 秒定律”,就是说一般要在秒级时间范围内给出分析结果，时间太长就失去价值了，这个速度要求是大数据处理技术和传统的数据挖掘技术最大的区别。
2.1 关系型数据库（RDBMS）
20 世纪 70 年代初，IBM 工程师 Codd 发表了著名的论文“A Relational Model of Data for Large Shared DataBanks”,标志着关系数据库时代来临。关系数据库的理论基础是关系模型，是借助于集合代数等数学概念和方法来处理数据库中的数据，现实世界中的实体以及实体之间的联系非常容易用关系模型来表示。容易理解的模型、容易掌握的查询语言、高效的优化器、成熟的技术和产品，使得关系数据库占据了数据库市场的绝对的统治地位。随着互联网 web2.0 网站的兴起，半结构化和非结构化数据的大量涌现，传统的关系数据库在应付 web2.0 网站特别是超大规模和高并发的 SNS（全称 Social Networking Services,即社会性网络服务） 类型的 web2.0 纯动态网站已经显得力不从心，暴露了很多难以克服的问题。
2.2 noSQL数据库
顺应时代发展的需要产生了 noSQL数据库技术，其主要特点是采用与关系模型不同的数据模型，当前热门的 noSQL数据库系统可以说是蓬勃发展、异军突起，很多公司都热情追捧之，如：由 Google 公司提出的 Big Table 和 MapReduce 以及 IBM 公司提出的 Lotus Notes 等。不管是那个公司的 noSQL数据库都围绕着大数据的 3 个 V,目的就是解决大数据的 3个 V 问题。因此，在设计 noSQL 时往往考虑以下几个原则，首先，采用横向扩展的方式，通过并行处理技术对数据进行划分并进行并行处理，以获得高速的读写速度；其次，解决数据类型从以结构化数据为主转向结构化、半结构化、非结构化三者的融合的问题；再次，放松对数据的 ACID 一致性约束，允许数据暂时出现不一致的情况，接受最终一致性；最后，对各个分区数据进行备份（一般是 3 份），应对节点失败的状况等。
对数据的应用可以分为分析型应用和操作型应用，分析型应用主要是指对大量数据进行分类、聚集、汇总，最后获得数据量相对小的分析结果；操作型应用主要是指对数据进行增加、删除、修改和查询以及简单的汇总操作，涉及的数据量一般比较少，事务执行时间一般比较短。目前数据库可分为关系数据库和 noSQL数据库，根据数据应用的要求，再结合目前数据库的种类，所以目前数据库管理方式主要有以下 4 类。
（1）面向操作型的关系数据库技术。
首先，传统数据库厂商提供的基于行存储的关系数据库系统，如 DB2、Oracle、SQL Server 等，以其高度的一致性、精确性、系统可恢复性，在事务处理方面仍然是核心引擎。其次，面向实时计算的内存数据库系统，如 Hana、Timesten、Altibase 等通过把对数据并发控制、查询和恢复等操作控制在内存内部进行，所以获得了非常高的性能，在很多特定领域如电信、证券、网管等得到普遍应用。另外，以 VoltDB、Clustrix 和NuoDB 为代表的 new SQL 宣称能够在保持 ACDI 特性的同时提高了事务处理性能 50 倍 ~60 倍。
（2）面向分析型的关系数据库技术。
首先，TeraData 是数据仓库领域的领头羊，Teradata 在整体上是按 Shared Nothing 架构体系进行组织的，定位就是大型数据仓库系统，支持较高的扩展性。其次，面向分析型应用，列存储数据库的研究形成了另一个重要的潮流。列存储数据库以其高效的压缩、更高的 I/O 效率等特点，在分析型应用领域获得了比行存储数据库高得多的性能。如：MonetDB 和 Vertica是一个典型的基于列存储技术的数据库系统。
（3）面向操作型的 noSQL 技术。
有些操作型应用不受 ACID 高度一致性约束，但对大数据处理需要处理的数据量非常大，对速度性能要求也非常高，这样就必须依靠大规模集群的并行处理能力来实现数据处理，弱一致性或最终一致性就可以了。这时，操作型 noSQL数据库的优点就可以发挥的淋漓尽致了。如，Hbase 一天就可以有超过 200 亿个到达硬盘的读写操作，实现对大数据的处理。另外，noSQL数据库是一个数据模型灵活、支持多样数据类型，如对图数据建模、存储和分析，其性能、扩展性是关系数据库无法比拟的。
（4）面向分析型的 noSQL 技术。
面向分析型应用的 noSQL 技术主要依赖于Hadoop 分布式计算平台，Hadoop 是一个分布式计算平台，以 HDFS 和 Map Reduce 为用户提供系统底层细节透明的分布式基础架构。《Hadoop 经典实践染技巧》传统的数据库厂商 Microsoft,Oracle,SAS,IBM 等纷纷转向 Hadoop 的研究，如微软公司关闭 Dryad 系统，全力投入 Map Reduce 的研发，Oracle 在 2011 年下半年发布 Big Plan 战略计划，全面进军大数据处理领域，IBM 则早已捷足先登“,沃森（Watson）”计算机就是基于 Hadoop 技术开发的产物，同时 IBM 发布了 BigInsights 计划，基于 Hadoop,Netezza 和 SPSS（统计分析、数据挖掘软件）等技术和产品构建大数据分析处理的技术框架。同时也涌现出一批新公司来研究Hadoop 技术，如 Cloudera、MapRKarmashpere 等。
3数据管理方式的展望
通过以上分析，可以看出关系数据库的 ACID 强调数据一致性通常指关联数据之间的逻辑关系是否正确和完整，而对于很多互联网应用来说，对这一致性和隔离性的要求可以降低，而可用性的要求则更为明显，此时就可以采用 noSQL 的两种弱一致性的理论 BASE 和 CAP.关系数据库和 noSQL数据库并不是想到对立的矛盾体，而是可以相互补充的，根据不同需求使用不同的技术，甚至二者可以共同存在，互不影响。最近几年，以 Spanner 为代表新型数据库的出现，给数据库领域注入新鲜血液，这就是融合了一致性和可用性的 newSQL,这种新型思维方式或许会是未来大数据处理方式的发展方向。
4 结束语
随着云计算、物联网等的发展，数据呈现爆炸式的增长，人们正被数据洪流所包围，大数据的时代已经到来。正确利用大数据给人们的生活带来了极大的便利，但与此同时也给传统的数据管理方式带来了极大的挑战。
传统数据库仍旧会有一席之地，至于NewSQL的优势又是什么，简单和大家说说：
首先关于“中间件+关系数据库分库分表”算不算NewSQL分布式数据库问题，国外有篇论文pavlo-newsql-sigmodrec，如果根据该文中的分类，Spanner、TiDB、OB算是第一种新架构型，Sharding-Sphere、Mycat、DRDS等中间件方案算是第二种（文中还有第三种云数据库，本文暂不详细介绍）。
基于中间件（包括SDK和Proxy两种形式）+传统关系数据库（分库分表）模式是不是分布式架构？我觉得是的，因为存储确实也分布式了，也能实现横向扩展。但是不是“伪”分布式数据库？从架构先进性来看，这么说也有一定道理。
“伪”主要体现在中间件层与底层DB重复的SQL解析与执行计划生成、存储引擎基于B+Tree等，这在分布式数据库架构中实际上冗余低效的。为了避免引起真伪分布式数据库的口水战，本文中NewSQL数据库特指这种新架构NewSQL数据库。
NewSQL数据库相比中间件+分库分表的先进在哪儿？画一个简单的架构对比图：
传统数据库面向磁盘设计，基于内存的存储管理及并发控制，不如NewSQL数据库那般高效利用；
中间件模式SQL解析、执行计划优化等在中间件与数据库中重复工作，效率相比较低；
NewSQL数据库的分布式事务相比于XA进行了优化，性能更高；
新架构NewSQL数据库存储设计即为基于paxos（或Raft）协议的多副本，相比于传统数据库主从模式（半同步转异步后也存在丢数问题），在实现了真正的高可用、高可靠（RTO30s，RPO=0）；
NewSQL数据库天生支持数据分片，数据的迁移、扩容都是自动化的，大大减轻了DBA的工作，同时对应用透明，无需在SQL指定分库分表键。