存档

‘数据库’ 分类的存档

Hash和Bloom Filter

2011年9月13日 sigma 11 条评论 35,951 views

这几天的“科研”中涉及到了一个概念,Bloom Filter(有的中文翻译为布隆过滤器,不知道正确否),今天看了下相关的资料,发现这东西和Hash还挺有关系的,在这里一并讲下。

Hash(函数/表)

Hash (中译为哈希,或者散列)函数在计算机领域,尤其是数据快速查找领域,加密领域用的极广。其作用是将一个大的数据集映射到一个小的数据集上面(这些小的数据集叫做哈希值,或者散列值)。Hash table(散列表,也叫哈希表),是根据哈希值(Key value)而直接进行访问的数据结构。也就是说,它通过把哈希值映射到表中一个位置来访问记录,以加快查找的速度。下面是一个典型的hash函数/表示意图:

哈希函数有以下两个特点:

  • 如果两个散列值是不相同的(根据同一函数),那么这两个散列值的原始输入也是不相同的。
  • 散列函数的输入和输出不是唯一对应关系的,如果两个散列值相同,两个输入值很可能是相同的。但也可能不同,这种情况称为“散列碰撞”(或者“散列冲突”)。上图中,John Smith和Sandra Dee就存在hash冲突。

Hash一个应用就是对数据集分类,比如上图,Hash值为0的表示可能在A集合中,Hash值为2的表示B集合中,依次类推,值为15的表示F集合中。但Hash冲突会在这里会导致严重的问题,对于一个未知的新值,其可能不属于上面任何一个集合,但由于冲突,其Hash值和上面的某一个相同,导致误报(因为事先我们不可能做一个含有无限多项输入的完整的Hash表,也就是原来的Hash函数不可能是完美的)。并且,hash冲突也会导致查找效率低下。

Bloom Filter

Bloom Filter是1970年由Bloom提出的。它实际上是一个很长的二进制向量和一系列随机映射函数(Hash函数)。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难。Bloom Filter广泛的应用于各种需要查询的场合中,如Orocle的数据库,Google的BitTable也用了此技术。

如果想判断一个元素是不是在一个集合里,一般想到的是将所有元素保存起来,然后通过比较确定。链表,树等等数据结构都是这种思路. 但是随着集合中元素的增加,我们需要的存储空间越来越大,检索速度也越来越慢(O(n),O(logn))。

这时候就可以利用哈希表这个数据结构(它可以通过一个Hash函数将一个元素映射成一个位阵列(Bit array)中的一个点)。这样一来,我们只要看看这个点是不是1就知道可以集合中有没有它了。这就是Bloom Filter的基本思想。

但这时,哈希冲突会是一个问题:假设Hash函数是良好的,如果我们的位阵列长度为m个点,那么如果我们想将冲突率降低到例如 1%, 这个散列表就只能容纳m/100个元素。显然这就不叫空间效率了(Space-efficient)了。解决方法也简单,就是使用多个Hash,如果它们有一个说元素不在集合中,那肯定就不在。如果它们都说在,虽然也有一定可能性它们都在说谎,不过直觉上判断这种事情的概率是比较低的。这种多个Hash组成的数据结构就叫Bloom Filter。

一个Bloom Filter是基于一个m位的位向量(b1,…bm),这些位向量的初始值为0。另外,还有一系列的hash函数(h1,…hk),这些hash函数的值域属于1~m。下图是一个bloom filter插入x,y,z并判断某个值w是否在该数据集的示意图:

 

上图中,m=18,k=3;插入x是,三个hash函数分别得到蓝线对应的三个值,并将对应的位向量改为1,插入y,z时,类似的,分别将红线,紫线对应的位向量改为1。查找时,当查找x时,三个hash值对应的位向量都为1,因此判断x在此数据集中。y,z也是如此。但是查找w时,w有个hash值对应的位向量为0,因此可以判断不在此集合中。但是,假如w的最后那个hash值比上图中的大1,这是就会认为w在此集合中,而事实上,w可能不在此集合中,因此可能出现误报。显然的,插入数据越多,1的位数越多,误报的概率越大。

Wiki的Bloom Filter词条有关于误报的概率的详细分析:Probability of false positives。从分析可以看出,当k比较大时,误报概率还是比较小的,因此这存储还是很空间有效滴。

Bloom Filter有以下几个特点:

  1. 不存在漏报(False Negative),即某个元素在某个集合中,肯定能报出来。
  2. 可能存在误报(False Positive),即某个元素不在某个集合中,可能也被爆出来。
  3. 确定某个元素是否在某个集合中的代价和总的元素数目无关。

优点:

相比于其它的数据结构,Bloom Filter在空间和时间方面都有巨大的优势。Bloom Filter存储空间和插入/查询时间都是常数。另外, Hash函数相互之间没有关系,方便由硬件并行实现。Bloom Filter不需要存储元素本身,在某些对保密要求非常严格的场合有优势。

