首先明确，bigtable是一个用来管理结构化数据的分布式存储系统 Introduciton bigtable的目标就是去scale到大数据的规模。并且应用范围比较广，从面向吞吐量的批处理任务到延迟敏感的用户服务。 bigtable并不提供完整的关系数据模型。而是提供了一个较为简单的数据模型，并且支持动态的控制数据的布局以及格式。从而让客户去推断数据的位置属性。 数据通过行和列名来进行索引。 bigtable将数据看作是未解析的字符串。 用户可以通过他们定义的schema来控制他们数据的位置。并且bigtable还…
为xv6添加线程库支持的设计 为xv6添加线程库支持，我们有两个点需要考虑。 生成新的线程 线程之间的同步 生成新的线程思路和linux中的lwp是一样的 具体可以看这封邮件 生成新的线程的思路和fork基本类似，只不过我们这里会把除了栈以外的地址空间共享。 这时候有个问题就是多个线程共享同一个地址空间的时候，我们只能释放一次，而不能让每个线程退出的时候都释放。 所以我们需要一个引用计数的结构。当两个进程共享地址空间的时候，他们就会共享这个引用计数器。只有最后一个离开的进程才需要释放整个地址空间 由于没有实现信号，…
内核初始化内存 内核需要建立一个映射来制定那些物理地址可用，那些不可用（比如对应了MMAP-IO，或者BIOS数据） 保留状态下的页不能被交换到磁盘上。比如不可用的物理地址，以及内核的数据或者代码 第0个页由BIOS使用，用于存放加电自检期间检查到的硬件数据 在启动过程的早期阶段，内核询问BIOS并了解物理地址的大小。 之后内核执行machine_specific_memory_setup，建立物理地址映射 他会根据BIOS给出的数据映射一些保留的页。并且分析物理内存区域表来初始化一些变量来描述内核的物理内存布局 …
就把这篇论文当作图计算的入门论文了 GNN中一个顶点的计算过程 要收集他的邻居的信息，然后aggregation，再传入到传统的DNN中做分类/回归 Roc用了一个linear regression model做partition 通过dp来最小化数据传输的代价 GNN对于每一个vertex学习一个vector representation，并可以用这个representation给下游任务。比如做vertex classification, graph classification, link predictio…
NeuGraph Programming Abstraction GCN: 初始情况下，每个vertex都有一个feature vector 每一个顶点都收集他邻居的特征向量，然后根据边上的权重进行加和。 然后一个全连接的NN来计算新一层的特征向量 比如在推荐系统中，如果用户对某一个item进行评分，就可以在用户顶点和item顶点之间连边，评分即作为边值。然后GCN可以从graph以及用户和item的特征中学习用户和item的embeddings。最后通过这些embedding来预测缺失的user-item评分 G…
Introduction pregel的program model类似BSP。每一个iteration叫做一个superstep。每一个superstep，系统会在读取上一个superstep传给顶点的数据，并应用user-defined function，然后他会沿边将数据传输出去，从而让他的邻居在下一个superstep使用这些数据 这种做法和MapReduce非常像，用户给出处理每个顶点的逻辑，然后系统会将这个操作应用到大规模的数据集上，并且不会暴露出执行顺序以及superstep之间的通信细节。 Model…
Motivation 虽然最先进的共享内存处理系统可以高效的处理图。但是缺乏可拓展性使得他们无法处理那些单台机器无法承载的图。而分布式解决方案虽然可以将图拓展到更大的规模。但是他们的性能和成本效率往往不是很好 一个对于前沿系统的比较 可以发现分布式系统的网络没有饱和。限制他的主要因素是计算而非通信 与共享内存系统相比，他们执行了更多的额指令，更多的内存引用，更差的局部性以及多核利用率低。这种低效性有多个来源：（1）通过hashmap来在全局和局部状态间转换vertexID，（2）维护顶点的副本，（3）在GAS中的c…
Recall Transaction in DBMS 整理一下DDIA中事务这一块 事务让我们可以为上层提供一个非常强大的抽象，而不需要将具体的细节暴露给上层 事务所提供的保证，即ACID，分别代表原子性，一致性，隔离性以及持久性 有的不符合ACID的系统有时被成为BASE，即基本可用性(Basic Available)，软状态(Soft state)，最终一致性(Eventual consistency) 原子性，指的是我们可以将事务内包含的一系列操作转化为原子操作，即要么所有的操作都发生了，要么一个也没发生。注…