《 大话 Ceph 》 之 CRUSH 那点事儿

《大话 Ceph 》系列文章通过通俗易懂的语言并结合基础实验,用最简单的描述来讲解 Ceph 中的重要概念。让读者对分布式存储系统有一个清晰的理解。

引言

那么问题来了,把一份数据存到一群 Server 中分几步?

Ceph 的答案是:两步。

  1. 计算 PG
  2. 计算 OSD

计算 PG

首先,要明确 Ceph 的一个规定:在 Ceph 中,一切皆对象。

不论是视频,文本,照片等一切格式的数据,Ceph 统一将其看作是对象,因为追其根源,所有的数据都是二进制数据保存于磁盘上,所以每一份二进制数据都看成一个对象,不以它们的格式来区分他们。

那么用什么来区分两个对象呢?对象名。也就是说,每个不同的对象都有不一样的对象名。于是,开篇的问题就变成了:

把一个对象存到一群 Server 中分几步?

这里的一群 Server,由 Ceph 组织成一个集群,这个集群由若干的磁盘组成,也就是由若干的 OSD 组成。于是,继续简化问题:

把一个对象存到一堆 OSD 中分几步?

Ceph 中的逻辑层

Ceph 为了保存一个对象,对上构建了一个逻辑层,也就是池(pool),用于保存对象,这个池的翻译很好的解释了 pool 的特征,如果把 pool 比喻成一个中国象棋棋盘,那么保存一个对象的过程就类似于把一粒芝麻放置到棋盘上。

Pool 再一次进行了细分,即将一个 pool 划分为若干的 PG (归置组 Placement Group),这类似于棋盘上的方格,所有的方格构成了整个棋盘,也就是说所有的 PG 构成了一个 pool 。

现在需要解决的问题是,对象怎么知道要保存到哪个 PG 上,假定这里我们的 pool 名叫 rbd,共有 256 个 PG,给每个 PG 编个号分别叫做0x0, 0x1, ...0xF, 0x10, 0x11... 0xFE, 0xFF

要解决这个问题,我们先看看我们拥有什么?1、不同的对象名。2、不同的 PG 编号。这里就可以引入 Ceph 的计算方法了 : HASH。

对于对象名分别为barfoo的两个对象,对他们的对象名进行计算即:

  • HASH('bar') = 0x3E0A4162
  • HASH('foo') = 0x7FE391A0
  • HASH('bar') = 0x3E0A4162

对对象名进行 HASH 后,得到了一串十六进制输出值,也就是说通过 HASH 我们将一个对象名转化成了一串数字,那么上面的第一行和第三行是一样的有什么意义? 意义就是对于一个同样的对象名,计算出来的结果永远都是一样的,但是HASH算法的确将对象名计算得出了一个随机数。

有了这个输出,我们使用小学就会的方法:求余数!用随机数除以PG的总数256,得到的余数一定会落在[0x0, 0xFF]之间,也就是这256个PG中的某一个:

  • 0x3E0A4162 % 0xFF ===> 0x62
  • 0x7FE391A0 % 0xFF ===> 0xA0

于是乎,对象bar保存到编号为0x62的PG中,对象foo保存到编号为0xA0的PG中。对象bar永远都会保存到PG 0x62中! 对象foo永远都会保存到PG 0xA0中!

现在又来了一亿个对象,他们也想知道自己会保存到哪个PG中,Ceph说:“自己算”。于是这一亿个对象,各自对自己对象名进行HASH,得到输出后除以PG总数得到的余数就是要保存的PG。

求余的好处就是对象数量规模越大,每个PG分布的对象数量就越平均。

所以每个对象自有名字开始,他们要保存到的PG就已经确定了。

那么爱思考的小明同学就会提出一个问题,难道不管对象的高矮胖瘦都是一样的使用这种方法计算PG吗,答案是,YES! 也就是说Ceph不区分对象的真实大小内容以及任何形式的格式,只认对象名。毕竟当对象数达到百万级时,对象的分布从宏观上来看还是平均的。

