&p&常言道，师傅领进门，修行靠个人，相信很多人或多或少是在别人的建议或带领下步入深度学习这个大坑，然后师傅说深度学习是个玄学，后面就靠个人修行，瞬间就懵了对不对？可能后面经过自己不断实验积累相关经验，会有一些自己的学习心得。本文可谓是深度学习中的一份秘籍，帮助你少走一些弯路。在本文中，列举了一些常用的机器学习的训练技巧，目的是对这些技巧进行简单的介绍并说明它们的工作原理。另外一些建议是斯坦福的&u&&a href=&/?target=http%3A//cs231n.github.io/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&CS231n&i class=&icon-external&&&/i&&/a&&/u&课程及之前总结的&u&&a href=&/?target=https%3A///Conchylicultor/Deep-Learning-Tricks/blob/master/networks.md& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&网络结构&i class=&icon-external&&&/i&&/a&&/u&。&/p&&p&本文的目录如下：&/p&&ul&&li&数据预处理&/li&&li&初始化&/li&&li&训练&/li&&li&正则化&/li&&li&网络结构&/li&&li&自然语言处理&/li&&li&增强学习&/li&&li&网络压缩&br&&/li&&/ul&&h2&&b&数据预处理&/b&&/h2&&p&（本部分原作者没有写，以个人的理解及相关补充这部分内容）&/p&&p&&b&What&/b&：输入神经网络数据的好坏直接关系着网络训练结果，一般需要对数据进行预处理，常用的数据预处理方式有：&/p&&p&&br&&/p&&ul&&li&去均值：每个原始数据减去全部数据的均值，即把输入数据各个维度的数据都中心化到0； &/li&&li&归一化：一种方式是使用去均值后的数据除以标准差，另外一种方式是全部数据都除以数据绝对值的最大值；&br&&/li&&li&PCA/白化：这是另外一种形式的数据预处理方式，一种方式是降维处理，另外一种是进行方差处理； &/li&&/ul&&p&&br&&/p&&p&&b&Why&/b&：通过对数据进行预处理能够使得它们对模型的影响具有同样的尺度或其他的一些目的。&/p&&p&&b&Ref&/b&：&u&&a href=&/?target=http%3A//cs231n.github.io/neural-networks-2/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&CS231n Convolutional Neural Networks for Visual Recognition.&i class=&icon-external&&&/i&&/a&&/u&&/p&&h2&&b&初始化&/b&&/h2&&p&&b&What&/b&：权重若初始化合理能够提升性能并加快训练速度，偏置一般设置为0，对于权重而言，建议统一到一定区间内：&/p&&p&&br&&/p&&ul&&li&对于线性层[1]：区间为[-v,v]，v = 1/sqrt(输入尺寸)，sqrt表示开根号； &/li&&li&对于卷积层[2]：区间为[-v,v]，v = 1/sqrt(卷积核的宽度x卷积核的高度x输入深度)； &/li&&li&批量标准化[3]在某些方面的应用降低了调整权值初始化的需要，一些研究结果页提出了相应的替代公式。 &/li&&/ul&&p&&br&&/p&&p&&b&Why&/b&：使用默认的初始化，每个神经元会随着输入数量的增多而存在一个方差，通过求根号缩放每个权重能确保神经元有近似的输出分布。&/p&&p&&b&Ref&/b&：&/p&&p&&br&&/p&&ul&&li&1.&u&&a href=&/?target=http%3A//www./pubs/192769/tricks-2012.pdf& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Stochastic Gradient Descent Tricks, Leon Bottou&i class=&icon-external&&&/i&&/a&&/u&； &/li&&li&2.在Torch中默认这么操作； &/li&&li&3.&u&&a href=&/?target=https%3A//arxiv.org/abs/%3Fspm%3D.blogcont.AWmFul%26file%3D& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift, S. Ioffe and C. Szegedy；&i class=&icon-external&&&/i&&/a&&/u&&/li&&/ul&&p&&br&&/p&&p&&b&What&/b&：对于长短期记忆网络（LSTM），遗忘偏置一般设置为1，可以加快训练过程。&/p&&p&&b&Why&/b&：直觉是训练开始时，想要信息在细胞之间传播，故不希望细胞忘记它的状态。&/p&&p&&b&Ref&/b&：&u&&a href=&/?target=http%3A//www.datascienceassn.org/sites/default/files/An%2520Empirical%2520Exploration%2520of%2520Recurrent%2520Network%2520Architectures.pdf%3Fspm%3D.blogcont.AWmFul%26file%3DAn%2520Empirical%2520Exploration%2520of%2520Recurrent%2520Network%2520Architectures.pdf& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&An Empirical Exploration of Recurrent Network Architectures, Rafal Jozefowicz et al.&i class=&icon-external&&&/i&&/a&&/u&&/p&&p&&br&&/p&&p&&b&What&/b&：对于t-分布领域嵌入算法（t-SNE），原作者建议对于大小为之间的数据集，将困惑度设置为5和50之间[1]，对于更大的数据集，相应的困惑度也会增。&/p&&p&&b&Why&/b&：困惑度决定了每个点的高斯分布的方差大小，更小的困惑度将获得更多的集群，大的困惑度与之相反，太大的困惑度没有任何意义；另外需要考虑的是画出的聚类不能保留原有的规模，聚类之间的距离不一定代表原始的空间几何，不同的困惑度能在数据结构上提供互补的信息，每次运行都会产生不同的结果[2]。&/p&&p&&b&Ref&/b&：&/p&&p&&br&&/p&&ul&&li&1.&u&&a href=&/?target=http%3A///s%3Fwd%3Dpaperuri%253A%d0e53d5d8ce70cf0dfdc3dfilter%3Dsc_long_sign%26tn%3DSE_xueshusource_2kduw22v%26sc_vurl%3Dhttp%253A%252F%%252Fdocument%252Fvid%252Fdb04eb2c-31d8-4ee3-abde-d422c86e2bc9%26ie%3Dutf-8%26sc_us%3D43442& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Visualizing High-Dimensional Data Using t-SNE, L.J.P. van der Maaten&i class=&icon-external&&&/i&&/a&&/u&. &/li&&li&2.&u&&a href=&/?target=http%3A//distill.pub/2016/misread-tsne/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&How to Use t-SNE Effectively, Wattenberg, et al., Distill, 2016.&i class=&icon-external&&&/i&&/a&&/u& &/li&&/ul&&p&&br&&/p&&h2&&b&训练&/b&&/h2&&p&&b&What&/b&：除了使用真值硬化目标外，同样可以使用软化目标（softmax输出）训练网络。&/p&&p&&b&Ref&/b&：&u&&a href=&/?target=https%3A//arxiv.org/abs/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Distilling the Knowledge in a Neural Network / Dark knowledge, G. Hinton et al.&i class=&icon-external&&&/i&&/a&&/u&&/p&&p&&br&&/p&&p&&b&What&/b&：学习率可能是需要调参中最重要的一个参数，一种策略是选择一些参数均有随机化学习率，并观察几次迭代后的测试误差。&/p&&img src=&/50/v2-832a0a34abcc59ee0561d_b.jpg& data-caption=&& data-rawwidth=&576& data-rawheight=&720& class=&origin_image zh-lightbox-thumb& width=&576& data-original=&/50/v2-832a0a34abcc59ee0561d_r.jpg&&&p&&b&Ref&/b&：Some advice for tuning the hyperparameters. Ref: Goodfellow et al 2016 Book&/p&&p&&br&&/p&&h2&&b&正则化&/b&&/h2&&p&&b&What：&/b&在RNN中使用Dropout，它仅仅应用于非循环连接[1]，但是一些最近的文章提出了一些技巧使得Dropout能应用于循环连接[2]。&/p&&p&&b&Ref&/b&：&/p&&p&&br&&/p&&ul&&li&1.&u&&a href=&/?target=https%3A//arxiv.org/abs/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Recurrent Neural Network Regularization, Wojciech Zaremba et al.&i class=&icon-external&&&/i&&/a&&/u& &/li&&li&2.&u&&a href=&/?target=https%3A//arxiv.org/abs/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Recurrent Dropout without Memory Loss, Stanislau Semeniuta et al.&i class=&icon-external&&&/i&&/a&&/u& &/li&&/ul&&p&&br&&/p&&p&&br&&/p&&p&&b&What&/b&：批量标准化（Batch Normalization, BN），增添了一个新的层，作者给出一些额外的技巧加速BN层的工作：&/p&&p&&br&&/p&&ul&&li&增大学习率；&br&&/li&&li&移除/减少dropout：在不增加过拟合发生的条件下加快训练； &/li&&li&移除/减少L2范数权值归一化； &/li&&li&加快学习率衰减速度：使得网络训练更快；&br&&/li&&li&移除局部响应归一化；&br&&/li&&li&将训练样本打乱地更彻底：防止相同的样本总出现在小批量中（验证集上提高了1%）； &/li&&li&减少光度失真；&br&&/li&&/ul&&p&&br&&/p&&p&&b&Why&/b&：&u&&a href=&/?target=https%3A///Why-does-batch-normalization-help& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&一些好的解释在此&i class=&icon-external&&&/i&&/a&&/u&。&/p&&p&&b&Ref&/b&：&u&&a href=&/?target=https%3A//arxiv.org/abs/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Accelerating Deep Network Training by Reducing Internal Covariate Shift, S. Ioffe and C. Szegedy.&i class=&icon-external&&&/i&&/a&&/u&&/p&&p&&br&&/p&&h2&&b&网络结构&/b&&/h2&&p&&b&What&/b&：使用跳跃式连接，直接将中间层连接到输入/输出层。&/p&&p&&b&Why&/b&：作者的观点是通过减少神经网络的底端与顶端之间的处理步骤使得训练深层网络更加简单，并减轻梯度消失问题。&/p&&p&&b&When&/b&：在一些CNN结构中或RNN中一些重要的层。&/p&&p&&b&Ref&/b&：&u&&a href=&/?target=https%3A//arxiv.org/abs/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Generating Sequences With Recurrent Neural Networks, Alex Grave et al.&i class=&icon-external&&&/i&&/a&&/u&&/p&&p&&br&&/p&&figure&&img src=&/50/v2-a568d8d4f87f890b363b0_b.jpg& data-rawwidth=&560& data-rawheight=&373& class=&origin_image zh-lightbox-thumb& width=&560& data-original=&/50/v2-a568d8d4f87f890b363b0_r.jpg&&&figcaption&RNN的跳跃式连接例子&/figcaption&&/figure&&p&&br&&/p&&p&&b&What&/b&：为LSTM增加窥视孔连接（连接之前输出到门的输入），根据作者的观点，这个操作对长时间依赖关系有用。&/p&&p&&b&Ref&/b&：&u&&a href=&/?target=http%3A//www.schraudolph.org/pubs/GerSchSch02.pdf& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Learning Precise Timing with LSTM Recurrent Networks, Felix A. Gers et al.&i class=&icon-external&&&/i&&/a&&/u&&/p&&p&&br&&/p&&p&&b&What&/b&：大多数的深度学习框架提供了一个结合SoftMax和Log的函数或者是在损失函数中计算SoftMax（在Tensorflow中是softmax_cross_entropy_with_logits，在Torch中是nn.LogSoftMax），这些应该被更好地使用。&/p&&p&&b&Why&/b&：Log（SoftMax）在数值上不稳定是小概率，从而导致溢出等不良结果。另外一种流行的方法是在Log中加入一些小数避免不稳定。&/p&&p&&br&&/p&&h2&&b&自然语言处理（NLP）&/b&&/h2&&p&&b&What：&/b&对于RNN和seq2seq模型的一些技巧：&/p&&p&&br&&/p&&ul&&li&嵌入尺寸：。更小的维度比如256也能导致很好的表现，但是更高的维度不一定导致更好的表现； &/li&&li&对于译码器而言：LSTM&GRU&Vanilla-RNN； &/li&&li&2-4层似乎普遍足够，但带有残差的更深网络看起来很难收敛，更多去挖掘更多的技巧； &/li&&li&Resd（密集的残差连接）&Res（近连接先前层）&无残差连接； &/li&&li&对于编码器而言：双向&单向（反向输入）&单向； &/li&&li&注意力（加法）&注意力（乘法）&无注意力； &/li&&li&使用光束会导致更好的结果；&br&&/li&&/ul&&p&&br&&/p&&p&&b&Ref&/b&：&u&&a href=&/?target=http%3A///s%3Fwd%3Dpaperuri%253A%252822abe28be9bbb62ecc079%2529%26filter%3Dsc_long_sign%26tn%3DSE_xueshusource_2kduw22v%26sc_vurl%3Dhttp%253A%252F%252Farxiv.org%252Fpdf%252F%26ie%3Dutf-8%26sc_us%3D& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Massive Exploration of Neural Machine Translation Architectures, Denny Britz, Anna Goldie et al.&i class=&icon-external&&&/i&&/a&&/u&&/p&&p&&br&&/p&&p&&b&What&/b&：对于seq2seq而言，翻转输入序列的顺序，保持目标序列的完整。&/p&&p&&b&Why&/b&：根据作者的观点，这种简单的数据变换极大提升了LSTM的性能。&/p&&p&&b&Ref&/b&：&u&&a href=&/?target=https%3A//arxiv.org/abs/Fspm%3D.blogcont.AWmFul%26file%3D& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Sequence to Sequence Learning with Neural Networks, Ilya Sutskever et al.&i class=&icon-external&&&/i&&/a&&/u&&/p&&p&&br&&/p&&p&&b&What&/b&：对于seq2seq而言，为编码器和译码器网络使用不同的权值。&/p&&p&&b&Ref&/b&：&u&&a href=&/?target=https%3A//arxiv.org/abs/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Sequence to Sequence Learning with Neural Networks, Ilya Sutskever et al.&i class=&icon-external&&&/i&&/a&&/u&&/p&&p&&br&&/p&&p&&b&What&/b&：当训练时，强制更正译码器的输入；在测试时，使用先前的步骤，这使得训练在开始时非常高效，Samy等人提出了一种基于模型转变的改进方法[1]。&/p&&p&&b&Ref&/b&：1.&u&&a href=&/?target=https%3A//arxiv.org/abs/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Scheduled Sampling for Sequence Prediction with Recurrent Neural Networks, Samy Bengio et al.&i class=&icon-external&&&/i&&/a&&/u&&/p&&p&&br&&/p&&p&&b&What&/b&：以无监督的方式训练一个网络去预测文本的下一个字符（char-RNN），该网络将学习一种能用来监督任务的表示（比如情感分析）。&/p&&p&&b&Ref&/b&：&u&&a href=&/?target=https%3A//arxiv.org/abs/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Learning to Generate Reviews and Discovering Sentiment, Ilya Sutskever et al.&i class=&icon-external&&&/i&&/a&&/u&&/p&&p&&br&&/p&&h2&&b&增强学习&/b&&/h2&&p&&b&What&/b&：异步：以不同的勘探政策同时训练多个代理，提升了鲁棒性。&/p&&p&&b&Ref&/b&：&u&&a href=&/?target=https%3A//arxiv.org/abs/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Asynchronous Methods for Deep Reinforcement Learning, V. Mnih.&i class=&icon-external&&&/i&&/a&&/u&&/p&&p&&br&&/p&&p&&b&What&/b&：跳帧：每隔4帧计算一次动作，而不是每帧都计算，对于其它帧，重复这个动作。&/p&&p&&b&Why&/b&：在Atari游戏中工作得很好，并且使用这个技巧以大约4倍的速度加快了训练过程。&/p&&p&&b&Ref&/b&：&u&&a href=&/?target=https%3A//arxiv.org/abs/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Playing Atari &i class=&icon-external&&&/i&&/a&&/u&with Deep Reinforcement Learning, V. Mnih. &/p&&p&&br&&/p&&p&&b&What&/b&：历史：不是仅仅将当前帧作为输入，而是将最后的帧与输入叠加，结合间隔为4的跳帧，这意味着我们有一个含t、t-4、t-8及t-12的帧栈。&/p&&p&&b&Why&/b&：这允许网络有一些动量信息。&/p&&p&&b&Ref&/b&：&u&&a href=&/?target=https%3A//arxiv.org/abs/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Deep Reinforcement Learning with Double Q-learning, V. Mnih.&i class=&icon-external&&&/i&&/a&&/u&&/p&&p&&br&&/p&&p&&b&What&/b&：经验回放：为了避免帧间的相关性，作为一个代理不是更新每一帧，最好是在过渡时期的历史中采样一些样本，该思想类似于有监督学习中训练前打乱数据集。&/p&&p&&b&Ref&/b&：&u&&a href=&/?target=https%3A//arxiv.org/abs/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Prioritized Experience Replay, Tom Schaul et al.&i class=&icon-external&&&/i&&/a&&/u&&/p&&p&&br&&/p&&p&&b&What&/b&：Parallel Advantage Actor Critic(PAAC)：通过代理的经验以及使用一个单一的同步更新模型使得简化A3C算法成为可能。&/p&&p&&b&Ref&/b&：&u&&a href=&/?target=https%3A//arxiv.org/abs/v2& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Efficient Parallel Methods for Deep Reinforcement Learning, Alfredo V. Clemente et al.&i class=&icon-external&&&/i&&/a&&/u&&/p&&p&&br&&/p&&h2&&b&网络压缩&/b&&/h2&&p&&b&What&/b&：在推理中，为了减少层数，通过批量归一化（BN）层能够吸收其它的权值。这是因为在测试时批量归一化进行地是一个简单的线性缩放。&/p&&p&&br&&/p&&p&&b&作者信息&/b&&/p&&p&&br&&/p&&b&&img src=&/50/v2-a4dae8f704d112fcd583d_b.jpg& data-caption=&& data-rawwidth=&326& data-rawheight=&326& class=&content_image& width=&326&&&/b&&p&&br&&/p&&p&&u&&a href=&/?target=http%3A//e-pot.xyz/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Conchylicultor&i class=&icon-external&&&/i&&/a&&/u&，谷歌大脑参与者,专注于机器学习和软件开发。&/p&&p&Linkedin：&u&&a href=&/?target=https%3A///in/potetienne/& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&https://www.&/span&&span class=&visible&&/in/potetie&/span&&span class=&invisible&&nne/&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/u&&/p&&p&Mail：etiennefg.&/p&&p&本文由北邮&a href=&/?target=http%3A///fly51fly%3Fspm%3D.blogconte60Y& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&@爱可可-爱生活&i class=&icon-external&&&/i&&/a&老师推荐，&a href=&/?target=http%3A///taobaodeveloperclub%3Fspm%3D.blogconte60Y& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&阿里云云栖社区&i class=&icon-external&&&/i&&/a&组织翻译。&/p&&p&文章原标题《Deep Learning Tricks》，作者：Conchylicultor，译者：海棠&/p&&p&&br&&/p&&p&&a href=&/?target=http%3A///m/33443/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&原文链接&i class=&icon-external&&&/i&&/a&&/p&&p&&b&更多技术干货敬请关注云栖社区知乎机构号：&a href=&/org/a-li-yun-yun-qi-she-qu-48& class=&internal&&阿里云云栖社区 - 知乎&/a&&/b&&/p&&p&&/p&
常言道，师傅领进门，修行靠个人，相信很多人或多或少是在别人的建议或带领下步入深度学习这个大坑，然后师傅说深度学习是个玄学，后面就靠个人修行，瞬间就懵了对不对？可能后面经过自己不断实验积累相关经验，会有一些自己的学习心得。本文可谓是深度学习…
&p&Microsoft的DocumentDB，即现在的Azure Cosmos DB背后基于Bw-Tree，笔者有意后面自己实现这个存储引擎，所以这里记录一些之前读这篇paper【1】的想法。&/p&&h2&1 动机&/h2&&p&这篇paper的目的是为了实现一个高性能的ARSs系统，所谓的ARSs即Atomic Record Stores，提供简单的key-value的原子访问接口，key-value通常提供put／get／scan的访问模型。基于ARSs可以很容易实现一个nosql系统，也可以基于它加上事物机制实现传统数据库。&/p&&p&Bw-Tree主要做了2个优化：&/p&&ol&&li&通过无锁的方式来操作b+tree，提升随机读和范围读的性能。核心的思想是把b+tree的page通过page id（PID）映射map，map的[key, value]变成[PID, page value]，把直接对page的修改，变成一个修改的操作记录，加入到“page value”，所以“page value”可能是一个“base page”即page原始的内容，和一串对page修改形成的记录的链表，而在修改记录链表中加入一个修改记录节点可以很容易变成一个无锁的方式来实现。另外就是对btree的split和merge操作也通过类似的原理，把具体的操作细化成好几个原子操作，避免传统的加锁方式。&/li&&li&把传统checkpoint刷page的变成通过log struct storage方式刷盘，把随机写变成顺序写，提高写的性能。&/li&&/ol&&p&传统的基于b+tree的存储引擎，例如BerkeleyDB和MySQL的innodb，读的性能很高，随机读和范围读都挺高，但是写性能比较低，因为写的时候，虽然只需要把redo log写入磁盘即可完成，但是为了缩短失效恢复时候的恢复时间，一般都需要频繁的做checkpoint，checkpoint是随机的写，随机写无论是在传统的机械硬盘还是SSD，或者PCID SSD上性能都较低，我们在实际测试MySQL的过程中，使用TPCC，通常能把磁盘写满，导致刷redo log性能降低，从而影响系统整体的吞吐量。&/p&&p&而基于LSM-tree典型的例如leveldb／rocksdb，写入性能较高，但是读性能，特别是范围读能力性能较差，例如读一条数据首先要看memtable中有没有，然后再扫描1级sstable和2级sstable，则需要多次磁盘io才能读到这条数据，特别是1级sstable每个分块的range还可能交叉，需要扫描多个1级sstable文件。另外一个就是在compact的时候会有一个性能的剧烈波动。&/p&&p&从上面看Bw-tree解决了b+tree（以BerkeleyDB，innodb为代表）和LSM-tree（以rocksdb为代表）高性能读和写不能兼得的问题，但是它并没有解决compact的时候带来的性能抖动问题。&/p&&p&最后值得一提的是Bw-Tree的性能，在xbox上测试可以达到&b&千万的OPS&/b&。这里必须要放出下面的性能对比测试：&/p&&img src=&/50/v2-7fdebaa932a456ebadc17_b.jpg& data-caption=&& data-rawwidth=&254& data-rawheight=&178& class=&content_image& width=&254&&&p&分别在上述3款硬件平台做的测试，其中Bw-Tree比BerkeleyDB高出好几倍。&/p&&h2&2 总体架构&/h2&&p&&br&&/p&&img src=&/50/v2-79d5f3657bbce84cb8c9_b.png& data-caption=&& data-rawwidth=&722& data-rawheight=&332& class=&origin_image zh-lightbox-thumb& width=&722& data-original=&/50/v2-79d5f3657bbce84cb8c9_r.png&&&p&系统分成了3层：&/p&&p&&b&B-tree Layer&/b&（论文中应该是笔误，写成Bw-tree layer，笔者认为叫做B-tree l）&/p&&ol&&li&维护在内存中的page，并把page组织成一棵树；&/li&&li&提供对这个树形结构的page的访问借口，search和update。&/li&&/ol&&p&&b&Cache Layer&/b&&/p&&ol&&li&把Bw-tree layer的page的抽象成逻辑页面，逻辑页面通过PID定义，提供给上层的B-tree使用，注意：&b&B-tree节点链接的不是page，而是逻辑页面，即PID&/b&。&/li&&li&维护了一个Mapping Table，Mapping Table维护了逻辑页面和物理页面的映射，管理物理页面在内存和磁盘上的换入换出。&/li&&/ol&&p&&b&Flash Layer&/b&：&/p&&ol&&li&实现了log-structure storage。存储系统的性能一般受限于磁盘的IO性能，特别是IOPS，Flash Layer实现的LSS实现了写大块数据，避免了磁盘去填充字节对齐，提升磁盘性能。&/li&&li&实现了磁盘垃圾数据的逻辑回收。&/li&&/ol&&p&&b&2.1 Mapping Table&/b&&/p&&p&Mapping Table保存了从逻辑页面到物理页面的映射，即上文提到的[PID, page value]，page value保存的就是物理页面。注意：&b&这个物理页面可能在内存中，也可能在磁盘中&/b&。逻辑页面通过PID定义，Mapping Table通过PID可以定位到page所在的位置（内存／磁盘），如果是在内存中，则会指向page所在的地址，如果page在磁盘，则是page所在磁盘的偏移量。&/p&&p&Mapping Table还会根据需要，决定是否要从磁盘中读取page到内存，以及把内存的数据刷入磁盘。&/p&&p&Bw-tree的节点是逻辑的，在内存和磁盘中没有保存在固定的位置，这点和btree不一样，在内存中它只需要分配一块内存就可以用来保存“page”数据，不像btree那样申请一大块内存用来放page，一般叫buffer pool，然后把buffer pool按固定大小分成切割成page，磁盘中的数据也是一样，保存在磁盘中的文件也是根据page大小切割成不同的小块。在这里，因为page是一个逻辑概念，并通过PID映射，它的大小可以不是固定的，也就是所谓的page的具备弹性（elastic），可以调整page的大小。&/p&&p&&b&2.2 Delta Updating&/b&&/p&&p&对page的状态的修改通过创建一个delta record，并把它挂载到对应的page上，这个操作是，通过CAS操作来完成修改的，CAS操作就避免了加锁，如果成功，delta record的地址变成page的新的物理地址，Mapping table中保存的[PID, page value]，其中page value具体实现的时候就是一个数据结构的内存地址，如果我们增加了一个delta record，挂载上去的最终结果就是“page value”所执行的内存地址变成了delta record的地址，当然delta record后面还会跟上原来的内容。&/p&&p&当合并page和delta record的时候，会创建一个新的page并应用delta record，可以节省内存的使用，并加快search的速度。新的page也是通过一个CAS操作来完成替换，老的page就可以做GC。&/p&&p&我们做修改的时候，即为page增加delta record的时候，同时允许无锁的读，同时避免了更新page数据的时候使用update-in-place的方式，即替换page部分内存值（这个的后果就是更新这块内存的时候需要加锁保护）。这里的关键就是通过Bw-Tree 的Mapping Table把对node的update只需要局限在这个节点，不会对其他的node有影响。&/p&&h2&2.3 Bw-Tree结构的修改&/h2&&p&latch不能保护对树的结构的修改，即所谓的SMO操作，例如分裂和合并，这类操作有一个问题，例如树分裂的时候可能修改不止一个page，老的page O，分裂后成为O‘和新page N，N将收到O的部分数据，O剩下另外一半数据，而O原来的父节点 P只指向O，本来应该同时包含O和N的。&b&这样分裂就不能通过一个简单的CAS操作&/b&搞定。&/p&&p&为了解决这个问题，这里把SMO操作分成一串操作，并把这一串操作的每个操作都变成原子操作，每个原子操作通过一个CAS来完成，这里使用B-link的数据结构设计来让整个实现更简单。具体就是把一个split分解成2个“half split”原子操作，为了保证没有线程要等待一个部分的SMO完成，线程会在看到这个部分的SMO操作之前，完成自己的操作，这样保证了没有线程需要等SMO操作完成。也就是说如果一个线程要做操作，这个操作本来可能会与SMO冲突，例如修改一个page的值，但是这个page这个时候要做split了，这里就是做了一个处理，让这个操作不应该看到进行到一半的SMO操作，即不能看到进行到一半的split或者merge，要么操作还没开始之前，SMO就完成了，要么就是自己操作完成前，SMO操作还没开始。&/p&&p&&b&2.4 Log Structured Store&/b&&/p&&p&这里使用LSS的时候，具备通用的LSS的有点，例如批量写入，很大程度上减少了IO次数。然而因为LSS有垃圾回收的原因，LSS需要额外的写操作，用来重新写入page和log合并后新的page。这里对这种情况做了优化，减少了这种情况的发生。&/p&&p&当刷入一个page的时候，只需要刷入与之前刷入的page的修改部分的数据，即delta数据。这种方式显著的减少了刷盘的数据量，增加了flush buffer中修改的page的个数，这样也可以减少了每个page刷盘的IO次数。另外增加的多个page首先会放到刷盘的flush buffer里面，然后一次刷入，减少刷盘的IO次数。这会给读带来一定的负担，因为page的所有不连续的delta和page数据都需要读入内存，但是这个正好利用SSD和flush的高性能的随机读硬件能力来弥补。&/p&&p&LSS会清理磁盘上老的日志数据，通过刷入delta数据，减少每个page对应的数据的存储数量，侧面减少了LSS的清理的压力。通过这种方式减少了传统的LSS的写放大的问题。&/p&&p&在做清理的时候，LSS还会对数据做重排，让page和他对应的delta数据排列在一块，加快访问性能。&/p&&p&&b&2.5 管理事务日志&/b&&/p&&p&在传统的数据库系统，ARS需要保证对每条记录的修改都已经持久化了，这样才能在crash的时候做失效恢复。&/p&&p&为了在crash的时候恢复，这里使用LSN（log sequence number）来标识每个修改操作日志。LSN为了支持失效的时候通过回放操作日志来恢复数据，LSN保证了回放的时候对每条操作日志，能够按照顺序，每条日志最多执行一次。&/p&&p&像传统的系统一样，当遵循了WAL日志原则的时候，page是flush lazily的，即操作日志是立即刷入磁盘，而修改的page是延后刷入磁盘的。与传统的做法不同的是，在写WAL日志的时候不会阻塞page刷盘。因为page和delta record是分开的，刷page的时候，只需要保证WAL日志还没有持久化的那部分的delta数据不刷盘即可。&/p&&h2&3 无锁的page管理&/h2&&p&这部分介绍了Bw-tree在内存中的page的结构，以及如何管理。首先会介绍page的结构，后面会讨论怎么通过无锁的方式来修改page的内容，后面会讨论传统的page的consolidation（即page和修改的部分的delta record的合并），这可以让search操作更加高效，然后讨论基于tree的索引的实现支持范围扫描，最后讨论内存的垃圾回收，通过一个基于epoch的安全访问机制实现内存安全的回收。&/p&&p&&b&3.1 虚拟的“page”&/b&&/p&&p&保存在Bw-Tree的page的信息，和传统的B+tree是一样的。内部的index node（索引节点）包含一对(key，pointer)，叶子节点的node包含(key，record)，与传统的不一样的地方是：&/p&&ol&&li&多了一个low key，保存了page里面保存的记录的最小的key；&/li&&li&多了一个high key，保存了page里面记录的最大的key；&/li&&li&多了一个side link pointer，指向了自己的右兄弟节点。这个做法和B-link tree类似。&/li&&/ol&&p&Bw-Tree有2个特性与其他设计不一样的地方：&/p&&ol&&li&page是逻辑的。这意味着page不需要是固定大小和占据固定的物理存储位置，在B+tree里面page id由于page是固定大小的，page在磁盘上文件的位置也是固定的。page通过PID来标识，Bw-tree的节点保存的是PID，我们通过PID从Mapping Table找到page的物理地址（内存地址或者磁盘地址）。&/li&&li&page是弹性的。意味page的大小没有限制。page随着往它之前插入delta record来增长，delta record可以是单条记录的修改，也可以系统管理的命令，例如分裂。&/li&&/ol&&p&&b&Updates&/b&&/p&&p&更新page的时候，从来不使用替换（即直接修改内存中的内容）的方式。而是通过创建一条delta record来描述对当前page的修改。delta record允许通过无锁操作增加到page中。&/p&&p&首先创建一条新的delta record D指向page的当前的物理地址P，P的物理地址可以从mapping table里面得到，delta record的内存地址将会作为page的地址，即page的地址后面会指向delta record的内存地址，即D的地址。delta record的地址会作为这个页面的新的内存地址，这个把Mapping Table中page P的地址替换为D的操作是一个CAS，具体就是替换的时候会判断Mapping Table里面这个PID对应的page的地址为是否为P，是则替换成功，否则失败，后面会分析CAS失败的情况下的处理。&/p&&p&上面描述的流程可以参考下图的(a)。因为所有Bw-tree的节点的地址都是通过PID来查找，所以更新一个page只需要更新Mapping Table里面保存的(PID, page)中对应page的地址即可。并且这是我们唯一需要使用无锁操作需要更新的地方。&/p&&img src=&/50/v2-8b5ea1fa2d989c22d4fd_b.jpg& data-caption=&& data-rawwidth=&276& data-rawheight=&131& class=&content_image& width=&276&&&p&&br&&/p&&p&上图(a)展示了更新一条delta record D到page P的过程，虚线连接的Page P是更新前的page的地址，实线是更新后page P的地址，指向了delta record D。因为更新是一个原子操作，只有一个线程的update可以成功，其他的线程都会失败，失败的线程会重试。&/p&&p&经过多次更新后，delta record会组成一个链表，这里叫delta chain，最后面跟一个最初的page，这个page我们叫他base page，就像上图(b)所示，每个新的update会更新这个delta chain的跟节点，mapping table会指向这个delta chain的根节点，即最后加入的那个delta record。&/p&&p&&b&叶子节点的更新操作&/b&&/p&&p&在叶子节点，update（delta record）有下面3种类型，insert，记录了往page中插入一条记录；modify修改了page中的一条记录；delete，删除了page中的一条记录。insert 和modify还包含修改的具体的数据，delete只包含被删除的记录的key。 delta record包含一个处理这个请求的client提供的LSN。我们用LSN来实现事务的失效恢复，同时LSN也是用来实现WAL协议的一个必须的标志。&/p&&p&&b&page 搜索&/b&&/p&&p&页面搜索的时候需要遍历delta chain，search会停在delta chain中第一次search到的key地方，然后读取它的delta record，如果delta record包含search key，并且是insert和update类型的，则直接返回结果，如果delta record标识search key删除，则返回搜索失败，如果delta record链表没有包含search key，则再对base page做二进制的查找，这个查找过程就是标准的B+tree叶子节点查找。&/p&&p&&b&3.2 Page consolidation(合并，类似于LSM的compact，后面用consolidation，中文笔者没有找到一个确切的词)&/b&&/p&&p&随着delta chain的增长搜索的性能会变低，所以使用consolidation技术来把delta chain和base page合并成一个新的base page。触发这个consolidation操作是通过访问线程在search的时候，检查到delta chain长度已经超过设定阈值。文中所说的“访问线程”即执行读或者写任务的线程。&/p&&p&当做consolidation的时候，线程首先创建一个新的base page（会申请一块新的内存），然后填充base page通过一个排序的向量，这个向量包含了page最近的修改记录，这些记录来自delta chain和老的base page（删除的记录会被忽略），然后线程会把新的base page的地址通过CAS赋值给mapping table对应的（PID，page value），如果成功，会要求对老的base page和delta chain上的delta record做垃圾回收，整个流程如上图的（b）所示。如果失败该线程会抛弃这个操作，销毁申请的新的base page的内存。该线程不会重试，因为失败了说明有另外一个线程已经成功做了一次consolidation了。&/p&&p&&b&3.3 范围扫描&/b&&/p&&p&范围扫描由一个key的范围来定义，即（low key，high key）。范围key也可以省略其中一个，省略的key代表了min key或者max key。同时scan还可以定义升序扫描和降序扫描。&/p&&p&扫描的时候维护了一个cursor，标识了当前的search已经到哪里了。对一个新的扫描，cursor就是low key（后面都是针对有low key和high key的升序扫描，其他的类似）。当一个page包含扫描范围的数据，并且在这次扫描第一次被访问到，我们会构建一个vector包含了这个page所有符合条件的record。当scan的过程中，页面如果没有被改变的话，可以让“next-page”操作更加高效。&/p&&p&每一次的“next-record”操作作为一次原子操作，而整个的scan操作不是原子的。事务锁会阻止我们看到已经被其它事务修改的记录（假设是在serializable transaction隔离级别），但是对于那些我们还没有访问的记录就不知道如何做同步控制了，所以在从vector返回一条record之前，我们会检查是否有一个update影响到了我们搜索的子范围。如果已经有update生效了，我们重新构建这个vector。&/p&&p&&b&3.4 垃圾回收&/b&&/p&&p&无锁的环境下，不允许以独占的方式访问共享的内存结构，例如Bw-tree的page，这样意味着一个或者多个reader可以同时访问一个page，即使这个page正在做update。我们不希望释放还在被其他线程访问的内存，例如在合并过程中，一个线程使用新的base page 替换老的base page和delta chain，并要求对老的base page 做垃圾回收。但是我们必须小心对待，不要把有其他线程还在访问的老的base page给释放了。类似的场景也出现在从Bw-tree删除一个page的时候。因为删除page的时候，可能还有其他线程正在访问这个page。这个是通过一个线程执行一个的“epoch”来实现的。&/p&&p&epoch是一种为了保护对象避免在使用前被提前释放的机制，具体的实现参考【2】中的&b&Epoch-based reclamation&/b&讲的比较清楚。当一个线程想保护一个它正在使用但是将会被回收的对象，例如search的时候，访问了一个page，就把当前线程加入 epoch，当这个依赖完成后，例如search这个page完成了，当前线程就退出epoch。通常一个线程在一个epoch的时间间隔设定为一个操作，例如一次insert，next-record。当线程注册到epoch E的时候，可能会看到将要被释放的老版本的对象。然而，一个线程注册epoch E成功之后，不可能会看到已经在epoch E-1中释放的对象，因为这个对象还没开始它的依赖周期。因此，一旦所有的线程注册到epoch E并完成然后退出这个epoch，回收epoch E中的所有对象是安全的。我们还使用epoch来保护存储和销毁PID。&/p&&h2&4 Bw-tree 结构的修改&/h2&&p&所有的Bw-tree结构的修改是使用无锁操作，下面首先描述节点分裂接着描述节点合并，然后讨论一个SMO（struct modification operations）在依赖它的操作之前先完成。&/p&&p&&b&4.1 节点分裂（split）&/b&&/p&&p&split通过访问线程触发，在访问线程访问page的时候，如果发现一个page的大小已经超过系统设定的阈值，该线程就会在做完自己的原来的操作后，进行page的分裂。&/p&&p&Bw-tree借用了B-link的基于2阶段的原子分裂技术。首先对child节点做分裂，然后更新parent节点，更新parent节点的时候，增加一个新的separator key，并把新分裂出来的page指针添加到父节点，这个对父节点的处理过程可以进行递归操作（也就是如果为父节点添加子节点导致父节点达到分裂的阈值，可以继续对父节点进行分裂）。B-link结构允许我们把分裂操作分成2个原子操作，因为B-link的side link（即每个节点保存了自己的左兄弟节点的指针）提供一个在子节点分裂后，还能通过side link做search操作。&/p&&p&&b&Child Split&/b&&/p&&p&如下图所示，为了分裂P，Bw-Tree要求在Mapping Table创建一个新的节点Q（Q是P的新的右节点）。然后我们从P找一个合适的separator key简写为Kp，用来做分裂，分裂后的Q包含从原来的Q来的比Kp大的记录，注意这个过程同时还包含一个consolidation操作，会合并delta chain中key比Kp大的delta。同时Q还包含一个side link用来连接之前的P，因为分裂后原来的P就成了Q的左兄弟节点。然后把Q添加到Mapping Table，这次的装配过程不需要CAS操作，因为Q只对split线程可见（因为这个时候我们还没有把Q加入到BTree中，查找Q范围的值还需要通过原来的P来查找，所以即使我们现在把Q装配到了Mapping Table，其他线程还是不能通过Mapping Table直接访问到Q）。这个时候的场景如下图(a)所示，Q包含P的部分数据，逻辑指向R，其中R是P的右兄弟节点，在这个点上，原来的P还在Mapping Table中，Q对其它的索引还是不可见。&/p&&img src=&/50/v2-1a141b15df709b8e5aafee25_b.jpg& data-caption=&& data-rawwidth=&260& data-rawheight=&183& class=&content_image& width=&260&&&p&&br&&/p&&p&做完上述的操作后，我们通过一个原子操作给P增加一个split delta record来实现对P的分裂，split delta包含2部分信息：&/p&&ol&&li&separator key Kp。用来把P里面的记录分开成，Q包含比Kp大的记录。&/li&&li&一个逻辑的sider link，指向新的右兄弟Q。&/li&&/ol&&p&上图的（b）描绘了上述的场景，P（PID）会指向delta record，delta record指向Page Q。这个时候，Q索引变成有效，即使它的父节点O没有指向它的指针。所有搜索的key包含在Q的范围的查找首先会去P，当遇到P里面的delta record的时候，当search key比separator key Kp大的时候，会递归的去到Q节点去查找，类似的如果search key小于separator key，只会在P查找。这个时候Q对其它线程就是可见的了，但是这个时候还不是通过Mapping Table的Q的PID来访问，而是通过P的PID来访问P，然后通过P里面我们增加的split delta record里面的sinder link来访问Q。&/p&&p&&b&Parent Update&/b&&/p&&p&为了直接搜索Q，这里通过给P和Q的父节点增加一个index term delta record来完成下半部分split，这个步骤所做的实际就是让Q能够直接通过BTree的父节点来直接访问，而不是通过P来间接访问。这个index term delta record包含下面的信息：&/p&&ol&&li&Kp，在P和Q中间的seperator key&/li&&li&指向Q的逻辑指针&/li&&li&Kq，针对Q的seperator key，之前的还需要去P搜索，现在通过Kq可以定向到去Q搜索了。&/li&&/ol&&p&我们记住在tree中走到当前节点的线路（即记录查找到当前节点经过了哪些父节点，记录这些节点的PID，保存在一个列表里面），这样就能够立即找到父节点。有时候我们记录的路线上的点是正确的，但是也有可能记住的父节点可能已经被合并到了其他节点，但是因为我们有epoch机制，所以我们能看到已经删除的状态，我们就能知道之前发生了什么，这样我们保证了我们记录的线路上的父节点的PID不会是一个危险的引用（所谓的危险的引用即该PID已经失效）。所以我们始终能够PID找到该节点的有效的内容，而当我们检测到一个节点被删除了（即通过这个节点的delta record查看），我们会沿着它的祖父节点再做一次对树的遍历，这样就找到还存活的父节点。&/p&&p&Kp和Kq在delta record中的作用是为了优化搜索的速度。因为搜索需要遍历在索引节点的delta chain，从delta chain中查找边界key v，v要比Kp要大，但是小于或者等于Kq，会让我们沿着逻辑指针去到Q。否则我们要到base page搜索去做二进制查找。上图的（c）展示了这个流程。&/p&&p&&b&Consolidations&/b&&/p&&p&与创建并装配（指把page挂到mapping table中并生效）一个完整的base page相比，分裂的时候通过增加一条delta record实现可以降低时延。降低时延可以降低split失败的概率。例如我们正在split的时候，有一个update操作突然发生了，这样会导致split失败。当然我们还是需要在某个时间对增加了delta record的分裂节点做consolidation，对于有split delta的page，合并会创建一个新的base page，它包含key小于delta record里面的seperator key的记录。对于有索引delta entry的page，我们合并的时候创建一个新的base page，包含新的separator keys和pointer。&/p&&p&&b&4.2 节点合并&/b&&/p&&p&和分裂类似，merge也是被访问线程触发，当访问线程发现node的大小小于一个阈值。merge的流程如下图所示，它比split复杂一些，需要更多的原子操作来完成。&/p&&img src=&/50/v2-23e695c25af_b.jpg& data-caption=&& data-rawwidth=&281& data-rawheight=&194& class=&content_image& width=&281&&&p&&b&标记删除。&/b&节点R将要被合并，也就是说这个节点会被删除，首先会更新这个节点，增加一个remove node delta record，如上图的(1)所示。这使得其它的线程都不能再使用节点R。当一个线程遇到包含remove node delta record的R节点的时候，读写都会通过他的side linker重定向到需要读R的左边的兄弟节点，并把更新写入它的左兄弟节点，因为原来的R节点的内容会被合并到其中。（这个时候读是否还是应该从R节点读，修改和写入添加到左兄弟节点？）&/p&&p&&b&Merging Children&/b&。R的左边兄弟节点设为L，会增加一条merge delta，merge delta会保留原来的R的指针。上图(b)显示了在merge过程中的R和L结构之间的关系。其中merge delta意味着R即将被合并到L，现在R逻辑上已经属于L的一部分了。&/p&&p&当我们search L的时候（这个时候它包含了自己L原来的key空间，也包含R的key空间），这样这个search就变成了对L和R组成的一棵树的search。为了达到上面的目的，node merge delta还包含seperator key，让上述的search能够找到正确的节点。&/p&&p&&b&Parent update&/b&。R的父节点设为P，现在可以通过删除R关联的索引来更新父节点。如上述(c)图所示。即给P节点增加一个index term delete delta来实现，index term delete delta不仅包含了R将被删除，还包含L将包含R原来的key空间。L新的key空间由L原来的low key和R之前的high key组成，这可以帮助我们重定向search的节点，帮助我们搜索原来R空间的时候，直接从L节点来查找。&/p&&p&当index term delete delta被posted（这个post即把delta数据添加到page的delta chian的根节点，并与Mapping Table中该节点做CAS，替换之前的PID匹配的指针），所有定向到R的路径都失效，这个时候，我们需要回收R的PID，这个通过在当前的活动的epoch中，把PID加入到待删除的PIDs列表。R的PID会等其他线程都从这个epoch退出的时候再删除。&/p&&p&&b&4.3 串行化结构的修改和更新&/b&&/p&&p&在Bw-tree实现中是假设数据更新的并发冲突在整个系统中都存在，可能是在把Bw-Tree集成到系统的时候的锁管理，也可能是事务模块。&/p&&p&回到Bw-tree，我们希望SMO修改的数据都能够串行化。所以我们必须构建一个串行化的结构来处理Bw-tree处理过程中的所有的更新。&/p&&p&我们把SMO分解的单个操作（一个SMO可以由多个原子操作组成）作为原子操作，并且使用无锁的方法，但是这里隐藏了一个问题，就是一个SMO可能是由多个原子操作组成的。针对这种只做了一半的SMO，我们可以把它作为一个未提交的状态，使用无锁的方法，这种情况是无法避免的。当一个线程遇到一个中间状态的SMO的时候，我们必须保证让线程在继续自己的update或者继续自己的SMO的时候，看到一个已经完成并且提交的SMO，即避免看到一个包含多个原子操作的SMO的中间状态。对于节点分裂，意味着它必须完成分裂，即 SMO通过post新的index term delta到他的父节点，当一个update或者SMO能够通过side pointer达到正确的page，它必须完成split SMO通过post 新的index term delta给父节点。只有这有它才能继续自己的活动，这样它可以强制一个未完成的SMO变成已提交的。&/p&&p&split和merge都是使用上述相同的机制，当删除一个节点R，我们通过访问他的左兄弟节点L的来装配merge delta，如果这个时候发现L即将被删除，我们会看到一个还没有完成的正在处理过程中的事务，我们需要删除L之前删除R来保证串行化，即我们在删除L之前，要保证之前merge的那个未完成的事务先做完，也就是先删除R。所有的SMO操作都是按照同样的方式实现串行化。为了达成这种先后删除的目的，我们就需要有一个SMO处理栈，把这些操作都压入栈中，保证先后执行，这样效率可能会比较低，但是由于这种竞争的情况不是经常发生，所以可以通过递归的方式来处理。&/p&&h2&5 Cache管理&/h2&&p&cache层负责在内存和flash之间实现读，写以及page的交换。它维护了Mapping Table并提供Bw-tree page的抽象。当Bw-tree层要求使用PID来关联一个page，cache层返回Mapping Table中它在内存中的指针。否则，如果这个地址是flash中的偏移量，即page没有在内存中，它从LSS中读取page到内存之后再返回内存地址。所有对page的更新，包括page的管理操作例如split和merge以及page的flush操作以及相关的在mapping table上的CAS操作都是通过PID来索引。&/p&&p&在内存中的page偶尔会被持久化到存储中，例如cache层会写入更新，当Bw-tree作为事务引擎的一部分做checkpoint的时候。page也会有通过内存和flash的交换来达到减少内存使用。当有多个线程把多个page刷入磁盘，需要有一个正确的顺序来保证写入的正确性。下面描述了page做split的时候的场景。&/p&&p&为了跟踪那个版本的page在持久化的存储，我们使用flush delta record，这个flush delta record使用CAS安装到mappting table的对应的page上，flush delta record同时记录了page上哪些被改变的已经flush到磁盘上，这样随后的flush只需要把增量的修改的内存刷入磁盘即可。当刷入一个page成功，flush delta会包含新的在磁盘上的offset和一些fields，用来描述刷入的page的状态。&/p&&p&剩下的章节描述cache层如何和LSS层配合。首先描述如何刷入LSS来配合一个独立的事务机制的要求。然后描述flush是如何执行的。&/p&&p&&b&5.1. Write Ahead Log Protocol和LSN&/b&&/p&&p&Bw-tree是一个ARS，可以包含一个事务引擎。当包含事务的时候，就对事务处理的方面做加强。 Deuteronomy[2]架构让这些方面的加强可以基于一个在事务和数据组件中间的协议来实现。即通过这种协议使得事务逻辑TC（transaction component）和数据管理DC（data component）所以解耦，所以这里使用Deuteronomy的架构来说明。其他的事务引擎也是类似的。&/p&&p&&b&LSN&/b&。通过一个Log Sequence Number来记录了插入和更新delta。最大的LSN和flushed是用来描述磁盘输入。LSN是由TC产生，并由它的事务日志使用。&/p&&p&&b&Transaction Log Coordination&/b&。TC在写入事务日志到磁盘的时候，需要更新End of stable Log（ESL） LSN的值。ELS LSN也是一个LSN，比它小的说明都已经持久化到磁盘了。它定期的发送ESL至到DC。它强迫DC不要使用大于最后的那个ELS做重复的操作。这样抱着DC是在持久化日志之后再执行对应的操作。为了保证这个规则，page上大于ESL的记录在刷入LSS的时候是不会包含在内的。&/p&&p&DC的page刷入磁盘是TC推进RSSP（Redo-Scan-Start-Point）的时候触发的，当TC想推进RSSP，它向DC发起一个RSSP的提议。这个的意图是允许TC删除比RSSP小的事务日志。TC将会等DC的确认，这个确认意味着DC已经把所有LSN小于RSSP变化的数据都已经持久化了。因为操作的结果已经持久化了，所以TC不需要在recovery的时候再发送这些操作给DC。对于DC，它在回应TC之前，需要把每个page上LSN小于RSSP的都持久化。这些flush是无阻塞式的，因为cache 管理会自己跳过那些LSN大于ESL的记录，即读的时候自动跳过还没有commit的记录。&/p&&p&为了支持无阻塞式的操作，我们限定page的合并的时候，只合并那些update delta的LSN小于等于ESL的。这样我们就能在flush page的时候排除那些LSN大于ESL的记录。&/p&&p&&b&Bw-tree机构的修改&/b&。我们围绕着page通过使用日志封装了系统事务作为bw-tree的SMOs的一部分。这个解决了我们无锁实现带来的一些并发对SMO访问的问题，例如2个线程同时去分裂同一个page。为了保证LSS和内存一致，我们不会commit一个SMO系统事务直到我们直到它的线程已经赢得竞争，安装SMO delta record到合适的page上。因此我们允许SMO并发，但是我们保证最多只有一个可以commit。在非常少的对象刷入LSS中间的开始和结束事务的记录是不会实例化到page。&/p&&p&&b&5.2 Flushing Pages to the LSS&/b&&/p&&p&LSS提供一个很大的buffer，cache管理用来管理page，系统事务，bw-tree结构的修改。下面会做一个大概的说明。&/p&&p&&b&Page marshalling&/b&。cache管理会把在内存中page的指针指向的内存做编码放入一段buff，er，这样好刷入磁盘，&b&当page有意向要刷入磁盘的时候，page的状态会被capture&/b&（capture的意思应该是霸占，独占，或者是被设置成一个特殊的状态，说明page正在flush，不要对他做其他的事情）。这点特别重要，因为page的state capture的晚一点，可能会违反WAL协议，或者page split的时候可能会移除了page中的一些record，但是这些record却是LSS需要被capture的。例如page上的数据已经编码到了flush buffer，这个时候可能发生split和合并，如果有已经被编码到flush buffer的record被删除，因为split的时候把split到另一个page的记录会从老的page删除，这个时候LSS capture的老的版本的page被capture就会找不到被删除的record，&b&在其他的split的page还没有被刷入磁盘的时候crash，这些记录就会丢失&/b&。当编码多条记录去做flush的时候，多条delta记录会被合并到page中，这样他们在LSS中会保持记录的连续性。&/p&&p&&b&增量flushing&/b&。当flush一个page的时候，cache manager只编码LSN介于之前已经被flush的最大的LSN和当前的ELS的delta records。之前已经flush的最大的LSN的信息会包含在page的最新的flush delta record中。&/p&&p&增量的flush意味着LSS刷盘的时候比整个page刷盘要节省磁盘。这对一个大的存储系统来说非常有价值，1）一次刷盘可以包含比刷整个page更多的page的更新。这样可以增加每个page的写的效率。2）LSS的清理线程可以不用因为磁盘被消耗过快而太繁忙，这样可以减少每个page的执行代价。同样可以减少写放大的问题。&/p&&p&&b&Flush Activity&/b&。flush buffer写入LSS依靠一个配置的阈值（当前是配置成1M，也就是buffer的数据超过1M了，就刷一次磁盘）来减少IO负载。它使用了一个double buffer来处理，这样一个buffer在通过异步的方式往LSS flush数据的时候，另一个buffer可以用来接受写入请求。&/p&&p&flush buffer里面的数据完成写入磁盘之后，在mapping table里面的对应page的状态也需要修改过来。这个是通过给page增加一个delta来实现，这个delta描述了page的数据已经flush成功，增加delta也是通过一个CAS操作完成的。如果flush buffer里面持久化的page都已经被通知到了，说明page是“clean”的，“clean”的意思就是page的修改都已经持久化到磁盘了。&/p&&p&cache manager监控Bw-tree使用的内存，当使用的内存超过一个阈值就把内存的数据交换到磁盘。当一个page是“clean”的，它就可以从内存中删除。在内存中删除一个page也是通过基于epoch的内存回收机制。&/p&&p&&br&&/p&&h2&6 参考资料&/h2&&p&【1】Justin J. Levandoski, David B. Lomet, Sudipta Sengupta
Microsoft Research The Bw-Tree: A B-tree for New Hardware Platforms&/p&&p&【2】&a href=&/?target=http%3A//habrahabr.ru/users/khizmax/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&khizmax&i class=&icon-external&&&/i&&/a& Lock-free Data Structures. The Inside. Memory Management Schemes&/p&
Microsoft的DocumentDB，即现在的Azure Cosmos DB背后基于Bw-Tree，笔者有意后面自己实现这个存储引擎，所以这里记录一些之前读这篇paper【1】的想法。1 动机这篇paper的目的是为了实现一个高性能的ARSs系统，所谓的ARSs即Atomic Record Stores，提供简单的…
&p&&b&摘要：&/b& 为了更好地让开发者们深入了解阿里开源，本文对社区内发布过的开源技术精品内容做了一次大汇总，包括115个阿里巴巴开源技术、阿里巴巴73款开源产品全向图、首届阿里开源峰会PDF+活动视频回顾等等。&/p&&p&开源是孵化新技术领域的容器，开源是技术演进的强大推动力。多年来，阿里巴巴集团一直积极拥抱开源事业，无论是开源软件的应用、回馈以至自研技术的开源都非常活跃。&/p&&p&为了更好地让开发者们深入了解阿里开源，本文对社区内发布过的开源技术精品内容做了一次大汇总，包括115个阿里巴巴开源技术、阿里巴巴73款开源产品全向图、首届阿里开源峰会PDF+活动视频回顾等等。&/p&&p&&b&阿里巴巴73款开源产品全向图&/b&&/p&&p&&br&&/p&&img src=&/v2-ec49a76de8ecf0668c0ec_b.jpg& data-rawwidth=&1144& data-rawheight=&873& class=&origin_image zh-lightbox-thumb& width=&1144& data-original=&/v2-ec49a76de8ecf0668c0ec_r.jpg&&&p&&br&&/p&&p&2016阿里巴巴73款开源产品全向图（9月制）点击图片可下载大图。&/p&&p&&br&&/p&&p&&a href=&/?target=http%3A///m/30649/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&2016阿里巴巴73款开源产品全向图详细介绍&i class=&icon-external&&&/i&&/a&&/p&&p&&br&&/p&&p&&b&“阿里开源项目最佳实践”在线技术峰会回顾资料&/b&&/p&&p&1. React 技术栈在蚂蚁金服的实践&/p&&ul&&li&演讲视频：&a href=&/?target=http%3A///m/30650/& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&/m/3065&/span&&span class=&invisible&&0/&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/li&&li&演讲整理文章：&a href=&/?target=http%3A///m/30651/& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&/m/3065&/span&&span class=&invisible&&1/&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/li&&/ul&&p&2. AliSQL功能特性详解&/p&&ul&&li&演讲视频：&a href=&/?target=http%3A///m/30652/& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&/m/3065&/span&&span class=&invisible&&2/&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/li&&li&PDF下载：&a href=&/?target=http%3A///m/30653/& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&/m/3065&/span&&span class=&invisible&&3/&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/li&&li&演讲整理文章：&a href=&/?target=http%3A///m/30654/& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&/m/3065&/span&&span class=&invisible&&4/&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/li&&/ul&&p&3. BeeHive：大型iOS项目解耦实践&/p&&ul&&li&演讲视频：&a href=&/?target=http%3A///m/30655/& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&/m/3065&/span&&span class=&invisible&&5/&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/li&&li&PDF下载：&a href=&/?target=http%3A///m/30656/& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&/m/3065&/span&&span class=&invisible&&6/&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/li&&li&演讲整理文章：&a href=&/?target=http%3A///m/30657/& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&/m/3065&/span&&span class=&invisible&&7/&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/li&&/ul&&p&4. Jstorm开源最佳实践 &/p&&ul&&li&演讲视频：&a href=&/?target=http%3A///m/30658/& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&/m/3065&/span&&span class=&invisible&&8/&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/li&&li&PDF下载：&a href=&/?target=http%3A///m/30659/& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&/m/3065&/span&&span class=&invisible&&9/&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/li&&li&演讲整理文章：&a href=&/?target=http%3A///m/30660/& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&/m/3066&/span&&span class=&invisible&&0/&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/li&&/ul&&p&5. Android平台页面路由框架ARouter最佳实践&/p&&ul&&li&演讲视频：&a href=&/?target=http%3A///m/30661/& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&/m/3066&/span&&span class=&invisible&&1/&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/li&&li&PDF下载：&a href=&/?target=http%3A///m/30662/& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&/m/3066&/span&&span class=&invisible&&2/&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/li&&li&演讲整理文章：&a href=&/?target=http%3A///m/30663/& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&/m/3066&/span&&span class=&invisible&&3/&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/li&&/ul&&p&6. 分布式消息引擎Apache RocketMQ最佳实践&/p&&ul&&li&演讲视频：&a href=&/?target=http%3A///m/30664/& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&/m/3066&/span&&span class=&invisible&&4/&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/li&&li&PDF下载：&a href=&/?target=http%3A///m/30665/& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&/m/3066&/span&&span class=&invisible&&5/&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/li&&li&演讲整理文章：&a href=&/?target=http%3A///m/30666/& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&/m/3066&/span&&span class=&invisible&&6/&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/li&&/ul&&p&7. Freeline：极速编译方案的开源之路&/p&&ul&&li&演讲视频：&a href=&/?target=http%3A///m/30667/& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&/m/3066&/span&&span class=&invisible&&7/&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/li&&li&演讲整理文章：&a href=&/?target=http%3A///m/30668/& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&/m/3066&/span&&span class=&invisible&&8/&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/li&&/ul&&p&8. 由 Weex 谈品牌经营心得&/p&&ul&&li&演讲视频：&a href=&/?target=http%3A///m/30669/& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&/m/3066&/span&&span class=&invisible&&9/&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/li&&li&PDF下载：&a href=&/?target=http%3A///m/30670/& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&/m/3067&/span&&span class=&invisible&&0/&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/li&&li&演讲整理文章：&a href=&/?target=http%3A///m/30671/& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&/m/3067&/span&&span class=&invisible&&1/&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/li&&/ul&&p&&br&&/p&&p&&b&此外，云栖社区曾发布过多期与开源产品相关的内容&/b&，比如：&/p&&p&&a href=&/?target=https%3A///articles/30796%3Fspm%3D.blogcontk7Rf& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&28款GitHub最流行的开源机器学习项目（一和二）：TensorFlow排榜首&i class=&icon-external&&&/i&&/a&&/p&&p&&a href=&/?target=https%3A///articles/Fspm%3D.searchblog.131.BLUkhx& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&史上最全的“大数据”学习资源（上和下）&i class=&icon-external&&&/i&&/a&&/p&&p&&a href=&/?target=https%3A///articles/43341%3Fspm%3D.blogcontk7Rf& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&史上最全的机器学习资料（上和下）&i class=&icon-external&&&/i&&/a&&/p&&p&&a href=&/?target=https%3A///articles/34833%3Fspm%3D.blogcontk7Rf& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&深度揭秘阿里移动端高性能动态化方案Weex&i class=&icon-external&&&/i&&/a&&/p&&p&&a href=&/?target=https%3A///articles/7474%3Fspm%3D.blogcontk7Rf& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&阿里自主研发的互动游戏引擎Hilo开&i class=&icon-external&&&/i&&/a&&a href=&/?target=https%3A///articles/7474%3Fspm%3D.blogcontk7Rf& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&源&i class=&icon-external&&&/i&&/a&&/p&&p&&br&&/p&&p&当然，专家文章下面的评论总是少不了这个问题“技术很好，会开源吗？”&/p&&p&云栖社区的好友开源中国早已跟踪阿里集团在Github上开源项目多年，形成了&b&阿里巴巴115个开源软件&/b&的汇总，如下：&/p&&p&&a href=&/?target=http%3A///m/30672/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&阿里巴巴开源技术汇总：115个软件 (一）&i class=&icon-external&&&/i&&/a&&/p&&p&&a href=&/?target=http%3A///m/30673/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&阿里巴巴开源技术汇总：115个软件(二)&i class=&icon-external&&&/i&&/a&&/p&&p&&a href=&/?target=http%3A///m/30674/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&阿里巴巴开源技术汇总：115个软件(三)&i class=&icon-external&&&/i&&/a&&/p&&p&&a href=&/?target=http%3A///m/30675/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&阿里巴巴开源技术汇总：115个软件(四)&i class=&icon-external&&&/i&&/a&&/p&&p&&a href=&/?target=http%3A///m/30676/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&阿里巴巴开源技术汇总：115个软件(五)&i class=&icon-external&&&/i&&/a&&/p&&p&在开源技术的基础上，阿里云官网也研发出多款&b&与业务线紧密结合的产品&/b&，推荐几款给大家： &/p&&p&&a href=&/?target=http%3A///m/30677/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&云数据库 MySQL 版&i class=&icon-external&&&/i&&/a&：MySQL 是全球最受欢迎的开源数据库之一，作为开源软件组合 LAMP（Linux + Apache + MySQL + Perl/PHP/Python）中的重要一环，广泛应用于各类应用场景。&/p&&p&&a href=&/?target=http%3A///m/30678/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&云数据库 Redis 版&i class=&icon-external&&&/i&&/a&：云数据库Redis版是兼容Redis协议标准的、提供持久化的内存数据库服务，基于高可靠双机热备架构及可无缝扩展的集群架构，满足高读写性能场景及容量需弹性变配的业务需求。&/p&&p&&a href=&/?target=http%3A///m/27545/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&云数据库 PostgreSQL 版&i class=&icon-external&&&/i&&/a&：PostgreSQL被业界誉为“最先进的开源数据库”，面向企业复杂SQL处理的OLTP在线事务处理场景，支持NoSQL数据类型（JSON/XML/hstore）、支持GIS地理信息处理。&/p&&p&&a href=&/?target=http%3A///m/30680/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&云数据库 HBase 版&i class=&icon-external&&&/i&&/a&：云数据库 HBase 版（ApsaraDB for HBase）是基于 Hadoop 且100%兼容HBase协议的高性能、可弹性伸缩、面向列的分布式数据库，轻松支持PB级大数据存储，满足千万级QPS高吞吐随机读写场景。&/p&&p&&a href=&/?target=http%3A///m/30681/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&数据传输服务DTS&i class=&icon-external&&&/i&&/a&：数据传输服务(Data Transmission Service) DTS支持关系型数据库、NoSQL、大数据(OLAP)等数据源间的数据传输。 它是一种集数据迁移、数据订阅及数据实时同步于一体的数据传输服务。&/p&&p&&a href=&/?target=http%3A///m/30682/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&E-MapReduce&i class=&icon-external&&&/i&&/a&：E-MapReduce 是构建于阿里云 ECS 弹性虚拟机之上，利用开源大数据生态系统，包括Hadoop、Spark、Kafka、Storm，为用户提供集群、作业、数据等管理的一站式大数据处理分析服务。&/p&&p&&br&&/p&&p&也欢迎对阿里技术开源感兴趣的社区/社群、媒体伙伴和技术开发者，联系社区，一起合作。&/p&&p&作者：乔川&/p&&h2&&b&更多技术干货敬请关注云栖社区知乎机构号：&a href=&/org/a-li-yun-yun-qi-she-qu-48& class=&internal&&阿里云云栖社区 - 知乎&/a&&/b&&/h2&&p&&/p&
摘要： 为了更好地让开发者们深入了解阿里开源，本文对社区内发布过的开源技术精品内容做了一次大汇总，包括115个阿里巴巴开源技术、阿里巴巴73款开源产品全向图、首届阿里开源峰会PDF+活动视频回顾等等。开源是孵化新技术领域的容器，开源是技术演进的强大…
&img src=&/50/v2-20dd22b77d42a29835cdf2719685bcfe_b.png& data-rawwidth=&800& data-rawheight=&605& class=&origin_image zh-lightbox-thumb& width=&800& data-original=&/50/v2-20dd22b77d42a29835cdf2719685bcfe_r.png&&&p&本篇将尝使用canvas + wasm画一个迷宫，生成算法主要用到连通集算法，使用wasm主要是为了提升运行效率。然后再用一个最短路径算法找到迷宫的出路，最后的效果如下：&/p&&p&&br&&/p&&img src=&/v2-aeedde3252c2_b.png& data-rawwidth=&1614& data-rawheight=&1220& class=&origin_image zh-lightbox-thumb& width=&1614& data-original=&/v2-aeedde3252c2_r.png&&&p&&br&&/p&&p&&br&&/p&&h2&1. 用连通集算法生成迷宫&/h2&&p&生成迷宫的算法其实很简单，假设迷宫的大小是10 * 10，即这个迷宫有100个格子，通过不断地随机拆掉这100个格子中间的墙，直到可以从第一个格子走到最后一个格子，也就是说第一个格子和最后一个格子处于同一个连通集。具体如下操作：&/p&&p&（1）生成100个格子，每个格子都不相通&/p&&p&（2）随机选取相邻的两个格子，可以是左右相邻或者是上下相邻，判断这两个格子是不是处于同一个连通集，即能否从其中一个格子走到另外一个格子，如果不能，就拆掉它们中间的墙，让它们相连，处于同一个连通集。&/p&&p&（3）重复第二步，直到第一个格子和最后一个格子相连。&/p&&p&那这个连通集应该怎么表示呢？我们用一个一维数组来表示不同的已连通的集合，初始化的时候每个格子的值都为-1，如下图所示，假设迷宫为3 * 3，即有9个格子：&/p&&img src=&/v2-e819bad72a8e_b.png& data-rawwidth=&906& data-rawheight=&174& class=&origin_image zh-lightbox-thumb& width=&906& data-original=&/v2-e819bad72a8e_r.png&&&p&每个索引在迷宫的位置：&/p&&img src=&/v2-435bf1a5efdd7ea37a60_b.png& data-rawwidth=&494& data-rawheight=&302& class=&origin_image zh-lightbox-thumb& width=&494& data-original=&/v2-435bf1a5efdd7ea37a60_r.png&&&p&负数表示它们是不同的连通集，因为我们还没开始拆墙，所以一开始它们都是独立的。&/p&&p&现在把3、4中间的墙拆掉，也就是说让3和4连通，把4的值置成3，表示4在3这个连通集，3是它们的根，如下图所示：&/p&&img src=&/v2-99a328c07b8dc6a84cda43c3c1f61368_b.png& data-rawwidth=&876& data-rawheight=&214& class=&origin_image zh-lightbox-thumb& width=&876& data-original=&/v2-99a328c07b8dc6a84cda43c3c1f61368_r.png&&&p&再把5、8给拆了：&/p&&img src=&/v2-367af42e0dd500efead85a53_b.png& data-rawwidth=&876& data-rawheight=&220& class=&origin_image zh-lightbox-thumb& width=&876& data-original=&/v2-367af42e0dd500efead85a53_r.png&&&p&再把4、5给拆了：&/p&&p&&br&&/p&&img src=&/v2-faf293e7bcb588b8f861dc0f5d0a55cf_b.png& data-rawwidth=&862& data-rawheight=&224& class=&origin_image zh-lightbox-thumb& width=&862& data-original=&/v2-faf293e7bcb588b8f861dc0f5d0a55cf_r.png&&&p&这个时候3、4、5、8就处于同一个连通集了，但是0和8依旧是两个不同的连通集，这个时候再把3和0中间的墙给拆了：&/p&&img src=&/v2-2382fd8caa138f0d5c8bf3611e9aae07_b.png& data-rawwidth=&884& data-rawheight=&240& class=&origin_image zh-lightbox-thumb& width=&884& data-original=&/v2-2382fd8caa138f0d5c8bf3611e9aae07_r.png&&&p&由于0的连通集是3，而8的连通集也是3，即它们处于同一个连通集，因此这个时候从第一个格子到最后一个格子的路是相通的，就生成了一个迷宫。&/p&&p&我们用UnionSet的类表示连通集，如下代码所示：&/p&&div class=&highlight&&&pre&&code class=&language-js&&&span&&/span&&span class=&kr&&class&/span& &span class=&nx&&UnionSet&/span&&span class=&p&&{&/span&
&span class=&nx&&constructor&/span&&span class=&p&&(&/span&&span class=&nx&&size&/span&&span class=&p&&){&/span&
&span class=&k&&this&/span&&span class=&p&&.&/span&&span class=&nx&&set&/span& &span class=&o&&=&/span& &span class=&k&&new&/span& &span class=&nb&&Array&/span&&span class=&p&&(&/span&&span class=&nx&&size&/span&&span class=&p&&);&/span&
&span class=&k&&for&/span&&span class=&p&&(&/span&&span class=&kd&&var&/span& &span class=&nx&&i&/span& &span class=&o&&=&/span& &span class=&k&&this&/span&&span class=&p&&.&/span&&span class=&nx&&set&/span&&span class=&p&&.&/span&&span class=&nx&&length&/span& &span class=&o&&-&/span& &span class=&mi&&1&/span&&span class=&p&&;&/span& &span class=&nx&&i&/span& &span class=&o&&&=&/span& &span class=&mi&&0&/span&&span class=&p&&;&/span& &span class=&nx&&i&/span&&span class=&o&&--&/span&&span class=&p&&){&/span&
&span class=&k&&this&/span&&span class=&p&&.&/span&&span class=&nx&&set&/span&&span class=&p&&[&/span&&span class=&nx&&i&/span&&span class=&p&&]&/span& &span class=&o&&=&/span& &span class=&o&&-&/span&&span class=&mi&&1&/span&&span class=&p&&;&/span&
&span class=&p&&}&/span&
&span class=&p&&}&/span&
&span class=&nx&&union&/span&&span class=&p&&(&/span&&span class=&nx&&root1&/span&&span class=&p&&,&/span& &span class=&nx&&root2&/span&&span class=&p&&){&/span&
&span class=&k&&this&/span&&span class=&p&&.&/span&&span class=&nx&&set&/span&&span class=&p&&[&/span&&span class=&nx&&root1&/span&&span class=&p&&]&/span& &span class=&o&&=&/span& &span class=&nx&&root2&/span&&span class=&p&&;&/span&
&span class=&p&&}&/span&
&span class=&nx&&findSet&/span&&span class=&p&&(&/span&&span class=&nx&&x&/span&&span class=&p&&){&/span&
&span class=&k&&while&/span&&span class=&p&&(&/span&&span class=&k&&this&/span&&span class=&p&&.&/span&&span class=&nx&&set&/span&&span class=&p&&[&/span&&span class=&nx&&x&/span&&span class=&p&&]&/span& &span class=&o&&&=&/span& &span class=&mi&&0&/span&&span class=&p&&){&/span&
&span class=&nx&&x&/span& &span class=&o&&=&/span& &span class=&k&&this&/span&&span class=&p&&.&/span&&span class=&nx&&set&/span&&span class=&p&&[&/span&&span class=&nx&&x&/span&&span class=&p&&];&/span&
&span class=&p&&}&/span&
&span class=&k&&return&/span& &span class=&nx&&x&/span&&span class=&p&&;&/span&
&span class=&p&&}&/span&
&span class=&nx&&sameSet&/span&&span class=&p&&(&/span&&span class=&nx&&x&/span&&span class=&p&&,&/span& &span class=&nx&&y&/span&&span class=&p&&){&/span&
&span class=&k&&return&/span& &span class=&k&&this&/span&&span class=&p&&.&/span&&span class=&nx&&findSet&/span&&span class=&p&&(&/span&&span class=&nx&&x&/span&&span class=&p&&)&/span& &span class=&o&&===&/span& &span class=&k&&this&/span&&span class=&p&&.&/span&&span class=&nx&&findSet&/span&&span class=&p&&(&/span&&span class=&nx&&y&/span&&span class=&p&&);&/span&
&span class=&p&&}&/span&
&span class=&nx&&unionElement&/span&&span class=&p&&(&/span&&span class=&nx&&x&/span&&span class=&p&&,&/span& &span class=&nx&&y&/span&&span class=&p&&){&/span&
&span class=&k&&this&/span&&span class=&p&&.&/span&&span class=&nx&&union&/span&&span class=&p&&(&/span&&span class=&k&&this&/span&&span class=&p&&.&/span&&span class=&nx&&findSet&/span&&span class=&p&&(&/span&&span class=&nx&&x&/span&&span class=&p&&),&/span& &span class=&k&&this&/span&&span class=&p&&.&/span&&span class=&nx&&findSet&/span&&span class=&p&&(&/span&&span class=&nx&&y&/span&&span class=&p&&));&/span&
&span class=&p&&}&/span&
&span class=&p&&}&/span&
&/code&&/pre&&/div&&p&我们总共用了22行代码就实现了一个连通集。上面的代码应该比较好理解，对照上面的示意图。如findSet函数得到某个元素所在的set的根元素，而根元素存放的是负数，只要存放的值是正数那么它就是指向另一个结点，通过while循环一层层的往上找直到负数。unionElement可以连通两个元素，先找到它们所在的set，然后把它们的set union一下变成同一个连通集。&/p&&p&现在写一个Maze，用来控制画迷宫的操作，它组合一个UnionSet的实例，如下代码所示：&/p&&div class=&highlight&&&pre&&code class=&language-js&&&span&&/span&&span class=&kr&&class&/span& &span class=&nx&&Maze&/span&&span class=&p&&{&/span&
&span class=&nx&&constructor&/span&&span class=&p&&(&/span&&span class=&nx&&columns&/span&&span class=&p&&,&/span& &span class=&nx&&rows&/span&&span class=&p&&,&/span& &span class=&nx&&cavans&/span&&span class=&p&&){&/span&
&span class=&k&&this&/span&&span class=&p&&.&/span&&span class=&nx&&columns&/span& &span class=&o&&=&/span& &span class=&nx&&columns&/span&&span class=&p&&;&/span&
&span class=&k&&this&/span&&span class=&p&&.&/span&&span class=&nx&&rows&/span& &span class=&o&&=&/span& &span class=&nx&&rows&/span&&span class=&p&&;&/span&
&span class=&k&&this&/span&&span class=&p&&.&/span&&span class=&nx&&cells&/span& &span class=&o&&=&/span& &span class=&nx&&columns&/span& &span class=&o&&*&/span& &span class=&nx&&rows&/span&&span class=&p&&;&/span&
&span class=&c1&&//存放是连通的格子，{1: [2, 11]}表示第1个格子和第2、11个格子是相通的&/span&
&span class=&k&&this&/span&&span class=&p&&.&/span&&span class=&nx&&linkedMap&/span& &span class=&o&&=&/span& &span class=&p&&{};&/span&
&span class=&k&&this&/span&&span class=&p&&.&/span&&span class=&nx&&unionSets&/span& &span class=&o&&=&/span& &span class=&k&&new&/span& &span class=&nx&&UnionSet&/span&&span class=&p&&(&/span&&span class=&k&&this&/span&&span class=&p&&.&/span&&span class=&nx&&cells&/span&&span class=&p&&);&/span&
&span class=&k&&this&/span&&span class=&p&&.&/span&&span class=&nx&&canvas&/span& &span class=&o&&=&/span& &span class=&nx&&canvas&/span&&span class=&p&&;&/span&
&span class=&p&&}&/span&
&span class=&p&&}&/span&
&/code&&/pre&&/div&&p&Maze构造函数传三个参数，前两个是迷宫的列数和行数，最后一个是canvas元素。在构造函数里面初始化一个连通集，作为这个Maze的核心模型，还初始化了一个linkedMap，用来存放拆掉的墙，进而提供给canvas绘图。&/p&&p&Maze类再添加一个生成迷宫的函数，如下代码所示：&/p&&div class=&highlight&&&pre&&code class=&language-js&&&span&&/span&&span class=&c1&&//生成迷宫&/span&
&span class=&nx&&generate&/span&&span class=&p&&(){&/span&
&span class=&c1&&//每次任意取两个相邻的格子，如果它们不在同一个连通集，&/span&
&span class=&c1&&//则拆掉中间的墙，让它们连在一起成为一个连通集&/span&
&span class=&k&&while&/span&&span class=&p&&(&/span&&span class=&o&&!&/span&&span class=&k&&this&/span&&span class=&p&&.&/span&&span class=&nx&&firstLastLinked&/span&&