Google Spanner是google在2012年公开的存储系统,它的最大特点就是数据分布在全球范围内,支持外部一致性的分布式事务。本文依据论文解读了该系统的设计和实现。
《挑战程序设计竞赛》读书笔记(一)搜索 回溯
本文阅读了《挑战程序设计竞赛》前几页,写了部分读书笔记。对其中一些例题增加了新的解法,文中增加了图示效果帮助自己和读者加深理解,扩充了回溯等算法,增加了回溯中搜索子集树和排列树的框架。
Deep Class
最近看了个有趣的talk:"A Philosophy of Software Design" by John Ousterhout。
如果要选一个概念,贯穿整个计算机系统,应该选哪个呢?
John Ousterhout问过Donald Knuth,Knuth给的答案是layers of abstraction。
John Ousterhout自己觉得是problem decomposition,要注意隔离复杂度。
Split-Order Hash基本原理
之前阅读论文并实现了一个可扩展的哈希表,已经在生产环境使用。这里简单描述一下思路和一些经验教训,详细的实现可以参见论文。
深度优先搜索求解青蛙交换位置小游戏
用DFS搜索算法求解青蛙交换位置游戏。详细描述了算法的步骤和代码结构,包括描述状态的表示,获取后续状态,执行递归的DFS搜索。该方法具有很强的通用性。
Bitcask简介
Bitcask是由Basho公司搞的一个产品。
技术设计
数据顺序追加到磁盘上的active data file,并在内存中建立hash索引。
active data file文件长到一定程度就切成old data file,新的数据写入新的active data file。
old data files定期merge成一个merged data file,merge过程中同时会生成一个hint file来索引这个merged data file。
data file存放格式
内存keydir
是一个key -> <file_id, valu...
Dynamo论文阅读笔记
Dynamo: Amazon’s Highly Available Key-value Store
Dynamo这篇论文是2007年出来的,以前读研究生的时候读过,前两天看了一篇NoSQL综述提到了这篇论文,今天重读一遍,简单做些笔记,里面有些东西还只是简单看了下不够深入。
Dynamo系统本身并没有提出新的技术,但是将各种分布式技术融合在一起,构建了一个高性能高可用高可扩展的key-value存储。Dynamo牺牲了强一致性,使用vector clock等方法把数据冲突...
FLP impossibility证明 阅读笔记
分布式系统一致性协议里面有一个FLP impossibility的结论,这个结论是说,在分布式系统中,异步网络(消息延迟可能任意大或丢失,消息可能乱序),只要有一个进程失效(进程死亡或者足够长时间不响应),就不可能设计出一个一致性协议。
该结论由Fisher、Lynch、Paterson三位分布式系统领域的科学家在1985年在论文Impossibility of Distributed Consensus with One Faulty Process证明。本文解读了证明过程。
Spanner: Becoming a SQL System论文阅读笔记
继2012年在OSDI年发表了Spanner论文《Spanner: Google’s Globally-Distributed Database》之后,Google在SIGMODE'17上发表了第二篇关于Spanner的论文《Spanner: Becoming a SQL System》。从整个的数据库系统角度看,2012年那篇讲是的Spanner的下半部分Storage Engine的一些feature:数据自动分区和全球部署、多副本Paxos高可用、支持外部一致性的分布式事务。2017年这篇主要讲是讲数据库的上半部分...
LB+Tree:面向3DXPoint优化的B+Tree
《LB+Trees: Optimizing Persistent Index Performance on 3DXPoint Memory》(VLDB20')
这是个设计非常巧妙的数据结构,这里简单描述下核心内容,读者可以直接读原文,行文非常清晰。
Abstract
3DXPoint的有些硬件特性,跟常规NVM差不多:
3DXPoint的访存粒度是64字节Cache Line
3DXPoint比DRAM慢2倍,比SSD快几个数量级
3DXPoint的写比读慢
使用clwb/sfence等特殊指令将数据从CPU...