锁优化与布隆过滤器
Categories: System / Data Structure
但如果多线程抢锁过于频繁，就会造成严重的性能下降。为了降低对锁的竞争，自然的想法就是，对主要的全局数据结构粒度拆分（比如 Java 的 ConcurrentHashMap 就是将哈希桶分成了多个段进行上锁）。减小锁的粒度
分配器中最重要的数据结构就是空闲列表，我们可以将空闲列表拆分成多个，每个空闲列表使用单独的锁。这样可以缓解多线程的竞争问题，但却解决不了多核架构的另外一个问题——缓存震荡（cache sloshing）。
bloom filter
背景
在平常生活中，包括在设计计算机软件时，我们经常要判断一个元素是否在一个集合中。比如在 FBI，一个嫌疑人的名字是否已经在嫌疑名单上；在网络爬虫里，一个网址是否被访问过等等。
最直接的方法就是将集合中全部的元素存在计算机中，遇到一个新元素时，将它和集合中的元素直接比较即可。一般来讲，计算机中的集合是用哈希表（hash table）来存储的。它的好处是快速准确，缺点是浪费存储空间。那有没有 更优化的数据结构呢？
简介
布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是由一个很长的bit数组和一系列哈希函数组成的。布隆过滤器可以用于检索一个元素是否在一个集合中。
原理
数组的每个元素都只占1bit空间，并且每个元素只能为0或1。
布隆过滤器还拥有k个哈希函数，当一个元素加入布隆过滤器时，会使用k个哈希函数对其进行k次计算,得到k个哈希值，并且根据得到的哈希值，在位数组中把对应下标的值置位1。
判断某个数是否在布隆过滤器中，就对该元素进行k次哈希计算，得到的值在位数组中判断每个元素是否都为1，如果每个元素都为1，就说明这个值在布隆过滤器中**。**
False positives 概率
误差率
布隆过滤器的误差率是指由于hash冲突，导致原本不再布隆过滤器中的数据，查询时显示在里面。
发现1，3，7号位均为1，此时需要去后台数查询
布隆过滤器使用场景
- 黑名单校验
- 快速去重
- 爬虫URL校验
- leveldb/rocksdb快速判断数据是否已经block中，避免频繁访问磁盘
- 解决缓存穿透问题
重点讲解一下缓存穿透
缓存穿透
- 概念
缓存穿透是指查询一个数据库中不一定存在的数据；正常流程是依据key去查询value，数据查询先进行缓存查询，如果key不存在或者key已经过期，再对数据库进行查询，并把查询到的对象，放进缓存。如果数据库查询对象为空，则不放进缓存。
如果每次都查询一个不存在value的key，由于缓存中没有数据，所以每次都会去查询数据库，对db造成很大的压力。
- 解决方案
- 缓存空值
将数据库中的空值也缓存到缓存层中，这样查询该空值就不会再访问DB，而是直接在缓存层访问就行。
- 缺点：空值过期时间不太好确定
- 使用布隆过滤器
- 构建方法
- 使用redis的module加载外部so文件
- 优点：操作简单
- 缺点：
- 需要高版本的redis
- 容易形成大key
- 借助bitmap来实现，k个hash函数，创建n个bitmap(推荐)
- 优点：操作简单
- 缺点：
- 由于redis的字符串要求最大为512M，所以需要拆分多个key
- 扩容稍微复杂
- 可以自己本地来实现布隆过滤器的计算，计算完之后在存入redis
- 优点：自己操作更灵活
- 缺点：
- 流程复杂
- 需要额外服务重启或当机之后布隆过滤器丢失问题
- 使用redis的module加载外部so文件
优点
- 节省内存空间
- 插入和查询时间复杂度都为O(1)
缺点
- 布隆过滤器不支持删除
- 由于哈希冲突的原因，可能会出现假阳性