Ceph算法 - crush

关于存储池

从某种意义上来讲，RADOS所提供的存储空间的管理接口，不应该将其放置在同一个平面当中，因此将其切割成多个不同的"逻辑存储空间"，称之为存储池。

RADOS存储集群提供的基础存储服务需要由"存储池（pool）“分割为逻辑存储区域，此类的逻辑区域亦是对象数据的名称空间。

• 实践中，管理员可以为特定的应用程序存储不同类型数据的需求分别创建专用的存储池，例如rbd存储池，rgw存储池等，也可以为某个项目或某个用户创建专有的存储池。
• 存储池还可以再进一步细分为一至多个名称空间（namespace）。同一个存储池内，无论属于哪个、哪些名称空间，数据都是被存储池中的PG进行存放，虽然处于不同名称空间，但可能处于同一个PG之上。
• 客户端(包括rbd和rgw等）存取数据时，需要事先指定存储池名称、用户名和密钥等信息完成认证，而后将一直维持与其指定的存储池的连接，于是也可以吧存储池看做是客户端的IO接口。

存储池类型

• 副本池（replicated）：任何一个数据对象存储在此类存储池中其冗余机制是通过创建多个数据对象副本来实现的，而副本数量是用户在创建存储池时指定。如，创建存储池时没指定类型，就是副本池，默认副本数量为3个（1主两从），统称副本数量。把每个对象在集群中存储为多个副本，其中存储于主OSD的为主副本，副本数量在创建存储池时由管理员指定；副本池类型为Ceph为默认的存储池类型。但是此存储池是非常浪费存储空间的。副本池对读IO有很好的附带表现
• 纠删码池（erasure code）：使用校验码可计算回数据。把各对象存储为N=K+M个块，其中，K为数据块数量，M为编码块数量，因此存储池的尺寸为K+M；纠删码块的数据就 是允许冗余的级别。如4+2，即允许最多两个数据块丢失。不是所有的应有都能支持纠删码池，如rbd必须使用副本池。radosGW可以使用纠删码池。

副本池IO

• 将一个数据对象存储为多副本
• 写入操作时，Ceph客户端使用CRUSH算法来计算对象的PG ID和Primary OSD
• 主OSD根据设定的副本教、对象的名称、存储池名称和集群运行图（Cluster Map）计算出PG的各铺助OSD，而后由主OSD将数据同步给这些辅助OSD。

对于有着三个副本的存储池来讲，任何一个PG都会选择三个OSD，因此，副本池所关联的OSD数量通常与冗余量相同。OSD，成为一个活动集。如图所示，其中一个OSD为主OSD负责读写操作，另外两个OSD负责从主OSD同步数据。当三个副本都存完，才能的到存储完成的消息的。客户的只需与主OSD通信，同步过程是OSD内部自行实现的。

纠删码池IO

纠删码是一种前向纠错码（FEC）代码

• 通过将K块的数据转换为N块，假设N=K+M，则其中的M代表纠删码算法添加的额外活冗余的块数量以提供冗余机制（即编码块），而N则表示在纠删码编码之后要创建的块的总数，其可以故障的块数为M（即N-K）个。
• 类似于RAID5

纠删码池减少了确保数据持久性所需的磁盘空间量，但计算量上却比副本存储池要更贵一些 RGW可以使用纠删码池，但RDB不支持。

例如，把包含数据ABCDEFGHI的对象NYAN保存到存储池中，假设纠删码算法会将内容分割为三个数据块：第一个包含ABC，第二个为DEF，最后一个为GHI，并为这三个数据块额外创建两个编码块：第四个YXY和第五个GQC，此时纠删码算法会通过计算哪家出GHI、和YXY

副本池所有从OSD没有次序之分，只有主和从两类角色之分，各个从没有次序。纠删码池是有次序的，这个顺序代表数据拼凑起来的数据。因此，每个分片应指定其在整个数据文件的偏移量是多少。

归置组

归置组（PlacementGroup）是用于跨OSD将数据存储在某个存储池中的内部数据结构。

• 相对于存储池来说，PG是一个虚拟组件，它是对象映射到存储池时使用的虚拟的层
• 出于规模伸缩及性能方面的考虑，Ceph将存储池细分为归置组，吧每个单独的对象映射到归置组，并将归置组分配给一个主OSD
• 存储池由一系列的归置组组成，而CRUSH算法则根据集群运行图和集群状态，将各PG均匀、伪随机地分布到急群众的OSD之上。
• 若某OSD失败或需要对集群进行重新平衡，Ceph则移动或复制整个归置组而无需单独寻址每个对象。

归置组在OSD守护进程和Ceph客户端之间生成了一个中间层，CRUSH算法负责将每个对象动态映射到一个归置组，然后再将每个归置组动态映射到一个或多个OSD守护进程，从而能够支持在新的OSD设备上线时动态进行数据重新平衡。

归置组作用

在存储池中存放100w数据对象，而使用100个归置组，一组内存放1w对象。归置组是从新平衡和恢复时的基本单元。使得数据单元不至于以文件或对象为单位。

归置组计数

归置组的数量有管理员在创建存储池是指定，而后由crush负责创建和使用

• 通常，PG的数量应该是数据的合理粒度的子集
  • 例如，一个包含256个PG的存储池意味着每个PG包含大约1/256的存储池数据
• 当需要将PG从一个OSD移动到另一个OSD时，PG的数量会对性能产生影响
  • PG数量过少，Ceph将不得不同时移动相当数量的数据，其产生的网络负载将对集群的正常性能输出产生负面影响。
  • 而在过多的PG数量场景中在移动极少量的数据时，Ceph将会占用过多的CPU和RAM，从而对集群的计算资源产生负面影响。
• PG数量在集群分发数据和重新平衡时扮演着重要作用
  • 在所有OSD之间进行数据持久存储及完成数据分布会需要较多的归置组，但是它们的数量应该减少到最大性能所需的最小数量值，以节省CPU和内存资源
  • 一般说来，对于有着超过50个OSD的RADOS集群，建议每个OSD大约有50-100个PG以平衡资源使用，取的更好的数据持久性和数据分布，更大规模的集群中，每个OSD大约可持有100-200个PG
  • 至少应该使用多少个PG，可通过下面的公式计算后，将其值以类似于四舍五入到最近的2的N次幂
    • (Total OSDs * PGPerOSD/Replication factor => Total PGs )
    • 可以使用的PG数量 = 总OSD数量* 每个OSD可以有多少个PG/复制因子（副本数量）
  • 一个RADOS集群上可能会存在多个存储池，因此管理员还需要考虑所有存储池上的PG分布后每个OSD需要映射的PG数量
  • PG数量一定是2的N次方倍，这样进行hash计算时，速度才会更快。Ceph要求每一个OSD上最多不能超过256个PG

归置组状态

依据PG当前的工作特性活工作进程所阶段，它总是处于某个活某些个“状态中”，最常见的状态应该为active+clean

PG的常见状态

• Active
  • 主OSD和各辅助OSD均处于就绪状态，可正常服务于客户端IO请求
  • 一般Peering操作过程完成后即会转入Active状态
• Clean
  • 主OSD和各辅助OSD均处于就绪状态，所有对象的副本数量均符合期望，并且PG的活动集和上行集为同一组OSD。
  • 活动集(Acting Set)：由PG当前的主OSD和所有的处于活动状态的辅助OSD组成，这组OSD负责执行此PG上数据对象的存取操作I/O
  • 上行集(Up Set)，根据CRUSH的工作方式，集群拓扑架构的变动将可能导致PG相应的OSD变动活扩展至其他的OSD之上，这个新的OSD集也成为PG的“（Up Set）”，其映射到的新OSD集可能不分地与原有OSD集重合，也可能会完全不相干；上行集OSD需要从当前的活动集OSD上复制数据对象，在所有对象同步完成后，上行集便成为新的活动集，而PG也将转为“活动（active）”状态。
• Peering
  • 如数据不一致，需将数据复制过去，这个复制数据过程就称之为对等过程。
  • 一个PG中的所有OSD必须就它们持有的数据对象状态达成一致，而“对等（Peering）”即为其OSD从不一致转为一致的过程。
• Degraded
  • 在某OSD标记为“down”时，所有映射到此OSD的PG即转入“降级（degraded）”状态
  • 此OSD重新启动并完成Perring操作后，PG将重新转回clean
  • 一旦OSD标记为down的时间超过5分钟，它将被标记出集群，而后Ceph将对降级状态的PG启动回复操作，直到所有因此而降级的PG重回clean状态
  • 在其内部OSD上某对象不可用活悄然崩溃时，PG也会被标记为降级状态，知道对象从某个权威副本上正确恢复。
• Stale 过期
  • 每个OSD都要周期性的向RADOS集群中的监视器报告其作为主OSD所持有的所有PG的最新统计数据，因任何原因导致某个主OSD无法正常向监视器发送此类报告，或者由其他OSD报告某个OSD已经down掉，则所有以此OSD的PG将立刻被标记为stale状态。
• Undersized
• PG中的副本数少于其存储池定义的个数时即转入undersized状态，回复和回填操作在随后会启动已修复其副本为期望值
• Scrubbing 一致性保障的非常重要机制，文件完整性检查
  • 各OSD还需要周期性的检查其所持有的数据对象的完整性，以确保所有对等OSD上的数据一致；处于此类检查过程中的PG便会被标记为scrubbing状态，这也通常被称作light scrubs、shallow scrubs或者simply scrubs。
  • 另外，PG还需偶尔需要进行deep scrubs检查以确保同一对象在相关的各OSD上能按位匹配，此时PG将处于scrubbing+deep状态。
• Recovering 恢复
  • 添加一个新的OSD至存储集群中或某OSD宕掉时，PG则由可能会被CRUSH重新映射进而将持有与此不同的OSD集，而这些处于内部数据同步过程中的PG则被标记为recovering状态；
• Backfilling 回填
  • 新OSD加入存储集群后，Ceph则会进入数据重新均衡的状态，即一些数据对象会在进程后台从现有OSD移到新的OSD之上，此操作过程为backfill。

CRUSH

把对象直接映射到OSD之上会导致二者之间的紧密耦合关系，变动底层OSD就会牵一发而动全身，因此在OSD设备变动时不可避免地对整个集群产生扰动

于是Ceph将一个对象映射进RADOS集群的过程分为两步

• 先是以一致性哈希算法将对象名称映射到PG
• 而后是将PG ID基于CRUSH算法映射到OSD

此两个过程都以“实时计算”的方式完成，而非畅通的查表方式，从而有效规避了任何组件被”中心化“的可能性，使得集群规模扩展不在受限。

这个实时计算操作用到的算法就是CRUSH

• Controlled Replication Uder Scalable Hashing
• 他是一种数据分布式算法，类似于一致性哈希算法，用于为RADOS存储集群控制数据分布。

客户端IO的简要工作流程

存取对象时，客户端从Ceph监视器检索出集群运行图，绑定到指定的存储池，并对存储池上PG内的对象执行IO操作。

• 存储池的CRUSH规则集和PG的数量是决定Ceph如何放置数据的关键性因素
• 基于最新版本的集群运行图，客户端能够了解到集群中的所有监视器和OSD以及他们各自的当前状态。
• 不过，客户端对目标对象的位置却一无所知。

执行对象的存取操作时，客户端需要输入的是和对象标识和和存储池名。至于存储到哪个PG、被映射到哪个OSD则是由算法来完成的。

• 客户端需要在存储池中存储命名对象时，他将对象名称、对象名册的hash码、存储池中的PG数量和存储池名称作为输入，而后由CRUSH计算出PG的ID及此PG的主OSD。
• 通过将对象的标识进行一致性hash运算得到的哈希值与PG位图掩吗进行“与”运算得到目标PG，从而得出目标PG的ID（pg_id），完成有Object至PG的映射。
• 而后，CRUSH算法便将以此pg_id、CRUSH运行图和归置规则（Placement Rules）为输入参数再次进行计算，并输出一个确定且有序的目标存储向量列表（OSD列表），从而完成从PG至OSD的映射。

Ceph客户端使用以下步骤来计算PG ID

• 客户端输入存储池名称及对象名称。例如pool = pool1以及object-id = obj1
• 获取对象名称并通过一致性hash算法对其进行hash运算，即hash(o)，其中o为对象名称
• 将计算出的对象标识hash码与PG位图掩吗进行“与”运算获得目标PG的标识符，即PG ID，例如1701
  • 计算公式为pgid=func(hash(o)&m,r)其中，变量o是对象标识符，变量m是当前存储池中PG的位图掩吗，变量r是指复制因子，用于确定目标PG中OSD数量。
• CRUSH根据集群运行图计算出与目标PG对应的有序的OSD集合，并确定出其主OSD
• 客户端渠道存储池名称对应的数字表示，例如存储池“pool1”的数字表示11
• 客户端将存储池的ID添加到PG ID，例如，11.1701
• 客户端通过直接与PG映射到的主OSD通信来执行诸如写入、读取或删除之类的对象操作。