IT牛人博客聚合

Google文件系统（Google File System，GFS）是构建在廉价的服务器之上的大型分布式系统。它将服务器故障视为正常现象，通过软件的方式自动容错，在保证系统可靠性和可用性的同时，大大减少了系统的成本。

GFS是Google云存储的基石，其它存储系统，如Google Bigtable，Google Megastore，Google Percolator均直接或者间接地构建在GFS之上。另外，Google大规模批处理系统MapReduce也需要利用GFS作为海量数据的输入输出。

系统架构

GFS将整个系统的节点分为三种角色：GFS Master（总控服务器），GFS Chunkserver（数据块服务器，简称CS）

查看全文: http://www.udpwork.com/item/6047.html

跨机房问题一直都是一个老大难的问题，先看传统数据库的跨机房方案。

Master/Slave方案

这是最常用的方案，适用于大多数需求。Master将操作日志实时地发送到Slave，Slave当成Master的一个Hot Backup。Master宕机时，服务切换到Slave，需要修改客户端逻辑使得Master失效时自动寻找新的Master。

这个方案有一个问题就是数据库的Master和Slave一般不是强同步的，所以，切换到Slave后可能丢失宕机前的少量更新。如果将Master和Slave做成强同步的，即：所有的数据必须同时写成功Master和Slave才成功返回客户端，这样又带来了另外一个问题：Master和Slave中任何

查看全文: http://www.udpwork.com/item/5684.html

8月2日（下周二）内部分享的ppt，分为几个部分：

1, 单机存储引擎看SQL与NOSQL；

2, NOSQL从单机扩展到多机的关键点；

3, 从Megastore看SQL与NOSQL的融合；

4, 设计实现的一些Work around方法及技巧；

ppt比较简单，这几天将针对其中的”单机扩展到多机“问题写一篇博客。

“云存储系统”赏析系列分享三：Sql与nosql
View more presentations from knuthocean

查看全文: http://www.udpwork.com/item/5566.html

Microsoft云存储服务分为两个部分，SQL Azure和Azure Storage。云存储系统的可扩展性和功能不可兼得，必须牺牲一定的关系数据库功能换取可扩展性。Microsoft实现云存储的思路有两种：

1, 做减法。SQL Azure直接在原有的SQL Server上引入分布式的因素，在满足一定可扩展性的前提下尽可能不牺牲原有的关系型数据库功能。SQL Azure的可扩展性是有限的，单个SQL Azure实例不允许超过50GB，这是因为SQL Azure不支持子表动态分裂，单个SQL Azure实例必须足够小从而可以被一个节点服务。具体信息可以参考我以前的一篇文章：Microsoft SQL Azure架构设计。

查看全文: http://www.udpwork.com/item/5001.html

我在数据库大会有一个报告：<<Oceanbase – 千亿级海量数据库>>，ppt已上传到Slideshare上。有一些同学问我，Oceanbase的创新点在哪里？

从大学的数据结构课程可以知道，数据量比较大时，有两种数据结构很常用：哈希表和B+树，分布式系统也是类似的。如下图：

Amazon的系统实现了一个分布式哈希表，而Google Bigtable, Yahoo PNUTS，Microsoft SQL Azure实现了一颗分布式B+树。分布式哈希表实现相对简单，但只支持随机读取；而分布式B+树支持范围查询，但实现比较复杂，主要有两个难点：

1, 状态数据的持久化和迁移。更新操作改变系统

查看全文: http://www.udpwork.com/item/4906.html

Amazon S3申请了一篇专利，名称为”Keymap Service Architecture for A Distributed Storage System“，而Amazon Simpledb的实现细节暂时没有公开。本文根据Dynamo论文，S3专利以及S3&Simpledb的对外API尝试推测这两个系统的内部实现。

对外API

1, S3：撇开S3系统中的Region, Bucket，用户权限管理等，和底层存储系统相关的API只有如下几种：

Put Object：将object加入到bucket中，即加入<bucket, name> => object 对；如果多个客户

