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.  概念远比当前的一些技术和标准重要。

挪威的森林(电影)

‘五一’看完了电影的挪威的森林,很早就看过了林少华2001  年版本的《挪威的森林》,一直为其感动,但过了很久之后总觉得书中有种阴郁和黑暗的部分在影响着我,居然有些害怕了,虽然之后很多时候都有空想再看看,都不敢再拿起。这两天无聊之时在豆瓣看到有了电影,评分不高5.7 ,但又有什么关系呢,我看电影更多的是希望看别人是如何理解电影的,能从中看到我看不到的一些内容。下了电影之后居然发现有两个版本,一个是133 分钟的,和豆瓣上长度以及字幕都匹配,还有一个是两个半小时的(记得很清楚这个版本有渡边君室友伴着音乐跳操的场景)。就配着字幕看了第一个版本。看完之后并没有看过书后那样怦然心动的感觉,内容和情愫依旧那么熟悉。

首先要感谢导演找了一个好直子:菊地凛子,她是那么美,完全改过了绿子和初美,以至于我都认为绿子和初美的选择是有问题的。菊地凛子的表演也是完美的,不做作也不隐藏,将直子失去木月的绝望、依赖着渡边君的甜蜜和矛盾、以及心灵深处最撤人心动的忧郁表现的淋漓尽致,对于这样的直子又还能有什么要求呢?其次要感谢导演选择了那么美的画面,从开场木月直子渡边三人共处的原野到直子调养的疗养院,从精心布置的绿子的阳台到透明墙壁的游泳馆,美的让我怀疑这是战后才二十二年的日本。最后要感谢导演选择了一个挺不错的男一号,没有英俊的掉渣,也没有俗气的掉粉,比较符合我心中安静、冷静却不懂得安慰女生的渡边君。说完电影的好就要吐槽下我的不满了,毕竟电影还是有很多令我不满的:

  1. 首先是演员,绿子的言语、神态和动作完全没有把书中的绿子描绘出来,唯一能够感到贴切的就是复制了书中的话;电影中初美和我印象中的初美长相差距有些大,这点不好评价,毕竟每个人心中都有自己的初美;永泽涂有其表,从演员的长相来看导演是花心思来找的人,但是从行为和言语无不看出演员的做作,从永泽把渡边的书扔到垃圾筒到渡边在阳台问永泽为什么这样对初美时永泽的反应。
  2. 导演对原著细节的取舍上有意见,很多原著中的场景都没有在电影中得以体现。绿子在贵族学校有趣的生活被忽视;直子几个亲人的离去电影中也没涉及;没有提及永泽活吞鼻涕虫、通过外务省考试还在学西班牙语的细节,永泽偏执、无情的性格难以体现;渡边送初美回家内容所剩无几。
  3. 配乐上,最直子死时以及渡边在海边旅行的配乐严重反对。
  4. 最终也是最重要的,导演没有还原原著的核心内容,而是简单的将其拍成一部爱情故事了。

排除绿子和直子亲属的死亡影响,对于直子之死我是这样理解的:

直子和木月从小生活在一起,木月几乎是直子与外界世界的唯一出口,而这出口的很大一部分也是伴随着和渡边君的,所以直子在失去木月之后渡边很自然的成为直子的唯一依靠。如果说直子对木月的情感是爱的话,那么从直子的角度来看她不可能在找到和木月一样经历的男生来代替,渡边也是一样,所以在电影中渡边在问直子是不是不爱他,直子没有说自己是不是爱渡边,因为完美主义的直子在不知道对渡边的感情是不是爱的时候,不会告诉自己爱的就是渡边,而只是告诉了渡边她与木月的感情是非常特殊的。

当木月走后的一年中我们不知道直子是如何度过的,但我们完全和可以想想的出来,她封闭了自己,不与他人交往,独自守卫着木月;同时她也是疑惑和痛苦的,疑惑木月为什么会抛弃自己而去,痛苦最心爱的人离自己而去,却要自己的受折磨般地生活在人世。而这些并不足以将直子推向精神分裂以及崩溃的边缘,这也是直子为什么在木月自杀后那么久都没有去疗养院,而当她和渡边那么短时间就不行了,因为直子对木月的爱是长久的,对渡边的爱是深刻的。

