布隆过滤器

布隆过滤器是一种数据结构，概率性数据结构，高效的插入与查询，回答的一定不存在或者可能存在。相比List, Set, Map更高效，占用空间少，但返回结果是概率的。
用HashMap判断某个元素是否存在当然是高效的O(1)，但是哈希表占用空间大，而且不能充分利用空间，所以在数据集大时可能无法一次性读入内存构建HashMap。

布隆过滤器是一个Bit向量，如有8位，三个哈希函数，如百度哈希生成1,4,7，阿里哈希成2,4,8，把相应的位置1，这时查询头条(哈希值347)-3是0,头条显然一定不在，但某个公司哈希值为148虽然都是1，但这是可能存在。

布隆过滤器需要考虑哈希函数的个数k，和bit向量的长度m，有公式

用在减少磁盘I/O或磁盘请求，一个值一定不存在就可不在进行后续的查询请求。

Larger-than-Memory Databases

对于大于内存的内存数据库而言，允许读写磁盘上的数据，但是和面向磁盘的数据还是有所不同的。
内存存储=面向元组
磁盘存储=面向块

OLAP经常需要访问整个表，仍要用面向磁盘的缓冲池进行处理

OLAP.png

For OLTP

OLTP通常会有热数据和冷数据，这时候就需要一种机制把冷数据移到磁盘中并在需要的时候能对它进行检索。
需要解决的问题：
运行时的操作怎么区分冷数据，用什么方式来分辨数据是不是冷的；驱逐策略，何时驱逐，被驱逐的元组通过什么方式访问(驱逐元数据)；数据的检索策略，检索的粒度，机制和由冷变热的合并

冷元组的识别 On-line——DBMS会检测事务访问的部分和追踪元组被访问的频率；追踪信息的元数据直接嵌在元组内；Off-line——在事务执行时会维护一个元组访问日志，用后台进程来计算访问频率。

驱逐时间 阈值——DBMS检测内存的使用情况，当内存使用到某个阈值时开始驱逐元组，但DBSM需要手动的移动数据；OS虚拟内存——OS决定什么时候把数据移入磁盘，后台进行。

被驱逐元组的元数据（在内存还是磁盘，磁盘中的如何访问） Tombstones——留一个标志指向磁盘中元组的地址，并更新索引中这个元组的指针指向这个Tombstone元组；布隆过滤器——每个索引用相似的数据结构，每个查询都是索引+过滤器进行查找(先用布隆过滤器看在不在，不在直接去磁盘中查找)；OS虚拟内存——OS会track哪些数据在磁盘，DBMS不需要额外的元数据。

Tombstones.png

布隆过滤器.png

数据检索粒度 一块中的所有元组——无论是否需要都把这一块中所有元组都合并入In-Memory Table Heap中，会需要很多CPU开销来更新索引，元组也更容易被驱逐；只合并需要的元组——只把查询访问的元组合并到In-memory table heap中，但是需要额外的bookkeeping to track holes

合并阈值 总是合并——检索的元组统统合并；只合并更新——除更新外的其他的放在临时缓存中；选择性更新——追踪每个块被访问的频率，如果一个块访问超过阈值就把这个块合并入in-memory table heap中。

检索机制 abort-and-restart——如果一个事务要访问被驱逐的元组就把这个事务abort，然后一个单独的后台线程从磁盘中检索这个元组合并到内存中；数据准备好后restart这个事务，在大量查询时无法保证一致性；异步检索——stall访问被驱逐的元组的事务直到把这个元组从磁盘中取出并合并入内存