对象存储系统Swift技术详解：综述与概念

       OpenStack Object Storage (Swift) 是用来创建冗余的、可扩展的对象存储（引擎）的开源软件。通过阅读Swift的技术文档，我们可以理解其中的设计的原理和实现的方法 。

       Swift项目已经进展有两年了，对外开放也一年有余，在国外的社区你可以获得许多帮助，但在国内只能找到一些零零散散不齐全的资料，许多人更喜欢坐享其成，而不是参与其中。本人于9月底开始接触swift，刚开始看文档的时候一知半解，有幸阅读了zzcase等人的博客，才得以入门。非常赞同郑烨在某本书序言中所说的话：“翻译向来是一件费力不讨好的事情。”。本人本着知识共享、共同进步的目的，与诸位分享。随着对swift设计原理的理解和源码的深入，文档经过数次反复的修改，希望对各位学习swift的童鞋有所帮助，水平有限，若各位发现有错误之处，恳请指出。文档中的红字部分表示还需斟酌，欢迎提出各种建议和想法。

 转载请注明译者和出处，谢谢！

                                                      Overview and Concepts

原文链接： http://www.cnblogs.com/yuxc/archive/2011/12/06/2278303.html  

• ring 环
• account 帐号
• container 容器
• object 对象
• zone 区域
• devcie 设备
• partition 虚节点
• replica 副本
• replication 复制
• Weight 权重
• Cluster 集群
• consistency window 一致性窗口

1.1 Proxy Server  代理服务器

       代理服务器负责Swift架构的其余组件间的相互通信。对于每个客户端的请求，它将在环中查询帐号、容器或者对象的位置并且相应地转发请求。也可以使用公共API向代理服务器发送请求。

       代理服务器也处理大量的失败请求。例如，如果对于某个对象PUT请求时，某个存储节点不可用，它将会查询环可传送的服务器并转发请求。

       对象以流的形式到达（来自） 对象服务器，它们直接从代理服务器传送到（来自）用户—代理服务器并不缓冲它们。

1.2 The Ring   环

       环表示存储在硬盘上的实体名称和物理位置间的映射。帐号、容器、对象都有相应的环。当swift的其它组件(比如复制)要对帐号、容器或对象操作时，需要查询相应的环来确定它在集群上的位置。

       环使用区域、设备、虚节点和副本来维护这些映射信息。环中每个虚节点在集群中都(默认)有3个副本。每个虚节点的位置由环来维护,并存储在映射中。当代理服务器转发的客户端请求失败时，环也负责决定由哪一个设备来接手请求。

       环使用了区域的概念来保证数据的隔离。每个虚节点的副本都确保放在了不同的区域中。一个区域可以是一个磁盘，一个服务器，一个机架，一个交换机，甚至是一个数据中心。

       在swift安装的时候，环的虚节点会均衡地划分到所有的设备中。当虚节点需要移动时(例如新设备被加入到集群)，环会确保一次移动最少数量的虚节点数，并且一次只移动一个虚节点的一个副本。

       权重可以用来平衡集群中虚节点在驱动器上的分布。例如，当不同大小的驱动器被用于集群中时就显得非常有用。

       ring被代理服务器和一些后台程序使用（如replication）。

1.3 Object Server  对象服务器

       对象服务器是一个简单的二进制大对象存储服务器，可以用来存储、检索和删除本地设备上的对象。在文件系统上，对象以二进制文件的形式存储，它的元数据存储在文件系统的扩展属性(xattrs)中。这要求用于对象服务器的文件系统需要支持文件有扩展属性。一些文件系统，如ext3，它的xattrs属性默认是关闭的。

       每个对象使用对象名称的哈希值和操作的时间戳组成的路径来存储。最后一次写操作总可以成功，并确保最新一次的对象版本将会被处理。删除也被视为文件的一个版本（一个以".ts"结尾的0字节文件，ts表示墓碑）。这确保了被删除的文件被正确地复制并且不会因为遭遇故障场景导致早些的版本神奇再现。

1.4 Container Server 容器服务器

       容器服务器的首要工作是处理对象的列表。容器服务器并不知道对象存在哪，只知道指定容器里存的哪些对象。 这些对象信息以sqlite数据库文件的形式存储，和对象一样在集群上做类似的备份。容器服务器也做一些跟踪统计，比如对象的总数，容器的使用情况。 

1.5 Account Server  帐号服务器

       帐号服务器与容器服务器非常相似，除了它是负责处理容器的列表而不是对象。

