精华内容
下载资源
问答
  • XSKY解读FAST'20 论文How to Copy File《关于如何高效率对文件目录进行快速克隆操作》 01导读 这篇发表于FAST20会议论文,是关于如何高效率对文件目录进行快速克隆操作,由来自北卡罗来纳大学教堂山...

    XSKY解读FAST'20 论文 How to Copy File 《关于如何高效率的对文件目录树进行快速克隆操作》

     

    01导读

    这篇发表于FAST20会议的论文,是关于如何高效率的对文件目录树进行快速克隆操作,由来自北卡罗来纳大学教堂山分校的Yang Zhan,Yizheng Jiao以及 罗格斯大学,佩斯大学,石溪大学,VMWare研究中心的相关研究人员合作开发完成的。

     

    本文并非是这篇论文的完整翻译稿,只是对里面的一些重点内容进行解读,有些地方解读不一定准确,建议感兴趣的同学结合原版论文一起阅读,以帮助大家拓宽思路。

     

    文章中所用图表,除非特别注明,都来自于原版论文。

     

    02概述

    作者在一开始先介绍了快速克隆的背景和重要性。随着虚拟化的广为流行,各种应用对快速克隆都有着很强的需求,典型的,如快速创建虚拟机,就需要快速克隆出虚拟机的“root filesystem”即一个image磁盘文件。而在容器场景下,如docker会非常频繁的对一个特定的文件系统目录树进行快速拷贝,这些都需要高效的克隆机制。

    针对于这些应用场景,现有的文件系统已经实现了一些“逻辑拷贝”功能,有别于“物理拷贝”,逻辑拷贝一般在实现时只进行一些元数据级别的拷贝,而只有在后续的修改中,才按需对文件数据进行拷贝并修改,这种功能称作COW(copy-on-write),这种方法在拷贝的时效性和空间的利用率方面都得到了较大的提升,因此现在已经成为克隆的基础技术。在实现时,一般存在着基于block粒度的COW和基于file或者dir级别的COW,比如btrfs和xfs使用的cp –reflink技术。

    这里作者指出,对于经典的COW技术,主要存在着“拷贝粒度”的问题,比如对于基于file级别的COW,一次微小的修改就可能导致昂贵的拷贝,比如1G大小的文件,只修改其中的1个字节,也会触发1G文件的拷贝。这会极大的增加初次COW写入时延,而且也不可避免的造成了空间上的浪费。反之,如果拷贝粒度过小,则初次COW写入时延有保证,但却容易造成碎片化(想象一下1个很大的文件,4K拷贝粒度,随机写入则会造成很多个4K COW块),后续顺序读的时候,因为这些4K数据并不是连续的,则读取速度会很慢。因此这里作者提出了自己对高效克隆的看法,需要满足如下4个特性才能被称作是合格的,作者称为“Nimble clones (敏捷克隆)”

    • 必须能快速的完成克隆操作。
    • 必须有良好的read locality (读取局部性),这样逻辑上相关的文件集读取起来会比较快,同时经过COW后,性能也应该保持一致。
    • 必须有良好的写性能,不管是对克隆前的文件集和克隆后的文件集进行写入。
    • 空间利用率必须要好。写放大应该尽量保持比较低的水平。

    作者在图1举例了现有的几种支持COW文件系统在多次克隆操作并且修改其中一小部分内容后,使用grep查询文件内容的衰减情况:

     

     

    从图中可以看出,在每次克隆和修改之后,读性能都会衰减。看XFS和ZFS的结果,16轮后大概有3~5倍的衰减。Btrfs表现的好一些,大概只有50%的衰减。总体来看,这几个文件系统都出现性能单调递减的特征。

    因此作者认为,这里的关键之处是应该将COW中的copy和write的大小进行解耦,即不应该使用一样的大小,如果是进行大的文件修改,那copy大块然后再覆盖写大块当然是合理的,但是如果是微小的修改,显然,应该将这次微小修改暂存起来,让多次微小修改进行聚合,在达到一定数量后,再批量处理显然会更合理一些。

    这篇论文在现有的BetrFS基础上,实现了一种高效的克隆机制,以同时满足前述的Nimble clones需要具备的特征。作者引入了称作CAW(Copy-on-Abundant-Write)的技术,以暂存微小数据修改,等合适的时机再进行COW。另外,这篇论文在3方面对原来的Bε-tree数据结构进行了改进与增强,1.将原来的Bε-tree树结构改造成Bε-DAG结构(directed acyclic graph,有向无环图),以满足对整棵树进行更好的遍历。2.引入了GOTO message,可以快速的持久化克隆操作。3.引入“translation prefix(前缀转换)”,用来满足对“延后数据拷贝”和 部分共享数据的查询。在引入这些优化和改进后,实验结果显示,对不同的模型,至少有33%到6.8倍的性能提升。

    论文的贡献点归结为:

    • 设计和实现了Bε-DAG数据结构,作为Nimble clones的基础。该方法扩展了Bε-tree,用来聚集小的修改,再择机进行批量写入。
    • 写优化的克隆实现。在进行克隆操作时,仅需简单的向DAG root节点写入一个GOTO message消息。
    • 量化的渐进分析表明,增加克隆不会影响其它的操作。克隆算法开销是对数级别的。
    • 全面的测试表明,优化过的BetrFS并没有对原来的BetrFS基线产生不利的影响,而在clone特性上,对比传统的支持克隆特性的文件系统,在性能上有3-4倍的提高,而对比不支持克隆特性的文件系统,则有2个数量级的提高。

     

    03BetrFS背景知识

    为深入理解这篇论文,需要先理解BetrFS的背景知识。BetrFS是该团队开发的一个用于研究型的文件系统,从2015年到现在,作者团队已经基于该文件系统发布了多篇论文,详情请参考BetrFS官网。

    BetrFS是一个内核态的基于KV存储的本地文件系统。不同于传统的文件系统,如XFS,Ext4,这些文件系统都是基于inode和B-tree(或B-tree变体)来管理和组织元数据和文件系统数据的。而BetrFS是基于Key-Value的,它有2个KV stores。其中,元数据KV存储的是 文件全路径(fullpath) 到 文件系统元数据(struct stat)的映射。数据KV 存储的是 {fullpath+block number} 到 4K block的映射。

     

     

    图片来源:附1

    BetrFS后端使用的KV存储是基于TokuDB的内核修改版本,虽然是KV存储,但Bε-tree在实现上与我们常见的基于LSM的levelDB或者rocksdb不同,它在内部实际上比较类似于B-tree数据结构,可以称作是一种Better tree。

    在附1中,作者团队详述了这种树的优点以及对于BetrFS的写优化。其中最关键的地方就是,这棵树在设计的时候,在树的node节点上预留了buffer空间。如下图,pivots与传统B-tree上的key一样,用来存放关键字key。而buffer则可以用来暂存一些对文件写的小IO,然后从root node上逐渐向叶子节点“流动”。一般的,设计node大小为2M~4M大小,这样在buffer空间将要写满的时候,才往下一级进行flush写入,这种优化能将小io写入转变成大块io写入,因此极大的提高了小IO写入的性能。

     

     

    图片来源:附2

    range查询

    因为采用了基于fullpath的KV存储,比如基于下面的文件名,在存储时都有相同的前缀,所以在实际算法运行中,基本都会落在同一个node上,因此在做range查询时,比如遍历目录下面的所有子目录或者文件时,落在磁盘上的IO,也将会是连续的,所以遍历速度会很快。同时,在删除操作中,也比较容易对删除流程进行优化,比如设计一个delete message,实现标记删除,然后后续在进行删除操作。

     

     

    基于fullpath的 rename操作

    对于基于fullpath的文件rename操作来说,是比较有挑战性的。回想一下,在Bε-tree中,所有key都是全路径的,因此在rename一个文件夹时,比如文件夹A rename成B,那么A下面所有子文件夹和子文件的key都要做对应的修改。作者团队在 附3 的论文中给出的解决方案是使用range rename操作,这种方案的关键之处在于在内部存有一个指针,用来指向文件夹源和目的的子树,range rename的操作可以转换成将这个指针转向,即所谓“pointer swing”,后续子树会进行自愈,以达到rename的目的。关于这种方法的更多细节,请参考附3论文,这里不再展开。

    掉电恢复一致性问题

    文件系统掉电恢复一致性向来是文件系统值得研究的一个关键问题,典型如ext4,xfs都使用了journal机制和事务性来保证在异常掉电时,文件系统依然能正确恢复,从而达到一致性的状态。BetrFS的Bε-tree也使用了类似的机制,对Bε-tree进行的任何修改,都需要提前记录日志,Bε-tree会周期性的进行checkpoint,比如每60s 进行一次checkpoint,完成后,会修剪redo log。在异常掉电时,依靠回放redo log来达到一致性的状态。

     

    04Cloning in BetrFS 0.5

    这一章作者介绍了如何在BetrFS中实现克隆特性,首先作者先从克隆最基础的语义开始讲起

    克隆操作语义

     

     

    克隆动作是原子的,即要么成功要么失败,不允许有中间状态。

    从KV-store的key空间角度来看,clone(s,d)意味着拷贝所有以s为前缀的key到新的以d为前缀的key,另外,它还会同时删除原来的以d为开头的key。

    Lifted Bε-DAGs

    克隆的本质是要在Bε-tree树上增加新的edge,以使得在访问克隆后的文件夹时,能通过某种方法访问克隆前的数据(克隆后的数据在不修改内容前,都是完全共享的)。在Bε-tree这样的数据结构上访问,是做不到这点的,因此,需要对Bε-tree进行改进,以支持共享访问,而DAG(有向无环图)可以完成这个功能。如下图所示,底层的node节点在DAG数据结构中,是可以被上面两个路径来访问的。

     

     

    图片来源:附4

    在对Bε-tree进行改进时,作者强调需要解决3个问题:

    1、因为对node可能有来自多个路径的访问,所以需要对node维护一份引用计数,引用计数并不存放在node本身的数据结构中,而是存放在专门的 node translation table 中,这样在修改引用计数时,并不需要更改node数据结构本身,避免了需要加速解锁等操作,以便于提升性能。

    2、问题2是在Bε-tree中,node通常设置的比较大,如2M~4M大小,这样也就意味着1个node上会有很多key值。因此,共享target node意味着会有一些冗余的key也会被共享,例如如下图2所示:

     

     

    底下的node包含了所有以s为前缀的key空间,但同时也包含了以q和v开头的key,而这些key是冗余的,不应该被访问到的。因此,作者在这里对pivots域内的key使用了过滤技术,以用来过滤那些冗余的key。

    3、使用translation prefix(前缀转换)技术,还是如上面图2所示,在将s开头的目录转换成以p开头的目录后,会在上面的节点上插入指针,指向下面的节点,那后续查询pw时,在pivots找到指向下面的节点,但因为是clone过来的,所以这里需要进行translation prefix,即先去掉p,在下面节点查询时,按照sw进行查询。这种转换只是临时的,因为克隆最终完成时,需要将节点变成一般的节点,后文会有描述。

    Creating clones with GOTO messages

    论文接下来讲述创建克隆的过程。首先,如下图3所示,要clone所有以s开头的key到以p开头的key,则需要先找到所有以s开头的key node的父节点,称作 LCA (lowest-common ancestor);

     

     

    接着要做的是一次flush操作,即将从最开始的root节点到LCA之间节点暂存的所有以s开头的key都持久化下来,以保证LCA是完整的包含了以s开头的完整key空间。待flush完成后,再向root节点插入一条GOTO message,则完成clone过程。

    那么这个GOTO message是做什么用处呢,这个是克隆动作本身的关键。它的组成大概是这样的:

    (a,b) - hight - dst_node

    (a,b) 表示覆盖的key空间, hight表示的是到target node的高度,dst_node表示目标 target。

    比如,若要查询的key为x,则先判断x是否落在(a,b)指示的key区间,如果落在这个区间,则接着会直接到dst_node 处继续进行查找。换句话说,goto message能够改变查找方向。

    Flushing GOTO messages

    GOTO message可以通过flush的方式,从root node向下面的node滑动。通过这种消息机制,可以将DAG中的遍历寻址信息编码进来,这样可以非常高效的完成克隆操作。GOTO message强大之处在于之后发生的所有查询,都因为GOTO确定的新的路径而发生了改变,换句话说,GOTO message能隐含的删除原来的所有以特定前缀开头的key空间。

    Converting a GOTO

    Goto message的转换过程和flush过程类似,在向下层滑动的时候,都会涉及到对重叠区的key空间的合并和处理,如下图:

     

     

    左边,区间 (pab,t) 包含了pivots区域内的 (pz,r), 因此在将goto message转换成标准 pivots时,会将原来的(pz,r) key空间删除掉,将 (pab,t)空间加入进去。

    而在部分重叠的情况下,还要更为复杂一些。比如上图左边的(pa,pz) 和(r,w)的部分重叠于 (pab,t)。

     

     

    在经过处理后,要注意的是 (pa,pab)这个空间的key,要加上前缀as2,因为在老的空间 (pa,pz), 向下查询时,前缀是s2,但经过转换后,pa前缀被去除,必须要把a加上才能和原来的key一致。这个是所谓的”lifted Bε-tree”技术,在作者团队的附3论文中有详述。

    Flushes, splits, and merges

    论文接下来讲节点的flush,split和merge。从较高层次上看,需要2个过程:

    1、需要将children node转换成 simple children

    2、再执行标准的Bε-tree flush,split 和merge过程

    Simple child的定义是该node引用计数为1,并且其边指向的child没有 translation prefix。

    在child都simple化后,Bε-DAG就形式化为 Bε-tree了,因此可以使用Bε-tree的方式进行节点的flush,split和merge。

    有至少两种场景都需要将一个节点simple化。第一种情况是其parent节点在buffer空间中累积了足够多的修改,需要执行CAW操作时。第二种情况是后台的heal线程在调整target的fanout时,需要进行split和merge操作,从而引发将节点simple化。注意,Simple化一个节点是在 flush, split 或者merge的过程中进行的。

    Simple化一个节点时,首先要做的就是先进行一次private 拷贝节点,如图5所示:

     

     

    得到这个private node以后,就可以对这个node进行“整理”,如下图,最左边的是最初的private node,里面的一些key空间是冗余的,会被删除,中间的图即是删除掉冗余key的图,最后,translation prefix也会被删除。

     

     

    值得注意的是,这些复杂的步骤只是在clone以后,有数据写入时,而且达到一定条件后才触发的,或者是在后台为了平衡Bε-DAG状态而进行的。对于那些未修改的共享node,是不需要进行这些复杂的过程的。

     

    05算法渐进分析

    对Bε-DAG的渐进分析表明,插入,查询,和克隆的复杂度都只与Bε-DAG的高度有关,它的渐进复杂度与lifted Bε-tree是一致的。可以这样考虑,如果我们将GOTO message都flush下去,转换成一般的pivots,这样消除掉GOTO message后,再断开共享的node链接后,就会形成一棵Bε-tree,这棵树的高度最高也就和Bε-DAG的高度相同。

    Bε-tree和Bε-DAG的高度都是 O(logB N), 前者N是指tree的key number,后者的N是指clone前的key加上clone的key个数。

    查询:因为Bε-DAG的高度是 O(logB N),因此IO查询代价也是O(logB N)

    插入:插入的复杂度和Bε-tree也是一样,为:

     

     

    克隆:克隆的过程可以分为2个阶段,第一个阶段是在线的,第二个阶段是后台的。在线阶段只包含将LCA以上的含有s的消息flush到LCA上和向root node上插入一条GOTO message的代价。这个代价是O(logB N)级别,后台处理阶段主要是后台进程将GOTO message向下flush,并且最终转换为一般的pivots。其算法复杂度也是O(logB N)级别。

     

    06评估分析

    论文在评估分析一章中给出了性能测试结果,主要回答了如下几个问题:

    • BetrFS 0.5中实现的克隆特性是否满足如下这4个设计目标:能高速创建克隆吗,读满足局部性原理吗,满足快速写吗,空间浪费如何;
    • 引入克隆特性,是否会对以前版本的性能造成冲击;
    • 克隆特性是否能提高真实应用的性能。

    作者对比了如下文件系统:baseline BetrFS(指没有克隆特性的BetrFS 0.4版本), ext4, Btrfs, XFS, ZFS, and NILFS2。

    克隆性能

    在克隆性能测试中,作者选择的是 单个目录下创建8个子目录,每个子目录下1个4M大小的文件,然后对这个目录进行克隆,在每次克隆后,向clone后的每个文件写入16字节(4KB对齐),以模拟小块IO修改。

    图7-a是clone延迟结果,图7-b是做16字节修改的写时延,图7-c是grep clone文件的读时延:

     

     

    在对比文件系统中,Btrfs使用基于reflink和volume snapshot两种模式,XFS使用reflink模式,ZFS使用volume snapshot模式。对于BetrFS,使用了禁止后台处理的 no cleaning模式和允许后台处理的正常模式。从结果可以看出,禁止后台处理模式和正常模式在性能表现基本一致,只是在空间利用率方面会产生一些波动。

    分析创建clone的时延,BetrFS大概只需要60ms的时延,这个结果比XFS快33%,比基于svol的Btrfs快58%,比起ZFS,则是有一个数量级的提高。另外,在多次clone后,BetrFS性能基本不会发生大的变化,而Btrfs和XFS则随着克隆数的增多,时延会逐渐增大,大概在8轮之后,时延就显示出翻倍了。

    在写时延方面,BetrFS性能是其它文件系统性能的8~10倍,这主要还是得益于BetrFS的CAW特性,其它文件系统基本都是COW类型的。另外随着clone数的增加,所有这些文件系统基本都没有明显的写性能损失。

    在读时延方面,因为grep操作基本属于scan类型的操作,BetrFS表现的很稳定,不会随着clone数的增加而衰减,而XFS和ZFS有着比较明显的衰减趋势,Btrfs也会衰减,但不是太严重,8次clone后,Btrfs-svol类型的衰减大概在10%,Btrfs文件类型的衰减大概在20%。另外作者也指出,在17次clone后,Btrfs衰减大概到了50%(图中没有画出)。

    下面表1显示的是空间开销,可以看出,每次clone修改,BetrFS 引入的开销只有16K左右,比其它文件系统都要好很多,另外,因为BetrFS后台的clean动作,会导致空间利用率有波动,在no clean模式下,空间开销会稳定在32K。总之,结果表明,在空间开销方面,BetrFS完成了预期的目标,不会对空间造成浪费。

     

     

    那么,BetrFS在其它文件操作模型下表现如何呢,作者也选取了一些用例进行评测。

    顺序IO

    在顺序读写IO方面,都能达到一个可以接受的性能。读性能方面,比最快的ext4文件系统,大概慢19%,在顺序写方面,比最快的Btrfs大概只慢6%。

     

     

    随机IO

    在随机读写性能测试中,作者选择 向一个10G大文件中随机进行 256K 个 4字节的读写,写入时是带上fsync标志以保证持久化到磁盘。

    结果表明,对于随机写,BetrFS 0.5比传统的文件系统大概要快39到67倍,而比起不带clone的BetrFS 0.4,大概只慢了8.5%。而对于随机读,BetrFS 0.5 比 最快的Btrfs只慢了12%。

     

     

    TokuBench测试

    作者使用TokuBench软件进行海量文件创建测试,大概创建3百万个200字节的小文件,分布在多个子目录中,每个子目录保持一定的平衡度,即不超过128个子目录或者128个子文件。结果表明,在海量小文件创建方面,BetrFS0.5和BetrFS0.4性能基本一致,比起Ext4文件系统,提高了大概95倍。

     

     

    目录操作性能

    在目录操作性能测试中,主要进行了递归的grep,find和delete操作,结果如下表所示,BetrFS 0.5和BetrFS 0.4性能基本一致,不会因为clone的引入而对性能有所损失,而比起传统的文件系统性能,都是有数量级的性能提高。

     

     

    具体应用的性能评测

    在具体应用程序的评测方面,作者选取了 git clone,tar,rsync,IMAP server进行测试,结果如下:

     

     

    图中的 BetrFS 0.5是在还没有克隆过的目录里面执行, BetrFS 0.5-clone 是在克隆后的目录里面执行。

    从结果可以看出,BetrFS在大部分场景中,都获得了最好的性能。在极个别场景中,BetrFS会有稍微的性能损耗,但也都是在可接受范围内。

    容器场景

    作者在 Linux Containers (LXC)场景中测试了clone的真实表现。容器后端默认使用Dir后端,这个后端内部实现为使用rsync进行复制目录,另外还可以定制自己的后端,在定制后端里面,可以高效的使用自己的clone机制。

     

     

    如表所示,BetrFS实现的容器后端克隆特性比ZFS和BetrFS要快好几倍,比起传统的Dir实现,则是好几个数量级的提高。

     

    07结语

    通过将CoW特性中的copy和write进行解耦,作者团队在已有的BetrFS之上,开发出了具有高效率的clone/读/写以及高效的空间使用率的新的文件系统。从性能测试结果以及真实应用的表现来看,都完成了这些看似矛盾的目标。同时,使用的一些如诸如小IO汇聚,批量写入,Bε-DAG等数据结构与技术都是比较通用的技术,可以用于任何以Key-value store为基础的应用软件上,而不仅仅只是文件系统。

     

    附1:FAST15 BetrFS: A Right-Optimized Write-Optimized File System(http://supertech.csail.mit.edu/papers/JannenYuZh15a.pdf

    附2:An Introduction to Bε-trees and WriteOptimization(https://www.usenix.org/system/files/login/articles/login_oct15_05_bender.pdf

    附3:The Full Path to Full-Path Indexing(https://www.usenix.org/system/files/conference/fast18/fast18-zhan.pdf

    附4:How to Copy Files slide(https://www.usenix.org/sites/default/files/conference/protected-files/fast20_slides_conway.pdf

    附5:原始论文链接 how to copy file(https://www.usenix.org/system/files/fast20-zhan.pdf

    发布于 2020-06-03

    https://zhuanlan.zhihu.com/p/145642958

    展开全文
  • 红黑树的一些基本概念 在讲TreeMap前还是先说一下红黑...(关于树和二叉查找树可以看我之前写的一篇文章树型结构) 红黑树是为了维护二叉查找树的平衡而产生的一种树,根据维基百科的定义,红黑树有五个特性,但我...

    红黑树的一些基本概念

    在讲TreeMap前还是先说一下红黑树的一些基本概念,这样可以更好地理解之后TreeMap的源代码。

    二叉查找树是在生成的时候是非常容易失衡的,造成的最坏情况就是一边倒(即只有左子树/右子树),这样会导致树检索的效率大大降低。(关于树和二叉查找树可以看我之前写的一篇文章树型结构

    红黑树是为了维护二叉查找树的平衡而产生的一种树,根据维基百科的定义,红黑树有五个特性,但我觉得讲得不太易懂,我自己总结一下,红黑树的特性大致有三个(换句话说,插入、删除节点后整个红黑树也必须满足下面的三个性质,如果不满足则必须进行旋转):

    1. 根节点与叶节点都是黑色节点,其中叶节点为Null节点
    2. 每个红色节点的两个子节点都是黑色节点,换句话说就是不能有连续两个红色节点
    3. 从根节点到所有叶子节点上的黑色节点数量是相同的

    上述的性质约束了红黑树的关键:从根到叶子的最长可能路径不多于最短可能路径的两倍长。得到这个结论的理由是:

    1. 红黑树中最短的可能路径是全部为黑色节点的路径
    2. 红黑树中最长的可能路径是红黑相间的路径

    此时(2)正好是(1)的两倍长。结果就是这个树大致上是平衡的,因为比如插入、删除和查找某个值这样的操作最坏情况都要求与树的高度成比例,这个高度的理论上限允许红黑树在最坏情况下都是高效的,而不同于普通的二叉查找树,最终保证了红黑树能够以O(log2 n) 的时间复杂度进行搜索、插入、删除

    下面展示一张红黑树的实例图:

    可以看到根节点到所有NULL LEAF节点(即叶子节点)所经过的黑色节点都是2个。

    另外从这张图上我们还能得到一个结论:红黑树并不是高度的平衡树。所谓平衡树指的是一棵空树或它的左右两个子树的高度差的绝对值不超过1,但是我们看:

    • 最左边的路径0026-->0017-->0012-->0010-->0003-->NULL LEAF,它的高度为5
    • 最后边的路径0026-->0041-->0047-->NULL LEAF,它的高度为3

    左右子树的高度差值为2,因此红黑树并不是高度平衡的,它放弃了高度平衡的特性而只追求部分平衡,这种特性降低了插入、删除时对树旋转的要求,从而提升了树的整体性能。而其他平衡树比如AVL树虽然查找性能为性能是O(logn),但是为了维护其平衡特性,可能要在插入、删除操作时进行多次的旋转,产生比较大的消耗。

    四个关注点在TreeMap上的答案

    关 注 点 结  论
    TreeMap是否允许键值对为空 Key不允许为空,Value允许为空 
    TreeMap是否允许重复数据 Key重复会覆盖,Value允许重复 
    TreeMap是否有序 按照Key的自然顺序排序或者Comparator接口指定的排序算法进行排序 
    TreeMap是否线程安全  非线程安全

    TreeMap基本数据结构

    TreeMap基于红黑树实现,既然是红黑树,那么每个节点中除了Key-->Value映射之外,必然存储了红黑树节点特有的一些内容,它们是:

    1. 父节点引用
    2. 左子节点引用
    3. 右子节点引用
    4. 节点颜色

    TreeMap的节点Java代码定义为:

    static final class Entry<K,V> implements Map.Entry<K,V> {
            K key;
            V value;
            Entry<K,V> left = null;
            Entry<K,V> right = null;
            Entry<K,V> parent;
            boolean color = BLACK;
            ...
    }

    由于颜色只有红色和黑色两种,因此颜色可以使用布尔类型(boolean)来表示,黑色表示为true,红色为false。

    TreeMap添加数据流程总结

    首先看一下TreeMap如何添加数据,测试代码为:

    public class MapTest {
    
        @Test
        public void testTreeMap() {
            TreeMap<Integer, String> treeMap = new TreeMap<Integer, String>();
            treeMap.put(10, "10");
            treeMap.put(85, "85");
            treeMap.put(15, "15");
            treeMap.put(70, "70");
            treeMap.put(20, "20");
            treeMap.put(60, "60");
            treeMap.put(30, "30");
            treeMap.put(50, "50");
    
            for (Map.Entry<Integer, String> entry : treeMap.entrySet()) {
                System.out.println(entry.getKey() + ":" + entry.getValue());
            }
        }
        
    }

    本文接下来的内容会给出插入每条数据之后红黑树的数据结构是什么样子的。首先看一下treeMap的put方法的代码实现:

    public V put(K key, V value) {
        Entry<K,V> t = root;
        if (t == null) {
            compare(key, key); // type (and possibly null) check
    
            root = new Entry<>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
        int cmp;
        Entry<K,V> parent;
        // split comparator and comparable paths
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        else {
            if (key == null)
                throw new NullPointerException();
            Comparable<? super K> k = (Comparable<? super K>) key;
            do {
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        Entry<K,V> e = new Entry<>(key, value, parent);
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }

    从这段代码,先总结一下TreeMap添加数据的几个步骤:

    1. 获取根节点,根节点为空,产生一个根节点,将其着色为黑色,退出余下流程
    2. 获取比较器,如果传入的Comparator接口不为空,使用传入的Comparator接口实现类进行比较;如果传入的Comparator接口为空,将Key强转为Comparable接口进行比较
    3. 从根节点开始逐一依照规定的排序算法进行比较,取比较值cmp,如果cmp=0,表示插入的Key已存在;如果cmp>0,取当前节点的右子节点;如果cmp<0,取当前节点的左子节点
    4. 排除插入的Key已存在的情况,第(3)步的比较一直比较到当前节点t的左子节点或右子节点为null,此时t就是我们寻找到的节点,cmp>0则准备往t的右子节点插入新节点,cmp<0则准备往t的左子节点插入新节点
    5. new出一个新节点,默认为黑色,根据cmp的值向t的左边或者右边进行插入
    6. 插入之后进行修复,包括左旋、右旋、重新着色这些操作,让树保持平衡性

    第1~第5步都没有什么问题,红黑树最核心的应当是第6步插入数据之后进行的修复工作,对应的Java代码是TreeMap中的fixAfterInsertion方法,下面看一下put每个数据之后TreeMap都做了什么操作,借此来理清TreeMap的实现原理。

    put(10, "10")

    首先是put(10, "10"),由于此时TreeMap中没有任何节点,因此10为根且根节点为黑色节点,put(10, "10")之后的数据结构为:

    put(85, "85")

    接着是put(85, "85"),这一步也不难,85比10大,因此在10的右节点上,但是由于85不是根节点,因此会执行fixAfterInsertion方法进行数据修正,看一下fixAfterInsertion方法代码实现:

    private void fixAfterInsertion(Entry<K,V> x) {
        x.color = RED;
    
        while (x != null && x != root && x.parent.color == RED) {
            if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
                Entry<K,V> y = rightOf(parentOf(parentOf(x)));
                if (colorOf(y) == RED) {
                    setColor(parentOf(x), BLACK);
                    setColor(y, BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    x = parentOf(parentOf(x));
                } else {
                    if (x == rightOf(parentOf(x))) {
                        x = parentOf(x);
                        rotateLeft(x);
                    }
                    setColor(parentOf(x), BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    rotateRight(parentOf(parentOf(x)));
                }
            } else {
                Entry<K,V> y = leftOf(parentOf(parentOf(x)));
                if (colorOf(y) == RED) {
                    setColor(parentOf(x), BLACK);
                    setColor(y, BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    x = parentOf(parentOf(x));
                } else {
                    if (x == leftOf(parentOf(x))) {
                        x = parentOf(x);
                        rotateRight(x);
                    }
                    setColor(parentOf(x), BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    rotateLeft(parentOf(parentOf(x)));
                }
            }
        }
        root.color = BLACK;
    }

    我们看第2行的代码,它将默认的插入的那个节点着色成为红色,这很好理解:

    根据红黑树的性质(3),红黑树要求从根节点到叶子所有叶子节点上经过的黑色节点个数是相同的,因此如果插入的节点着色为黑色,那必然有可能导致某条路径上的黑色节点数量大于其他路径上的黑色节点数量,因此默认插入的节点必须是红色的,以此来维持红黑树的性质(3)

    当然插入节点着色为红色节点后,有可能导致的问题是违反性质(2),即出现连续两个红色节点,这就需要通过旋转操作去改变树的结构,解决这个问题。

    接着看第4行的判断,前两个条件都满足,但是因为85这个节点的父节点是根节点的,根节点是黑色节点,因此这个条件不满足,while循环不进去,直接执行一次30行的代码给根节点着色为黑色(因为在旋转过程中有可能导致根节点为红色,而红黑树的根节点必须是黑色,因此最后不管根节点是不是黑色,都要重新着色确保根节点是黑色的)。

    那么put(85, "85")之后,整个树的结构变为:

    fixAfterInsertion方法流程

    在看put(15, "15")之前,必须要先过一下fixAfterInsertion方法。第5行~第21行的代码和第21行~第38行的代码是一样的,无非一个是操作左子树另一个是操作右子树而已,因此就看前一半:

    while (x != null && x != root && x.parent.color == RED) {
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
            Entry<K,V> y = rightOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {
                if (x == rightOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateLeft(x);
                }
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateRight(parentOf(parentOf(x)));
            }
        }
        ....
    }

    第2行的判断注意一下,用语言描述出来就是:判断当前节点的父节点与当前节点的父节点的父节点的左子节点是否同一个节点。翻译一下就是:当前节点是否左子节点插入,关于这个不明白的我就不解释了,可以自己多思考一下。对这整段代码我用流程图描述一下:

    这里有一个左子树内侧插入与左子树点外侧插入的概念,我用图表示一下:

    其中左边的是左子树外侧插入,右边的是左子树内侧插入,可以从上面的流程图上看到,对于这两种插入方式的处理是不同的,区别是后者也就是左子树内侧插入多一步左旋操作

    能看出,红黑树的插入最多只需要进行两次旋转,至于红黑树的旋转,后面结合代码进行讲解。

    put(15, "15")

    看完fixAfterInsertion方法流程之后,继续添加数据,这次添加的是put(15, "15"),15比10大且比85小,因此15最终应当是85的左子节点,默认插入的是红色节点,因此首先将15作为红色节点插入85的左子节点后的结构应当是:

    但是显然这里违反了红黑树的性质(2),即连续出现了两个红色节点,因此此时必须进行旋转。回看前面fixAfterInsertion的流程,上面演示的是左子树插入流程,右子树一样,可以看到这是右子树内侧插入,需要进行两次旋转操作:

    1. 对新插入节点的父节点进行一次右旋操作
    2. 新插入节点的父节点着色为黑色,新插入节点的祖父节点着色为红色
    3. 对新插入节点的祖父节点进行一次左旋操作

    旋转是红黑树中最难理解也是最核心的操作,右旋和左旋是对称的操作,我个人的理解,以右旋为例,对某个节点x进行右旋,其实质是:

    • 降低左子树的高度,增加右子树的高度
    • 将x变为当前位置的右子节点

    左旋是同样的道理,在旋转的时候一定要记住这两句话,这将会帮助我们清楚地知道在不同的场景下旋转如何进行。

    先看一下(1)也就是"对新插入节点的父节点进行一次右旋操作",源代码为rotateRight方法:

    private void rotateRight(Entry<K,V> p) {
        if (p != null) {
            Entry<K,V> l = p.left;
            p.left = l.right;
            if (l.right != null) l.right.parent = p;
            l.parent = p.parent;
            if (p.parent == null)
               root = l;
            else if (p.parent.right == p)
                p.parent.right = l;
            else p.parent.left = l;
            l.right = p;
            p.parent = l;
        }
    }

    右旋流程用流程图画一下其流程:

    再用一张示例图表示一下右旋各节点的变化,旋转不会改变节点颜色,这里就不区分红色节点和黑色节点了,a是需要进行右旋的节点:

    左旋与右旋是一个对称的操作,大家可以试试看把右图的b节点进行左旋,就变成了左图了。这里多说一句,旋转一定要说明是对哪个节点进行旋转,网上看很多文章讲左旋、右旋都是直接说旋转之后怎么样怎么样,我认为脱离具体的节点讲旋转是没有任何意义的。

    这里可能会有的一个问题是:b有左右两个子节点分别为d和e,为什么右旋的时候要将右子节点e拿到a的左子节点而不是b的左子节点d?

    一个很简单的解释是:如果将b的左子节点d拿到a的左子节点,那么b右旋后右子节点指向a,b原来的右子节点e就成为了一个游离的节点,游离于整个数据结构之外

    回到实际的例子,对85这个节点进行右旋之后还有一次着色操作(2),分别是将x的父节点着色为黑色,将x的祖父节点着色为红色,那么此时的树形结构应当为:

    然后对节点10进行一次左旋操作(3),左旋之后的结构为:

    最后不管根节点是不是黑色,都将根节点着色为黑色,那么插入15之后的数据结构就变为了上图,满足红黑树的三条特性。

    put(70, "70")

    put(70, "70")就很简单了,70是85的左子节点,由于70的父节点以及叔父节点都是红色节点,因此直接将70的父节点85、将70的叔父节点10着色为黑色即可,70这个节点着色为红色,即满足红黑树的特性,插入70之后的结构图为:

    put(20, "20")

    put(20, "20"),插入的位置应当是70的左子节点,默认插入红色,插入之后的结构图为:

    问题很明显,出现了连续两个红色节点,20的插入位置是一种左子树外侧插入的场景,因此只需要进行着色+对节点85进行一次右旋即可,着色+右旋之后数据结构变为:

    put(60, "60")

    下面进行put(60, "60")操作,节点60插入的位置是节点20的右子节点,由于节点60的父节点与叔父节点都是红色节点,因此只需要将节点60的父节点与叔父节点着色为黑色,将节点60的组父节点着色为红色即可。

    那么put(60, "60")之后的结构为:

    put(30, "30")

    put(30, "30"),节点30应当为节点60的左子节点,因此插入节点30之后应该是这样的:

    显然这里违反了红黑树性质(2)即连续出现了两个红色节点,因此这里要进行旋转。

    put(30, "30")的操作和put(15, "15")的操作类似,同样是右子树内侧插入的场景,那么需要进行两次旋转:

    1. 对节点30的父节点节点60进行一次右旋
    2. 右旋之后对节点60的祖父节点20进行一次左旋

    右旋+着色+左旋之后,put(30, "30")的结果应当为:

     

    put(50, "50")

    下一个操作是put(50, "50"),节点50是节点60的左子节点,由于节点50的父亲节点与叔父节点都是红色节点,因此只需要将节点50的父亲节点与叔父节点着色为黑色,将节点50的祖父节点着色为红色即可:

    节点50的父节点与叔父节点都是红色节点(注意不要被上图迷糊了!上图是重新着色之后的结构而不是重新着色之前的结构,重新着色之前的结构为上上图),因此插入节点50只需要进行着色,本身这样的操作是没有任何问题的,但问题的关键在于,着色之后出现了连续的红色节点,即节点30与节点70。这就是为什么fixAfterInsertion方法的方法体是while循环的原因:

    private void fixAfterInsertion(Entry<K,V> x) {
        x.color = RED;
    
        while (x != null && x != root && x.parent.color == RED) {
        ...
        }
    }

    因为这种着色方式是将插入节点的祖父节点着色为红色,因此着色之后必须将当前节点指向插入节点的祖父节点,判断祖父节点与父节点是否连续红色的节点,是就进行旋转,重新让红黑树平衡。

    接下来的问题就是怎么旋转了。我们可以把节点15-->节点70-->节点30连起来看,是不是很熟悉?这就是上面重复了两次的右子树内侧插入的场景,那么首先对节点70进行右旋,右旋后的结果为:

    下一步,节点70的父节点着色为黑色,节点70的祖父节点着色为红色(这一步不理解或者忘了为什么的,可以去看一下之前对于fixAfterInsertion方法的解读),重新着色后的结构为:

    最后一步,对节点70的父节点节点15进行一次左旋,左旋之后的结构为:

    重新恢复红黑树的性质:

    1. 根节点为黑色节点
    2. 没有连续红色节点
    3. 根节点到所有叶子节点经过的黑色节点都是2个

    ----------------------------------------------

     

    本文先研究一下红黑树的移除操作是如何实现的,移除操作比较复杂,具体移除的操作要进行几次旋转和移除的节点在红黑树中的位置有关,这里也不特意按照旋转次数选择节点了,就找三种位置举例演示红黑树移除操作如何进行:

    • 移除根节点,例子就是移除节点30
    • 移除中间节点,例子就是移除节点70
    • 移除最底下节点,例子就是移除节点85

    首先来过一下TreeMap的remove方法:

    public V remove(Object key) {
        Entry<K,V> p = getEntry(key);
        if (p == null)
            return null;
    
        V oldValue = p.value;
        deleteEntry(p);
        return oldValue;
    }

    第2行的代码是获取待移除的节点Entry,做法很简单,拿key与当前节点按指定算法做一个比较获取cmp,cmp=0表示当前节点就是待移除的节点;cmp>0,取右子节点继续比较;cmp<0,取左子节点继续比较。

    接着重点跟一下第7行的deleteEntry方法:

    private void deleteEntry(Entry<K,V> p) {
        modCount++;
        size--;
    
        // If strictly internal, copy successor's element to p and then make p
        // point to successor.
        if (p.left != null && p.right != null) {
            Entry<K,V> s = successor(p);
            p.key = s.key;
            p.value = s.value;
            p = s;
        } // p has 2 children
    
        // Start fixup at replacement node, if it exists.
        Entry<K,V> replacement = (p.left != null ? p.left : p.right);
    
        if (replacement != null) {
            // Link replacement to parent
            replacement.parent = p.parent;
            if (p.parent == null)
                root = replacement;
            else if (p == p.parent.left)
                p.parent.left  = replacement;
            else
                p.parent.right = replacement;
    
            // Null out links so they are OK to use by fixAfterDeletion.
            p.left = p.right = p.parent = null;
    
            // Fix replacement
            if (p.color == BLACK)
                fixAfterDeletion(replacement);
        } else if (p.parent == null) { // return if we are the only node.
            root = null;
        } else { //  No children. Use self as phantom replacement and unlink.
            if (p.color == BLACK)
                fixAfterDeletion(p);
    
            if (p.parent != null) {
                if (p == p.parent.left)
                    p.parent.left = null;
                else if (p == p.parent.right)
                    p.parent.right = null;
                p.parent = null;
            }
        }
    }

    用流程图整理一下这里的逻辑:

    下面结合实际代码来看下。

    移除根节点

    根据上面的流程图,根节点30左右子节点不为空,因此要先选择继承者,选择继承者的流程为:

    分点整理一下移除节点30做了什么:

    1. 由于节点30的右子节点不为空,因此从节点70开始不断取左子节点直到取到叶子节点为止,最终取到的节点s为节点50
    2. p的key=s的key即50,p的value=s的value即50,由于此时p指向的是root节点,因此root节点的key和value变化,变为50-->50
    3. p=s,即p原来指向的是root节点,现在p指向s节点,p与s指向同一份内存空间,即节点50
    4. 接着选择replacement,由于p与s指向同一份内存空间,因此replacement判断的是s是否有左子节点,显然s没有,因此replacement为空
    5. replacement为空,但是p有父节点,因此可以判断出来p也就是节点50不是root节点
    6. 接着根据流程图可知,节点p是一个红色节点,这里不需要进行移除数据修正
    7. 最后节点p是其父节点的左子节点,因此节点p的左子节点置为null,再将p的父节点置为null,相当于把节点p移除

    经过上述流程,移除根节点30之后的数据结构如下图:

     

    移除中间节点

    接着看一下移除中间节点TreeMap是怎么做的,这里以移除节点70为例,继续分点整理一下移除节点70做了什么:

    1. 节点70有左右子节点,因此还是选择继承者,由于节点70的右子节点85没有左子节点,因此选出来的继承者就是节点85
    2. p的key=s的key即85,p的value=s的value即85,此时p指向的是节点70,因此节点70的key与value都变为85
    3. key与value赋值完毕后执行p=s,此时p指向节点85
    4. 接着选择replacement,由于85没有左右子节点,因此replacement为null
    5. replacement为null且节点p即节点85有父节点,根据流程图可知,节点p是一个黑色节点,因此需要进行删除数据修正
    6. 最后节点p是其父节点的右子节点,因此节点p的右子节点置为null,再将p的父节点置为null,相当于把节点p移除

    总体流程和移除根节点差不多,唯一的区别是节点85是一个黑色节点,因此需要进行一次删除数据修正操作。删除数据修正实现为fixAfterDeletion方法,它的源码:

    private void fixAfterDeletion(Entry<K,V> x) {
        while (x != root && colorOf(x) == BLACK) {
            if (x == leftOf(parentOf(x))) {
                Entry<K,V> sib = rightOf(parentOf(x));
    
                if (colorOf(sib) == RED) {
                    setColor(sib, BLACK);
                    setColor(parentOf(x), RED);
                    rotateLeft(parentOf(x));
                    sib = rightOf(parentOf(x));
                }
    
                if (colorOf(leftOf(sib))  == BLACK &&
                    colorOf(rightOf(sib)) == BLACK) {
                    setColor(sib, RED);
                    x = parentOf(x);
                } else {
                    if (colorOf(rightOf(sib)) == BLACK) {
                        setColor(leftOf(sib), BLACK);
                        setColor(sib, RED);
                        rotateRight(sib);
                        sib = rightOf(parentOf(x));
                    }
                    setColor(sib, colorOf(parentOf(x)));
                    setColor(parentOf(x), BLACK);
                    setColor(rightOf(sib), BLACK);
                    rotateLeft(parentOf(x));
                    x = root;
                }
            } else { // symmetric
                Entry<K,V> sib = leftOf(parentOf(x));
    
                if (colorOf(sib) == RED) {
                    setColor(sib, BLACK);
                    setColor(parentOf(x), RED);
                    rotateRight(parentOf(x));
                    sib = leftOf(parentOf(x));
                }
    
                if (colorOf(rightOf(sib)) == BLACK &&
                    colorOf(leftOf(sib)) == BLACK) {
                    setColor(sib, RED);
                    x = parentOf(x);
                } else {
                    if (colorOf(leftOf(sib)) == BLACK) {
                        setColor(rightOf(sib), BLACK);
                        setColor(sib, RED);
                        rotateLeft(sib);
                        sib = leftOf(parentOf(x));
                    }
                    setColor(sib, colorOf(parentOf(x)));
                    setColor(parentOf(x), BLACK);
                    setColor(leftOf(sib), BLACK);
                    rotateRight(parentOf(x));
                    x = root;
                }
            }
        }
    
        setColor(x, BLACK);
    }

    方法第3行~第30行与第30行~第57行是对称的,因此只分析一下前半部分也就是第3行~第30行的代码。第三行的代码"x == leftOf(parentOf(x))"很显然判断的是x是否其父节点的左子节点。其流程图为:

    从上图中,首先可以得出一个重要的结论:红黑树移除节点最多需要三次旋转

    先看一下删除数据修正之前的结构图:

    p指向右下角的黑色节点85,对此节点进行修正,上面的流程图是p是父节点的左子节点的流程,这里的p是父节点的右子节点,没太大区别。

    sib取父节点的左子节点即节点60,节点60是一个黑色节点,因此这里不需要进行一次旋转。

    接着,sib的左右子节点不是黑色节点且sib的左子节点为红色节点,因此这里只需要进行一次旋转的流程:

    1. 将sib着色为它父节点的颜色
    2. p的父节点着色为黑色
    3. sib的左子节点着色为黑色
    4. p的父节点右旋

    经过这样四步操作之后,红黑树的结构变为:

    最后一步的操作在fixAfterDeletion方法的外层,节点85的父节点不为空,因此将节点85的父节点置空,最终移除节点70之后的数据结构为:

     

    移除最底下节点

    最后看看移除最底下节点的场景,以移除节点85为例,节点85根据代码以节点p称呼。

    节点p没有左右子节点,因此节点p不需要进行选择继承者的操作;同样的由于节点p没有左右子节点,因此选择出来的replacement为null。

    接着由于replacement为null但是节点p是一个黑色节点,黑色节点需要进行删除修正流程:

    1. 节点p是父节点的右子节点,那么节点sib为父节点的左子节点50
    2. sib是黑色的,因此不需要进行一次右旋
    3. sib的左子节点是红色的,因此这里需要进行的操作是将sib着色为p父节点的颜色红色、将p的父节点着色为黑色、将sib的左子节点着色为黑色、将p的父节点进行一次右旋

    这么做之后,树形结构变为:

    最后还是一样,回到fixAfterDeletion方法外层的代码,将p的父节点置为null,即节点p就不在当前数据结构中了,完成移除,红黑树最终的结构为:

     

    展开全文
  • XSKY解读FAST'20 论文 How to Copy File 《关于如何高效率对文件目录进行快速克隆操作》01导读这篇发表于FAST20会议论文,是关于如何高效率对文件目录进行快速克隆操作,由来自北卡罗来纳大学教堂山分校...

    XSKY解读FAST'20 论文 How to Copy File 《关于如何高效率的对文件目录树进行快速克隆操作》

    01导读

    这篇发表于FAST20会议的论文,是关于如何高效率的对文件目录树进行快速克隆操作,由来自北卡罗来纳大学教堂山分校的Yang Zhan,Yizheng Jiao以及 罗格斯大学,佩斯大学,石溪大学,VMWare研究中心的相关研究人员合作开发完成的。

    本文并非是这篇论文的完整翻译稿,只是对里面的一些重点内容进行解读,有些地方解读不一定准确,建议感兴趣的同学结合原版论文一起阅读,以帮助大家拓宽思路。

    文章中所用图表,除非特别注明,都来自于原版论文。

    02概述

    作者在一开始先介绍了快速克隆的背景和重要性。随着虚拟化的广为流行,各种应用对快速克隆都有着很强的需求,典型的,如快速创建虚拟机,就需要快速克隆出虚拟机的"root filesystem"即一个image磁盘文件。而在容器场景下,如docker会非常频繁的对一个特定的文件系统目录树进行快速拷贝,这些都需要高效的克隆机制。

    针对于这些应用场景,现有的文件系统已经实现了一些"逻辑拷贝"功能,有别于"物理拷贝",逻辑拷贝一般在实现时只进行一些元数据级别的拷贝,而只有在后续的修改中,才按需对文件数据进行拷贝并修改,这种功能称作COW(copy-on-write),这种方法在拷贝的时效性和空间的利用率方面都得到了较大的提升,因此现在已经成为克隆的基础技术。在实现时,一般存在着基于block粒度的COW和基于file或者dir级别的COW,比如btrfs和xfs使用的cp –reflink技术。

    这里作者指出,对于经典的COW技术,主要存在着"拷贝粒度"的问题,比如对于基于file级别的COW,一次微小的修改就可能导致昂贵的拷贝,比如1G大小的文件,只修改其中的1个字节,也会触发1G文件的拷贝。这会极大的增加初次COW写入时延,而且也不可避免的造成了空间上的浪费。反之,如果拷贝粒度过小,则初次COW写入时延有保证,但却容易造成碎片化(想象一下1个很大的文件,4K拷贝粒度,随机写入则会造成很多个4K COW块),后续顺序读的时候,因为这些4K数据并不是连续的,则读取速度会很慢。因此这里作者提出了自己对高效克隆的看法,需要满足如下4个特性才能被称作是合格的,作者称为"Nimble clones (敏捷克隆)"

    · 必须能快速的完成克隆操作。

    · 必须有良好的read locality (读取局部性),这样逻辑上相关的文件集读取起来会比较快,同时经过COW后,性能也应该保持一致。

    · 必须有良好的写性能,不管是对克隆前的文件集和克隆后的文件集进行写入。

    · 空间利用率必须要好。写放大应该尽量保持比较低的水平。

    作者在图1举例了现有的几种支持COW文件系统在多次克隆操作并且修改其中一小部分内容后,使用grep查询文件内容的衰减情况:

    f9f2930885ba8c284a1d7d93ba27d8e3.png

    从图中可以看出,在每次克隆和修改之后,读性能都会衰减。看XFS和ZFS的结果,16轮后大概有3~5倍的衰减。Btrfs表现的好一些,大概只有50%的衰减。总体来看,这几个文件系统都出现性能单调递减的特征。

    因此作者认为,这里的关键之处是应该将COW中的copy和write的大小进行解耦,即不应该使用一样的大小,如果是进行大的文件修改,那copy大块然后再覆盖写大块当然是合理的,但是如果是微小的修改,显然,应该将这次微小修改暂存起来,让多次微小修改进行聚合,在达到一定数量后,再批量处理显然会更合理一些。

    这篇论文在现有的BetrFS基础上,实现了一种高效的克隆机制,以同时满足前述的Nimble clones需要具备的特征。作者引入了称作CAW(Copy-on-Abundant-Write)的技术,以暂存微小数据修改,等合适的时机再进行COW。另外,这篇论文在3方面对原来的Bε-tree数据结构进行了改进与增强,1.将原来的Bε-tree树结构改造成Bε-DAG结构(directed acyclic graph,有向无环图),以满足对整棵树进行更好的遍历。2.引入了GOTO message,可以快速的持久化克隆操作。3.引入"translation prefix(前缀转换)",用来满足对"延后数据拷贝"和 部分共享数据的查询。在引入这些优化和改进后,实验结果显示,对不同的模型,至少有33%到6.8倍的性能提升。

    论文的贡献点归结为:

    · 设计和实现了Bε-DAG数据结构,作为Nimble clones的基础。该方法扩展了Bε-tree,用来聚集小的修改,再择机进行批量写入。

    · 写优化的克隆实现。在进行克隆操作时,仅需简单的向DAG root节点写入一个GOTO message消息。

    · 量化的渐进分析表明,增加克隆不会影响其它的操作。克隆算法开销是对数级别的。

    · 全面的测试表明,优化过的BetrFS并没有对原来的BetrFS基线产生不利的影响,而在clone特性上,对比传统的支持克隆特性的文件系统,在性能上有3-4倍的提高,而对比不支持克隆特性的文件系统,则有2个数量级的提高。

    03BetrFS背景知识

    为深入理解这篇论文,需要先理解BetrFS的背景知识。BetrFS是该团队开发的一个用于研究型的文件系统,从2015年到现在,作者团队已经基于该文件系统发布了多篇论文,详情请参考BetrFS官网。

    BetrFS是一个内核态的基于KV存储的本地文件系统。不同于传统的文件系统,如XFS,Ext4,这些文件系统都是基于inode和B-tree(或B-tree变体)来管理和组织元数据和文件系统数据的。而BetrFS是基于Key-Value的,它有2个KV stores。其中,元数据KV存储的是 文件全路径(fullpath) 到 文件系统元数据(struct stat)的映射。数据KV 存储的是 {fullpath+block number} 到 4K block的映射。

    8d728a67d55576715c73aabd0fd83600.png
    展开全文
  • 在本篇文章里我们给读者们分享了关于python如何实现决策算法相关知识点内容,需要朋友们参考下。
  • 虽然平衡二叉树支持范围查询,但是这这种数据结构要范围查找要往回找,即回溯到父结点,而B+树的 叶子结点的指针的效率则更高。 3、为什么选择B树的一个结点存多个元素的结构? 因为数据库的索引是存储在文件中的,...

    1、为什么不用Hash表作为索引?

    Hash表进行范围查询比较困难,如select * from sanguo where id >10;

    2、为什么不用平衡二叉树作为索引?

    虽然平衡二叉树支持范围查询,但是这这种数据结构要范围查找要往回找,即回溯到父结点,而B+树的 叶子结点的指针的效率则更高。

    3、为什么选择B树的一个结点存多个元素的结构?

    因为数据库的索引是存储在文件中的,而读取文件内容又要进行磁盘I/O操作,普通树的结 点只有一个元素,进行磁盘I/O的次数很多,而B树的一节点多数据的结构减少了磁 盘I/O的次数,提高了查找效率。

    4、磁盘存取数据的局部性原理

    某个数据被取出,那么该数据的周围一定会被用到。

    5、操作系统存储数据的单位

    操作系统是按照页为单位存取数据的,1页默认为4KB

    6、一个结点里面应该存多少个元素?或者说一个结点应该多大?

    因为操作上系统是按页为单位存取的,因此为了避免数据的浪费,一个结点的大小应该为页的整数倍。MySQL数据库的一页大小为16KB,因此为一个结点应为4页。

    7、MySQL的B+树为什么不在非叶子结点存储数据?

    MySQL中B+树的一个结点的大小刚好为数据库的一页的大小,如果存储了数据,那么 存储的索引数就会减少,从而促使整颗B+数变高,从而增加了磁盘I/O次数,降低了查找效率。

    8、MyISAM和InnoDB的主键索引B+树的区别?

    MyISAM的B+树索引中的叶子节点存储的是数据的地址,而InnoDB引擎中B+树的叶子 节点中则直接存的是数据,这样可以减少一次磁盘I/O操作。

    9、MyISAM和InnoDB的辅助索引和辅助索引B+树结构的区别?

    MyISAN的辅助索引的存储结构与主键索引相同,而InnoDB的辅助索引的B+树的叶子 结点没有存储所有的数据,而是存储了每行数据的主键,如果表中没有创建主键,InnoDB会自己创建一个隐藏的默认主键存储。

    10、MySQL的一页的默认值为什么为16KB?

    假设一行数据为1KB大小,那么B+树的一个叶子结点可以存16行(16KB/1KB)数据, 非叶子结点只存储了索引值和指针,主键索引在InnoDB默认为bigInt类型(8B),一个 指针的大小为6B,因此一个非叶子结点可存储1170对索引+指针,B+树高度为2时, 叶子结点的个数为117016条数据,当为高度为3时,可存储11701170*3条数据。 一页的数据为16KB已经足够。

    11、联合索引的存储

    联合索引是将多个索引拼接起来来构建B+树的。

    12、如何判断能不能用到索引?

    如果到使用B+树的结点能帮助缩小查询范围,那么就能用到索引,如果查询条件不能 用到B+树的结点来缩小查询范围,那么就是用不到索引。因此联合索引查询要遵循最左前缀原则,如果不使用最左前缀原则,那么就用不到联合索引。

    13、最左前缀原则

    如果对表中的字段a、b、c建立联合索引,且顺序为a、b、c。

    select * from table where a = 1 ;
    select * from table where a = 1 and b = 1;
    select * from table where a = 1 and b = 1 and c = 1;
    select * from table where a = 1 and c = 1;
    

    采用以上字段进行查询的sql语句都会使用到索引,但是最后一个sql语句略有不同,虽然根据a、c字段联合查询,但是它只用到了a的索引,使用索引的结果就等效于第一句的情况,也就是说c = 1并没有用到联合索引。

    而b、bc、c字段单独使用则不会用到联合索引。

    展开全文
  • 2-3树、2-3-4树 定义:直接你看网上的各种文档,对于2-3的定义晦涩难懂,我们...那么我们队这个定义进行一个解读:二叉排序树本身就是左子树的值小于根节点的值,右子树的值大于根节点的值的一种二叉树,换句话说...
  • 上周末,我们已经提前分析了神武第一个新门派“无名谷”所有门派技能、御魂技能和星穹效果,本期有会根据昨晚官方爆料相关内容进行修正和补充。上期链接:神武新门派—无名谷,技能细节及初步解读(没看过上期...
  • 今天起我会开一个关于机器学习基础知识分享专题,这篇文章是第一篇。今天分享一篇Boosting一类算法早期核心论文解读,是GBDT等算法奠基性文章。很多同学都读过xgboost和li...
  • 要解决上面这两个问题,需要一个衡量人能力标准,这个标准不仅适用于招聘,同样也适用于考核、职等评定等,我叫这种标准为技能。 这里所说技能,不仅包含技术能力,还包括工作能力。我始终认为一个人...
  • 在今年ICRA的关于腿足式机器人Workshop中,来自宇科技Speaker王兴兴( @王兴) 展示了其新四足机器人产品AlienGo部分性能和设计细节,作者当时就对这款新机器人很有兴趣,遂写了如下文章做一个简要设计...
  • HashMap中resize()方法源码解读(基于jdk1.8) ...然后就是扩容(关于扩容本次仅讲解一下链表相关操作,红黑部分,后续有时间会继续进行讲解)(具体讲解可以继续往下看,话不多说看源码) resize第一步:确
  • 本篇文章给大家带来内容是关于mysql索引和事务详细解读,有一定参考价值,有需要朋友可以参考一下,希望对你有所帮助。一、索引是做什么?很多时候,当你应用程序进行SQL查询速度很慢时,应该想想是否...
  • ML之XGBoost:《XGBoost: A Scalable Tree ...更重要是,我们提供了关于缓存访问模式、数据压缩和分片见解,以构建一个可伸缩的树增强系统。通过结合这些见解,XGBoost可以使用比现有系统少得多资源来扩展
  • HashMap 深度解读

    2020-07-21 22:03:57
    ​ HashMap 是一个非常重要类,在面试中百问不爽,下面我们就来捋一捋关于HashMap知识点,以下讲述主要基于Java8。 1. 底层结构 ​ 在 Java7 中,HashMap 底层结构是数组 + 链表,但是在Java8 后,这个结构...
  • c4.5算法解读

    千次阅读 2018-11-09 20:33:24
    C4.5算法是用于生成决策树的一种经典算法,是ID3算法的一种延伸和优化。 所以要介绍C4.5算法,就要把ID3,以及ID3中设计的熵的概念一起进行讲解。 关于熵的概念在溯源探幽--熵的世界文章中做了很详细的介绍,所以....
  • JDK 8 HashMap源码解读

    2020-08-01 21:54:48
    树的相关知识只作为回顾,不会详细说明。 树 树: 有且仅有一个特定的成为根的节点 当n>1时,其余节点可分为m(m>0)个互不相交的有限集 T1、T2、…、Tn,其中每一个集合本身又是一棵树,并且称为根的子树。 ...
  • 上篇文章我们介绍了 HashMap 的主要特点和关键方法源码解读,这篇文章我们介绍 HashMap 在 JDK1.8 新增树...传统 HashMap 的缺点HashMap 在 JDK 18 中新增的数据结构 红黑树HashMap 中关于红黑树的三个关键参数HashM
  • 关于spss软件操作,pdf格式,关于决策分析结果详细解读,有利于深刻认识是spss决策算法。
  • 数据结构关于二叉树建立遍历以及应用二叉树进行编解码 实验要求 必做部分 1. 小明会按照前序方式输入一棵二叉树。例如,输入$ACG##H##D##BE#I##F##话,代表了下面这棵: 2. 请分别按照前序、中序、后序...
  • 本文会从JDK1.7和1.8两个版本hashmap着手分析,其中主要是分析了hashMap初始化过程,putVal过程,扩容过程,化过程。不到之处,欢迎大家指正。 如果想仔细了解红黑相关...3.JDK1.7头插法会产生,那关于头插.
  • 遍历Dom:先序遍历DOM树的5种方法! 三层架构+m v c +mvp+m v vm()+MVC,MVP 和 MVVM 的图示 剖析vue MVVM实现原理 控制器(controller):angularJS概念理解三:控制器 构造器+生命周期:Vue学习-构造器 +关于Vue....
  • 关于已发布标准勘误表,我们特别邀请到——SGS技术专家及E-FMEA项目经理,为大家详细解读勘误细则,干货内容火热出炉!AIAG VDA FMEA手册,章节1.4.1修正:DFMEA用于分析如框图/边界图或结构所示边界中所定义...
  • 关于题意的解读 其实,题目差不多就是让我们求逆序对(只不过每个逆序对有一个权值)。 这会让我们联想起一道题目:【洛谷3157】[CQOI2011] 动态逆序对。 这两道题目似乎只有以下几点不同: ...
  • 关于wiki上的解读,之前做了一次简单的翻译,根据此文档,详细研读了源代码,先把核心思想呈现出来。基本流程如下:当用户输入搜索词语前缀时,通过前端调用solr的suggest,找到Suggeser对象,Suggester...
  • 共7440字,阅读约20分钟01导读这篇发表于FAST20会议论文,是关于如何高效率对文件目录进行快速克隆操作,由来自北卡罗来纳大学教堂山分校Yang Zhan,Yizheng Jiao以及 罗格斯大学,佩斯大学,石溪大学,...
  • 关于DOM,我们了解了可以用DOM操纵HTML的一些属性和样式,还... 不过在使用DOM动态操纵HTML元素之前,我们还是先了解一下DOM树,下面是我从网上找的一个DOM树的图片,它的截图如下:  如果大家学习过“树”这
  • java.util.HashMap 是JDK里散列的一个实现,JDK6里采用位桶+链表的形式实现,Java8里采用的是位桶+链表/红黑树的方式,非线程安全。关于散列可以看这篇文章,   这篇文章主要是对JDK6和Java8里java.util.HashMap...
  • 关于asm

    2016-08-26 23:14:22
    asm解读   目的: 程序分析:用于分析程序,动态生成proxy等。 程序生成:可在内存中生成java类并编译,所谓的just in time ...基于事件的就类似于xml的SAX,而基于树的就像DOM.这2种 API都有各自的有点与缺点...

空空如也

空空如也

1 2 3 4
收藏数 69
精华内容 27
关键字:

关于树的解读