+2
0

分布式知识的总结(V1.0)

longhao 发表于 2012年09月15日 16:32 | Hits: 11060
Tag: Java | Web Service | acid | base | cap | 分布式

1:分布式理论

CAP(Eric Brewer)
    Web服务无法同时满足以下3个属性
  • Consistency(一致性),数据一致更新,所有数据变动都是同步的
  • Availability(可用性),每个操作都必须以可预期的响应结束
  • Partition tolerance(分区容错性),即使出现单个组件无法可用,操作依然可以完成
    在任何数据库设计中,一个Web应用至多只能同时支持上面的两个属性,不可能三者兼顾。对于分布式系统来说,分区容错是基本要求,所以必然要放弃一致性。对于大型网站来说, 分区容错和可用性的要求更高,所以一般都会选择适当放弃一致性。对应CAP理论,NoSQL追求的是AP,而传统数据库追求的是CA,这也可以解释为什么 传统数据库的扩展能力有限的原因。

ACID解决方案
    ACID数据库事务极大地简化了应用开发人员的工作.正如其缩写标识所示,ACID事务提供以下几种保证:

  • Atomicity(原子性),事务中的所有操作,要么全部成功,要么全部不做.
  • Consistency(一致性)在事务开始与结束时,数据库处于一致状态.
  • Isolation(隔离性) 事务如同只有这一个操作在被数据库所执行一样.
  • Durability(持久性). 在事务结束时,此操作将不可逆转.(也就是只要事务提交,系统将保证数据不会丢失,即使出现系统Crash,译者补充).
    数据库厂商在很久以前就认识到数据库分区的必要性,并引入了一种称为2PC(两阶段提交)的技术来提供跨越多个数据库实例的ACID保证

BASE解决方案

  • Basically Available(基本可用)
  • Soft-state( 软状态/柔性事务)
  • Eventual Consistency(最终一致性)
    BASE模型是传统ACID模型的反面,不同与ACID,BASE强调牺牲高一致性,从而获得可用性,数据允许在一段时间内的不一致,只要保证最终一致就可以了。
 

2:分布式系统基础组件

RPC

message queue

failure detection

  • “The φ Accrual Failure Detector”

分布式系统中的一致性

  • "Principles of Computer Systems Design" 第十章(可以到MIT 网站下载)
  • 虚拟同步(virtual synchrony)系统
    • K.P. Birman 的两篇论文,讲述虚拟同步的概念的实现方法
      • Reliable Communication in the Presence of Failures
      • Exploiting virtual synchrony in distributed systems
    • 扩展的虚拟同步(Extended Virtual Synchrony),也称为 TOTEM 协议
      • Y. Amir 等,"The Totem Single Ring Ordering and Membership Protocol"
      • L.E. Moser 等,"Extended Virtual Synchrony"
    • Corosync 是 TOTEM 协议的一个开源实现,当前 RedHat 等提供的企业集群使用它作为一致性协议。
  • 采用类似 Paxos 算法的系统
    • Leslie Lamport, "Paxos Made Simple"
    • "Paxos Made Live – An Engineering Perspective" Google 实现 Paxos 算法时的工程考虑。
    • Zookeeper,两篇介绍 ZooKeeper 的论文
      • ZooKeeper: Wait-free coordination for Internet-scale systems
      • A simple totally ordered broadcast protocol
    • Google 的 Chubby,"The Chubby lock service for loosely-coupled distributed systems"
  • 最终一致性
    • 最终一致性概念
    • Cassandra 中最终一致性的应用
      • 基于 Gossip 协议的组成员管理,论文 "Efficient Reconciliation and Flow Control for Anti-Entropy Protocols"
      • 基于 Merkle tree 的数据同步算法:“Informed content delivery across adaptive overlay networks”
  • CAP 理论
  • BASE 理论 http://queue.acm.org/detail.cfm?id=1394128

3:分布式数据库和分布式文件系统

Google File System

MooseFS

Ceph

Dynamo

  • 论文 "Dynamo: Amazon’s Highly Available Key-value Store"

Big Table

Cassandra

Parallel Database

  • Yahoo! PNUTS 论文 "PNUTS: Yahoo!’s Hosted Data Serving Platform"
  • GreenPlum 并行数据库,私有软件,非开源
  • HadoopDB,论文 "HadoopDB: An Architectural Hybrid of MapReduce and DBMS Technologies for Analytical Workloads"

分布式数据库对比

论文 "Benchmarking Cloud Serving Systems with YCSB"

4:大规模数据处理

  • MapReduce
  • Hive, Pig
    • Hive 论文 "Hive – A Petabyte Scale Data Warehouse Using Hadoop"
    • Pig 论文 "Pig Latin: A Not-So-Foreign Language for Data Processing"
  • search engine (Lucene)

5:关系数据库

  • 数据库设计与实现基本理论
    • Book "Database System Implementation"
  • transaction processing
    • Book "Transaction Processing: Concepts and Techniques"
    • Book "Principles of Transaction Processing, Second Edition"
  • 性能优化
    • Book "High Performance MySQL"
    • Book "Physical Database Design"
  • SQLite 代码分析
  • PostgreSQL

6:分布式系统理论研究

    这几本书里面,"distributed algorithms" 比较偏重纯理论,与实际技术相关性不大,阅读优先级较低;"distributed systems: principles and paradigms" 讲了不少实际系统,但是讲的不是很深入(也很难讲深入),初学者可以先浏览一遍;"Principles of computer systems design: an introduction" 是一本新书,对系统设计的很多思想讲的很透彻清晰,优先级较高。

  • Lynch's book "distributed algorithms"
  • Tanenbaum's book "distributed systems: principles and paradigms"
  • "Principles of computer systems design: an introduction"
  • CAP theorem paper, "Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services"

7:值得读的博客
 

原文链接: http://www.longtask.com/blog/?p=761

0     +2

我要给这篇文章打分:

可以不填写评论, 而只是打分. 如果发表评论, 你可以给的分值是-5到+5, 否则, 你只能评-1, +1两种分数. 你的评论可能需要审核.

评价列表(2)

  • +1 guest voted at 2012-09-24 17:40:04

  • +1 guest voted at 2012-10-09 10:07:47