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 ：

   

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

• OceanStore API

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

• 自检/自省机制

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

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

原型实验现状和相关工作

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

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