这里给出更Ceph一点的说明,实际上在Ceph中,存在着多个pool,每个pool里面存在着若干的PG,如果两个pool里面的PG编号相同,Ceph怎么区分呢? 于是乎,Ceph对每个pool进行了编号,比如刚刚的rbd池,给予编号0,再建一个pool就给予编号1,那么在Ceph里,PG的实际编号是由pool_id+.+PG_id组成的,也就是说,刚刚的bar对象会保存在0.62这个PG里,foo这个对象会保存在0.A0这个PG里。其他池里的PG名称可能为1.12f, 2.aa1,10.aa1等。

Ceph中的物理层

理解了刚刚的逻辑层,我们再看一下Ceph里的物理层,对下,也就是我们若干的服务器上的磁盘,通常,Ceph将一个磁盘看作一个OSD(实际上,OSD是管理一个磁盘的程序),于是物理层由若干的OSD组成,我们的最终目标是将对象保存到磁盘上,在逻辑层里,对象是保存到PG里面的,那么现在的任务就是打通PG和OSD之间的隧道。PG相当于一堆余数相同的对象的组合,PG把这一部分对象打了个包,现在我们需要把很多的包平均的安放在各个OSD上,这就是CRUSH算法所要做的事情:CRUSH计算PG->OSD的映射关系

加上刚刚的对象映射到PG的方法,我们将开篇的两步表示成如下的两个计算公式:

  • 池ID + HASH('对象名') % pg_num ===> PG_ID
  • CRUSH(PG_ID) ===> OSD

使用HASH代替CRUSH?

在讨论CRUSH算法之前,我们来做一点思考,可以发现,上面两个计算公式有点类似,为何我们不把

  • CRUSH(PG_ID) ===> OSD 改为
  • HASH(PG_ID) %OSD_num ===> OSD

我可以如下几个由此假设带来的副作用:

  • 如果挂掉一个OSD,OSD_num-1,于是所有的PG % OSD_num的余数都会变化,也就是说这个PG保存的磁盘发生了变化,对这最简单的解释就是,这个PG上的数据要从一个磁盘全部迁移到另一个磁盘上去,一个优秀的存储架构应当在磁盘损坏时使得数据迁移量降到最低,CRUSH可以做到。
  • 如果保存多个副本,我们希望得到多个OSD结果的输出,HASH只能获得一个,但是CRUSH可以获得任意多个。
  • 如果增加OSD的数量,OSD_num增大了,同样会导致PG在OSD之间的胡乱迁移,但是CRUSH可以保证数据向新增机器均匀的扩散。

所以HASH只适用于一对一的映射关系计算,并且两个映射组合(对象名和PG总数)不能变化,因此这里的假设不适用于PG->OSD的映射计算。因此,这里开始引入CRUSH算法。

引入CRUSH算法

千呼万唤始出来,终于开始讲CRUSH算法了,如果直接讲Sage的博士论文或者crush.c的代码的话,可能会十分苦涩难懂,所以我决定尝试大话一把CRUSH,希望能让没有接触过CRUSH的同学也能对其有所理解。

首先来看我们要做什么:

  • 把已有的PG_ID映射到OSD上,有了映射关系就可以把一个PG保存到一个磁盘上。
  • 如果我们想保存三个副本,可以把一个PG映射到三个不同的OSD上,这三个OSD上保存着一模一样的PG内容。

再来看我们有了什么:

  • 互不相同的PG_ID。
  • 如果给OSD也编个号,那么就有了互不相同的OSD_ID。
  • 每个OSD最大的不同的就是它们的容量,即4T还是800G的容量,我们将每个OSD的容量又称为OSD的权重(weight),规定4T权重为4,800G为0.8,也就是以T为单位的值。

现在问题转化为:如何将PG_ID映射到有各自权重的OSD上。这里我直接使用CRUSH里面采取的Straw算法,翻译过来就是抽签,说白了就是挑个最长的签,这里的签指的是OSD的权重。

