Cassandra 分布存储系统简介

　　【摘要】:本文简要介绍了Cassandra分布存储系统的设计理念及其使用的各种分布存储技术。文章首先分析了Cassandra分布存储系统出现的缘由——Facebook社交网络的系统需求，然后着重介绍了Cassandra系统中区别传统关系型数据库的数据结构，并且简要分析了其分区技术在分布存储系统中的应用，同时，介绍了基于数据的复制机制来达到数据高度的可获得性、安全性和系统良好的扩展性的方式。最后，本文宏观的总结了Cassandra系统的运行过程及适用范围。
　　
　　【关键词】:分布存储，网络，数据库。
　　
　　 前言
　　Cassandra是一种分布存储系统，很多商业服务网站使用它来对大量的结构化的数据进行管理。在对大量数据的管理中，Cassandra可以提供高速有效的服务并从未出现过错误。Cassandra运行于数百个节点的结构之上，而在这类规模的系统中，各类组件，无论规模大小，都会持续的抛出异常。然而，Cassandra保持数据持久性的方式很好的应对了这些异常，为存储系统提高了强大的可靠性和扩展性。尽管Cassandra在一些设计和实施等方面与传统的数据库存在相似之处，但是Cassandra并不完全支持关系数据模型，即它不是一个传统的关系数据库。Cassandra提供给客户端一个相对比较简单的数据模型，这种数据模型支持对数据的布局和格式动态的控制。Cassandra系统旨在高效迅速的处理大量的写操作，与此同时不会牺牲读操作的效率，因而确保具有这种特性的商业网站能够为客户提高高效便捷的服务。
　　
　　简介
　　Cassandra最初是由AvinashLakshman和PrashantMalik在Facebook开发设计，在2008年，Facebook将它贡献给了开源社区。Cassandra的出现与Facebook的系统特性息息相关。Facebook是世界最大的社交网络平台，在高峰时段，Facebook要向数亿的用户提供服务，而Facebook数万台的服务器也遍布了全世界的各个数据中心。基于以上对海量数据处理的需求，Facebook想要为用户提供优质的、可靠的和高效的服务，一个必要的条件在于其系统平台应具有高度的扩展性以应对不断增长的用户数量和数据处理需求数量。因此，处理一个包含大量组件的系统可能出现的各种异常现象是Facebook系统平台维护人员的常规工作：在任意时间点上，总会有少量却很关键的服务器和网络组件出现错误。在这种情形下，软件系统应该以某种容错的机制处理错误，而不是将错误当作异常来处理。因此，为了达到以上指出的系统的可靠性和扩展性，Facebook开发了Cassandra。
　　
　　数据结构
　　在Cassandra这种分布存储系统中，类似于关系数据库中的表结构是一个多维分布映射图，并且以一个主键作为索引。在这种映射图中，一个对象的值是高度结构化的，其中，行主键是一个没有长度限制的字符串——通常情况下为16-36个字节。需要注意的是，在数据的任一副本中，针对任何一个行主键的操作都是原子的，即使多个列被同时读或者写。在Cassandra中，列的结构近似于Bigable中的列结构——列被组合在一起，并被称为一个ColumnFamily或者SuperColumnFamily。下面详细介绍Cassandra的列结构。
　　
　　Column
　　一个Column是一个包含名称、值和时间戳的元组。它是最小的数据容器，其中，名称和值通常没有长度限制。Column相当于关系数据库中的字段，不同的是，每一行中的Column内容可以不同，而关系数据库中一张表内每行所对应的列字段都是相同的。这种方式相对比较灵活，对于具有少量字段，并且访问时通常只需要通过Key/Value配对的数据非常适用。
　　SuperColumn
　　一个SuperColumn是包含名称和值的元组，它并不包含Column中的时间戳。SuperColumn的值并不是一个二进制字节而是映射容器——包含“Key/Value”的组合。简而言之，SuperColumn是一个包含多个Column的容器，在被包含的每个Column中，其Key值与其名称一致。SuperColumn可以表达一个object的多个属性，每个属性用一个Column表示。
　　ColumFamily
　　一个ColumFamily结构类似于关系型数据库中的表结构，它可以包含任意数量的行（row）。一个ColumFamily有一个名称（类似于关系数据库表的名称），和若干行。在每一行中，分别包含各自的key（类似于行主键）和值（value）——包含多个Column的映射表，其结构与之前介绍的SuperColumn一致。
　　
　　API
　　
　　Cassandra的API提供如下三种方法：
　　
　　 insert(table;key;rowMutation)
　　 get(table;key;columnName)
　　 delete(table;key;columnName)
　　
　　columnName可以指ColumnFamily或者SuperColumnFamily中的任意一个Column或者任意一个SuperColumn中的Column的名称。
　　
　　系统架构
　　一个存储系统的结构通常比较复杂，除去保证真实数据持久性的必要组件，存储系统还应该具有如下特性和功能：扩展性和平衡负荷的有效解决方案、伙伴关系管理（membership）和错误检测、错误恢复、同步化复制、超负荷处理、状态转移、并行和任务排序、请求配置、请求路由、系统监视与警告，以及系统配置管理。而在Cassandra系统的搭建过程中，所应用的核心分布存储技术主要包括：存储空间分区，数据复制，伙伴关系管理，错误处理和系统扩展增容，所有的这些模块协同工作，一起处理用户的读写请求。以下分别介绍在Cassandra中应用的各种分布存储技术。
　　
　　1. 分区（partition）
　　Cassandra最重要的设计特性之一即为可扩展性。为了达到这一目标，Cassandra分布存储系统使用分区技术。具体而言，在Cassandra分布存储系统中，存在多个位于不同地理位置的存储节点，每个节点按照某种算法和方式复制存储一定量的数据。新加入的数据以某种方式被分配到系统中的任一节点中。当数据量不断增多时，可以通过增加节点的书目来提高系统的容量。当然，在Cassandra系统中，新增一个或多个节点并不会对已存在的绝大多数节点造成影响，它只会改变一个局部的存储状况。以上存储方式的实现是通过动态分区的方式达到的，下面详细介绍这一技术。
　　为了达到以上目标，存储系统应该可以将数据动态的分配给集群中的不同的节点，或者说能够动态的对存储空间进行分区，并将节点存入。Cassandra使用一致性哈希函数对数据进行分区：哈希函数的输出范围是一个固定的圆环空间，称为“ring”。在这个圆环中，最大的哈希输出值与最小的哈希输出值相毗邻。系统中的任一节点被分配一个随机的值，这个随机的值代表了其在圆环空间上的位置。同时，对任一的数据的Key值做哈希运算，输出的结果代表这个数据在圆环空间上的位置。与此同时，从任一数据在圆环上的位置为起点，沿着圆环顺时针移动找到第一个节点，那么这个节点即为负责这个数据的存储容器。因此，圆环空间上的任一节点都负责存储其前一个节点和它之间的所有数据。这样的好处是增加或者删除一个节点只会影响其周围的小范围空间，而对圆环空间上的绝大多数其他节点没有任何影响，进而达到了较好的扩展性。然而，这种随机分配的机制并没有考虑到不同节点的存储能力，Cassandra解决这个问题的方法是分析圆环空间上的各节点的负载情况，并且使信息负荷量比较小的节点向负荷量比较大的节点移动，以缓解其存储压力。
　　
　　2. 复制
　　Cassandra使用数据复制的方法来保证数据高度的可用性和持久性。在Cassandra系统中，每个数据都会在N个主机上进行复制，每个Key值，k，会被指定给集群中的一个节点。如前所述，每个节点负责其控制范围内的数据的副本，并且，为了在本地存储其控制范围内的Key值，节点会将其控制的Key值在圆环空间上的其他N-1个节点上进行复制，当然，Cassandra为客户端提供了很多可供选择的数据复制策略，比如“架构不可知”（RackUnaware），“架构可知”（RackAware）（同一数据中心内）和“数据中心可知”（DatacenterAware）。应用程序可以根据需要选择自己复制数据的策略。如果一个特定的应用程序选择了“架构不可知”的数据复制策略，那么那些被复制的但尚未指派存储节点的副本会选择圆环空间上初始节点的前N-1个节点。而对于“架构可知”和“数据中心可知”复制策略，则需要涉及比较复杂的算法。具体而言，Cassandra使用Zookeeper系统③在其集群中选择一个领导节点（leader），。新加入集群的任一节点都要与领导节点进行通信，领导节点会告知其负责的副本的所在区域，同时领导节点要确保每个节点不会负责多于N-1的圆环空间上的区域。记录每个节点负责的圆环区域的元数据会缓存在所有节点上并且在Zookeeper中做容错处理——这种方式可以确保当某个节点瘫痪后再恢复时，它能够了解到其原本负责的区域。例如，当集群的一个节点崩溃后返回时，它同Zookeeper与领导节点或者其他节点进行通信，领导节点或其他节点返回存储在他们内部的关于这个节点崩溃前的存储信息，这个节点通过这些信息恢复其存储功能，重新负责原来的圆环区域。相似的概念可以借鉴Dynamo中的“偏好列表”（preferencelist），即负责给定区域的节点列表。
　　
　　基于以上的介绍，我们了解到，Cassandra节点簇中的每个节点都了解系统中的其他节点和其负责的存储区域。通过这种方式，Cassandra可以在节点瘫痪和网络分区的情况发生变化时保证数据的持久性。数据中心会因为很多因素而停止工作，比如停电，断网或者自然灾害。而Cassandra系统中数据的每个行（row）都会在多个节点被复制。实际上，一个Key的“偏好列表”就是保证拥有这个Key副本的N各节点分布在不同的数据中心。这些数据中心通过高速的网络相连接。这种跨越多个数据中心的复制机制保证了在某些数据中心瘫痪时，系统不会受到很大影响，数据也不会丢失。
　　
　　3. 伙伴关系（Membership）
　　Cassandra节点集群中的节点间关系——我们称之为“伙伴关系”（Membership），是建立在Scuttlebutt的基础之上的——一种非常高效的、基于“Gossip”的关系机制。Scuttlebutt显著的特性在于其高效的CPU利用率和“Gossip”通道的利用率。下面通过错误检测的机制来进一步理解Cassandra中的伙伴关系。
　　
　　错误检测（FailureDetection）是一种利用节点间关系的模块，通过错误检测，一个节点可以判断系统中的其他节点是否在正常的工作。在Cassandra系统中，错误检测也用来避免一个节点试图同一个无法到达的错误或者瘫痪的节点进行交互。Cassandra利用一个改进版本的AccrualFailureDetector去完成错误检测。AccrualFailureDetector的观念在于，错误检测模块并不是通过返回一个布尔值来表示一个节点工作与否，而是返回一个代表每个被检测节点的质疑等级值，这个值被定义为Φ，Φ值可以动态的调整以反应被检测节点的网络和加载的条件。AccrualFailureDetector的方法类似于统计学中的建设检验问题，而Φ相当于检验的统计量。在Cassandra系统中，Φ有如下的意义：给定一个具体的Φ值，我们在检测节点时，会以某个对应的概率错误的认为这个节点存在错误。例如假设当Φ=1时我们检测节点A，那么错误的判断节点A工作状况的概率为10%。同理，当Φ=2时，对应的概率为1%，当Φ=3时，对应的概率为0.1%，依次类推。每个节点收到系统内其他节点的“Gossip”信息的内部到达时间都被存储在各自的节点的样本窗口（samplingwindows）中，系统通过估计这些内部到达时间的分布来计算Φ值。然后再给定的显著性要求下（允许犯错误的概率），用计算出来的Φ与分布中的临界值做比较，如果大于临界值，则拒绝原假设，即某个节点的确存在错误，针对这个节点的操作被中止；如果计算出来的Φ小于临界值，则接受原假设，即某个节点没有错误，可以进行对它的操作。具体过程见图1.以前的文献认为内部到达时间类似服从高斯分布（Gaussian），但是Cassandra使用指数分布来更好的估计这一分布。总的来说，AccrualFailureDetector拥有很高的精确度和运行速度，并且这种错误检测的机制可以根据不同的网络条件和服务器负荷情况来进行自我调整。
　　
　　图1：AccrualFailureDetector
　　4. 引导程序（Bootstrapping）
　　当一个节点初次运行时，它在圆环空间上随机选择一个片段作为它的位置。为了使系统能够容错，圆环上节点的位置映射永久的保存在本地磁盘上，同时也存储在领导节点上。然后，这个片段的信息被以“Gossip”的方式传递到集群中的其他节点上。通过这种方式，圆环空间上的所有节点都能够同时了解其他节点的位置及存储情况。这也保证了在复制一节中提到的高度的数据可获得性：因为每个节点都存有其他所有节点的信息，因此，当任一节点接受到读写请求时，它能够将针对某个Key值的请求正确的传递到存储这个Key值的其他节点上。通过bootstrapping，当一个节点需要接入集群时，首先它会读取其配置文件中的连接点列表。这些集群中初始的连接点被称为集群的种子，种子也可以来自配置服务，如领导节点Zookeeper。
　　
　　5. 扩展增容
　　在分区一节中，曾经提到过Cassandra系统高度的扩展性，即新加入的存储节点不会影响整个系统的正常工作。具体而言，当一个新的节点加入到系统中时，它被指派一个圆环空间上的片段，来缓解高负荷的节点。这种方式的结果是，新的节点会分割其他节点原来负责的区域，而新的节点只会分割它在圆环上的位置周围的节点的存储区域，而不会影响其他区域。存储空间被分割的节点将其放弃的数据使用“kernel-kernel”的复制技术传递给新的节点。实际运行情况表明这些数据可以以每秒40MB的速度从一个单一节点传递到其他节点。Cassandra的开发人员通过使多个副本同时参与“bootstrap”传输来提高传输速度，这种并行传输的方式的机制与Bittorrent相似。通过高速的复制技术，Cassandra系统达到了高度的扩展性。
　　
　　 以上五种技术是在Cassandra系统中应用的比较核心的分布存储技术，他们协同工作，保证了数据高度的可获得性和扩展性。当数据量不断扩大时，Cassandra系统能够使用以上方法很好的保持系统的稳定，此外以上方法也保证了数据的安全性，基于复制机制的存储方式不仅提高了可获得性，同时面对若干主机出现瘫痪的情形，也能保持系统的正常工作，并且确保数据不会丢失。同时，Cassandra系统也能够保证数据的持久性，这种数据的持久性要依赖本地文件系统。具体而言，对于写操作，通常涉及两个子操作：1.将写操作记录到一个“commitlog”中；2.当前一个操作成功后，更新内存中的数据结构。当内存中的数据容量达到一个特定值时，它将自己导入本地磁盘中。所有的写操作都连续存储在本地磁盘上，并且建立行主键的索引以便查询，这些索引与数据文件一同存储。对于读操作，首先查询内存中的数据结构，找不到所需信息时才检索本地磁盘。这种内存—磁盘的双重存储，和首先将任一写操作记录到“commitlog”并存入磁盘的方式，通过本地文件系统的持久性保证了数据的持久性。
　　
　　总结
　　 Cassandra分布存储系统旨在应对海量数据的存储、数据的安全性问题以及基于Key-value的查询需求。通过运用上文提到的各种技术，Cassandra将数据从传统的关系数据库单一数据中心的存储方式过渡到分布的存储方式。具体而言，Cassandra的系统结构为多个分布在不同地点的存储节点，这些节点通过高速网络相连。数据通过某种哈希算法被指派到系统中的各个节点中。同时，系统利用复制的技术将存储在不同节点内的数据信息复制到其他节点上，这保证了数据的安全性，同时也提高了数据的获取速度，具体的分配机制见上文“分区”一节的介绍。当数据量不断扩大时，会有更多的节点加入到Cassandra系统的集群中，Cassandra节点集群的圆环逻辑结构保证了节点的加入不会影响系统中其他节点的工作，这使得系统具有良好的扩展性能。这种分区-复制的技术也保证了当系统中一个或多个节点瘫痪时，系统仍能正常工作，这是因为每个节点上不仅存储了自己复制的区域内的数据，还保存着其他节点内数据的副本和所有节点存储情况的元数据，进而在发生节点瘫痪时保证数据的安全。
　　 相对于关系型数据库，Cassandra分布存储系统中的数据结构并不能很好的支持复杂的结构关系查询，但是对于一些只针对某个Key值进行简单查询的数据，其性能和反应时间要远远优于关系型数据库。比如在当今流行的各大网络社区或B2B,B2C网站中，面对海量的数据和每天大量的信息吞吐量，Cassandra这类基于Key-value的分布式存储系统会逐渐的更加广泛地得到应用。
　　
　　参考文献:
　　
　　[1]. GiuseppeDeCandia,DenizHastorun,MadanJampani,GunavardhanKakulapati,AvinashLakshman,AlexPilchin,SwaminathanSivasubramanian,PeterVosshallandWernerVogels,Dynamo:Amazon’sHighlyAvailableKey-valueStore,2007
　　[2]. FayChang,JeffreyDean,SanjayGhemawat,WilsonC.Hsieh,DeborahA.WallachMikeBurrows,TusharChandra,AndrewFikes,RobertE.Gruber,Bigtable:ADistributedStorageSystemforStructuredData,2006
　　[3]. AvinashLakshman,PrashantMalik,Cassandra-ADecentralizedStructuredStorageSystem,2009
　　[4]. ArinSarkissian,WTFisaSuperColumn?AnIntrototheCassandraDataModel,2010-3-22
　　[5]. MoritzY.BeckerPeterSewell,ComputerLaboratory,UniversityofCambridge,JJThomsonAvenue,Cambridge,UnitedKingdom,Cassandra:DistributedAccessControlPolicieswithTunableExpressiveness
　　[6]. JonathanEllis,Cassandra_OpenSourceBigtable+Dynamo,2010
　　[7]. RonaldMathies,InstallingandusingApacheCassandraWithJavaPart1(Installation),InstallingandusingApacheCassandraWithJavaPart2(Datamodel),InstallingandusingApacheCassandraWithJavaPart3(Datamodel2),InstallingandusingApacheCassandraWithJavaPart4(ThriftClient),InstallingandusingApacheCassandraWithJavaPart5(ThriftClient2),2010
　　[8]. MikePerham,CassandraInternals–WritingandReading,http://www.mikeperham.com,2010