当直子在东京第一和渡边相遇时,两人都是慌张无措的,没有人知道应该做些什么,只是一直一前一后的散步,以至于散步都成为两人的习惯。而封闭已久的直子第一次找到了可以分担、交流感情的人,虽然这种分担和交流几乎是无言的,但却给了直子极大的慰藉,而这种情愫在直子20 岁生日发展到了最高点。鲁莽的渡边在提到木月后,直子的心理产生了第一次强烈的对抗,一方面是完美主义的直子守卫着的木月,一方面是将自己自己第一次给了渡边,并心向所属的背判,两者的纠结使得直子精神上无法接收从而住进了疗养院。

在疗养院的直子之后一直都没有走出木月和渡边、过去和现在的纠葛,这种纠葛不断激化加剧最终将直子带向了死亡。渡边在直子住进疗养院后一共去看过直子三回,每一次都让直子感觉到自己对渡边的依赖和感情在不断加剧,同时也使得她认为自己对木月的背叛在加深。直子体会到了与渡边一起时的快乐和幸福,这种快乐幸福并不亚于与之前同木月一起的快乐幸福。她会为渡边做与为木月一样的事情。她与渡边在一起的快乐和幸福她渴望拥有却在渡边走后、夜深人静独自一人时害怕拥有。

第三次渡边去直子那里的时候,告诉了直子他将在学校外面新租一间房,希望直子能和他一起生活。这对于直子来说恐怕是最大最大的幸福了,能够和自己爱的人相互慰藉依靠生活,该是多么美好和渴望的一件事啊,但是善良、完美的直子始终还是摆脱不了木月的纠葛。在幸福即将降临之时,却也是内心最不平静的时候,直子开始出现幻听、幻觉,是心中的那个木月出来告诉直子不能抛弃她而去。最终直子在这样的纠葛中离去。不能说直子的自杀是为木月的选择,也有人说直子是在幻觉、幻听中被自杀的也有些不合适,我觉得也不完全是对渡边的爱和与木月之间持久的情感使得直子自杀。最终善良、单纯、完美、忧郁的直子是被善良、单纯、完美、忧郁的直子所杀。

Web caching with consistent hashing 一致性哈希Web 缓存

读这篇文章源自于一致性哈希的开山之作:Consistent hashing and random trees: Distributed caching protocol for relieving hot spots on World Wide Web。在STOC 上下了原文后觉得估计得花和The part-time parliament 差不多时间来读吧,以后有必要深入学习再看吧!一致性哈希Web 缓存是与开山之作同一作者David Karger 1999年所写 。

STOC 会议上有许多经典的算法,但很多有晦涩难看懂没有引起大家的注意,直到某个采用了该算法的应用得到大家的认可,该算法才得以为大家所接受。分布式一致性Paxos 算法也是这样。(下面左图是consistent hash 开山作引用情况,右边是The part-time parliament 每年引用量,可见在这些牛文在引用量巅峰期之前都有几年的沉寂期,来自CiteSeerX)

conshashing  paxos

言归正传:

problem

congested network and swmaped servers 集中式缓存存在问题

related work

cooperating cache 将缓存复制到不同的机器,存在数据复制和副本一致性问题

hashing 缓存通过哈希保存到不同机器上,存在扩展性以及churn 问题:当一个节点失效或新增一个节点会导致大量失效和缓存的迁移,比如 7×i+4 mod 24 到 7×i+4 mod 23

our work

浏览器上添加哈希函数,将URL 资源定向到动态变化的可用缓存,无副本且减少失效率

consistent hashing

假设有n 个缓存节点,根据其哈希结果使用二叉树进行组织

our system

组成:1.actual cache system  2.user’ browsers   3.domain name server

浏览器对URL 进行哈希得到虚拟地址,返回给DNS 服务器

DNS 服务器通过客户端的虚拟地址查到到对应的缓存节点物理地址IP

缓存节点从原始Web 服务器取数据并保存一份副本,可相应浏览器请求

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 赞助