那么问题就来了,总不至于每次都挑容量最大的OSD吧,这不分分钟都把数据存满那个最大的 OSD了吗?是的,所以在挑之前先把这些OSD搓一搓,这里直接介绍CRUSH的方法,如下图(可忽视代码直接看文字):

  • CRUSH_HASH( PG_ID, OSD_ID, r ) ===> draw
  • ( draw &0xffff ) * osd_weight ===> osd_straw
  • pick up high_osd_straw

第一行,我们姑且把r当做一个常数,第一行实际上就做了搓一搓的事情:将PG_ID, OSD_ID和r一起当做CRUSH_HASH的输入,求出一个十六进制输出,这和HASH(对象名)完全类似,只是多了两个输入。所以需要强调的是,对于相同的三个输入,计算得出的draw的值是一定相同的。

这个draw到底有啥用?其实,CRUSH希望得到一个随机数,也就是这里的draw,然后拿这个随机数去乘以OSD的权重,这样把随机数和OSD的权重搓在一起,就得到了每个OSD的实际签长,而且每个签都不一样长(极大概率),就很容易从中挑一个最长的。

说白了,CRUSH希望随机挑一个OSD出来,但是还要满足权重越大的OSD被挑中的概率越大,为了达到随机的目的,它在挑之前让每个OSD都拿着自己的权重乘以一个随机数,再取乘积最大的那个。那么这里我们再定个小目标:挑个一亿次!从宏观来看,同样是乘以一个随机数,在样本容量足够大之后,这个随机数对挑中的结果不再有影响,起决定性影响的是OSD的权重,也就是说,OSD的权重越大,宏观来看被挑中的概率越大。

这里再说明下CRUSH造出来的随机数draw,前文可知,对于常量输入,一定会得到一样的输出,所以这并不是真正的随机,所以说,CRUSH是一个伪随机算法。下图是CRUSH_HASH的代码段,我喜欢叫它搅拌搅拌再搅拌得出一个随机数:

如果看到这里你已经被搅晕了,那让我再简单梳理下PG选择一个OSD时做的事情:

  • 给出一个PG_ID,作为CRUSH_HASH的输入。
  • CRUSH_HASH(PG_ID, OSD_ID, r) 得出一个随机数(重点是随机数,不是HASH)。
  • 对于所有的OSD用他们的权重乘以每个OSD_ID对应的随机数,得到乘积。
  • 选出乘积最大的OSD。
  • 这个PG就会保存到这个OSD上。

现在趁热打铁,解决一个PG映射到多个OSD的问题,还记得那个常量r吗?我们把r+1,再求一遍随机数,再去乘以每个OSD的权重,再去选出乘积最大的OSD,如果和之前的OSD编号不一样,那么就选中它,如果和之前的OSD编号一样的话,那么再把r+2,再次选一次,直到选出我们需要的三个不一样编号的OSD为止!

当然实际选择过程还要稍微复杂一点,我这里只是用最简单的方法来解释CRUSH在选择OSD的时候所做的事情。

下面我们来举个例子,假定我们有6个OSD,需要从中选出三个副本:

这是r = 0的情况,这时候,我们选出(CRUSH_HASH & 0xFFFF) * weight的值最大的一个,也就是osd.10x39A00,这就是我们选出的第一个OSD。 然后,我们再让r = 1,再生成一组CRUSH_HASH的随机值,乘以OSD的weight,再取一个最大的得到第二个OSD,依此得到第三个OSD,如果在此过程中,选中了相同的OSD,那么将r再加一,生成一组随机值,再选一次,直到选中三个OSD为止。

CRUSH算法的应用

理解了上面CRUSH选择OSD的过程,我们就很容易进一步将CRUSH算法结合实际结构,这里给出Sage在他的博士论文中画的一个树状结构图:

最下面的蓝色长条可以看成一个个主机,里面的灰色圆柱形可以看成一个个OSD,紫色的cabinet可以也就是一个个机柜, 绿色的row可以看成一排机柜,顶端的root是我们的根节点,没有实际意义,你可以把它看成一个数据中心的意思,也可以看成一个机房的意思,不过只是起到了一个树状结构的根节点的作用。