查看全文: http://www.udpwork.com/item/4634.html

从09年第一次阅读Dynamo论文，到最近阅读Amazon S3的一篇专利，一路过来对论文的理解可以简单归结为两个字 – 纠结。第一次看到Amazon Dynamo论文，有一种眼前一亮的感觉，Dynamo通过巧妙地组合一些P2P技术在Amazon构建了一个工程上可行的系统，CAP，NWR, Vector Clock一时成为流行词，更为神奇的是，Dynamo号称能够让用户设置不同的NWR策略从而在CAP三者之间获得一个很好的权衡，鱼和熊掌亦可兼得。而Amazon S3系统的核心基本可以分为两个部分：Blob系统存储对象(Object) + 类似Dynamo的系统存放Keymap，即”Key => Obje

查看全文: http://www.udpwork.com/item/4571.html

RDBMS的优势在于功能，包括事务，强一致性，同时支持随机读和顺序扫描，索引。NOSQL系统的优势在于扩展性和性能。Google的经验告诉我们，系统设计的关键点还是在于可扩展性，依赖于底层GFS+Bigtable提供的无与伦比的可扩展性，Megastore能够在上层不断完善功能，兼具RDBMS和NOSQL系统的优点。

1, 兼顾随机读和顺序扫描。Bigtable底层的存储引擎为MemTable + SSTable构成的Merge-Dump存储引擎，SSTable设计成8K ~ 64K的块，块之间有序，随机读取型应用可以选择较小的块尺寸。和传统关系型数据库的B+树存储引擎不同的是，Merge-Dump存储引擎中的SSTable是只读

查看全文: http://www.udpwork.com/item/4511.html

最近CSDN头条有一篇介绍Google Megastore的文章，讲得挺好，本文主要针对Google Megastore的事务实现做一个更详细的探讨。Google Megastore的底层是GFS + Bigtable系统，GFS + Bigtable解决可扩展性问题，但提供的用户接口简单：读接口只提供Get随机读取和Scan连续扫描，写接口也只能够支持单行事务。Google Megastore构建在Bigtable系统之上，通过客户端封装复杂的特性，包括事务支持，基于Entity Group的数据模型，多机房同步等。Megastore的适用场景比较广泛，如社交类，邮箱，Google日历等。

Entity Group模型

互联网

查看全文: http://www.udpwork.com/item/4319.html

NOSQL系统一般都会宣传一个特性，那就是性能好，然后为什么呢？关系型数据库发展了这么多年，各种优化工作已经做得很深了，NOSQL系统一般都是吸收关系型数据库的技术，然后，到底是什么因素束缚了关系型数据库的性能呢？我们从系统设计的角度看这个问题。

1, 索引支持。关系型数据库创立之初没有想到今天的互联网应用对可扩展性提出如此高的要求，因此，设计时主要考虑的是简化用户的工作，SQL语言的产生促成数据库接口的标准化，从而形成了Oracle这样的数据库公司并带动了上下游产业链的发展。关系型数据库在单机存储引擎支持索引，比如Mysql的Innodb存储引擎需要支持索引，而NOSQL系统的单机存储引擎是纯粹的，只需要支持基于主键的随机读取和

查看全文: http://www.udpwork.com/item/4197.html

常用的数据结构包括：数组，队列，堆栈，链表，树（平衡二叉树，B树，Trie树，堆），哈希表，图，后缀数组，等等。其中，堆，图结构，Trie树及后缀数组解决特定问题，其它数据结构解决通用的查找，更新，删除操作。

查找，更新和删除操作一般是O(1)，O(logN)或者O(N)，通用的数据结果大致可分为如下三种：

1, 极端型；某些操作的算法复杂度为O(1)，另外一些算法复杂度为O(N)，比如有序链表查找复杂度为O(N)，更新和删除为O(1)；

2, 平衡型：主要操作的复杂度为O(logN)，比如平衡二叉树及各种变种，B树的查找，更新和删除操作的复杂度都为O(logN)；

3, 取巧型：主要指哈希表，最差情况下的算法复杂度虽然很高

