这篇论文讲的就是lamport的logic lock The Partial Ordering 如果一个事件A发生早于B，大多数人会说A发生在B之前。因为他们会用物理时间来证明这个定义。然而，如果一个系统要满足规范，那么这个规范就必须根据系统内可观察到的事件给出。如果我们的规格是物理时间，那么系统必须包含真正的时钟，而且就算是他包含了真正的时钟，我们也会遇到时钟不准确的可能性。所以我们不通过物理时钟定义“happened before“ 我们假设一个系统由若干个进程组成，每个进程包含了具有全序关系的若干个事件。同时…
整体架构 貌似和bigtable完全相同 level由这几个组建组成 memtable 是一个主存中的跳表。按序存储。当容量到达阈值的时候就转换成一个不可修改的memtable immutable memtable 不可修改的memtable。当他被创建的时候，leveldb的后台压缩进程会利用其中的内容创建一个sstable。持久化到磁盘中 log WAL，每次写操作要先顺序写日志。从而保证我们可以从异常状态下恢复。 写操作的原子性也由日志来保证，当日志成功写入的时候，写操作成功。当写日志异常的时候，后续的恢复会…
Abstraction 论文中说这个percolator是用来进行增量处理的一个系统，用来替换MapReduce在google indexing system中的作用 但是没有提到transaction相关的东西 Introduction 考虑我们为网页构建索引的任务。索引系统首先会把每个网页都爬下来，如果有多个URL都指向了相同的内容，那么拥有最高的PageRank的URL会被保留下来放到索引中。我们还会把每一个链接对应的anchor text附在他指向的页面中。同时要保证对于链接指向的重复的内容，我们也会把它转…
Consistency level in DBMS CAP中的C和ACID中的C都代表了consistency，但是他们的含义是完全不同的。 比如ACID中，一致性是指用户定义的语义。指的是我们不会违反引用约束，外键约束，以及一些用户定义的约束。 而在CAP中的C指的是让并发执行的分布式系统表现的像是一个单线程的中心化的系统。在某一时刻的读必须只有一种可能的情况，即他们反映了最近写入的数据 在ACID中，consistency level通常是不会使用的。因为ACID中的C基本上都是application deve…
背景 隔离的定义（为了清晰我就贴原文而不是自己翻译了） Database isolation refers to the ability of a database to allow a transaction to execute as if there are no other concurrently running transactions 隔离的目的就是我们在并发执行事务的时候不希望一个事务的读写操作作用于一些临时的，错误的，或者不完整的数据 最强的隔离级别被成为可串行化（serializability）…
Chubby lock service chubby的目的就是为一些低耦合的分布式系统提供粗粒度的锁服务，以及可靠（但是低容量）的存储。 chubby提供的接口则类似于一个带有锁的分布式文件系统。但是chubby的设计重点在于可用性以及可靠性。而非高性能。 Introduction lock service的目的是让客户去同步他们的活动，并且对一些信息达成一致。 我们希望chubby为一些系统提供粗粒度的锁服务，特别的是处理选主的问题。比如GFS通过chubby来指定一个master。bigtable也通过chub…
首先明确，bigtable是一个用来管理结构化数据的分布式存储系统 Introduciton bigtable的目标就是去scale到大数据的规模。并且应用范围比较广，从面向吞吐量的批处理任务到延迟敏感的用户服务。 bigtable并不提供完整的关系数据模型。而是提供了一个较为简单的数据模型，并且支持动态的控制数据的布局以及格式。从而让客户去推断数据的位置属性。 数据通过行和列名来进行索引。 bigtable将数据看作是未解析的字符串。 用户可以通过他们定义的schema来控制他们数据的位置。并且bigtable还…
为xv6添加线程库支持的设计 为xv6添加线程库支持，我们有两个点需要考虑。 生成新的线程 线程之间的同步 生成新的线程思路和linux中的lwp是一样的 具体可以看这封邮件 生成新的线程的思路和fork基本类似，只不过我们这里会把除了栈以外的地址空间共享。 这时候有个问题就是多个线程共享同一个地址空间的时候，我们只能释放一次，而不能让每个线程退出的时候都释放。 所以我们需要一个引用计数的结构。当两个进程共享地址空间的时候，他们就会共享这个引用计数器。只有最后一个离开的进程才需要释放整个地址空间 由于没有实现信号，…
内核初始化内存 内核需要建立一个映射来制定那些物理地址可用，那些不可用（比如对应了MMAP-IO，或者BIOS数据） 保留状态下的页不能被交换到磁盘上。比如不可用的物理地址，以及内核的数据或者代码 第0个页由BIOS使用，用于存放加电自检期间检查到的硬件数据 在启动过程的早期阶段，内核询问BIOS并了解物理地址的大小。 之后内核执行machine_specific_memory_setup，建立物理地址映射 他会根据BIOS给出的数据映射一些保留的页。并且分析物理内存区域表来初始化一些变量来描述内核的物理内存布局 …