1.6 Replication  复制

       复制是设计在面临如网络中断或者驱动器故障等临时性故障情况时来保持系统的一致性。

       复制进程将本地数据与每个远程拷贝比较以确保它们都包含有最新的版本。对象复制使用一个哈希列表来快速地比较每个虚节点的子段，容器和帐号的复制使用哈希值和共享的高水位线的组合进行版本比较。

       复制更新基于推模式的。对于对象的复制，更新只是使用rsync同步文件到对等节点。帐号和容器的复制通过HTTP或rsync来推送整个数据库文件上丢失的记录。

       复制器也确保数据已从系统中移除。当有一项（对象、容器、或者帐号）被删除，则一个墓碑文件被设置作为该项的最新版本。复制器将会检测到该墓碑文件并确保将它从整个系统中移除。

1.7 Updaters   更新器

       在一些情况下，容器或帐号中的数据不会被立即更新。这种情况经常发生在系统故障或者是高负荷的情况下。如果更新失败，该次更新在本地文件系统上会被加入队列，然后更新器会继续处理这些失败了的更新工作。最终，一致性窗口将会起作用。例如，假设一个容器服务器处于负荷之下，此时一个新的对象被加入到系统。当代理服务器成功地响应客户端的请求，这个对象将变为直接可用的。但是容器服务器并没有更新对象列表，因此此次更新将进入队列等待延后的更新。所以，容器列表不可能马上就包含这个新对象。

       在实际使用中，一致性窗口的大小和更新器的运行频度一致，因为代理服务器会转送列表请求给第一个响应的容器服务器，所以可能不会被注意到。当然，负载下的服务器不应该再去响应后续的列表请求，其他2个副本中的一个应该处理这些列表请求。

1.8 Auditors  审计器

       审计器会在本地服务器上反复地爬取来检测对象、容器、帐号的完整性。一旦发现不完整的数据(例如，发生了bit rot的情况：可能改变代码)，该文件就会被隔离，然后复制器会从其他的副本那里把问题文件替换。如果其他错误出现(比如在任何一个容器服务器中都找不到所需的对象列表)，还会记录进日志。

       环决定数据在集群中的位置。帐号数据库、容器数据库和单个对象的环都有独立的环管理，不过每个环均以相同的方式工作。这些环被外部工具管理，服务器进程并不修改环，而是由其他工具修改并传送新的环。

       环从路径的MD5哈希值中使用可配置的比特数，该比特位作为一个虚节点的索引来指派设备。从该哈希值中保留的比特数称为虚节点的幂，并且2的虚节点的幂次方表示虚节点的数量。使用完全MD5哈希值来划分，环允许集群的其他组件一次以分批的项来工作，这将更有效率地完成，或者至少比独立地处理每一个项或者整个集群同时工作的复杂度更低。

       另一个可配置的值是副本数量，表示有多少个虚节点->设备分派来构成单个环。给定一个虚节点编号，每个副本的设备将不会与其它副本的设备在同一个区域内。区域可以基于物理位置、电力分隔、网络分隔或者其它可以减少多个副本在同个时间点上失效的属性用来聚合设备。

2.1 Ring Builder   环构造器

       使用工具ring-builder来手动地构建和管理环。ring-builder将虚节点分配到设备并且生成一个优化的Python结构，之后打包(gzipped)、序列化(pickled)，保存到磁盘上，用以服务器的传送。服务器进程只是不定时地检测文件的修改时间，如果需要就重新加载环结构在内存中的拷贝。因为ring-builder管理环的变化的方式，使用一个稍旧的环仅意味对于的一小部分的虚节点，它的3个副本中的一个不正确，这还是容易解决的。

       ring-builder也存有它本身关于环信息的构造器文件和额外所需用来构建新环的数据。保存多份构建器文件的备份拷贝非常重要。一种选择是当复制这些环文件时，复制这些构造器文件到每个服务器上。另一种这是上传构造器文件到集群中。构造器文件的完整性受损将意味着要重新创建一些新的环，几乎所有的虚节点将最终分配到不同的设备，因此几乎所有的数据将不得不复制到新的位置上。所以，从一个受损的构建器文件恢复是有可能的，但是会造成数据在一段时间内不可用。

2.2 Ring Data Structure   环数据结构

环的数据结构由三个顶层域组成：在集群中设备的列表；设备id列表的列表，表示虚节点到设备的指派；以及表示MD5 hash值位移的位数来计算该哈希值对应的虚节点。