查看全文: http://www.udpwork.com/item/4079.html

Key-Value系统只需要支持简单的随机读(Get)，写(Put)和删除(Del)操作。由于磁盘是顺序存储介质，因此可以往数据文件追加Key-Value记录并在内存中存放记录所在的磁盘位置，即索引信息。由于对同一个Key的更新(Put)操作以最后一个为准，内存中的索引只需要记录最新的Key-Value对位置即可，而对于删除操作，也是往数据文件追加一个删除记录。由于内存的大小有限，需要尽可能减小索引记录的大小，比如只支持64位的整数Key（其它类型的Key可以通过md5运算得到64位的整数值）。

内存中的索引信息包括64位的Key（8字节），Key-Value记录所在的磁盘位置（8字节），Key-Value记录在磁盘中的长度（4字

查看全文: http://www.udpwork.com/item/4065.html

单机存储引擎解决单机读写问题，Merge-Dump存储引擎设计成一种通用的存储引擎，同时支持数据写入，随机读取和顺序扫描功能。顺序扫描功能应用很广，比如MapReduce批处理，同一个广告主的所有关键词广告统计，用户浏览所有的收藏信息，淘宝卖家管理大量的商品等。简单的KV系统只需要支持随机读取，而类似Bigtable这样的通用表格系统需要考虑基于主键的顺序扫描功能。Bigtable中的Merge-Dump存储引擎结构如下：

用户的操作首先写入到MemTable中，当内存中的MemTable达到一定的大小，需要将MemTable dump到持久化存储中生成SSTable文件。这里需要注意，除了最早写入的SSTable存放了最终结果以

查看全文: http://www.udpwork.com/item/4066.html

分布式文件系统很多，包括GFS，HDFS，淘宝开源的TFS，Tencent用于相册存储的TFS (Tencent FS，为了便于区别，后续称为QFS)，以及Facebook Haystack。其中，TFS，QFS以及Haystack需要解决的问题以及架构都很类似，这三个文件系统称为Blob FS (Blob File System)。本文从分布式架构的角度对三种典型的文件系统进行对比。

我们先看GFS和HDFS。HDFS基本可以认为是GFS的一个简化版实现，二者因此有很多相似之处。首先，GFS和HDFS都采用单一主控机+多台工作机的模式，由一台主控机(Master)存储系统全部元数据，并实现数据的分布、复制、备份决策，主控机还实现

查看全文: http://www.udpwork.com/item/4067.html

OSDI 10中有一篇Facebook图片存储系统Haystack的论文，名称为”Finding a needle in Haystack: Facebook’s photo storage”。从这篇论文可以看出，数据量大的应用有时也并不复杂。

我们先给Facebook图片存储系统算一笔账。Facebook目前存储了260 billion图片，总大小为20PB，通过计算可以得出每张图片的平均大小为20PB / 260GB，约为800KB。用户每周新增图片数为1 billion (总大小为60TB)，平均每秒钟新增的图片数为10^9 / 7 / 40000 (按每天40000s计)，约为每秒350

查看全文: http://www.udpwork.com/item/4068.html

检测一台机器是否宕机的应用场景如下：

1, 工作机器宕机，总控节点需要能够检测到并且将原有服务迁移到集群中的其它节点。

2, 总控节点宕机，总控节点的备份节点（一般称为Slave）需要能够检测到并替换成主节点继续对外服务。

检测一台机器是否宕机必须是可靠的。在大规模集群中，机器可能出现各种异常，比如停电，磁盘故障，过于繁忙导致假死等。对于机器假死，如果总控节点认为机器宕机并将服务迁移到其它节点，假死的机器又认为自己还可以提供服务，则会出现多个节点服务同一份数据而导致数据不一致的情况。

首先必须明确，理论上检测另外一台机器是否宕机是无法做到的，有兴趣的同学可以参考Fischer的论文。可以简单理解如下：A机器往B机器发送心跳包

查看全文: http://www.udpwork.com/item/4070.html