OceanStore:An Architecture for Global-Scale Persistent Storage

OceanStore 项目地址                              论文地址

OceanStore 声称是一个全球规模的存储网络。因为这个网络基于不可信服务器,数据进行冗余和加密处理,为提供高可用性与性能,数据可能在任何地方、任何时间被缓存,OceanStore 能够忍受区域性中断服务和 DOS 服务攻击。在 CMU 已经有了原型,可参见上面 OceanStore 项目地址。

OceanStore 基于的原则

  • 不可信网络基础:OceanStore 认为网络永远是不可信的,服务器可能无声无息的死机或者把信息泄露给第三方,只有用户才是可信的,并只有用户才有明文,一旦进入 OceanStore 所有的信息必须加密,并允许服务器参与数据一致性的管理。
  • 游动的数据(nomadic data):像 OceanStore 这样规模的系统,数据要能够任何地点和时间缓存,这样混乱的缓存(promiscuous caching)就使得数据一致性和位置变得复杂,但却为可用性提供了很好的弹性优化数据位置。

OceanStore 概述

OceanStore 中最基础的单元是对象,每个对象有一个全球唯一标识(GUID),为达到数据冗余,对象被复制到多个服务器。每个服务器上的副本都是独立存在的(不依赖于其他服务器上的副本)。当要定位一个对象有两个机制:首先通过一个概率算法找到最近包含对象的服务器,其次如果概率算法失效了,还有一个稍慢的层次结构算法。

OceanStore 内通过“更新”操作改变对象,每次更新会产生一个新的版本号,数据的一致性也是通过版本号来维持的。根据对象属性可分为 active 和 archival 两种,active 是经过更新的了的最新版本对象, archival 只提供永久只读的对象,archival 形式的对象通过 erasure code 分散到成百上千个服务器中,当需要时可以从指定多个服务器中恢复出来,我们称这种高冗余的数据编码为 deep archival storage。

应用通过一系列会话(session)与 OceanStore 交互,每次会话都是一串读和写的操作,并支持非常松的一致性语义到 ACID 语义,并对外提供了一些可用接口(如 Unix 文件系统接口)。

最后 OceanStore 支持优化数据的放置和动态数据迁移,我们归纳这种“智能”的优化机制为“自省机制”。

OceanStore 应用

电子邮件(email)是普通却实施起来复杂的应用,分布式的邮件服务器具有更好的负载,却存在严重的内部一致性问题,并且 email 对安全性要求高, OceanStore 采用锁和安全机制,内省机制优化把用户信件迁移到离用户近的服务器上。OceanStore 能够建立超大数据仓库,通过冗余保证数据安全,并分散大流量数据。对最新的流应用也支持的不错。

OceanStore 结构

  • 命名空间

我们已经知道对象通过 GUID 命名, GUID 实际上是用户密钥和一些可读名称的哈希,服务器的 GUID 是其公钥的哈希,文档分片的 GUID 是其内容的哈希,对象在服务器端可以看过是目录。每个用户通过一个 root 目录包含自己所有对象,并通过 root 的安全控制方法(如公钥)进行访问控制,但对于服务器是没有 root 目录的。

  • 访问控制

OceanStore 加密所有不是可以全部公开的数据,服务器保存公开可读访问控制列表(ACL),并通过其判断访问者对某数据是否可读。这样服务器就会忽视所有未授权的更新。

  • 数据位置和路由

OceanStore 中条目(entity 这里指 floating replica、archival fragment 或者 client)可以自由的“定居”于任意服务器,这样就提供了很好的灵活性。所有的条目由一个或多个 GUID 定义,用户通过协议消息与条目交互,这些协议消息的目标不是 IP,而由 OceanStore 的路由层路由协议消息并送到要求的最近 GUID。这样有很大好处:多个节点同时处理路由消息,可以去掉故障节点,避免消息回环,最后还可以根据路由情况更新节点位置信息,而且当副本被删除或者迁移了,也只有网络知道,对用户是透明的。具体路由机制还是同上讲定位对象的两种方法。

当一个服务器无法响应请求,会路由到另外一个邻居,简化的 Bloom filter 完成这个功能, D 层深度的 Bloom filter 可看做 D 个普通 Bloom filter 的排列,运行于每个服务器中。1-th filter 是本地所有对象的记录, i-th filter 是当前节点到所有距离 i 节点的集合。请求沿着 filter 指示离对象最小距离(hop-count)的路径走。

宽分布式数据位置算法使用的是 Plaxton 的变种(Plaxton 也没看过)。每个对象归属于多个节点,并允许少量节点崩溃可继续访问该对象;信息分布具有高冗余、易扩展的优势,当发生宕机时,可利用冗余信息进行重建;免维护操作,当发现节点失效自动处理。

  • 更新模型

更新模型解决了写共享问题,达成 ACID 语义。更新语义保留了 Bayou 的 key functionality 和 Coda 的 merge proceduce。由于 OceanSea 内副本均是加密信息,允许以下操作:比较版本比较大小搜索替代块插入块删除块,其中块的操作讲到了指针块(index blocks)和数据块(data block)类似于 ZFS 中的相同概念。

解决更新冲突的最好方法就是列出更新次序,OceanStore 用 primary tier 代替单个的更新服务器以解决单个服务器瓶颈问题,primary tier 处在高带宽、高连接的网络,当有更新交给它们时,它们之间执行 serialization of protocol 以交付更新,然后由primary tier 自顶向下地传播更新,客户在提交给这些第一层次的节点时也向周围的节点发布更新,为了使得自己保留的更新与 primary tier 的更新一致,对每个更新都加上时间戳。

论文从数学上计算了一致性协议的效率,因为没有功能原型,这样的结论感觉不靠谱。

  • Deep Archival Storage(深度文档存储)

OceanStore 文档机制使用 erasure code 将输入的数据分为若干碎片,文章中计算了文档可用概率 P

     \begin{displaymath} P = \sum_{i=0}^{r_f} \frac{\binom{m}{i}\binom{n-m}{f-i}}{\binom{n}{f}} \end{displaymath}

其中 n 为机器总数,m 为不可用机器总数,f 为每个文档碎片数,$r_f$为要恢复出文档还需多少碎片。为验证碎片恢复出的正确性和完整性,我们对每个碎片使用层次哈希方法来验证,最上层的哈希作为对象的 GUID ,这样使得每个文档中碎片都完全地自检验。

  • OceanStore API

OceanStore API 通过会话,会话担保,更新和回滚提供对 OceanStore 的访问。

  • 自检/自省机制

OceanStore 包含了大量服务器、链接、磁盘容量和计算量,难免出现问题,OceanStore 使用了自检机制进行观测和优化,通过特定领域(domain-specific)的简单语言描述所有事件的处理,第一步对事件流进行均衡和过滤,第二层交付给数据库进行深度分析并结合、吸收历史信息,以利于系统具有延续性,最终处理了本机事务后,交付给父节点进一步处理。

具体的自检机制由以下组件组成:Cluster Recognition 识别和分组相关文件;Replica Management 调整移动副本位置和数量使得访问更加高效,当一个副本访问请求过高时,其父节点重建一个新副本加速访问;其他方面,如易管理性。

原型实验现状和相关工作

系统语言为 JAVA ,现有一个 UNIX 文件系统和 WWW  API 接口。原型中概率算法定位组件已经完成并近似最优效率,并应用了自检的预取机制,正确地获取了高阶相关系数。

文章的相关工作比较了和自己类似的系统,提过了 OceanStore 的特点。

OceanStore:An Architecture for Global-Scale Persistent Storage》上有2条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据