接口 一个ABC，后面会继承这个类做各种实现 clean up function 代码比较好懂，唯一让我感到疑惑的是 clean up function 这部分 1 2 // FIXME: 不太理解为什么需要很多个clean up function 3 // Cleanup functions are stored in a single-linked list. 4 // The list's head node is inlined in the iterator. 5 struct CleanupNode { 6 // True if the node is not used. Only head nodes …

arena时levelDB中的内存池实现 接口 没有太多好说的，都非常直观。 补了些注释 1 2class Arena { 3 public: 4 Arena(); 5 6 Arena(const Arena&) = delete; 7 Arena& operator=(const Arena&) = delete; 8 9 ~Arena(); 10 11 // Return a pointer to a newly allocated memory block of "bytes" bytes. 12 char* Allocate(size_t bytes); 13 14 // …

FilterPolicy接口 1 2class LEVELDB_EXPORT FilterPolicy { 3 public: 4 virtual ~FilterPolicy(); 5 6 // Return the name of this policy. Note that if the filter encoding 7 // changes in an incompatible way, the name returned by this method 8 // must be changed. Otherwise, old incompatible filters may be 9 // passed to methods …

Cache接口 没有太多好说的，可以注意这里用了void*来表示任意类型数据。 在c++17之后可以考虑用std::any代替，参考 std::any 笔记 1 2 3namespace leveldb { 4 5class LEVELDB_EXPORT Cache; 6 7// Create a new cache with a fixed size capacity. This implementation 8// of Cache uses a least-recently-used eviction policy. 9LEVELDB_EXPORT Cache* NewLRUCache(size_t capacity); 10 …

levelDB是一个有序的KV存储，因此key的顺序是十分关键的 levelDB提供用户自己定义key顺序的能力 先看下comparator的接口 接口 include/leveldb/comparator.h 1 2// A Comparator object provides a total order across slices that are 3// used as keys in an sstable or a database. A Comparator implementation 4// must be thread-safe since leveldb may invoke its methods …

背景 最近在做一个智能算力相关的项目，类似美团外卖广告智能算力的探索与实践 其中实现控制系统需要与数据库交互。 虽然最后技术选型并没有使用到levelDB,但是想趁机把代码读了吧。 很惊讶的发现我大三的时候声称自己读过部分levelDB代码，甚至还写了几篇相关的博客，比如 murmurhash源码分析 Lock-free vs wait-free concurrency 内存屏障（Memory Barriers） levelDB 学习笔记 但是我却一点都没印象了.... 仔细看来很多概念在当时可能都是没有充分理解的，而且从数目上来看，应该并没有完整看完levelDB代码。 所以重新开个坑，看看自己比起毕业前有没有长进【没有 先从 …

分析levelDB源码的时候遇到的...发现是一个广泛应用的hash算法，而且是纯c写的，于是找来了源码看。 **MurmurHash** 是一种非[加密](https://zh.wikipedia.org/wiki/)型[哈希函数](https://zh.wikipedia.org/wiki/)，适用于一般的哈希检索操 …

起因是最近在看levelDB源码，其中port里的atomic_pointer.h文件用到了内存屏障。。 于是来学习一下。。 粗略得说下我自己的理解。 代码的顺序并不和执行的顺序完全对应，出于对效率的追求，cpu和编译器会对一些顺序指令重排，以期得到最大的执行效率。 比如下面这段代码： // example 2 // void *ptr, v, _store; v = ptr; _store = v; somefunc(); v = _store; v的值是没有改变的，那么编译器可能会认为_store = v; v = _store; 是多余的，就直接把这一段给“优化”掉了。这段代码在单线程中确实是多余的，但是在多线程环境下，可能 …

先放原始论文。。。以此表达对这个算法的敬意orz 论文链接 问题引出： 那天百度一面，frog学姐问了我如何判断两篇新闻稿的相似度的问题....我满篇口胡...也只是回答了一些诸如从图片上考虑。。或者去掉stop word之后得到特征向量然后计算余弦值之类得到传统想法。。。 今天看到了google在用的网页去重的算法（？。。。感觉好神奇。。。准备面试到现在，第一个让我感到惊异而不是套路的算法orz 对于处理**大规模文本（500字以上吧）**的时候效果很好。。。但是算法思想却又非常简单。 这才是算法的美丽之处吧。。。。leetcode上的那些纱布技巧也好意思叫算法。。。？ 网页去重，其实本质还是网页相似度的计算....首先是两篇，之 …