带你读《存储漫谈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()函数的运算速度。


相关文章
|
6天前
|
存储 分布式计算 数据挖掘
数据架构 ODPS 是什么?
数据架构 ODPS 是什么?
51 7
|
6天前
|
数据采集 搜索推荐 数据管理
数据架构 CDP 是什么?
数据架构 CDP 是什么?
21 2
|
16天前
|
API 持续交付 开发者
后端开发中的微服务架构实践与挑战
在数字化时代,后端服务的构建和管理变得日益复杂。本文将深入探讨微服务架构在后端开发中的应用,分析其在提高系统可扩展性、灵活性和可维护性方面的优势,同时讨论实施微服务时面临的挑战,如服务拆分、数据一致性和部署复杂性等。通过实际案例分析,本文旨在为开发者提供微服务架构的实用见解和解决策略。
|
17天前
|
弹性计算 Kubernetes Cloud Native
云原生架构下的微服务设计原则与实践####
本文深入探讨了在云原生环境中,微服务架构的设计原则、关键技术及实践案例。通过剖析传统单体架构面临的挑战,引出微服务作为解决方案的优势,并详细阐述了微服务设计的几大核心原则:单一职责、独立部署、弹性伸缩和服务自治。文章还介绍了容器化技术、Kubernetes等云原生工具如何助力微服务的高效实施,并通过一个实际项目案例,展示了从服务拆分到持续集成/持续部署(CI/CD)流程的完整实现路径,为读者提供了宝贵的实践经验和启发。 ####
|
5天前
|
SQL Java 数据库连接
Mybatis架构原理和机制,图文详解版,超详细!
MyBatis 是 Java 生态中非常著名的一款 ORM 框架,在一线互联网大厂中应用广泛,Mybatis已经成为了一个必会框架。本文详细解析了MyBatis的架构原理与机制,帮助读者全面提升对MyBatis的理解和应用能力。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
Mybatis架构原理和机制,图文详解版,超详细!
|
5天前
|
Cloud Native 安全 API
云原生架构下的微服务治理策略与实践####
—透过云原生的棱镜,探索微服务架构下的挑战与应对之道 本文旨在探讨云原生环境下,微服务架构所面临的关键挑战及有效的治理策略。随着云计算技术的深入发展,越来越多的企业选择采用云原生架构来构建和部署其应用程序,以期获得更高的灵活性、可扩展性和效率。然而,微服务架构的复杂性也带来了服务发现、负载均衡、故障恢复等一系列治理难题。本文将深入分析这些问题,并提出一套基于云原生技术栈的微服务治理框架,包括服务网格的应用、API网关的集成、以及动态配置管理等关键方面,旨在为企业实现高效、稳定的微服务架构提供参考路径。 ####
26 5
|
9天前
|
监控 Go API
Go语言在微服务架构中的应用实践
在微服务架构的浪潮中,Go语言以其简洁、高效和并发处理能力脱颖而出,成为构建微服务的理想选择。本文将探讨Go语言在微服务架构中的应用实践,包括Go语言的特性如何适应微服务架构的需求,以及在实际开发中如何利用Go语言的特性来提高服务的性能和可维护性。我们将通过一个具体的案例分析,展示Go语言在微服务开发中的优势,并讨论在实际应用中可能遇到的挑战和解决方案。
|
7天前
|
负载均衡 监控 Cloud Native
云原生架构下的微服务治理策略与实践####
在数字化转型浪潮中,企业纷纷拥抱云计算,而云原生架构作为其核心技术支撑,正引领着一场深刻的技术变革。本文聚焦于云原生环境下微服务架构的治理策略与实践,探讨如何通过精细化的服务管理、动态的流量调度、高效的故障恢复机制以及持续的监控优化,构建弹性、可靠且易于维护的分布式系统。我们将深入剖析微服务治理的核心要素,结合具体案例,揭示其在提升系统稳定性、扩展性和敏捷性方面的关键作用,为读者提供一套切实可行的云原生微服务治理指南。 ####
|
7天前
|
消息中间件 缓存 Cloud Native
云原生架构下的性能优化实践与挑战####
随着企业数字化转型的加速,云原生架构以其高度解耦、弹性伸缩和快速迭代的特性,成为现代软件开发的首选模式。本文深入探讨了云原生环境下性能优化的关键策略与面临的主要挑战,通过案例分析,揭示了如何有效利用容器化、微服务、动态调度等技术手段提升应用性能,同时指出了在复杂云环境中确保系统稳定性和高效性的难题,为开发者和架构师提供了实战指南。 ####
20 3
|
7天前
|
运维 Kubernetes Cloud Native
深入理解云原生架构:从理论到实践
【10月更文挑战第38天】本文将引导读者深入探索云原生技术的核心概念,以及如何将这些概念应用于实际的软件开发和运维中。我们将从云原生的基本定义出发,逐步展开其背后的设计哲学、关键技术组件,并以一个具体的代码示例来演示云原生应用的构建过程。无论你是云原生技术的初学者,还是希望深化理解的开发者,这篇文章都将为你提供有价值的见解和实操指南。

热门文章

最新文章