XonLab

序现在普适性较强的适合磁盘的索引结构无非就是B-tree和LSM-tree，两种结构的最本质的不同在于，一个是就地更新（B-tree）一个是非就地更新（LSM-tree）。就地更新的索引结构拥有最好的读性能(随机读与顺序读)，而随机写性能很差，无法满足现实工业中的工作负载要求。而非就地更新的索引结构LSM-tree充分发挥顺序写入的高性能特性，成为写入密集的数据系统的基础。 在开始论述wisckey带来了什么改变之前，我们先回顾一下经典LSM-tree的实现。 LevelDB实现前文提到LSM-tree的优势在于非就地更新，它的表现形式实际上就是延迟更新，顺序写入数据。但这样做也带来了很多问题。首先同一个key可能会占据多个存储空间，简单的解决方案就是每次读取的时候都是从后往前倒序的查找数据，这样保证了拿到的数据一定是最新的，该操作的复杂度为O（n）。优化该方案的手段就是后台对数据文件进行压缩，删去过时的数据。 每次压缩的过程本质上是一次归并排序的过程(为了支持范围查询，以及空间压缩)，那么就需要找到所有分段文件中有重合范围的文件，进行合并(min_key与max_key)。并且不能合 ...

Abstract我们展示了WiscKey，一个基于LSM树的持久键值存储，具有高性能的数据布局，将键和值分开，以最小化I/O放大。WiscKey的设计是高度面向SSD优化的，利用了设备的顺序和随机性能特性。我们通过Benchmark和YCSB工作负载展示了WiscKey的优势。Benchmark结果显示，WiscKey加载数据库的速度比LevelDB快2.5×-111×，随机查找快1.6×-14×。在所有六个YCSB工作负载中，WiscKey都比LevelDB和RocksDB快。 Introduction持久的键值存储在各种现代数据密集型应用中发挥关键作用，包括网络索引[16,48]、电子商务[24]、数据重复删除[7,22]、照片存储[12]、云数据[32]、社交网络[9,25,51]、在线游戏[23]、消息传递[1,29]、软件存储库[2]和广告[20]。通过支持高效的插入、点查找和范围查询，键值存储成为这些领域的基础技术。 对于写密集型工作负载，基于日志结构合并树（LSM树）[43]的键值存储已经成为最先进的技术。基于LSM树构建的各种分布式和本地存储被广泛部署在大规模生产环境中 ...

Efficient key-value stores with Ranged Log-structured Merge Trees Nae Young Song and Heon Young YeomDept. of Computer Science and Engineering Seoul National University Seoul, South Korea Email: {nysong, yeom}@dcslab.snu.ac.kr Hyuck Han Dept. of Computer Science Dongduk Women’s University Seoul, South Korea Email: hhyuck96@dongduk.ac.kr 摘要LSM树旨在用日志-结构化方法来为频繁更新的数据提供一个高效的索引。它重排数据时使用延迟更新，利用内存组件来将索引的更新传播给一个或多个磁盘组件。因此基于LSM树的存储引擎可以有较好的写性能。然而在合并的过程中有着较高的写放大和内存消耗，降低了系统的总性能。 此篇论文中，我们提出了一种Ranged ...

这一章研究的问题是一个Packet是如何经过路由从一端到另一端的。路由选择的依据是什么？ Flooding topology 拓扑结构; Flooding采用多播来传递Packet每个Router都会把包发给与它相连的每一个Router，这也导致了链路的高占用率，和形成环的可能性，一旦成环Packet将会在这个环里被一直转发。不过这种机制也有好处，因为每个Router肯定都会被遍历，所以如果目的端和某个Router相连，那Packet一定会被发送到目的端。当然Flooding实际上也不会导致包被永远转发因为TTL会限制被转发的次数。 Source Routing Source Routing指的当源知道网络的拓部结构，自然它也知道要传Packet到目的端要经过哪些Router，所以它会在自己发出的包中指定每一跳的路径。 Forwarding Table 每个Router维护一张转发表，根据转发表来决定下一跳。 转发表听起来效率比较好，也是目前主要采用的转发流量的方法，但问题在于这张转发表该如何正确构建呢？ Bellman-Ford Algor ...

Network Address Translation(NAT) NAT 的作用是暴露一个公共的IP，外部流量想访问内网时会先经过NAT，然后NAT把流量转发给对应的内网主机。这样就不用每个设备都占用一个公共的IP了，但这也产生了新的问题，NAT后的IP都是NAT来管理并分配的，外网怎么能拿到NAT后的IP并发起连接呢? 现在A在NAT后面，B想访问A，但是现在NAT中没有B到A的映射，自然无法访问到A。此时就需要rendezvous service，图中的R提供rendezvous service，首先A和B都会在R中注册。如果B想连接A，它会先想R发出请求，然后R携带着B的地址向A发出请求，A再来反向连接到B，以此来建立A和B之间的连接。 如果A，B都在NAT后面，A、B想要连接彼此都需要先找R，R做中继来转发A、B的流量。 HTTP HTTP协议即超文本传输协议，那么什么是超文本？超文本指的是一个文档格式，使得我们可以把一些格式和内容信息放到一个文档中。超文本由ASCII字符构成。 HTTP Request Format HTTP会携带请求的方法（GET、POST… ...

