银河里的星星
英文原文：http://developer.yahoo.com/blogs/hadoop/posts/2011/02/mapreduce-nextgen/
zz from：http://blog.nosqlfan.com/html/1451.html
注：随着Hadoop的流行，其局限性也在一定程度体现，各大公司也在hadoop上做了很多修改，下面是雅虎对Hadoop下一代的重构计划。原文地址：http://sandaobusi.javaeye.com/blog/941740
zz from：http://www.dbthink.com/?p=666&cpage=1#comment-596
source : The Seven Secrets of Successful Data Scientists
1.选择合适的工具,杀鸡不要随便用牛刀,打蚊子毋需高射炮.
2.对所有的数据做压缩, 原因, 我们处在一个IO密集的世界
3.拆分,拆分,还是拆分
4.对数据取样,不是每次分析都需要使用全量数据
5.拿来主义,善于从开源社区,寻找已经解决好的方案,毋需不断重建轮子
6.Data Locality, 让数据毋需移动即可进行分析
7.不要过于聪明,专注于解决你实际面临的困难,不要去解决太过于遥远的问题
zz from：http://www.dbthink.com/?p=483
本文是Ebay的架构师在2008年发表给ACM的文章,是一篇解释BASE原则,或者说最终一致性的经典文章. 文中Dan讨论了BASE与ACID原则的基本差异, 以及如何设计大型网站以满足不断增长的可伸缩性需求,期间如何对业务做调整与折衷. 以及一些具体的折衷技术的介绍.
译文：http://www.importnew.com/2896.html
http://research.google.com/pubs/pub36726.html
译考文献：
http://rdc.taobao.com/blog/cs/?p=666 Percolator 中的分布式事务
http://blog.csdn.net/maray/article/details/6978958 Percolator中的两阶段提交实现分析
http://www.spnguru.com/?p=435 使用分布式事务和通知机制处理大规模增量型数据
译文：http://www.importnew.com/2617.html
译考文献：
http://duanple.blog.163.com/blog/static/70971767201192104236129/ Dynamo Dremel ZooKeeper Hive
http://www.meirendaddy.com/blog/?p=1007 Google的Dremel + bigquery
http://hi.baidu.com/dyerac/blog/item/f4c4211689317a0a972b43af.html Dremel论文阅读笔记
zz from：http://blog.sciencenet.cn/home.php?mod=space&uid=449420&do=blog&id=444736
Jason Baker, Chris Bond, James C. Corbett, JJ Furman, Andrey Khorlin, James Larson,
Jean Michel L′eon, Yawei Li, Alexander Lloyd, Vadim Yushprakh
Google, Inc.
简述 Megastore是一个存储系统，应对目前的交互在线服务之需求。Megastore以一种全新的方式混合了NoSQL数据存储的可伸缩性以及传统关系型数据库管理系统RDBMS的易用性，并同时提供了强一致性保护以及高可用性。 我们提供了完全序列化的ACID语法以及细致分区了的数据。该分区允许我们在遍布广域网的范围内，同步的复制每个写，以一个合理的延迟进行工作，并支持数据中心的无缝的故障恢复（failover），本文献描述了Megastore的语法以及复制算法。同样描述了我们Megastore构建的在支持广大范围内支持的系列谷歌服务产品时的经验。
分类和主题描述
C.2.4【分布式系统】：分布式数据库；
H.2.4【数据库管理】：系统|并行，分布式数据库
常用字 算法， 设计， 性能， 可靠性
关键字 大型数据库， 分布式事务处理， BigTable, Paxos
1. 介绍
交互式在线服务使得存储社区遇到新需求，就像桌面应用程序迁移到云所需面对的一样。诸如email这样的服务， 协同文档，以及社会网络以指数形式增长，并对现存的架构极限进行测试中。面对这些服务存储是具有挑战性的，这是由于一系列的相互矛盾的需求。 首先，因特网带来了巨大的潜在受众，所以应用就必须是高可扩展的。一个可以用MySQL 进行快速构建的服务可以是一个数据存储【参见：www.mysql.com】，但是将这个服务扩展到百万用户就需要对其存储架构作一个完全的重新设计。其次，服务必须为用户而竞争。这需要快速的开发的特性以及快速的投入市场所需的时间。第三，服务必须是响应的；即是说，存储系统必须有低延迟特性。第四点，服务必须提供给用户以一致的观点看待数据，更新的结果必须立即可视以及持久的保存。看到编辑一个云端电子表格软件消失，无论该表格如何简要，都是很差的用户体验。最后，用户期望英特网服务是24乘7小时的， 故服务必须保持高可靠性。系统对各种故障（faults）还必须对“从个别磁盘，机器失败到从路由起一直影响到整个数据中心的大规模运行中断的出错范围”保持透明（be resilient to）。 这些需求是向矛盾的。关系型数据库就用于构建应用，提供了一个功能的富集，但是关系型数据库却难于扩展到数亿的（hundreds of millions ）用户。诸如谷歌BigTable【参见：Bigtable: 就结构化数据的分布式存储系统】，Apache hadoop的 Hbase【参见：hbase.apache.org】，或Facebook的Cassandra【参见：incubator.apache.org/cassandra】一类的NoSQL 数据存储是高可扩展的，但其受限的API以及松一致性模型（loose consis-tency models ）使得应用开发变得复杂化了。由于为了确保就复制数据的一致性视图，特别是在故障发生期间，故而在远距离数据中心间复制数据的同时提供低延迟性是一个挑战。 Megastore 是一个存储系统，其开发适合了现今交互式在线服务的需求。Megastore 设计方式是全新的，由于其融合了NoSQL 数据存储的可扩展性以及传统RDBMS的易用性。它用同步重复来达到高可用性以及对数据的一致视图。简言之，它对“有足够低下延迟性的远距离复制”提供了一个完全序列化的ACID语法以支持交互应用。 我们通过RDBMS以及NoSQL的折衷，进行设计以达致前述需求：我们对数据存储进行分区并且各自复制了其分区，就分区提供了完全的ACID语法，但在其上仅有受限的一致性保证（limited consistency guarantees）。我们提供了传统的数据库特性，诸如二级索引(译注：参见扩展存储引擎)，但仅仅有那些“可以在用户可以忍受范围内的，并在延迟性限制内的”特性，并且仅支持我们的分区模式可以支持的语法。我们主张从大多数因特网服务而来的数据可以被适当的分区（诸如，用户），从而使该种方法可行，并且一个小的，但是并不简短精炼的特性集可以极大的减缓开发云应用的负担。
与传统智慧形成一个对照的是品【参见：分布式事物处理之外的生活：一个特例独行的观点，垂直 paxos 以及 主要备份复制】，我们可以使用Paxos 【参见：兼职的议会】来构建一高可用性系统，该系统就“地理分布远距离数据中心的同步复制写交互应用”提供了可信的潜在因素。虽然许多系统使用Paxos仅仅用于锁，主线程选择（master election），或者元数据复制以及配置（Congurations），我们相信Megastore 是用Paxos 的最大系统部署，在数据中心之间的每次写时复制主用户数据。Megastore 在谷歌中已近广泛的应用了数年【 参见20 】。它控制了多于30亿写以及200亿的每日读事务以及在全球数据中心上存储了大约拍字节的主数据（primary data）。
该文献的核心贡献是以下三点：
数据模型的设计，以及允许进行快速开发的、“从构建开始就具有高可用性与扩展性的”交互应用的存储系统；
Paxos 复制的实现以及就地理分布的数据中心低延迟性操作之一致算法优化，从而对系统提供高可用性；
就我们在谷歌内大规模部署Megastore 的经验给出的报告。
该文献以下述形式组织。第二节描述了Megastore 如何通过“使用分区和证明我们对许多网络交互应用的设计之充分性”来提供可用性以及扩展性。第三节提供了一个Megastore的数据模型以及特性的全局概览。第四节详细解释了复制算法，并就它们实际执行性能如何给出测量方式。第五节总结了我们开发该系统的经验。在第六节我们将回顾相关的工作。第七节进行总结。
2.面向可用性及扩展性 （TOWARD AVAILABILITY AND SCALE）
和我们需要的存储系统平台的全局性，可靠性以及规模上任意大的特性形成对比的是，我们的硬件构建块缺失地理意义上受限制的，易于出错的，且必然是能力受限的。我们必须将这些组件绑定到一个统一的全体，该全体提供将提供更高的吞吐量以及可靠性。
为了做到这一点，我们采取了双管齐下的方法（two-pronged approach）：
就可用性（availability），我们实现了一同步的，容错的“就远距离连接进行优化了的”日志复制器；
就规模（scale）而言，我们将数据分区到有巨大空间的小数据库集之中（a vast space of small databases），其中每个都有自己的复制日志存储于NoSQL数据存储的每一复制（each with its own replicated log stored in a per-replica NoSQL datastore）。
2.1 复制（Replication）
在单一数据中心的诸多主机上的复制数据通过“克服特定主机失败（host-specic failures）”提升了可用性，但这种提升效果却是递减的（but with diminishing returns）。我们仍旧必须面对外部世界互联的网络以及其驱动，把控网络的基础设施架构（infrastructure）。很节俭的构建出来的站点冒着一定级别的广泛设施中断供应（facility-wide outages ）的危险【参见：数据中心作为计算机： 数据仓库级别的机器之设计介绍】，并在地域性灾难面前是脆弱不堪的。就云存储而言，为了达致可用性要求，服务提供商必须在全球地理范围内复制数据。
2.1.1 策略（Strategies）
我们就大范围复制对通用策略进行了评估：
异步主从（Asynchronous Master/Slave） 主节点复制预写式（write-ahead）日志条目到至少一个从节点（slave）。附加日志在并行传输到从节点的主节点是被确认的。主节点可以支持快速的ACID事务，但却要在从节点的故障切换时（failover）冒时间下降或数据丢失的风险。从而需要一个一致性协议在主机间进行协调（A consensus protocol is required to mediate mastership）。
同步主从（Synchronous Master/Slave）一个主节点将在应答从节点前等待，直至改变被反映到从节点中，从而允许无数据丢失的故障恢复。主节点和从节点失效需要外部系统及时的侦测到。
优化复制（Optimistic Replication）一均匀复制组的任何成员可以接受变异（mutations）【参见：23】，且在组内以异步方式进行传播。可用性和延时性（latency）是极好的。然而，全局突变排序（the global mutation ordering）在commit时的时间是不可知的，故事务（transactions）是不可能的。
我们避免这种“在宕机时会引起数据丢失的”策略，大规模系统通常有该缺陷。我们同样还丢弃了不许可ACID原子事务操作的策略。尽管对最终一致性系统（eventually consistent systems）有操作优势，目前在快速应用开发中放弃“读-修改-写”这种特色，还是太困难。我们同样丢弃了重量级主机（heavyweight master）的操作。故障恢复需要的一系列高延迟性阶段（high-latency stages）,常常会导致用户可见的中断供应（outage），并还常伴随巨大数量的复杂性。如果我们可以在所有主机（masters）间进行区分，那又何必将容错系统构建为仲裁成员以及故障切换工作流呢？
2.1.2 进入Paxos（Enter Paxos）
我们决定使用Paxos， 其是一个经过证明了，并优化了的，容错的，无需区分主机的一致性算法【参见:工程师视角的Paxos构造，兼职的议会】。我们在一组对称的对等节点上复制了预写式日志。任何节点可以初始化读以及写。各日志附加了一个从主要复制（a majority of replicas）而来的应答块，且该复制在少数情况下会被缠住（in the minority catch up），就好象它们能使算法的内在容错性质排除对显著的宕机状态（“failed” state）的需要。一个就Paxos的新特性，将详细在4.4.1节中描述，允许在任何实时复制时进行本地复制。另一个扩展允许允许单程写（single-roundtrip writes ）。
即便Paxos拥有容错能力， 但使用单一日志仍然是有限制的。将备份遍布在广域范围内（With replicas spread over a wide are），通讯延迟性将限制总体上的吞吐量（communication latencies limit overall throughput），而且，当目前没有备份或者对写的应答的主要失效时（majority fail to acknowledge writes），前进的步伐被限制住了。在传统的把控成千上万用户的SQL数据库主机上，使用一个异步的复制日志（a synchronously replicated log）会冒大范围中断影响的风险【参见：大范围同步复制数据库的性能】。所以为了提升可用性以及吞吐量，我们使用多复制日志（multiple replicated logs），其中每一个都把控“数据集中自己的分区”。
zz from：http://blog.csdn.net/AE86_FC/archive/2010/08/08/5796640.aspx
（说明：Pregel的名字来历很有意思。是为了纪念欧拉的七桥问题[7]，七座桥就位于Pregel这条河上。）
Abstract
许多实际应用问题中都涉及到大型的图算法。比如网页链接关系和社会关系图等。这些图都有相同的特点：规模超大，常常达到数十亿的顶点和上万亿的边。这么大的规模，给需要在其上进行高效计算的应用提出了巨大的难题。在这篇论文中，我们将提出一种适合处理这类问题的计算模式。将程序用一系列的迭代来描述(Programs are expressed as a sequence of iterations)，在每一次迭代中，每一个顶点都能接收来自上一次迭代的信息，并将这些信息传送给下一个顶点，并在此过程中修改其自身的状态信息，以该顶点为起点的出边的状态信息，或改变整个图的拓扑结构。这种面向顶点的方法足够的灵活，可以用来描述一系列的算法。这种计算模式被设计的足够高效，可扩展，和足够的容错，并在有上千台的计算节点的集群中得以实现。这种模式中隐式的同步性(implied synchronicity)使得它对程序的确认变得简单。分布式相关的细节已经被一组抽象的API给隐藏。而展现给人们的仅仅是一个表现力很强，很容易编程的大型图算法处理的计算框架。
Keywords
分布式计算，图算法
1．Introducetion
Internet使得Web graph成为一个人们争相分析和研究的热门对象。Web 2.0更是将对社会关系网的关注推向高潮。同时还有其他的大型图对象（如交通路线图，报纸文献，疾病爆发路径，以及科学研究的发表文章中的引用关系等），也已经被研究了很多年了。同时也有了许多相应的应用算法，如最短路径算法，page rank理论演变而来的图相关算法等等。同时还有许多其他的图计算问题也有着相当的实际价值，如最小切割，以及连通分支等相关问题。
事实证明，高效的处理大型图对象的计算是一件极具挑战性的事情。图算法常常暴露出类似不高效的本地内存访问，针对每个顶点的处理过少，以及在计算过程中改变并行度等问题。分布式的介入更是加剧了locality的问题，并且加剧了在计算过程中机器发生故障而影响计算的可能性。尽管大型图形无处不在，其商业应用也非常普及，但是一种通用的，适合各种图算法的大型分布式环境的实现到目前还不存在。
要实现一种大型图计算的算法通常意味着要在以下几点中作出选择:
zz from：http://bbs.sciencenet.cn/home.php?mod=space&uid=449420&do=blog&id=480749
【原题】Dynamo: Amazon’s Highly Available Key-value Store
【译文】发电机：亚马逊的高可用键值对存储
Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati,
zz from：http://www.dbthink.com/?p=372
By Avinash Lakshman Facebook ,Prashant Malik Facebook; Translated By Jametong
本文翻译自Facebook员工在LADIS大会上发布的论文.Cassandra – A Decentralized Structured Storage System
这篇论文中,两位作者详细介绍了Cassandra的系统架构,它的设计初衷,设计应用时使用到的相关技术,以及设计/实现/使用过程中得到的经验教训.
SQL解析
http://www.cnblogs.com/RicCC/archive/2008/03/09/OQL-ANTLR-SQL-Parser.html ANTLR实现的SQL解析器 – OQL
http://packages.python.org/sqlparse/ python sqlparser
http://www.cppblog.com/woaidongmao/archive/2008/11/22/67588.aspx 用Lex和Yacc做一个简单的SQL解释器
http://foja.dcs.fmph.uniba.sk/kompilatory/docs/compiler.pdf Compiler Construction using Flex and Bison
zz from：http://blog.csdn.net/wh62592855/archive/2011/05/17/6427766.aspx
【原文】 Hive – A Petabyte Scale Data Warehouse Using Hadoop
【作者】 Facebook 数据架构组 ： Ashish Thusoo, Joydeep Sen Sarma, Namit Jain, Zheng Shao, Prasad Chakka, Ning Zhang, Suresh Antony, Hao Liu and Raghotham Murthy
作者：Mike Burrows Google Inc 2006
译者：phylips@bmy 2011-7-2
出处：http://duanple.blog.163.com/blog/static/7097176720112643946178/
摘要
本文描述了我们在Chubby锁服务系统上的相关经验。该系统旨在为松散耦合的分布式系统提供粗粒度的锁以及可靠性存储(低容量的)。Chubby提供了一个非常类似于具有建议性锁的分布式文件系统的接口，设计的侧重点在可用性及可靠性而不是高性能。该服务已有很多应用多年的运行实例，其中一些实例可能同时为成千上万个客户端提供服务。本论文描述了其最初的设计及期望的应用，并通过将其与实际应用情况进行对比，来说明设计应如何修正以容纳各种差异。
英文原文：http://infolab.stanford.edu/~backrub/google.html
中文版：http://leoncom.org/?p=650350
【摘要】 这篇文章中，我们介绍了google，它是一个大型的搜索引擎的原型，搜索引擎在超文本中应用广泛。Google的设计能够高效地抓网页并建立索引，它的查询结果比其它现有系统都高明。这个原型的全文和超连接的数据库至少包含24000000个网页。我们可以从http://google.stanford.edu/ 下载。设计搜索引擎是一项富有挑战性的工作。搜索引擎为上亿个网页建立索引，其中包含大量迥然不同的词汇。而且每天要回答成千上万个查询。在网络中，尽管大型搜索引擎非常重要，但是学术界却很少研究它。此外由于技术的快速发展和网页的大量增加，现在建立一个搜索引擎和三年前完全不同。本文详细介绍了我们的大型搜索引擎，据我们所知，在公开发表的论文中，这是第一篇描述地如此详细。除了把传统数据搜索技术应用到如此大量级网页中所遇到的问题，还有许多新的技术挑战，包括应用超文本中的附加信息改进搜索结果。本文将解决这个问题，描述如何运用超文本中的附加信息，建立一个大型实用系统。任何人都可以在网上随意发布信息，如何有效地处理这些无组织的超文本集合，也是本文要关注的问题。
作者：Cary G.Gray and David R. Cheriton 1989
译者：phylips@bmy 2011-5-7
出处：http://duanple.blog.163.com/blog/static/70971767201141111440789/
[
序：所谓租约(leases)，其实就是一个合同，即服务端给予客户端在一定期限内可以控制修改操作的权力。如果服务端要修改数据，首先要征求拥有这块数据的租约的客户端的同意，之后才可以修改。客户端从服务端读取数据时往往就同时获取租约，在租约期限内，如果没有收到服务端的修改请求，就可以保证当前缓存中的内容就是最新的。如果在租约期限内收到了修改数据的请求并且同意了，就需要清空缓存。在租约过期以后，客户端如果还要从缓存读取数据，就必须重新获取租约，我们称这个操作为“续约”{!引用自<<租约机制简介>>}。租约是一个很形象的叫法。虽然最初租约是被用于解决分布式文件缓存的一致性，随着时间的推移，该机制逐步被应用于更多的场景下，比如在GFS，Chubby中都可以看到它的应用，当然这也是翻译本文的重要原因，为深入理解GFS，chubby，租约是一个基础。关于整个租约机制的更多介绍及扩展可以通过译考文献1租约机制简介得到更多信息。本文只是提出租约机制的最初的那篇论文的内容。
1、Load Balancer
该模式中，一个分发器基于某种策略确定由哪个worker实例处理请求。应用最好是无状态的，以使任何一个worker实例都能同等处理请求。大量的网站都会用到负载均衡器这个模式的。
from：http://www.infoq.com/cn/articles/scalability-principles
作者 Simon Brown 译者 王丽娟 发布于 2008年7月25日 下午8时25分
从最简单的水平来看，可伸缩性就是做更多的事情。更多的事情可以是响应更多的用户请求，执行更多的工作，或处理更多的数据。设计软件这件事本身是复杂的，而让软件做更多的工作也有其特有的问题。这篇文章针对构建可伸缩软件系统提出了一些原则和方针。
看多了正面文章，今天看一篇负面批评吧，在MapReduce几乎已经成为大中型NoSQL产品标配的今天，如果有人说MapReduce完全是个垃圾，估计有很多人要受不了了。下面的一篇文章是一些RDBMS系统的大牛人从多个方面对MapReduce的批评，不妨一看。
zz from：http://pt.alibaba-inc.com/wp/dev_related_728/brewers-cap-theorem.html
英文版：http://www.julianbrowne.com/article/viewer/brewers-cap-theorem
Amazon和EBay一直在喝的酷爱(kool aid)饮料。
by Julian Browne on 2009.1.11 （经Julian授权翻译此文，原文参见）
1976年6月4号，周5，在远离音乐会大厅的一个楼上的房间内，在位于Manchester的Lesser Free Trade Hall，Sex Pistols乐队（注：Sex Pistols的经理人Malcolm McLaren 2010.4.8去世）开始了他们的第一次演出（gig，注：规模太小称不上演唱会）。关于当晚谁出席了那场演出有些混乱，部分是因为6周后的另一场音乐会，但最主要的还是因为，这场演出被认为是永久改变西方音乐文化的一场演出。这场演出是如此的重要且富有象征意义，以至于David Nolan写了一本书：《我发誓我在那里：那场改变了世界的演出》，对那些声称自己看过那场演出的人做出判断。因为6月4号被认为是punk摇滚的开始。
Werner Vogels on December 23, 2008
http://www.allthingsdistributed.com/2008/12/eventually_consistent.html
这篇文章是Werner Vogel在2008年发布在ACM Queue上的一篇数据库方面的重要文章，阐述了NoSQL数据库的理论基石－－最终一致性，对传统的关系型数据库（ACID，Transaction）做了较好的补充。国内已有很多相关方面的介绍，比如InfoQ在2009年的介绍，但基本没有完整翻译的版本。在这里做一个完整的翻译，供初学者参考。
zz from：http://www.oschina.net/news/15813/hadoop-mapreduce?from=rss
最近雅虎开发者博客发了一篇介绍Hadoop重构计划的文章。因为他们发现当集群的规模达到4000台机器的时候，Hadoop遭遇到扩展性的瓶颈，目前他们正准备开始对Hadoop进行重构。