存档

文章标签 ‘hash’

在面试时经常会问一个问题,请列举出hash在数据库内部的应用,hash的原理虽然简单,但是它在数据库中可以说是无处不在。其中hash partition是hash在数据库中一个简单的应用,虽然它没有range partition那么常用,但是我们在做数据库水平拆分时,其实就是利用了hash partition的原理,利用hash函数对某个key进行运算,然后将其分布到不同的主机上,原理很简单。
我们在设计时遇到了一个问题,当分区的数量需要变化时,基于hash的原理,数据可能会从一个分区移动到另外一个分区,因为某个key在4个分区时,可能被分布在分区3,而在8个分区时,可能被分布在分区5。这样每当分区数量变化时,就需要全部重新分布数据,代价很高。
那么Oracle是怎么做的?首先可以肯定的是Oracle的hash partition在分区增加时,不需要做全部数据的重新分布。有人告诉我Oracle的hash函数比较牛,可以保证分区数量增加时,这个hash函数可以让原来的数据还在旧的分区中,而新的数据可以分布在新的分区。Oracle的函数无非就是get_hash_value或ora_hash(10g),从hash的原理上来说,这也是不可能做到的。
我们对hash partition都有一个常识,就是partition的数量最好是2的次方,也就是2,4,8,16……,否则分区会出现不分区均衡的现象,按照hash的原理,不管是几个分区,都可以做到完全均衡的,为什么会不均衡,其实答案已经出来了,Oracle为了能够增加分区,为你预留了几个看不到的分区。
假设我们有6个分区,一共8000条数据,数据的分布如下图:

hash partition不能直接增加分区,而是split当前分区,当需要增加到8个分区时,实际上是分区3和分区4分别split产生新的分区7和分区8,如下图:

Oracle如何做到分区数量增加后,其他分区的数据不受影响呢,其实很简单,Oracle在做hash运算时,预留了分区,比如6个分区,实际上是用8个分区的hash来运算的,只不过把缺少的分区的数据合并到其他分区,这样就会出现数据不均衡的情况。Oracle的公式是这样的,用等于或者大于当前分区数量的最小的一个2的N次方,比如6个分区做8个hash bucket。我们再来考虑一下2,4,8,16(2的N次方)的情况,比如要把4个分区加为5个分区,因为已经是2的N次方,所以数据会均匀分布,而且Oracle还是使用4个hash bucket。这时新增的分区5实际上把分区1 split后产生的,这时因为有5个分区了,所以会使用8个hash bucket。这时Oracle的hash函数就比较牛了,它可以保证2,4,8,16个分区时,同一个键值分布在相同的分区或者是对应可以合并的分区,看下面的SQL:
select ora_hash(‘hellodba’,1)+1 par2,ora_hash(‘hellodba’,3)+1 par4,ora_hash(‘hellodba’,7)+1 par8,ora_hash(‘hellodba’,15)+1 par16 from dual;
PAR2 PAR4 PAR8 PAR16
———- ———- ———- ———-
[...]

12 4th, 2009 | Filed under 大话技术
标签: ,

设想以下的一个问题:有一个keyword的集合,我们需要快速判定某个keyword是否包含在其中。最简单的方法是遍历,但是效率很差。我们马上想到了hash的方法,因为在Oracle内部,hash无处不在。比如在cache buffer中找到某个block,在shared pool中找到某个SQL等等。我们可以把keyword的集合build成一个hash table,然后根据keyword计算hash值,通过是否落在相应的hash bucket中,这样就可以实现快速查找的目的。这个方法不错,但是当keyword过多时,hash table会占用大量内存,效率也会随之下降。
今天公司的架构师介绍了一个新的方法给我:Bloom Filter。它是一种基于随机数(或Hash)的数据结构,它支持对成员使用较少空间来存储,却能得到较高效率的查询。换句话说:在Bloom Filter 可以用于检索一个元素是否在一个集合中。其原理如下:
建立一个容量为500万的Bit Array结构(Bit Array的大小和keyword的数量决定了误判的几率),将集合中的每个keyword通过32个hash函数分别计算出32个数字,然后对这32个数字分别用500万取模,然后将Bit Array中对应的位置为1,我们将其称为特征值。简单的说就是将每个keyword对应到Bit Array中的32个位置上,见下图:

当需要快速查找某个keyword时,只要将其通过同样的32个hash函数运算,然后映射到Bit Array中的对应位,如果Bit Array中的对应位全部是1,那么说明该keyword匹配成功。
Bloom filter 是一个集合的有损编码,所以它不是一种“保险”的方案,存在一定的误判率。
有人问:这个对DBA有什么用?虽然我们不直接开发应用,但是开阔视野和思路对我们同样重要。难道我们碰到这种问题就只能用like或者in去解决吗?
–EOF–
后记:要深入了解Oracle,hash的原理和实现是必须要掌握的。有一次面试一个技术专家,高精尖的技术谈得头头是道,但是连hash的基本原理都说不清楚。对于一个技术专家来说,不能只懂“高精尖”,没有基础的知识,任何“高精尖”都只是空中楼阁,对于DBA,尤其如此。

4 8th, 2009 | Filed under 大话技术
标签: