by ·0 Comments

本文是对《A Primer on Memory Consistency and Cache Coherence》这本书前一半内容的记录和理解，主要涉及memory consistency model。 1. 引言 对于多处理器共享内存系统来说，consistency和coherence都关注的是共享内存(shared memory)及cache的正确性问题，而人们把这个问题拆成两个方面是为了更好地将这个复杂问题分治解决。 1.1 Consistency 一般需要被详细讨论的是多核(或线程)共享内存(shared memory)的consistency模型，因为单核单线程问题相对简单直观。内存consistency模型规定的是：多线程同时进行load/store操作时，怎样的执行顺序是对的，怎样是错的。比较简单直接的consistency模型包括sequential consistency、TSO(total store consitency，x86使用)等。 1.2 Coherence 本文主要记录与consistency有关的内容，但因为consistency的实现与coherence有关，所以要简单介绍下coherence及其与consistency的关系。 虽然coherence的中文也翻译成“一致性”，但coherence这个词通常跟在cache后面，即缓存一致性(cache coherence)，解决缓存一致性问题的方法也被称为缓存一致性协议(cache coherence protocol)。那么共享内存系统的cache为什么需要coherence协议保证共享内存系统正确性呢？这是因为cache一般分为L1、L2和L3等很多层，L1等比较高的层级中，cache是每个核所独占的，一般只有L3、memory等层级才是共享的。在每个核独占的层级中，可能出现统一内存地址的数据在不同独占cache中数值不一样的情况，这时cache的状态可以称为incoherent。通过无效化等coherence协议，可以保证多核系统cache的正确性。 1.3 Consistency 和 Coherence的关系 对于sequential consistency和TSO等比较简单的consistency model来说，保证了coherence的cache可以被看成一个“黑盒”甚至对consistency model透明，黑盒中有cache实现有保证cache使用正确的coherence protocol，而consistency更关注程序(或处理器核)的访存顺序。因此对于简单的consistency model和coherence protocol来说，两者是解耦的。 1.4 一个小例子 如果上边几段不易理解，作者在书中用一个例子解释了这两个名词的基本含义，简单记录如下，有改编： consistency的例子 设想有三个人，计算机体系结构课程老师、教务处网站管理员和上课的学生，老师最开始在教务处上登记了上课的地点是152教室，但是开学第一节课后发现选课的人太多了152坐不下，于是准备下节课开始换到更大的252教室，于是老师先①找教务处网站管理员说“请你把网站上我课的教室信息改到252（要求①），随后通知学生们去教务处网站查询下节课的上课地点（要求②）。这就产生了一个问题，网站管理员可能是第二天才更新的网站，而学生是接到老师的通知马上重新查看了教务处网站，因此学生下周又来到了152教室，老师的计划和最后的结果出现了不一致情况。 问题就出在老师的做法无法保证学生在网站被修改之后再去网站查询。要想保证学生查到正确的信息，一种简单的办法就是保证管理员的确更新了数据，然后再通知学生们。这种简单的办法就可以称为一种一致性模型。 我们把这个例子对应到实际的内存系统中，给管理员和学生要做的两件事（要求①和②）可以分别看成一条store命令和一条load命令，目标都是教务处网站上老师的教室号，这个目标可以看成同一块内存地址，因此对同一内存地址执行的store和load命令是否可以调换顺序(管理员在学生查询才修改了网站)，调换顺序后是否破坏了程序的正确性，就是内存一致性模型memory consistency model所负责的。也就是说，出现上述情况算不算错，应该是当前的一致性模型所判断的：相对于我们每个人心中直觉上的一致性模型，这种走错教室的情况肯定是错了，但是对于一个性格怪异的老师，也许他觉得这样也是对的，比如他可以找他的同事帮他上152教室的课，他自己上252教室的课，也正因他如此怪异，所以他最开始联系网站管理员时也遵循了他心中的怪异的一致性模型，没有等网站确实修改就给学生们发了查询教室的通知。 coherence的例子 紧接上个例子，与之不同的是，很多学生在最开始选课的时候就把《体系结构》这门课的教室152记在了自己的小本本上，但是后来，管理员将网站上教室信息改成了252。虽然学生的小本本上和教务处网站上的信息应该是同一个信息，应该是一样的，但是这时两者一个152，一个252，这就出现了incoherent的情况。 在内存系统中，学生的小本本就相当于cache，而教务处网站相当于memory，学生将memory中的某个值拷贝到了cache中，当memory被其他人更新时，学生自己的cache就应该同时立即处于无效的状态。这里出现incoherent的原因就是没有一个cache coherence protocol来保证cache的正确性。比如，一个简单的coherence protocol可以这么干：在网站更新后，老师挨个找到每个学生，把他们的小本本记的152划掉?，无效化协议就是这种思想。 2. […]

by ·0 Comments

“新司机”虽然上路了，但并不知道走了多少弯路，因为还知道有没有走上正路。但上路也快一年了，当然有一些体会，就算是错的，也该想过些什么。如果我什么体会都不写出来，那么这些想法总会在我的脑子中绕啊绕啊的。所以我希望写些出来，也许这样就可以不用刻意提醒自己不要忘记它们，也好专心”开车”。而且我想，车技总是不断积累联系和回看总结的过程，也许我将来看现在自己的体会，不是嘲笑自己的车技太差就是羡慕自己的没有迷路运气。当然还有一种情况，就是我能因这些感想能将其他”新司机”带上(歪)路，我也是很欣慰的。。。 这系列文章，不去反省自己的缺陷，不去叙述自己的经历，只写下当前所总结的体会。本篇博客，我将写一下对存储栈的理解。后边，我还可能从存储组织(文件系统/存储结构)、存储缓存和虚拟化存储等几方面写下体会。 1. 层次化封装 就像OSI网络参考模型一样，存储也是有层次的，如果在网络中我们将这些层次称为网络协议栈(TCP/IP协议栈)，那么在存储中我们经常用存储栈(storage stack)或I/O栈(I/O stack)与之对应。 顾名思义，栈这一种直上直下一层叠一层的结构。在网络的层次中，数据链路层关心的是MAC地址，网络层关心的是IP地址，栈中的所有层次分工协作，大家像流水线一样将数据层层传递如下图。 在存储层次中，也有类似的分工。比如以Linux存储栈为例，文件系统主要关心的是文件的组织结构，向上将接口暴露给用户；而文件系统下一层的块存储设备层则关心实际数据的去向，主要和存储设备打交道。下图是一个单机上比较复杂的情况，以一个运行在KVM虚拟机中的MySQL为例。当然如果考虑远程网络分布式存储，应该更复杂。 2. 为什么层次是必要的 除了网络和存储，其实编程语言中封装的这种概念，在我看来就类似这种层次化的形式。比如在很多编程语言中常用的SHA256、MD5等安全Hash算法或者链表、各种常用数据结构的库等。这节的问题就以编程中的封装和层次开发为例进行说明。 对编程语言的库来说，问题在于，既然哈希算法的计算方法都是开源的，数据结构都是固定的形式，为什么不自己写呢？首先想到的可能是自己写费时费力，其次一个被很多人使用的库一般都是由各路大神优化而来，应该比自己实现的效果要好，但最重要的，库是可以复用的。 比如那么当我们在这些其他人实现的库的基础上构建自己的应用的时候，就是在库的封装之上进行的开发，这就形成了库–>我的应用的这样的层次结构。进一步说，如果我们是在其他人的库的基础上开发了更高层的库，比如我在其他人写的二叉树库的基础上开发了用于排序的库，那么我们的封装层次就又涨了一层：二叉树库–>排序库–>其他人的应用。再展开说，我们甚至可以冲破一种编程语言的界限，表示出更完整的封装层次：数字逻辑–>指令集–>汇编语言–>系统调用–>编程语言标准库–>二叉树库–>排序库–>其他应用。 如果只是从左到右或者从上到下画出这种层次图，我们还是无法理解层次的必要性，但是如果我们想横向扩充，这种层次就是很必要的。极端的情况：如果我们所有的层次都重叠在一起，那么也许我想开发一个gui小应用，就要从汇编开始，一直沿着操作系统改到库和应用逻辑，简直不现实，这也是软件工程中耦合和内聚的概念。换句话说，不论我们是靠近硬件还是靠近应用的程序员，我们都可以从自己出发，只要向上层和下层提供不变的接口，那么不论我们在自己的范围怎么折腾，都不会破坏其他层次的工作。 回到存储，我们只有将管理文件的file system和下层的设备驱动通过块设备层和虚拟文件系统(VFS)层解耦，才能在单独编写多中设备驱动不用再去修改文件系统代码，也才能在添加新的文件系统功能的同时不用担心对老的设备是否可以工作。 3. 为什么层次可能影响性能 还是以编程语言为例，很多都认可C语言相对其他语言是高效的，但学汇编的人可能觉得汇编才是最高效的，这都没有错，汇编比C高效，但并不属于高级程序语言，C比Python高效，但是指针这种东西没有谁可以一时半会搞定。实际上，汇编–>C–>Python就可以认为是这样封装起来的。某种程度上来说，我们开发C语言应用可以看成是和开发Python是在一个层次上的。。。对于存储也是一样的，层次总是一层一层网上堆的。堆到越上层，越具有其简单易用的特性，而这种层次化页必然会带来性能上的降低。 现在在我看来，存储层次升高带来的性能损失的根本原因是因为在层次间信息的不对称的同时还有些层次要越层”搞事情”。具体来说，层次之间的沟通通过接口，由于层次间较松的耦合，某一层中无法获知其他层中的具体细节。比如，应用程序可能要告诉文件系统具体要读的文件名，但并不知道文件具体存在什么地址；文件系统可能告诉块设备驱动它具体要读内容的地址，但是块设备层就不知道这内容属于什么文件了。 但是，存储的管理不光“你告诉我你要什么数据，我把数据传给你”那么简单：首先，由于数据的重要性，各个层次都要用自己的机制保证数据的完整性和一致性；其次，也要利用数据的局部性，用dram作为cache来弥合内存和二级存储设备间的性能差异。那么大家都要保证数据可靠，大家也都在加把劲降低IO读写延迟，真的是齐心协力力量大吗？ 当然大家都想整个系统变得更好，但是既然层级之间信息不对称，一定会因为缺少合作，而导致自己所做的工作不如预期，甚至起到副作用。我们是需要加强各层间的耦合交互？还是提升各层的“智能”让其揣测其它层的想法？还是应该聘请一个“存储栈独裁程序”来统一发出号令？这块儿学问就大了，还是新司机的我理解并不够深入，车技提升后还要展开多写写。。。 4. 在适当的层次做适当的事 Python认为程序员要指针没啥用，于是没有设计出指针的概念。而可能在一些C语言程序员眼中，Python因此就是一种有缺陷的语言。但是我们可能忽略了一点，就是没有谁禁止过Python程序员学习C语言，也没有人禁止过C程序员学Python。对于一个项目来说，没有最好的语言，只有最合适的。 对于存储层次同样如此，比如同样是数据加密，我们可以在应用程序中加密数据，可以在文件系统中加密数据，可以在数据网络传输之前进行，极端的情况，甚至也可以在硬盘硬件中进行加密。对于cache，我们可以在应用层开辟内存作为cache、或者利用文件系统缓存，或者磁盘的硬件缓存等。选择很多，不同的功能，适合的位置也是不同的，同样和上节一样，这块儿学问就大了，还是新司机的我理解并不够深入，车技提升后还要展开多写写。。。

