Dynamo: Amazon’s highly available key-value store

原文  中文翻译  参考:Kai – An Open Source Implementation of Amazon’s Dynamo

本文一直为分布式key-value 存储系统以及分布式存储的业内人士所推崇,个人觉得有两个原因:

  1. 分布式key-value 存储近年发展迅速。Dynamo 更是集成了近些年最新的技术如:DHT(分布式哈希表)、consistent hashing(一致性哈希)、多版本、副本策略和Merkle tree 等。
  2. 文章从设计、实施者的角度分析了分布式key-value 存储在实践中的问题和解决方法,并总结了Dynamo 在实现、配置等方面的经验与教训,对后来者非常有借鉴意义。

继续阅读

来自dirkmeister 关于存储系统的总结

原文:http://dirkmeister.blogspot.com/2010/01/storage-systems-course-my-own-idea.html 需翻墙

 

我上一篇文章总结了国际顶级学校及其存储系统实验室的一些存储课程。

在这篇文章中,我将提取我自己对存储课程的一些观点和想法并组织起来。我假设有个15 周的课程并且每周有1 个半小时讲演(就像我们在德国):

引言,概述,磁盘驱动器结构

Material: Ruemmler, Wilkes An introduction to disk drive modeling

  1. Disk Scheduling / SSD 磁盘调度/固态硬盘
    Material: Iyer, Druschel. Anticipatory scheduling: A disk scheduling framework to overcome deceptive idleness in synchronous I/O, Agrawal et al. Design Tradeoffs for SSD Performance
  2. RAID  冗余磁盘整列
    Material: Patterson et al. Introduction to Redundant Arrays of Inexpensive Disk (RAID), Corbett. Row-Diagonal Parity for Double Disk Failure Correction
  3. Local File Systems  本地文件系统
  4. Local File System Case Studies: ext3, btrfs
    Material: Valerie Aurora. A short history of btrfs, Card et al. Design and Implementation of the Second Extended Filesystem
  5. Local File Structures (Sequential, Hashing, B-Tree)  本地文件结构
    Material: Comer. The Ubiquitous B-Tree
  6. SAN / NAS / Object-based Storage
    Material: Sacks. Demystifying DAS, SAN, NAS, NAS Gateways, Fibre Channel, and iSCSI
  7. Examples: NFS, Ceph, GoogleFS/Hadoop DFS
    Material: Weil. Ceph, A scalable, high-performance distributed file system, Ghemawat et al. The Google File System
  8. Snapshots and Log-based Storage Designs  快照和基于日志存储设计
    Material: Brinkmann, Effert. Snapshots and Continuous Data Replication in Cluster Storage Environments, Hitz et al.File System Design for an NFS File Server Appliance, Rosenblum, Ousterhout. The Design and Implementation of a Log-Structured File System
  9. Fault Tolerance, Journaling, and Soft Updates 容错,日志和软件升级
    Material: Prabhakaran et al. Analysis and Evolution of Journaling File Systems, Seltzer et al. Journaling Versus Soft Updates: Asynchronous Meta-data Protection in File Systems
  10. Advanced Hashing: Consistent Hashing, Share, and Crush
    Material: Karger et al. Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web, Weil et al. CRUSH: controlled, scalable, decentralized placement of replicated data
  11. Caching, Replication  缓存,副本管理
    Material: Nelson et al. Caching in the Sprite network file system, Kistler et al. Disconnected operation in the Coda File System
  12. Consistency, Availability, and Partition Tolerance  一致性,可用性和分区容忍性
    Material: DeCandia et al. Dynamo: Amazon’s Highly Available Key-value Store, Helland, Life beyond Distributed Transaction: An Apostate’s Opinion
  13. Data Deduplication  重复数据删除
    Material: Muthitacharoen et al., A Low-bandwidth Network File System, Douglis, Iyengar. Application-specific Delta-encoding via Resemblance Detection
  14. Performance Analysis  新能分析
    Material: Traeger, A nine year study of file system and storage benchmarking (at least parts of it)

我推荐的一些书:

