LevelDB源码解析(5) WriteBatch
简介 LevelDB的官方注释是这么介绍WriteBatch的： WriteBatch holds a collection of updates to apply atomically to a DB 如何保证原子性可能需要看完对WriteBatch的使用才能理清楚，这里只能确定一个WriteBatch对象可以包含多条更新记录（插入/删除），支持批量写入。 WriteBa……
LevelDB源码解析(4) MemTable
简介 MemTable是LevelDB在内存中的缓存库。用户写入数据时，LevelDB会先把数据写入到MemTable中。如果MemTable写满了，就会新建一个MemTable进行写入。后台再异步把旧的MemTable压缩写到磁盘上。因为旧的MemTabl……
LevelDB源码解析(3) 变长编码
背景 LevelDB在内存中存储key、value时，最后是以单值形式存储到一个跳跃表中的，跳跃表我们在上一篇文章LevelDB源码解析之SkipList(跳跃表）聊过了。这里主要想谈一下，LevelDB是如何把key、value编码到一个单值里面的，顺带分……
LevelDB源码解析(2) SkipList(跳跃表)
背景 SkipList是LevelDB的MemTable使用的底层存储结构，LevelDB实现了一个支持泛型的跳跃表。本文不会具体介绍跳跃表的数据结构，如果读者不了解跳跃表的原理、实现，可以先看一下跳跃表（Skiplist）从原理到实现 SkipList的对外……
跳跃表（SkipList）从原理到实现
数组与链表 数组和链表是非常基础的两种数据结构，链表每次查找都需要从头结点开始线性遍历，时间复杂度是O(n)。而数组通过维护元素顺序可以使用二分查找，查找的时间复杂度是O(lg(n))。查找效率方面数组完胜链表。 但是由于数组插入或删除元素时必须要移动所有受影……
LevelDB源码解析(1) Arena内存分配器
背景 LevelDB中需要频繁申请和释放内存，如果直接使用系统的new/delete或者malloc/free接口申请和释放内存，会产生大量内存碎片，进而拖累系统的性能表现。所以LevelDB实现了一个Area内存分配器来对内存进行管理，以保证性能。 Aren……
C/C++中的断言(assert与static_assert)
assert简介 assert被C/C++用来判断某些条件是否成立，比如判断指针类型的大小sizeof(void*)是否大于8,或者判断malloc返回的指针是否为null。 assert的函数申明如下： void assert( int expression ); 如果expression为0，即false，a……
内存乱序与C++内存模型详解
内存乱序 内存乱序指的是内存操作出现乱序，CPU缓存、编译器优化、处理器指令优化等都会改变内存顺序，造成内存乱序。 学习内存顺序容易陷入了一个误区，因为内存顺序是和CPU架构、编译器息息相关的，想要去深入理解CPU缓存怎么导致内存乱序的，编译器优化和处理器指令……
聊一聊原子操作
先举个栗子 下面的C++代码编译执行后，v的输出是多少呢？每个线程都执行了10000次v++，总共2个线程，那么v的最终结果应该是20000，结果是这样吗？ #include <iostream> // std::cout #include <thread> // std::thread int v = 0; void plus() { for(int i=0; i<10000; i++) { ++v; } } int main() { std::thread t1(plus); std::thread t2(plus); t1.join(); t2.join(); std::cout << "v: " << v << std::endl; } //编译执行指令：g……
简易编译器实现（二）使用Bison创建语法分析器
简易编译器实现（一）使用Flex创建词法分析器一文介绍了编译器的概念和七个阶段，并说明了如何使用Flex创建词法分析器。本篇文章介绍如何使用Bison创建语法分析器，并实现基本的运算能力。本文继续使用简易编译器实现（一）使用Flex创建词法分析器中提出的集……