by ·0 Comments

时隔近3个月，我本科毕业后第一次回到了西安，见到了在本校读研的舍友们，不过主要还是来参加信息存储年会的。 会议有特邀报告、青年学者报告和优秀论文交流报告，分别是大神级的学者、大神级的青年学者和大神级的博士生进行报告，听了这些报告真的感觉到自己的差距有多么大，同时感觉不虚此行。 这是一篇我所听报告的部分内容的总结，语言从我个人理解的角度出发，信息可能不全或不准确，如有问题，欢迎讨论和指正。 阻变存储器性能优化方法的研究 冯丹教授讲的题目是“ 阻变存储器性能优化方法的研究 ”。首先RRAM(阻变式存储，Resistive Random Access Memory，ReRAM)是一种非易失性存储器(NVM)，尺寸单元小，有发展潜力。冯丹教授这次的报告是比较偏硬件，但还是有很多启发。 背景： DRAM在技术上要降低能耗、提升容量越来越难，而且DRAM技术提高的速度比CPU慢，另外技术工艺达到40nm之后很难再提高。所以ReRAM代替DRAM是一种选择。 RRAM的存在的问题： 1. reset延迟和能耗代价均高于set；2. TLC的延迟大于SLC；3. 存在IR-drop的问题，离驱动电源越近，延迟越低。 几项工作： 1. 针对上述第一点问题，提出了可以将对角线上的set和reset并行，这样降低了总延迟时间。 2. 针对上述第二点问题，使用了一种“压缩率感知”的方法，利用MLC/TLC中中间几种状态慢于两边状态的特点，将中间的几个状态合并，根据压缩的工作负载的压缩率，来进行决策，重新编码存储（比如把原来MLC的4中状态中的第2、3两种合为一个状态，这样就变成了3中状态，减小了延迟和能耗）。3. 针对上边的第三点问题，用双端驱动代替单端驱动，这样处于接近电源驱动的区域就增多了，并且可以根据快慢在驱动层中区分硬件上的快慢区域，来合理使用。 半层次化的语义存储体系结构 华中科大华宇教授的报告，讲了一种” 半层次化的语义存储体系结构 “，希望将原来的存储结构（比如文件系统的目录结构）转为一种多标签的索引结构。 背景： 存储有5个趋势，分别是更大规模、智能化、一体化（计算和存储更近）、长期化和边缘化（雾计算，临近计算等）。 问题： 存储的层次化越来越明显，同时新兴的存储期间很多(PCM、SSD、DRAM、3D Xpoint……)；NVM能缓解存储的压力，但是由于寿命等问题无法从根本上解决问题；对于文件系统来说，查找树不是太高就是太胖；locality的设计思想是用稀缺资源存储最热的数据，但目前的大趋势是locality正在减小；cache的适应能力弱，比如需要较强时间的预热，代价很高。 解决思路： 用语义存储带起当前的存储模式，例如：文件系统中使用扁平化的树结构，一个文件同时贴上(识别出)多种标签；有了这种模式，非精确dedulication中可以在关联数据间进行，提升效率；近似图像语义间的dedupe；data cube是对于高维查找提前做出计算的一种方法，如果基于语义，可以缩小计算范围。 数据中心驱动下KV系统的设计和实现 德州大学阿灵顿分校的Song Jiang教授主要讲了KV系统的缓存问题。 问题： 由于在分布式存储中，所有的访问都要经过metadata server(MDS)，所以MDS是一个瓶颈，应用Key-Value(KV)系统就是取消了MDS的一种解决方案。KV系统是需要缓存的，怎么更高效的利用有限的缓存空间是一个问题。 思路： 可以使用更好的缓存数据替换算法，但是并没有效果太好的；可以提升内存容量，但是这会直接导致成本上升；可以利用压缩提升缓存利用率，但是解压和压缩也会导致很大的性能下降。 方法： 对实际访问trace数据分析发现，随着缓存空间的增长，缓存命中率上升到80%是很快的，但从80%上升到90%则需要更多的内存，基于这点，将cache分级，最热的数据不进行压缩，对并非太热的数据进行压缩，这就很好的平衡了压缩解压缩的延迟和缓存的利用率问题。 对于这种方法，还有一个解释，就是对cache命中，即使要进行解压缩操作，时间也远远小于访问存储服务器进行磁盘访问，这样，即使缓存利用率提升了5%，也可能带来很大的性能提升效果。Song教授解释的意思是，由于磁盘访问的速度特别慢，在命中率从90%提升到95%的情况下，更应该看到的是未命中率降低了一半(10%–>5%)，而不是命中率提升了很少（90%->95%） 其他 清华的陆游游博士介绍了NVM+RDMA的分布式存储方案，有了RDMA，CPU传送所有数据的等待时间减小到传送存储地址的时间。 华科博士生左鹏飞提出了一种基于位置分享的解决哈希冲突的策略，用于NVM系统。 上海交大的博士生董明凯介绍了他发表在ATC 17上的文章Soft Updates Made Simple and […]