对于我来说,有些关键点非常重要:

  • To clearly separate between classes of file systems and a concrete example. The best example is the class of network file systems vs. NFS. At the end there should be no much question if something is an inherent property of a class of file systems or of the concrete implementation  能清楚的分辨不同类型文件系统和具体的例子。最好的例子就是网络文件系统类和NFS。最后应该对某个东西是某类文件系统的相关性质还是具体应用不存在疑问
  • To have enough time to handle the basic concepts independently from concrete usages. For example explaining B-Trees as an important file structures independent from the usage in e.g. BTRFS.    独立于具体应用,花足够的时间掌握基本概念。比如解释B-树是一个重要的文件结构,独立于比如在BTRFS 中的使用
  • The concepts are more important than the current technology or standards.  概念远比当前的一些技术和标准重要。

Consistent hashing 的python 实现

部分代码参考之前的“写一个分布式存储系统有多简单?”,保持数据服务器端不变,修改客户端节点选择方式即可。

修改:1、添加HashRing 类,进行一致性哈希环的管理,保存在客户端client ,因此节点/数据服务器端可以不做任何修改(添加hello 测试)。2、客户端修改节点选择方式,使用consistent hashing。

接受一致性哈希的国内的也比较多了,可以参考这里

继续阅读

常见key-value 存储系统

Berkeley DB

1991 年,软件库可构建嵌入式key-value 数据库,C 语言,被MySQL使用。

memcached

2003 年,分布式全内存数据库,C 语言,使用网站:YouTubeRedditFacebook,和Twitter

BigtableHbase

2004 年、2007年,基于DFS 的NoSQL 数据库,Java 语言,2010 年Facebook 开始使用Hbase

Hypertable

2009 年,灵感来自Google Bigtable,C++,百度

Cassandra

2008 年,key-value 数据库,Java 语言,Facebook 开发

couchDB

2005 年,使用JSON 保存数据的NoSQL 数据库,Erlang 语言,IBM 开发

Dynamo

2007 年SOSP 论文,结构key-value 存储,Java 语言(未开源),Amazon S3 使用

MongoDB

2009年,面向文档的数据库系统,C++ 语言,使用网站:SourceForgeThe New York Times

Redis

2009年,类似但优于memcached、基于内存、优化耐久性key-value 数据库,C 语言,VMware 赞助

SSD 并行的性能影响

原文: Performance Impact and Interplay of SSD Parallelism through Advanced Commands, Allocation Strategy and Data Granularity

文章是胡杨博士在2011 ICS 上发表的,通过他的模拟软件SSDsim 对SSD 的并行和高级命令(advanced commands)的分析得出了一些SSD 设计实现上的建议.之前都苦于没有SSD 比较详细的综述,于是自己凑了和了一篇(之前写过的综述),而这篇文章则似乎更适合作SSD 的综述,讲的很清晰。

Idea

通过多层次的SSD 仿真器SSDsim 分析了SSD 内部影响性能的因素(并行)。

总结

  1. large pages 在许多情况下对SSD 有比较大的负面影响
    1. 越大的pages 更易导致数据的迁移
  2. 不同physical-page allocation 可应用于不同环境中,对任意工作负载都会有一个最优方案
    1. Static allocation 读性能在所有情况下最优
  3. 高级命令在一些情况下能够改进SSD 性能,但是用不当会适得其反
    1. 使用高级命令必须带有约束条件才能够提升性能
  4. SSD 四种并行:channel 层、chip 层、die 层和plane 层并行,它们优先级对性能有影响并和2、3中physical-page allocation 与高级命令相互作用、影响。
    1. 并行的优先顺序应该为:1、channel-level  2、chip-level  3、die-level  4、plane-level

微软云存储架构(Azure Cloud Storage)

原文:Windows Azure Storage: A Highly Available Cloud Storage Service with Strong Consistency

 

IDEA

A cloud storage system that provides customers the ability to store seemingly limitless amounts of data with high availablity and strong consistency. 为用户提供高可用、高一致性并近乎无限空间的云存储。

 

System characteristics 系统特点:

  1. High availablity and strong consistency 高可用性和强一致性
  2. Global and scalable namespace/storage 全局可扩展的名字空间、存储
  3. Multiple data abstractions from a single stack 支持多种类型的数据
  4. Automatic load balancing 自动负载均衡
  5. Range Partition vs Hashing 使用动态区域划分,而没采用哈希
  6. Append-only system 存储系统只有append 操作。
  7. End-to-end checksum 端到端的校验和
  8. Separate log file per RangePartition 日志文件粒度为RangePartition

高可用通过多副本策略实现(默认三个),数据写入的原子性操作保证强一致性。Azure 支持blob(数据块)、Table(structured storage)和Queues(消息队列)三类数据。所有数据都是以添加的方式写入的。

继续阅读