缺点:

另外,一般情况下不能从Bloom Filter中删除元素. 我们很容易想到把位列阵变成整数数组,每插入一个元素相应的计数器加1, 这样删除元素时将计数器减掉就可以了。然而要保证安全的删除元素并非如此简单。首先我们必须保证删除的元素的确在Bloom Filter里面. 这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。

参考资料:

  1. http://en.wikipedia.org/wiki/Hash_function
  2. http://en.wikipedia.org/wiki/Bloom_filter
  3. http://antognini.ch/papers/BloomFilters20080620.pdf

Redis实现之虚拟存储系统(VM)实现(四)–线程式虚存(Threaded VM)交换

2011年8月6日 sigma 7 条评论 6,313 views

非阻塞虚存的几种实现选择

由于阻塞式虚存实现有各种缺点,因此,Redis实现了非阻塞式的虚存系统。实现非阻塞式虚存系统有以下几种方法:

  1. 最显然的方法,就是把整个redis做成多线程的,每个数据库操作都是自动分配到某个线程(或者fork一个新的线程),这样就不存在阻塞的问题。但是这对redis不是一个好的解决方案,因为为了实现提高操作速度,redis没有锁,保证原子性是通过顺序执行来保证的,因此整个redis引入多线程要增加锁,导致速度变慢(也许多核上能快点),并且极大增加代码量(现在redis只有1万行代码)。
  2. 通过非阻塞式IO实现,由于redis是基于事件循环的(event-loop based),可以采用非阻塞IO。但redis的作者基于以下两点把这个否了:①非阻塞文件操作不像sockets,会导致很多不兼容的问题,这和操作系统紧密相关,要做很多和操作系统相关的工作。②另外一个原因就是,在虚存中,文件IO操作仅仅是一部分,还有很多事件花在数据的编解码上面(编解码成交换文件swap file)。
  3. 于是就剩下最后一种方法,通过增加IO线程来完成数据交换。

下面,具体介绍第三种实现,即IO线程:

IO线程

IO线程的设计目标依重要性排列如下:

  • 实现简单:尽量减少数据冲突(race)的可能性;用简单的锁;VM的代码要能够和Redis的其他代码分离(个人感觉这符合设计正交性原则)。
  • 高性能,对于客户端访问数据不会造成锁(等待)。
  • IO线程要能够编解码交换文件(针对第二种实现的缺点2)。

鉴于以上目标,Redis 的非阻塞VM实现的方式为,实现了一个redis主线程(实际和客户端交互的线程,处理请求),以及一些通过一个简单的信号量(mutex)和任务队列进行通信的IO进程。简单的说,主线程将IO请求交给IO线程进行后台处理(通过将一个(IO)任务结构交给server.io_newjobs队列)。假如没有IO进程,则新建一个。有些IO进程完成IO任务后,结果将发送到server.io_processed队列。IO进程将通过UNIX管道给主进程一个信号,以便告知已经完成,可以继续新的任务。

阅读全文…

Redis实现之虚拟存储系统(VM)实现(三)–阻塞式虚存(Blocking VM)交换

2011年7月24日 sigma 2 条评论 5,104 views

个人理解,所谓阻塞式虚存(Blocking VM),是指redis发生数据交换时,进程被阻塞,不能干其他的事情(后面一篇文章将讲到Threaded VM相反,有独立VM线程)。

在Redis中,启用阻塞式虚存需要在配置文件中将server.vm_max_threads设成0(即不为Threaded VM),和VM另一个相关配置变量是sever.vm_max_memory,它表示Redis中数数据所占用的最大内存(实际上运行过程中可能大于这个值),只有数据量占用内存大于这个值时,才会出现数据交换到disk。

交换到硬盘

数据交换是通过一个计划任务函数(cron function)实现的。这个函数每隔一定的时间会检查是否超出了内存最大值(out of memory)。假如发现超出了最大值,则通过循环调用vmSwapOneObject(这个函数只有一个参数,0表示阻塞式,1表示线程式)来将数据交换到硬盘。

vmSwapOneObject实现如下:

  1. 和Cache替换一样,很关键的一点就是需要找到需要交换出去的Object,使得交换代价最小(后面会讲redis是如何决定的)。
  2. 被交换出去的object关联的值(value)通过阻塞式被交换到硬盘。
  3. key的storage域被设置成REDIS_VM_SWAPPED,vm域也将改写,包括页表索引值,以及所占用的页数。
  4. 释放被swap的object的内存,在哈希表(hash table)中将对应的value的入口设置成NULL。

这个函数一直被调用,直到如下情况:swap空间已满,或者数据对象占用的内存小于sever.vm_max_memory。

阅读全文…

Redis实现之虚拟存储系统(VM)实现(二)–数据交换(Swap)的实现

2011年7月17日 sigma 4 条评论 54,198 views