基于这样的结构选择OSD,我们提出了新的要求:

  • 一共选出三个OSD。
  • 这三个OSD需要都位于一个row下面。
  • 每个cabinet内至多有一个OSD。

这样的要求,如果用上一节的CRUSH选OSD的方法,不能满足二三两个要求,因为OSD的分布是随机的。

那么要完成这样的要求,先看看我们现在有什么:

  • 每个OSD的weight。
  • 每个主机也可以有一个weight,这个weight由主机内的所有OSD的weight累加而得。
  • 每个cabinet的weight由所有主机的weight累加而得,其实就是这个cabinet下的所有OSD的权重之和。
  • 同理推得每个row的weight有cabinet累加而得。
  • root的weight其实就是所有的OSD的权重之和。

所以在这棵树状结构中,每个节点都有了自己的权重,每个节点的权重由下一层节点的权重累加而得,因此根节点root的权重就是这个集群所有的OSD的权重之和,那么有了这么多权重之后,我们怎么选出那三个OSD呢?

仿照CRUSH选OSD的方法:

  • CRUSH从root下的所有的row中选出一个row。
  • 在刚刚的一个row下面的所有cabinet中,CRUSH选出三个cabinet。
  • 在刚刚的三个cabinet下面的所有OSD中,CRUSH分别选出一个OSD。

因为每个row都有自己的权重,所以CRUSH选row的方法和选OSD的方法完全一样,用row的权重乘以一个随机数,取最大。然后在这个row下面继续选出三个cabinet,再在每个cabinet下面选出一个OSD。

这样做的根本意义在于,将数据平均分布在了这个集群里面的所有OSD上,如果两台机器的权重是16:32,那么这两台机器上分布的数据量也是1:2。同时,这样选择做到了三个OSD分布在三个不同的cabinet上。

那么结合图例这里给出CRUSH算法的流程:

  • take(root) ============> [root]
  • choose(1, row) ========> [row2]
  • choose(3, cabinet) =====> [cab21, cab23, cab24] 在[row2]下
  • choose(1, osd) ========> [osd2107, osd2313, osd2437] 在三个cab下
  • emit ================> [osd2107, osd2313, osd2437]

这里给出CRUSH算法的两个重要概念:

  • BUCKET/OSD : OSD和我们的磁盘一一对应,bucket是除了OSD以外的所有非子叶节点,比如上面的cabinet,row,root等都是。
  • RULE : CRUSH选择遵循一条条选择路径,一个选择路径就是一个rule。

RULE一般分为三步走 : take-->choose N-->emitTake这一步负责选择一个根节点,这个根节点不一定是root,也可以是任何一个Bucket。choose N做的就是按照每个Bucket的weight以及每个choose语句选出符合条件的Bucket,并且,下一个choose的选择对象为上一步得到的结果。emit就是输出最终结果,相当于出栈。

这里再举个简单的例子,也就是我们最常见的三个主机每个主机三个OSD的结构:

我们要从三个host下面各选出一个OSD,使得三个副本各落在一个host上,这时候,就能保证挂掉两个host,还有一个副本在运行了,那么这样的RULE就形如:

  • take(root) ============> [default] 注意是根节点的名字
  • choose(3, host) ========> [ceph-1, ceph-2, ceph-3]
  • choose(1, osd) ========> [osd.3, osd.1, osd.8]
  • emit()

这里我们来简单总结一下:我们把一个生产环境的机房画成一个树状结构,最下面一层为OSD层,每个OSD有自己的权重,OSD的上面由host/rack/row/room/root等等节点构成,每个节点的权重都是由下层的节点累加而成,CRUSH选择每个节点的算法(straw)都是一样的,用它们的weight乘以一个随机数取其中最大,只是我们通过choose的语句来判断选择的节点类型和个数。最后不要忘了选出来的结果是PG->OSD的映射,比如:pg 0.a2 ---> [osd.3, osd.1, osd.8]pg 0.33 ---> [osd.0, osd.5, osd.7], 每个PG都有自己到OSD的映射关系,这个关系用公式总结就是: CRUSH(pg_id) ---> [osd.a, osd.b ...osd.n]