by ·0 Comments

（发布于 April 3, 2013， 意译于12/9/2016） 原文链接 ：https://lwn.net/Articles/545244/ 另一个版本的翻译(有些句子没有翻): http://kernel.taobao.org/index.php?title=%E5%86%85%E6%A0%B8%E6%9C%88%E6%8A%A52013-04#In-kernel_memory_compression 吐槽 : 我的天呐！！翻译完我才发现有人翻译过了，早知道我就不自己翻译了，痛苦死我了。。 PS :内容我还没有完全理解，仅供参考，以原文为准。 阿姆达尔定律告诉我们一个计算机系统肯定存在一个瓶颈。历史上，对于很多工作负载这个瓶颈都是cpu，所以人们在不断提升cpu性能。所以现在，渐渐地，ram成为了瓶颈。有时当数据在ram和disk之间来回传递时，cpu就在一边干瞪眼呢。增大ram有时并不是一个好的或者经济的做法，更快的I/O或者ssd可以缓解问题，但是不能消除这个瓶颈。 如果可以增大ram中数据的有效容量，不是很好吗？既然cpu闲置，也许我们可以拿闲置的cpu周期来专注这件事。这就是内核内压缩的目标：用闲置的cpu周期来做ram中的压缩和解压缩。 算上刚刚发布的zswap，现在有3个内核内实现的压缩方法在被建议merge到内核的内存管理(memory management, MM) 子系统：zram, zcache和zswap。乍一看可能会让人觉得一个就够了吧，但是他们三个却有很大的不同，可能面向着不同的用户群。所以就像现在内核中存在很多文件系统一样，有一天内核中也会存在多种压缩方案吧，不过这还得李纳斯大神和主要的内核开发者说了算。。。为了方便说明，本文把这些方案统称“zproject”，并对比了这些方案。我们先说明一些关键原则和压缩遇到的挑战。然后我们会从三个层次说明并详细地阐释这些zprojects设计上的不同选择，之后我们还讨论zprojects怎么和内核其他部分交互，最后给出结论。 压缩基础 要让压缩在内核中工作，内核必须把字节序列放入内存中再压缩，之后内存中也应保有压缩后的版本，以备这些数据被再次使用。压缩状态下的数据不能被读写，所以对压缩版本的数据再进行解压缩后才能继续读写这些数据。 字节序列压缩多少都可以，但还是以一个固定大小的单元压缩较方便。贯穿整个内核的一种基本的存储单元是page，一个page由PAGE_SIZE个字节组成，通常的linux支持的架构中，page的大小是4KB。如果这个page对准了PIGE_SIZE的地址分界，那么它就被称为page frame。对于每个page frame，内核在ram中都有相应的struct page结构。所有这三个zprojects都用page作为压缩的单元，并且通过开辟和管理page frames来存储压缩页。 有很多可用的压缩算法，但总的来说，高压缩比意味着高cpu周期，运行的快的算法一般压缩比较低。在时间效率和压缩率之间做出权衡很重要。这三种zprojects，默认都使用内核lib/文件夹中的LZO(1X)算法，这种算法做出了很好的权衡。然而，算法的选择还是很灵活的，也许cpu运行的算法还会被一些特殊架构的硬件压缩引擎取代呢。 一般，存在一些数据一会儿压缩一会儿解压缩的循环，数据序列大概和序列中的字节数成正比。因为页比较大，页压缩和解压缩都是很昂贵的操作，所以我们希望限制这些操作的数量。因此我们必须谨慎的选择哪些页要被压缩，尽可能找到那些可能会被再次用到同时最近不会用的页，以免把cpu时间浪费在重复的压缩然后立刻又解压缩上。因为压缩页不能直接访存某个字节，我们必须要保证内核清楚地辨识出哪个是压缩页，避免对压缩页中的字节尝试cpu的线性地址操作，同时保证压缩页可以被找到并可以在被访问时解压缩。