Redis的虚拟存储系统(VM subsystem)的目的是实现将Redis对象(Redis Objects)方便的在主存(Memory)和硬盘(Disk)之间交换。在Redis虚拟存储系统中,Redis仅仅会将和值(Values)关联的对象交换(swap)到硬盘上。在前一篇日志中,对VM涉及的数据结构进行简要介绍,在这篇日志中,将介绍数据交换的具体过程。

在具体讲Redis数据交换的具体实现之前,有必要讲下swap文件,swap文件是由若干页(page)组成的,每页包含着给定字节数的数据。由于不同的redis实例的最优配置不一样(取决于你实际存储数据的大小),这些参数可以通过redis.conf文件进行修改。下面是默认的大小:

 vm-page-size 32
vm-pages 134217728
 

Redis使用位向量(英文为bitmap,这是一些连续的位,每位的值为0或1)来表示在硬盘中page是否被使用。假如一个给定位是1,则表示该页被使用(有swap文件存在上面),为0,表示该页未被使用。

通过在内存中使用位向量(下面将称为页表位向量),可以在很少的内存消耗情况下取得巨大的性能提升,因为我们仅仅只需要为每页提供一位。对于上面的默认配置,总共有4G的虚存,但是只需要16M的内存给页表位向量。

为了将主存上的数据交换到交换空间,我们需要做如下步骤(假设没有使用虚存线程,仅仅是块实现)。

  1. 找出需要多少页来存储交换文件。这仅仅需要通过调用rdbSavedObjectPages函数即可返回需要的页数。
  2. 知道需要的页数后,我们需要找到交换空间中一些连续的页来存储。这是通过vmFindContiguousPages函数实现的。这个函数有可能因为内存满了而失败,也有可能因为找不到连续的页失败。当这种情况发生时,交换将被取消,数据将继续保存在内存中。
  3. 最终,我们只需要调用vmWriteObjectOnSwap函数即可以将数据交换到对应的位置。数据交换完成后,对应的主存被释放,对应的key也被标记为REDIS_VM_SWAPPED,而对应的页表位向量也被标记为使用中。
    而将交换空间的数据切回到主存中,则很简单,由于知道对象存的位置以及占用页数。只需要调用vmLoadObject即可以完成。

注:本文内容翻译自redis源码包doc目录中的相关文档。

Redis实现之虚拟存储系统(VM)实现(一)–Swap file数据结构

2011年7月3日 sigma 8 条评论 11,373 views

Redis的虚拟存储系统(VM subsystem)的目的是实现将Redis对象(Redis Objects)方便的在主存(Memory)和硬盘(Disk)之间交换。在Redis虚拟存储系统中,Redis仅仅会将和值(Values)关联的对象交换(swap)到硬盘上。

在Redis的顶层的Hash 表中,将一部分的Redis对象(键Key)映射到另一部分Redis对象(值Value)。从而实现可以只将value交换到硬盘,而key对象不交换到硬盘,这保证了Redis非常好的查找性能(一般查找都是通过Key实现)。Redis虚存系统设计目标就是保证有虚存的Redis系统和没有虚存的Redis系统性能相差不大。

当一个对象(包括Key 和 Value)被交换到硬盘,在Hash表中:

  • Key还在内存中,保存着一个代表着Kye的Redis对象。
  • Value被设成了NULL。

到这里,你也许会问,在哪里存储被交换出去的Value信息(这Value和某个Key关联着)。事实上,在Redis中,就在Key对象中。

下面是Redis对象robj的数据结构:

  /* The actual Redis Object */
typedef struct redisObject {
    void *ptr;
    unsigned char type;
    unsigned char encoding;
    unsigned char storage;  /* If this object is a key, where is the value?
                             * REDIS_VM_MEMORY, REDIS_VM_SWAPPED, ... */
    unsigned char vtype; /* If this object is a key, and value is swapped out,
                          * this is the type of the swapped out object. */
    int refcount;
    /* VM fields, this are only allocated if VM is active, otherwise the
     * object allocation function will just allocate
     * sizeof(redisObjct) minus sizeof(redisObjectVM), so using
     * Redis without VM active will not have any overhead. */
    struct redisObjectVM vm;
} robj;
 

正如你所看到的,这个数据结构中有一些域是和虚拟存储相关的。最重要的域是storage,其取值可能有如下几个:

  • REDIS_VM_MEMORY: 对应的Value就在内存中
  • REDIS_VM_SWAPPED: 对应的Value已被交换, 并且hash表中入口刚被设成了NULL.
  • REDIS_VM_LOADING: 对应的Value已被交换, hash表中入口是NULL, 并且对象正从硬盘Load到主存中(这个值仅仅在线程VM/ThreadedVM激活时有效,具体什么事threaded VM,详见我的下一篇博文).
  • REDIS_VM_SWAPPING: 对应的Value在主存中, hash表中入口是一个指向redis对象的指针, 但是系统存在一个把这些Value交换到硬盘的IO任务.

阅读全文…

无觅相关文章插件,快速提升流量