More than code

More Than Code
The efficiency of your iteration of reading, practicing and thinking decides your understanding of the world.
paper

High-Performance Concurrency Control Mechanisms for Main-Memory Databases

High-Performance Concurrency Control Mechanisms for Main-Memory Databases 这次换一个记录的方式。点出思考和关键点,而不是类似翻译似的看文章 single version locking works well when transaction are short and contention is low The multiversion schemes have higher overhead but are much less sensit…

2022年7月16日 0条评论 300点热度 0人点赞 sheep 阅读全文
paper

Opportunities for Optimism in Contended Main-Memory Multicore Transactions

Opportunities for Optimism in Contended Main-Memory Multicore Transactions 看这篇文章主要是看看各种并发控制的protocol Abstract 他提到那些与concurrency control无关的implementation choices是导致性能下降原因。 Intrudoction partially-pessimistic concurrency control, dynamic transaction reordering以及M…

2022年7月10日 0条评论 258点热度 0人点赞 sheep 阅读全文
paper

Serializable Snapshot Isolation in PostgreSQL

Serializable Snapshot Isolation in PostgreSQL Abstract 就是SSI在Postgres中的实现 Overview Postgres之前只有snapshot isolation。9.1版本提供了SSI的实现。 Postgres的SSI实现必须要和现有的特性结合,而不能像research prototype一样忽略很多细节。比如要支持replication,two phase commit,subtransaction。还有控制memory useage。 和之前的系…

2022年7月10日 0条评论 317点热度 0人点赞 sheep 阅读全文
未分类

leveldb-9 Cache

Cache 这次看看Cache 和文档中的不同,文档中的这个是goleveldb的。而我们看的是C++的leveldb C++的leveldb就是一个简单的LRUCache 并发控制通过一个大mutex来保护。为了减少冲突分了Shard 不过leveldb中的LRU是intrusive的,他的Node内嵌了list和hashmap的变量 LRU的主体在这里,其中HandleTable是一个哈系表,由key映射到Handle上 lru和in use其实可以猜到,一个是lru的链表,一个是当前使用的,也就是pin住的链…

2022年7月8日 0条评论 372点热度 1人点赞 sheep 阅读全文
未分类

leveldb-8 SSTable(3) Read & Write

SSTable(3) Read & Write 参考文档在这里 还是看这个图。footer是固定的,通过footer去找到meta index block和index block meta index block指向filter block,为什么不直接让footer指向filter block呢?因为meta index block中存储了filter的名字,是变长的。而footer是定长的。所以增加了一个额外的indirection 代码中主要是在table builder做写操作 table buil…

2022年7月3日 0条评论 311点热度 1人点赞 sheep 阅读全文
未分类

leveldb-7 SSTable(2) filter block

SSTable(2) filter block 文档在这里 这次代码比较简单 StartBlock的作用就是不断构建索引到filter offsets Finish会把剩下的数据的filter构建出来。然后把每块对应的offset追加进来,最后加上总共的array length以及BaseLg。具体含义可以看文档 result就是这些data block 可以看到核心的逻辑就是这个GenerateFilter了。他会先把当前的buffer切成原本的key。然后通过CreateFilter创建filter 这里的Cr…

2022年7月3日 0条评论 230点热度 0人点赞 sheep 阅读全文
未分类

leveldb-6 SSTable(1) data block

SSTable(1) data block 每次minor compaction都会生成新的sstable,major compaction会将若干个sstable合并成一个大的sstable。 这次我们看一下sstable的读写过程。参考文章在这里 一个sstable文件按照块划分,用来提高读写效率。每个块的大小为4kb,每个block中除了存储数据还有压缩类型以及校验码 sstable中不同的block有不同的功能 data block 由于leveldb是按序存储,所以我们会使用类似前缀压缩的技术。不同的是每…

2022年6月21日 0条评论 290点热度 0人点赞 sheep 阅读全文
未分类

Rust ODT

Rust ODT ODT主要处理的是包含区间赋值的问题。以前的名字叫Old Driver Tree。核心思路就是通过随机数据的情况下,区间赋值的操作可以合并很多区间为一个整块。我们通过三元组的形式,即left,right,value来表示区间。在查询的时候就只查询范围内的三元组。由于区间赋值可以合并区间,所以总共要查询的数量很少。 可以从这道题来了解这个数据结构 ODT的核心就是两个函数。一个是split,将我们维护的区间中在一个点处断开。还有一个是assign,即区间赋值 fn split(&mut se…

2022年6月20日 0条评论 236点热度 1人点赞 sheep 阅读全文
未分类

leveldb-5 Memtable

Memtable 这次到了memtable中,也就是leveldb的内存中数据结构 参考文章 跳表的思路就是通过概率来进行平衡,而非平衡树那样强制平衡。从而使得我们的实现可以简化很多。 上面这个例子就是增加指针的链表。让我们可以稳定按照2的次幂的步数进行跳跃。但是缺点就是很不容易处理,因为插入的时候要去仔细计算我们跳过了多少节点,从而判断是否增加额外指针。 一个拥有k个指针的结点成为k层结点。50%的结点为1层节点,25%的结点为2层节点。如果保证每层结点的分布概率相同,则仍然可以拥有相同的查询效率。 有关更加细节…

2022年6月19日 0条评论 245点热度 1人点赞 sheep 阅读全文
未分类

leveldb-4 Log

Log 这一次来看看日志,参考文章在这里 leveldb不提供事务,所以我们不必记录undo log来保证事务原子性。但是需要提供redo log来保证数据是持久化的。 每次写入write batch到memtable之前,要先将操作写入到日志中。保证写操作在之后是可以redo的。 在将memory db冻结成为immutable memory db后,对应的日志文件也会被冻结。然后通过minor compaction将immutable memory db写入成SSTable后,冻结的log就可以被删除。因为他对…

2022年6月18日 0条评论 205点热度 0人点赞 sheep 阅读全文
12345…21
分类目录
  • ARTS
  • C++
  • CSAPP
  • daily
  • database
  • leetcode
  • linux
  • ml
  • paper
  • rocksdb
  • rust
  • ScummVM
  • tech
  • 其他
  • 未分类
  • 笔记
  • 算法
  • 计算机图形学
归档
  • 2023年9月
  • 2023年7月
  • 2023年6月
  • 2023年5月
  • 2023年4月
  • 2023年2月
  • 2023年1月
  • 2022年9月
  • 2022年7月
  • 2022年6月
  • 2022年5月
  • 2022年4月
  • 2022年3月
  • 2022年2月
  • 2022年1月
  • 2021年12月
  • 2021年11月
  • 2021年10月
  • 2021年9月
  • 2021年8月
  • 2021年7月
  • 2021年6月
  • 2021年5月
  • 2021年4月
  • 2021年3月
  • 2021年1月
  • 2020年12月

COPYRIGHT © 2021 heavensheep.xyz. ALL RIGHTS RESERVED.

THEME KRATOS MADE BY VTROIS