2.2.1 List of Devices   设备列表

设备的列表在Ring类内部被称为devs。设备列表中的每一项为带有以下键的字典：

注意：设备的列表可能包含了holes，或设为None的索引，表示已经从集群移除的设备。一般地，设备的id不会被重用。一些设备也可以通过设置权重为0.0来暂时地被禁用。为了获得有效设备的列表（例如，用于运行时间轮询），Python代码如下：devices = [device for device in self.devs if device and device[\'weight\']]

2.2.2 Partition Assignment List   虚节点分配列表

       这是设备id的array(\'I\')组成的列表。列表中包含了每个副本的数组array(\'I\')。每个array(\'I\')的长度等于环的虚节点数。在array(\'I\')中的每个整数是到上面设备列表的索引。虚节点列表在Ring类内部被称为_replica2part2dev_id。

       因此，创建指派到一个虚节点的设备字典的列表，Python代码如下：devices =[self.devs[part2dev_id[partition]] for part2dev_id in self._replica2part2dev_id]

       array(\'I\')适合保存在内存中，因为可能有几百万个虚节点。

2.2.3 Partition Shift Value  虚节点位移值

       虚节点的位移值在Ring类内部称为_part_shift。这个值用于转换一个MD5的哈希值来计算虚节点，对于那个哈希值是哪个数据。仅哈希值的前4个字节被用于这个过程。例如，为了计算路径/account/container/object的虚节点，Python代码如下：

partition = unpack_from(\'>I\',md5(\'/account/container/object\').digest())[0] >> self._part_shift

2.3 Building the Ring  构建环

       环的初始化构建首先基于设备的权重来计算理想情况下分配给每个设备的虚节点数量。例如，如虚节点幂为20，则环有1,048,576个虚节点。如果有1000个相同权重的设备，那么它们每个分到1,048.576个虚节点。设备通过它们要求的虚节点数来排序，并在整个初始化过程中保持顺序。

       然后，环构建器根据最适合的原则将每个虚节点的副本分配到设备，限制拥有相同虚节点的副本的设备不能在同一个区域中。每分配一次，设备要求的虚节点数减1并且移动到在设备列表中新的已排序的位置，然后进程继续执行。

       当基于旧环来构造新环时，每个设备所需的虚节点数量被重新计算。接下来，将需要被重新分配的虚节点收集起来。所有被移除的设备将它们已分配的虚节点取消分配并把这些虚节点添加到收集列表。任何一个拥有比目前所需的虚结点数多的设备随机地取消分配虚结点并添加到收集列表中。最后，收集列表中的虚节点使用与上述初始化分配类似的方法被重新分配。

       每当有虚节点的副本被重新分配，重分配的时间将被记录。我们考虑了当收集虚节点来重新分配时，没有虚节点在可配置的时间内被移动两次。这个可配置的时间数量在RingBuilder类内称为min_part_hours。这一限制对于已被移除的设备上的虚节点的副本被忽略，因为移除设备仅发生在设备故障并且此时别无择选只能进行重新分配。

    由于收集虚节点用来重新分配的随机本性，以上的进程并不总可以完美地重新平衡一个环。为了帮助达到一个更平衡的环，重平衡进程被重复执行直到接近完美(小于1%）或者当平衡的提升达不到最小值1%（表明由于杂乱不平衡的区域或最近移动的虚节点数过多，我们可能不能获得完美的平衡）。

2.4 History  发展史

     环的代码在到达当前版本并保持一段时间的稳定前发生了多次反复的修改，如果有新的想法产生，环的算法可能发生改变甚至从根本上发生变化。这一章节将会描述先前尝试过的想法并且解释为何它们被废弃了。

A “live ring” option was considered where each server could maintain its own copy of the ring and the servers would use a gossip protocol to communicate the changes they made. This was discarded as too complex and error prone to code correctly in the project time span available. One bug could easily gossip bad data out to the entire cluster and be difficult to recover from. Having an externally managed ring simplifies the process, allows full validation of data before it’s shipped out to the servers, and guarantees each server is using a ring from the same timeline. It also means that the servers themselves aren’t spending a lot of resources maintaining rings.

曾考虑过"live ring"选项，其中每个服务器自己可以维护环的副本并且服务器将使用gossip协议进行通讯它们所作做的变化。该方法由于过于复杂并且在工程有效时间内正确编写代码容易产生错误而被废弃。一个Bug是可以很容易把坏数据gossip到整个集群而恢复很困难。通过外部管理环可以简化这一过程，允许数据在传输到服务器前进行数据的完整验证，并且保证每个服务器使用相同时间线的环。这也意味着服务器本身不用花费大量的资源来维护环。

A couple of “ring server” options were considered. One was where all ring lookups would be done by calling a service on a separate server or set of servers, but this was discarded due to the latency involved. Another was much like the current process but where servers could submit change requests to the ring server to have a new ring built and shipped back out to the servers. This was discarded due to project time constraints and because ring changes are currently infrequent enough that manual control was sufficient. However, lack of quick automatic ring changes did mean that other parts of the system had to be coded to handle devices being unavailable for a period of hours until someone could manually update the ring.

有一对"ring server"选项曾被考虑过。一个是所有的环查询可以由调用独立的服务器或服务器集上的服务器来完成，但是由于涉及到延迟被弃用了。另一个更类似于当前的过程，不过其中服务器可以提交改变的请求到环服务器来构建一个新的环，然后运回到服务器上。由于工程时间的约束以及就目前来说，环的改变的频繁足够低到人工控制就可以满足而被弃用。然后，缺乏快速自动的环改变意味着系统的其他部件不得不花上数个小时编码来处理失效的设备直到有人可以手动地升级环。

The current ring process has each replica of a partition independently assigned to a device. A version of the ring that used a third of the memory was tried, where the first replica of a partition was directly assigned and the other two were determined by “walking” the ring until finding additional devices in other zones. This was discarded as control was lost as to how many replicas for a given partition moved at once. Keeping each replica independent allows for moving only one partition replica within a given time window (except due to device failures). Using the additional memory was deemed a good tradeoff for moving data around the cluster much less often.

当前的环程序将一个虚节点的每个副本独立地分配给一个设备。某个环程序版本中尝试使用1/3的内存，其中虚节点的第一个副本被直接分配而另外两个则在环中“行走”直到在其它区域找到额外的设备。这个方法因为对于给定虚节点的多个副本立刻移动会使得控制失效而被废除。（不是很通顺啊）保持每个副本的独立性考虑在给定的时间窗口内仅移动一个虚节点副本（除了由于设备故障）。使用额外的内存看起来是一个不错的权衡，在集群中可以更低频率地移动数据。

Another ring design was tried where the partition to device assignments weren’t stored in a big list in memory but instead each device was assigned a set of hashes, or anchors. The partition would be determined from the data item’s hash and the nearest device anchors would determine where the replicas should be stored. However, to get reasonable distribution of data each device had to have a lot of anchors and walking through those anchors to find replicas started to add up. In the end, the memory savings wasn’t that great and more processing power was used, so the idea was discarded.

另一个被尝试过的环设计是不把虚节点到设备的分配存储在内存中的大列表里而是为每个设备分配一个哈希集合或锚。虚节点将会来自数据项的哈希值来决定并且最近的设备锚将决定副本存储的位置。然而，为了获得更合理的数据分布，每个设备不得不用于大量的锚并且沿着这些锚来寻找副本开始合计。最后，由于内存存储没有那么大并且花费了更多的处理能力，这个想法被废弃了。

A completely non-partitioned ring was also tried but discarded as the partitioning helps many other parts of the system, especially replication. Replication can be attempted and retried in a partition batch with the other replicas rather than each data item independently attempted and retried. Hashes of directory structures can be calculated and compared with other replicas to reduce directory walking and network traffic.

       一个完整的无虚节点的环也被尝试，但是由于虚节点有助于系统的许多其他部件，尤其是复制而被废弃。复制可以在虚节点与其它副本的批处理中被尝试和重试，而不是每个数据项独立地被尝试和重试。目录结构的哈希值可以被计算并用来与其它副本比较来减少目录的遍历和网络流量。

Partitioning and independently assigning partition replicas also allowed for the best balanced cluster. The best of the other strategies tended to give +-10% variance on device balance with devices of equal weight and +-15% with devices of varying weights. The current strategy allows us to get +-3% and +-8% respectively.

虚节点和独立地分配虚节点的副本也考虑了最佳平衡的集群。其他策略的最佳平衡集群在设备平衡上倾向于对于平等权重的设备给出+-10%的变化而对于变化权重的设备则给出+-15%。当前的策略允许我们获得相应+-3%和+-8%的变化。

Various hashing algorithms were tried. SHA offers better security, but the ring doesn’t need to be cryptographically secure