到目前为止,我们已经完成了一份数据保存到一群Server的第二步,再整体回顾下这个流程:

  • 每个文件都有一个唯一的对象名。
  • Pool_ID + HASH(对象名) % PG_NUM 得到PG_ID
  • CRUSH(PG_ID) 得到该PG将要保存的OSD组合
  • 这个对象就会保存到位于这些OSD上的PG上(PG就是磁盘上的目录)

所以,HASH算法负责计算对象名到PG的映射,CRUSH负责计算PG到OSD的映射,暂且记住这一点。

CRUSH里的虚虚实实

现在,我们有三台主机,每台主机上的配置如下:

但是想要构建成如下的结构:

这里我们不能把一台主机劈成两半把SATA盘和SSD各分一半,所以就来介绍下CRUSH里面的虚虚实实,什么是实?所有的OSD都是实实在在的节点!什么是虚?除了OSD之外的所有Bucket都是虚的!

也就是说,我们可以建立几个Bucket,分别名叫ceph-1-sata,root-sata,ceph-1-ssd, root-ssd,而这些Bucket不需要和实际结构有任何关系,可以看成是我们假想出来的结构,为了达到分层的目的,我们可以假象出任意形式的bucket。

将所有的SATA添加到ceph-x-sata节点下,再将ceph-x-sata加入到根节点root-sata下,同理处理剩下的三个SSD盘。那么现在可以制定两个RULE:

  • rule-sata:
    • take(root-sata)
    • choose(3, host)
    • choose(1, osd)
    • emit
  • rule-ssd:
    • take(root-ssd)
    • choose(3, host)
    • choose(1, osd)
    • emit

