Home

豆瓣笔记是指形如https://www.douban.com/note/699086917/这样链接样式的帖子，严格来讲，我没有搞清楚豆瓣对于这款产品的定位，话题广场、日记、豆列下的文章似乎都在其中。 想做这个事情，缘起于单纯想看看这个文艺网站下的青年们在关注什么。 另外一个是很久不爬东西了手痒，厂长经常说不忘初心，我的初心有一部分大概也是 spider. 断断续续爬了130w+的文章，用的 scrapy，代码就不介绍了，放到了TinyTools这里，这里贴下一些结论。 1. 200 vs 404 个人觉得判断豆瓣是否重视这个产品可以看下死链率，从 scrapy 运行日志可以很轻松的拿到，匹配Crawled (200)或者Crawled (404)即可。 其中 404 页面...

bloom filter 的相关论文较多，按照时间线整理了下自己觉得比较有意义的。有些观点没有找到佐证的中文资料，如有错误还请指出。 1. Space/Time Trade-offs in Hash Coding with Allowable Errors Burton Bloom 在1970年发表的文章，布隆过滤器的开山之作。 给定一个 set，查找某个 key 是否存在于该 set，通常考虑两点： time: 查找时间 space: 空间成本(例如 hash 目标区域大小) Burton Bloom 在论文里提出了第三点：Allowable Fraction of Errors. ，即允许一定概率的误判，来获取空间成本的显著降低。 A Sample Appl...

leveldb 的filter block用到了 filter policy，其中默认提供的是BloomFilterPolicy，即布隆过滤器，这篇笔记聊聊布隆过滤器的理论和在 leveldb 里的实现。 1. 简介 bloom filter是一种数据结构，作用类似于 hash table，相对于后者，空间利用率更高。 不过这种高利用率是有代价的，当我们在 bloom filter 查找 key 时，有返回两种情况： key 不存在，那么 key 一定不存在。 key 存在，那么 key 可能存在。 也就是说 bloom filter 具有一定的误判率。 2. 理论知识 先介绍下 bloom filter 的几个组成： n 个 key m bits...

leveldb笔记之8:sstable

1. 简介 leveldb 里 sstable 文件里，有多个 block 组成。其中 filter block 用于提高 sstable 的读取效率，源码位于 filter_block.cc. 本文主要分析 filter block 的数据格式以及FilterBlockBuilder/FilterBlockReader类的实现。 2. 如何提高查找性能 在 leveldb 中，查找 data block使用二分法，能够达到 lg(n) 的复杂度，如果想进一步提高，就需要用到 filter block 了。 如果说 data block 的作用是查找 key 对应的 value，那么 filter block 则是查找 key 是否存在于该 data block，起到提前过滤...