前置知识硬中断：由外部设备产生的异步中断，可能发生在任何时间。比如网卡通过DMA将报文写入内存后将发出硬中断，来请求CPU处理报文数据。这是一种典型的事件驱动的模型。 软中断：由CPU产生，比如在程序执行过程中出现错误时，会产生软中断以此来让出CPU。 NIO、BIO：在数据传输的过程中，通信的双方在把数据交给CPU前都会先把数据放到缓冲区中，输入有输入缓冲区，输出有输出缓冲区。现在有一个A事件想向剩余空间只有5KB输出缓冲区写完10KB的数据那自然是无法写入的，也即会触发阻塞。NIO的处理方式是给A返回一个EAGAIN error，之后开始执行B事件，C事件… 等到设置的A的重试时间到了的时候再次尝试写入A，而BIO的处理方式是无法写完时，A事件就一直等待直到缓冲区有空间能完全写入10KB数据，然后再去执行B事件。 用户态与内核态的转换：在程序执行的过程中如果涉及到一些硬件调用或者遇到了错误，就会出现用户态与内核态的转换。假设申请某一资源时，CPU先会保存现场，然后触发80中断进入内核态，根据具体的资源类型来使用不同的系统调用，当调用完毕拿到资源后，恢复现场变为内核态，继续执行指令。 ...

在网络传输的过程中，拥塞是不可避免的。因为packet switching只负责尽可能的发包，而不去管链路的拥挤情况。如果出现了拥塞则排队中的包会进入Buffer，Buffer满后会丢弃并要求重传，这一是浪费了这个包传输过来所使用的链路资源，二是会进一步加剧拥塞。此时，就需要拥塞控制，来尽可能地避免重传。拥塞控制的设计目标有以下几点： 高吞吐量：尽可能高效的利用链路 公平性：确保所有flow在进入瓶颈链路时能被公平对待 面对变化的网络情况可以快速做出反应 分布式控制 TCP的设计思想就是高效的利用链路，在这个思想指导下，TCP连接时丢包重传是必须的，这实际上是一个信号，告诉TCP链路已经到承受能力的极限了，但是要降低重传的概率，这样才能让包高效的被传输到对端。 TCP Congestion Control TCP的拥塞控制由终端实现，它由观察到的事件来决定如何做出反应（是否丢包），利用滑动窗口来实现流量控制，并试图找出一个能让所有包都正常传输的流速。 如果一个滑动窗口的长度小于Round-trip time(RTT)那么链路上就会看到一个终端一会发一个包停一会让后再发一个 ...

一个接口类型的值被分两部分：一个具体类型（动态类型）和该类型的一个值（动态值）。在Go中类型只是编译时的一个概念，所以类型不是一个值。 在以下四个语句中w有着三个不同的值（最初和最后是同一个值）。在Go中接口和引用类型(slice、指针、map、通道、函数)如果只声明，没有初始化的话，其值是nil。如果数组或者结构体这样的复合类型，零值是其所有元素所有成员的零值。 var w io.Writer w = os.Stdout w = new(bytes.Buffer) w = nil 对接口来说它的的零值就是把它的动态类型和值都设置成nil。一个接口值是否为nil取决于动态类型，所以现在这是一个nil接口值。可以用w == nil或者w != nil来检测该接口值是否为nil，如果调用一个nil接口的任何方法都会导致崩溃。 w.Write([]byte("Xonlab")) // 崩溃；对空指针取引用 第二个语句把*os.File类型的值赋给了w 这次赋值把具体类型隐式转换为了接口类型，它的显示转化形式是io.Write(os.Stdout)。不论这种转换是显式还是 ...

Propagation Delay 传播延迟指的是在链路以某种速度传输1bit所用的时间。 Packetization Delay 打包延迟指的是从包中第一个bit开始计算，到最后一个bit被放入链路所经过的时间。 End-to-end delay 端到端延迟：Package从一端传输到另一端的时间，具体的计算方法就是每一个Router间的传播延迟+打包延迟的总和。 当链路上出现拥塞时，Router会将待转发的包放入Buffer此时的端对端延迟要在加上一项排队延迟，该项延迟是不可预测的，它由链路的拥塞时间决定。 Queue Model 这个队列模型就像一个水桶，Package从各个Router发到队列中，再以R的速度出队。这里就涉及到两个转发策略：即时转发、存储转发。不同的策略会影响队列的占用率。 从这可以看出为什么要把数据分解成Package来传输，因为这样可以利用链路来近乎并行的传输Package以降低端到端延迟。 Generic Packet Switching 当Package到达Router后将经历以下几个过程 查找地址，然后根据转发表来决定 ...

The Log-Structured Merge-Tree（LSM-Tree） Patrick O'Neil, Edward Cheng Dieter Gawlick, Elizabeth O'Neil To be published: Acta Informatica 摘要：高性能事务系统通常以在历史表中追加记录的的方式来追踪各项活动；同时事务系统生成日志来应对可能的数据恢复。这两种生成信息的方式都可以从一个高效的索引中受益。在TPC-A基准测试中有一项测试修改下就可以在给定的History表上对给定account的活动记录进行高效的查询支持。但这需要在快速增长的History表上建立一个针对account id的索引。不幸的是标准的基于磁盘的索引结构比如B树将花费两倍的I/O成本来维护实时索引，这会把系统的总I/O成本增加百分之五十，所以一个很明显的优化方法就是降低维护实时索引的成本。Log-Structured Merge-tree (LSM-tree)是一个面向磁盘的数据结构，旨在提供一个可以应对长时间大量插入与删除的低成本索引。LSM使用一种推迟和分批更新索引的改进算法， ...