具体的建造指令可以参考之前的这篇博客《自定义CRUSH》(http://xuxiaopang.com/2016/10/10/ceph-full-install-el7-jewel/#自定义crush)

这一节想要说明的是,CRUSH里面的节点除了OSD之外的所有bucket都是可以自定义的,并不需要和实际的物理结构相关,但要记住这样做的目的是将OSD分开,从而建立适当的RULE去选择OSD,所以不要把树状结构建立的脱离了实际情况,比如从三个机器上各挑一个OSD然后放到一个自定义的host节点下,虽然可以这样做,但是是没有意义的,说白了要根据自己的数据分布要求去构建OSD树结构,因为CRUSH只认RULE,并不知道你底层的实际结构!!!

甚至,你可以像这篇博客《CRUSHMAP:层次聚类映射示例》 (http://cephnotes.ksperis.com/blog/2015/02/02/crushmap-example-of-a-hierarchical-cluster-map/)里面一样构建出花式的树状结构!一切都在于你的想象力以及集群的应用需求。

Ceph中的CRUSH

现在再正式介绍CRUSH算法在Ceph中的存在形式,首先导出一个集群的CRUSH Map:

[root@ceph-1 ~]# ceph osd getcrushmap -o /tmp/map
got crush map from osdmap epoch 67
[root@ceph-1 ~]# crushtool -d /tmp/map -o /tmp/map.txt 
[root@ceph-1 ~]# cat /tmp/map.txt 
# begin crush map
tunable choose_local_tries 0
tunable choose_local_fallback_tries 0
tunable choose_total_tries 50
tunable chooseleaf_descend_once 1
tunable straw_calc_version 1

# devices
device 0 osd.0
device 1 osd.1
device 2 osd.2
device 3 osd.3
device 4 osd.4
device 5 osd.5
device 6 osd.6
device 7 osd.7
device 8 osd.8

# types
type 0 osd
type 1 host
type 2 chassis
type 3 rack
type 4 row
type 5 pdu
type 6 pod
type 7 room
type 8 datacenter
type 9 region
type 10 root

# buckets
host ceph-2 {
    id -2        # do not change unnecessarily
    # weight 5.970
    alg straw
    hash 0    # rjenkins1
    item osd.0 weight 1.990
    item osd.1 weight 1.990
    item osd.2 weight 1.990
}
host ceph-1 {
    id -3        # do not change unnecessarily
    # weight 5.970
    alg straw
    hash 0    # rjenkins1
    item osd.3 weight 1.990
    item osd.4 weight 1.990
    item osd.5 weight 1.990
}
host ceph-3 {
    id -4        # do not change unnecessarily
    # weight 5.970
    alg straw
    hash 0    # rjenkins1
    item osd.6 weight 1.990
    item osd.7 weight 1.990
    item osd.8 weight 1.990
}
root default {
    id -1        # do not change unnecessarily
    # weight 17.910
    alg straw
    hash 0    # rjenkins1
    item ceph-2 weight 5.970
    item ceph-1 weight 5.970
    item ceph-3 weight 5.970
}

# rules
rule replicated_ruleset {
    ruleset 0
    type replicated
    min_size 1
    max_size 10
    step take default
    step chooseleaf firstn 0 type host
    step emit
}

# end crush map
[root@ceph-1 ~]#

简单介绍下几个区域的意义:

  • tunable:还记得CRUSH_HASH算法中的r变量吗,选择失败的时候这个值经常会自加一,choose_total_tries 50这个50就是用来限定总共失败的次数的,CRUSH算法本身是个递归算法,所以给定一个总共失败次数防止算法无限选择失败。那么如果要选出3副本,选失败了50次只选出一个OSD,那么最终结果是?CRUSH将输出[osd.a, ,]这样的输出,也就是说只给出一个OSD,一般很少会遇到这种情况,除非你要从一个只有一个host的root下面去选出三个host。
  • devices : 就是所有的OSD的集合。
  • types: 就是集群内所有的Bucket+OSD的类型的取值范围,所有的Bucket都要属于这些类型,当然,你可以自己增删这里给出的类型,注意type后面的数字必须唯一,因为CRUSH算法在保存类型时不是使用字符串,而是类型对应的数字,所以类型名称在CRUSH眼里是没有意义的。
  • buckets:就是树上的除了OSD以外的节点,从内容来看可以发现,每个bucket都有向下包含关系,这里看到ID和类型的ID是一样的,CRUSH在底层并不保存节点的名称字符串,而是以数字保存的,值得一提的是,OSD的ID是大于等于零的,bucket的ID是小于零的。还有就是alg straw,因为straw是最公平的选择方法,其实还有三个算法(uniform, tree, list),因为没有straw综合分高,所以就不介绍了。
  • rules: 最下面的rule区域是我们修改的最多的地方,replicated_ruleset这个是这个rule的名称,需要唯一,同样CRUSH只保存这个rule的ID,其ID就是ruleset 0这里的0,所以需要添加一个rule的时候需要注意名称和ID都不能重复。下面的三个step就是RULE的三步走策略,里面具体的参数我就不再赘述,可以参考ceph官方文档《CRUSH地图》这章 (http://docs.ceph.com/docs/master/rados/operations/crush-map/)。

还是简单的讲解下这句step chooseleaf firstn 0 type host, 实际的RULE里面分为choosechooseleaf两种,其中choose用于选择多个Bucket,Bucket是最终选择结果,相当于choose(3, Bucket)chooseleaf用于选择多个Bucket,并在这些Bucket下各选出一个OSD,OSD是最终选择结果,相当于choose(3, Bucket) + choose(1, osd)type后面的host就是要选择的Bucket类型。firstn后面的0,是选择的副本数,0等于副本数,也就是3的意思,具体参考官方文档的解释。

所以Sage论文中的图,对应到实际CRUSH的RULE就是:

rule Sage_Paper {
    ruleset 0
    type replicated
    min_size 1
    max_size 10
    step take root
    step choose firstn 1 type row
    step chooseleaf firstn 0 type cabinet
    step emit
}

总结

介绍完了这两步走的核心流程之后,最后再着重强调下计算两字,可以发现,从对象计算PG再到PG计算OSD组合,从头到尾都是通过计算得到最终的映射关系的,但是这些计算不论放在客户端还是服务器端,计算的结果都是相同的,因为里面所谓的随机值都是伪随机,只要传入一样的输入得到的输出结果都是一样的,所以Ceph把计算对象存储位置的任务发放给客户端,实际上,客户端在计算完一个对象需要保存的OSD之后,直接和OSD建立通讯,将数据直接存入OSD中,只要集群的Map没有变化,客户端和服务端计算出来的保存位置都是一样的,所以这大大的降低了服务器端的计算压力。

本文没有直接介绍CRUSH算法,而是从把一个对象存进Ceph的流程来分析,着重解释了对象到PG的映射,PG到OSD的映射这两个流程,介绍了它们的计算方法。

最后再给一个别人画的计算路径图,仅供理解。

大话Ceph系列文章

《大话Ceph》之PG那点事儿 《大话 Ceph》之 RBD 那点事儿 《大话 Ceph 》之 CephX 那点事儿

本文来自:Tstack 公众号

原创声明,本文系作者授权云+社区-专栏发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

2 条评论
登录 后参与评论

相关文章

来自专栏吕晟的专栏

机器学习库初探之 TensorFlow

什么是TensorFlow?TensorFlow™ 是一个采用数据流图(data flow graphs),用于数值计算的开源软件库。节点(Nodes)在图中表...

6451
来自专栏marsggbo

Tensorflow datasets.shuffle repeat batch方法

由结果我们可以知道TensorFlow能很好地帮我们自动处理最后一个batch的数据。

1232
来自专栏软件开发 -- 分享 互助 成长

散列表(哈希表)

序言: 如果将一系列的记录按照关键字的某种函数存储,那么在查找某个数据的时候就可以直接通过关键字计算出来了,而不在需要“比较”,这样会非常高效,这就是散列技术。...

1738
来自专栏沈唁志

PHP使用递归算法查找子集获取无限极分类等实操

递归函数是我们常用到的一类函数,最基本的特点是在函数或子过程的内部,直接或者间接地调用自己的算法,但必须在调用自身前有条件判断,否则无限调用下去,也就是所谓的死...

863
来自专栏C/C++基础

CUDA Study Notes

SSE(Streaming SIMD Extensions,单指令多数据流扩展)指令集是Intel在Pentium III处理器中率先推出的。其中包含70条指令...

912
来自专栏PPV课数据科学社区

【工具】Apache Spark 1.5发布了!!!

Apache Spark社区刚刚发布了1.5版本,大家一定想知道这个版本的主要变化,这篇文章告诉你答案。 DataFrame执行后端优化(Tungsten第一...

2746
来自专栏代码永生,思想不朽

utf8中文字符串的多模式匹配算法的优化

上个月接触到了我组的一个关于在海量文本中匹配字符串业务。读源代码时发现一些问题,并针对这些问题做了优化工作,效果非常明显。

1803
来自专栏量子位

TensorFlow 1.2正式发布,新增Python 3.6支持

王小新 编译整理 量子位 出品 | 公众号 QbitAI TensorFlow 1.2.0今日正式发布。 主要功能和改进点: 在Windows系统下新增对Pyt...

3234
来自专栏撸码那些事

【抽象那些事】 命令式抽象

这种坏味是由操作转换为类引起的,表现为类中只定义了一个方法,有时候类名和方法名相同。这种坏味还常常表现为方法操作的数据位于另一个类中。

3478
来自专栏闪电gogogo的专栏

压缩感知重构算法之正则化正交匹配追踪(ROMP)

  在看代码之前,先拜读了ROMP的经典文章:Needell D,VershyninR.Signal recovery from incompleteand i...

2696

扫码关注云+社区