带你读《存储漫谈Ceph原理与实践》第二章Ceph 架构2.2 Ceph 数据寻址(三)

简介: 带你读《存储漫谈Ceph原理与实践》第二章Ceph 架构2.2 Ceph 数据寻址

2.2.3    Bucket随机选择算法

Ceph 的设计目标是采用通用的硬件来构建大规模、高可用性、高扩展性、高性能的分布式存储系统。Ceph 的设计目标是可以管理大型分级存储网络的分布式存储系统,在网络中不同层级具有不同的故障容忍程度,这种容忍度称为故障域。

在通常情况下一台存储服务器会包含多个磁盘,每个机架则会有多台服务器,为了实现在这些服务器上构建的存储集群具有较高的可靠性,数据通常采用多副本策略,其副本存放分布在不同机架的服务器磁盘上。SageCeph存储系统中设计了CRUSH算法,它是一种基于深度优先的遍历算法,在CRUSH最初的实现中,Sage一共设计了4种不同的基本选择算法,这些算法也是后期算法的基础。

1.  几种类型的 bucket介绍

 

CRUSH中定义了 4种类型的bucket来代表集群架构中的叶子节点:一般类型 bucket

(uniformbucket、列表类型bucketlistbucket、树结构类型bucket(treebucket以及稻草类型bucket(strawbucket,这4种类型的bucket对应了4CRUSH算法。

◆  Uniformbucket

Uniform类型的 bucket在选择子节点时不考虑权重,全部随机选择,因此,它要求桶内所有元素的权值相等。它的查找速度最快,但桶内元素改变时,设备中的数据会被完全重组,uniformbucket适用于 bucket 中很少添加或删除元素,即存储系统 ClusterMap相对稳定的场景。

◆  Listbucket

List类型的 bucket 采用链表数据结构,链表中的元素可拥有任意的权重配置,在查找节点元素时,只能顺序进行,性能较差,时间复杂度为 O(n),这一特性限制了存储集群的 部署规模。但桶内新增元素时,listbucket 可以产生最优的数据移动,而桶内删除数据时,listbucket会增加额外的数据移动,即该类型bucket 更适用于小规模存储集群,且集群规模偶有扩展的场景。

◆  Treebucket

Tree类型的 bucket 采用加权二叉排序树数据结构,相较于链表数据结构,其节点元素查找效率更高,时间复杂度为 O(logn),适用于规模更大的存储集群管理。但当集群的ClusterMap发生变化时,树状结构需要旋转调整以作适配,这决定了该类型bucket更适合于规模较大、查找频繁,但集群结构相对稳定的场景。

◆  Strawbucket

Straw类型的 bucket 通过类似抽签的方式公平竞争来选取节点元素。定位副本时,bucket中的每一项元素都对应一个随机长度的straw数值,拥有最长长度最大straw数值的元素被选中。Straw类型bucket的定位过程比 listbuckettreebucket都要慢,但当集群结构出现变动(添加或删除元素)时,存储集群的数据移动量最优,即该类型bucket

更适用于集群规模常有变化的场景。

简要总结,当 bucket固定且集群设备规格统一时比如 Ceph存储系统搭建在完全相同磁盘配置的服务器集群上uniformbucket查找速度最快;如果一个bucket预计将会不断增长,则 listbucket在其列表开头插入新项时将提供最优的数据移动;而当删除bucketdevice 时,listbucket 带来额外的数据移动,strawbucket 则可以为子树之间的数据移动提供最优的解决方案。treebucket是一种适用于任何情况的 bucket,兼具性能与数据迁移效率,但其综合表现略低于 strawbucket。

Bucket   类型的选择需要基于预期的集群结构变化,权衡映射方法的元素查找运算量和储集群数据移动之间的效率,基于此观点,对比以上4种类型bucket如表2-1所示straw类型的 bucket综合表现最优。

表2-1    4种类型的bucket对比

 

类型

时间复杂度

添加元素难度

删除元素难度

uniform

O(1 )

poor

poor

list

O(n )

optimal

poor

tree

O(logn )

good

good

straw

O(n )

better

better

考虑到呈爆炸式增长的数据存储空间需求(CRUSH添加元素,在大型分布式存储系统中某些部件故障是常态(CRUSH删除元素,以及愈发严苛的数据可靠性需求需要将数据副本存储在更高级别的故障域中,如不同的数据中心,因此,CRUSH默认采用了性能较为均衡的straw 算法,strawbucket 也是Ceph 中默认的bucket 类型。

2.  Straw算法介绍

 

上文介绍到 straw类型的 bucket 通过类似抽签的方式公平竞争来选取节点元素,这种抽签算法即为 straw算法,它的关键在于如何计算签长。

核心计算过程如下。

staticintbucket_straw_choose(structcrush_bucket_straw*bucketintxintr)

{

    u32 i;

int high = 0;

    u64 high_draw = 0;

 

 

   u64draw;

for (i =0; i <bucket->h.size; i++) {

draw=crush_hash32_3(bucket->h.hashxbucket->h.items[i]r);draw &=0xffff;

draw*=bucket->straws[i];

if (i== 0|| draw> high_draw){high = i;

high_draw= draw;

}

}

returnbucket->h.items[high];

}


 

算法核心流程如下。

(1)  给出一个 PG_ID,作为 CRUSH_HASH方法的输入;

(2)  CRUSH_HASH(PG_ID,OSD_ID,r)方法调用之后,得出一个随机数;

(3)  对于所有的 OSD用它们的权重乘以每个OSD_ID 对应的随机数,得到乘积;

(4)  选出乘积最大的 OSD

(5) 这个 PG就会保存到这个 OSD上。

如果两次选出的 OSD一样,Ceph会递增 r再选一次,直到选出 3个编号不一样的OSD为止。

通过概率分布可知,只要样本容量足够大,那么最后选出的元素概率就会是相同的,   从而使数据可以得到均匀分布。但是在实际使用过程中,很多因素都会使得集群不够均衡,如磁盘容量不尽相同等,这就需要额外添加其他因子来控制差异。straw      算法就是通过使用权重对签长的计算过程进行调整来实现的,即让权重大的元素有较大的概率获取更大的   签长,从而更容易被抽中。

Straw算法选出一个元素的计算过程,其时间复杂度是O(n)

3.  Straw2算法介绍

 

理论上,在样本足够多的情况下,OSD 被选中的概率只与权重相关,下面以添加元素为例。

(1)  假定当前集合中一共有n个元素e1e2en

(2)  向集合中添加一个新元素en+1:(e1,e2,…,en,en+1)。

(3)  针对任意的输入 x,在加入 en+1 之前,分别计算每一个元素的签长并假定其中最大值为dmaxd1d2dn

(4)  因为新元素 en+1的签长计算只与自身编号和自身权重相关,所以可以使用 x立计算其签长(同时其他元素无须重新计算,假定签长为dn+1

(5)  因为 straw算法需要选出最大签长作为输出,所以:若 dn+1>dmax,那么 x将被重新映射至 en+1上,反之,对 x的已有映射不会产生影响。

由上可见,添加一个元素,straw    算法会随机地将一些原有元素中的数据重新映射至新加的元素之中。同理,删除一个元素,straw    算法会将该元素中的数据全部重新随机映射至其他元素之中。因此无论添加或者删除元素,都不会导致数据在除被添加或者删除之外的两个元素(即不相干的元素)之间进行迁移。这也是 straw算法的设计初衷,即一个元素的 weight调高或者调低,效果作用于该调整了weight的元素以及另外一个特定的相关元素,数据会从另一个元素向它迁入或者从它向另一个元素迁出,而不会影响到集群内其他不相关的元素。

理论上,straw算法是完美的,但随着 Ceph 存储系统应用日益广泛,不断有用户向Ceph社区反馈,每次集群有新的OSD加入、旧的 OSD 删除,或用户仅在一个元素上做很小的权重调节后,就会触发存储集群上很大的数据迁移。这迫使Sagestraw算法重新进行审视。

经代码分析,straw算法的 weight计算会关联一个所有元素共用的 scalingfactor(比例因子,即 Ceph集群中某个元素的权重值调整,都会影响到集群内其他元素的权重值变化。

straw算法实现如下。

max_x = -1

max_item =-1

foreach item:

x = hash(inputr)

x = x* item_strawif x > max_x

max_x = xmax_item= item

returnmax_item

 

由上述算法可知,max_item的输出主要由数据输入(input、随机值(ritem_ straw计算得出,而 item_straw通过权重计算得到,伪代码实现如下。

 


reverse= rearrange all weights in reverse order

straw = -1

weight_diff_prev_total= 0

foreach item:

item_straw= straw* 0x10000

weight_diff_prev=(reverse[current_item]-reverse[prev_item])* item_remainweight_diff_prev_total+= weight_diff_prev

weight_diff_next=(reverse[next_item]-reverse[current_item])* item_remainscale= weigth_diff_prev_total/ (weight_diff_next+ weight_diff_prev)

straw*=pow(1/scale1/item_remain)

 

straw算法中,将所有元素按其权重进行逆序排列后逐个计算每个元素的 item_straw,计算过程中不断累积当前元素与前后元素的权重差值,以此作为计算下一个元素item_straw的基准。因此 straw 算法的最终结果不但取决于每一个元素自身权重,而且也与集合中所有其他元素的权重强相关,从而导致每次加入新的元素或者从集群中剔除元素时都会引起不相干的数据迁移。

Sage 及社区对该问题进行了修复,出于兼容性的考虑,Sage重新设计了一种对原有straw算法进行修正的新算法,称为straw2straw2 在计算每个元素的签长时仅使用自身权重,因此代码可以完美反应Sage的初衷(也因此可以避免不相干的数据迁移,同时计算也变得更加简单,其伪代码如下。

 

max_x = -1

max_item =-1

foreach item:

x = hash(inputr)

x = ln(x/65536) / weight

if x >max_xmax_x=x

max_item = itemreturnmax_item

 

分析 straw2算法可知,straw2算法将 scalingfactor修改为 ln(x/65536) /weight的方式作为代替,针对输入和随机因子执行后,结果落在 [0~65535],因此 x/65536然是小于 1 的值,对其取自然对数[ln(x/655536)]后的结果为负数 1,进一步,将其除以 

自身权重(weight)后,权重越大,其结果越大,从而体现了我们所期望的每个元素权重对于抽签结果的正反馈作用。这个变化使得一个元素权重值的修改不会影响到其他的元素权重,集群内某个元素的权重调整引发的集群数据迁移范围也得到了很好的控制。

简要总结straw算法里面添加节点或者减少节点,其他服务器上的OSD之间会有PG的流动(即数据的迁移);Straw2算法里面添加节点或者减少节点,只会有 PG从变化的节点移出或者从其他点移入,其他不相干节点不会触发数据的迁移。CephLuminous版本开始默认支持 straw2算法。

 

1  CRUSH算法整体是整型运算,新引入的ln()函数是一个浮点运算,为了算法整体效率,当前的实施方法是引入了一128KB的查找表来加速ln()函数的运算速度。


相关文章
|
10天前
|
运维 Cloud Native 持续交付
云原生架构的演进与实践####
【10月更文挑战第16天】 云原生,这一概念自提出以来,便以其独特的魅力和无限的可能性,引领着现代软件开发与部署的新浪潮。本文旨在探讨云原生架构的核心理念、关键技术及其在实际项目中的应用实践,揭示其如何帮助企业实现更高效、更灵活、更可靠的IT系统构建与管理。通过深入剖析容器化、微服务、持续集成/持续部署(CI/CD)等核心技术,结合具体案例,本文将展现云原生架构如何赋能企业数字化转型,推动业务创新与发展。 ####
109 47
|
6天前
|
Kubernetes 负载均衡 Docker
构建高效后端服务:微服务架构的探索与实践
【10月更文挑战第20天】 在数字化时代,后端服务的构建对于任何在线业务的成功至关重要。本文将深入探讨微服务架构的概念、优势以及如何在实际项目中有效实施。我们将从微服务的基本理念出发,逐步解析其在提高系统可维护性、扩展性和敏捷性方面的作用。通过实际案例分析,揭示微服务架构在不同场景下的应用策略和最佳实践。无论你是后端开发新手还是经验丰富的工程师,本文都将为你提供宝贵的见解和实用的指导。
|
4天前
|
存储 安全 Java
系统安全架构的深度解析与实践:Java代码实现
【11月更文挑战第1天】系统安全架构是保护信息系统免受各种威胁和攻击的关键。作为系统架构师,设计一套完善的系统安全架构不仅需要对各种安全威胁有深入理解,还需要熟练掌握各种安全技术和工具。
27 10
|
4天前
|
监控 Cloud Native Java
云原生架构下微服务治理策略与实践####
【10月更文挑战第20天】 本文深入探讨了云原生环境下微服务架构的治理策略,通过分析当前技术趋势与挑战,提出了一系列高效、可扩展的微服务治理最佳实践方案。不同于传统摘要概述内容要点,本部分直接聚焦于治理核心——如何在动态多变的分布式系统中实现服务的自动发现、配置管理、流量控制及故障恢复,旨在为开发者提供一套系统性的方法论,助力企业在云端构建更加健壮、灵活的应用程序。 ####
44 10
|
3天前
|
缓存 运维 监控
后端开发中的微服务架构实践与挑战#### 一、
【10月更文挑战第22天】 本文探讨了微服务架构在后端开发中的应用实践,深入剖析了其核心优势、常见挑战及应对策略。传统后端架构难以满足快速迭代与高可用性需求,而微服务通过服务拆分与独立部署,显著提升了系统的灵活性和可维护性。文章指出,实施微服务需关注服务划分的合理性、通信机制的选择及数据一致性等问题。以电商系统为例,详细阐述了微服务改造过程,包括用户、订单、商品等服务的拆分与交互。最终强调,微服务虽优势明显,但落地需谨慎规划,持续优化。 #### 二、
|
4天前
|
运维 Cloud Native 持续交付
云原生架构下的微服务设计原则与实践####
【10月更文挑战第20天】 本文深入探讨了云原生环境中微服务设计的几大核心原则,包括服务的细粒度划分、无状态性、独立部署、自动化管理及容错机制。通过分析这些原则背后的技术逻辑与业务价值,结合具体案例,展示了如何在现代云平台上实现高效、灵活且可扩展的微服务架构,以应对快速变化的市场需求和技术挑战。 ####
23 7
|
1天前
|
开发者 容器
Flutter&鸿蒙next 布局架构原理详解
本文详细介绍了 Flutter 中的主要布局方式,包括 Row、Column、Stack、Container、ListView 和 GridView 等布局组件的架构原理及使用场景。通过了解这些布局 Widget 的基本概念、关键属性和布局原理,开发者可以更高效地构建复杂的用户界面。此外,文章还提供了布局优化技巧,帮助提升应用性能。
58 4
|
1天前
|
存储 Dart 前端开发
flutter鸿蒙版本mvvm架构思想原理
在Flutter中实现MVVM架构,旨在将UI与业务逻辑分离,提升代码可维护性和可读性。本文介绍了MVVM的整体架构,包括Model、View和ViewModel的职责,以及各文件的详细实现。通过`main.dart`、`CounterViewModel.dart`、`MyHomePage.dart`和`Model.dart`的具体代码,展示了如何使用Provider进行状态管理,实现数据绑定和响应式设计。MVVM架构的分离关注点、数据绑定和可维护性特点,使得开发更加高效和整洁。
136 2
|
6天前
|
消息中间件 Java API
微服务架构设计与实现:从理论到实践
微服务架构设计与实现:从理论到实践
27 7
|
3天前
|
监控 Cloud Native 测试技术
云原生架构下的性能优化与实践####
【10月更文挑战第21天】 本文深入探讨了在云原生环境下,如何通过一系列技术手段和最佳实践来提升应用性能。文章首先概述了云原生架构的基本原则与优势,随后详细分析了影响性能的关键因素,包括容器编排、微服务设计、持续集成/持续部署(CI/CD)流程以及监控与日志管理。针对这些因素,文中不仅介绍了具体的优化策略,如资源请求与限制的合理配置、服务间通信的高效实现、自动化测试与部署的优化,还结合案例分析,展示了如何在实际项目中有效实施这些策略以显著提升系统响应速度和处理能力。此外,文章还强调了性能测试的重要性,并提供了几种常用的性能测试工具和方法。最后,总结了云原生性能优化的未来趋势,为开发者和架构师
9 2

热门文章

最新文章