Monthly Archive for 12月, 2009

Oracle排序算法

Published
by
jacky
on 2009-12-30
in 大话技术
. 6 Comments

大牛jonathan lewis在圣诞节出了一个小题目：Holiday Quiz

I have a table with one million rows, there are no indexes on the table. The table has a column called sortcode which has no nulls, and has been generated in a highly random way so that no value appears more than four times. Consider the following queries:

select sortcode
from t1
order by sortcode;

select  sortcode
from (
select sortcode
from t1
order by sortcode
) where rownum <= 10;

How many rows are sorted in each of these two queries – and roughly how much memory would you expect Oracle to use ?

从表面上看，两个SQL仅仅是返回数量的不同，因为没有索引，所以就算只返回10行，但是也必须完成整个排序过程，所以从排序的资源消耗上，两者应该没有太大差异。

Jonathan公布了答案：Short sort，主要是Oracle引入了一个针对sort的改进，即version 1 sort，大致原理是用一个二叉树来保存最终需要返回的记录，并且记录这个二叉树中最大的值，针对每个值逐一与这个最大值比较，如果大于这个最大值就直接丢弃（因为这里要寻找最小的10条记录），如果小于最大值，则插入到这个二叉树中去，最终返回这10条记录。因为普通的排序要返回所有记录，如果也采用这个存储方式，即用二叉树来存储排序的结果，可能非常耗费内存，所以这个改进只针对返回结果集比较少的情况。另外用二叉树，可以迅速的找到插入的位置，减少比较的次数。最后Jonathan还用三个极端情况来证明了这个排序算法的效果，正序，反序和随机，正序和随机时，因为大部分值都在第一次比较就被丢弃，所以占用内存和比较次数都很少；相反，如果是反序的情况，因为几乎所有的值都需要插入到这个二叉树中，占用内存和比较次数都大幅度增加，关于这个话题大家可以看Jonathan的博客，这里不再赘述。

我这里想讨论另外一个话题，Oracle到底采用什么排序算法？我查阅了很多资料，都没有提及。学过计算机的人都知道排序算法是一个古老而又有趣的话题，我们熟知的有：冒泡排序，选择排序和插入排序，这三种排序算法比较简单，但是效率不高。高效率的排序算法有：快速排序，堆排序和归并排序，我们下来大致介绍下这三个排序算法。

快速排序是采用分治法的策略，即分而治之，首选选取一个中枢值（一般选序列中的第一个数），每次规划将序列按照这个中枢值分成两个序列，左边的序列都比中枢值小，而右边的序列都比中枢值大，一次规划完成后，中枢值找到了其最终的位置，并且将原有序列分为两个部分，然后再用同样的方法分别处理这两个序列，直到排序全部完成。快速排序是一种效率很高的排序算法，如果采用原地分割的算法，快速排序占用很少的额外空间。

堆排序有点类似于插入排序，但是他利用了堆积树（堆）这种数据结构，堆积树其实就是一棵完全二叉树，但是又满足堆属性：子节点的属性总是大于或者小于其父节点，即所谓的大根堆和小根堆。排序的过程实际上就是把数据不断插入到堆积树上，而返回排序结果的过程就是不断取堆的最大（大根堆）或者最小值（小根堆），并不断缩小堆的过程。

归并排序就是将两个或多个有序的序列合并为一个有序序列的排序过程，称为两路归并排序和多路归并排序。归并排序的算法是在每个有序队列上设置一个指针，通过不断移动指针，在每个序列上取出元素进行比较，并合并的过程。归并排序通常使用在外部排序中。

内排序和外排序，内排序指在内存中完成的排序过程，外排序指排序内容无法在内存中一次完成，而需要借助外部存储来完成排序的过程。

根据Jonathan的实验，我们可以看到上面这个排序优化的例子，实际上利用了堆排序的特性，但是由于堆积树本身需要额外的空间，在返回记录数很多的情况下，并不适合，实验也证明，如果采用堆积树来保存所有记录，需要占用更多的空间。关于Oracle的排序算法，虽然不是很明确，但是很可能是快速排序的一种，因为快速排序占用稳定的空间，通常情况下可以提供很好的效率。如果排序无法在内存中一次完成，Oracle需要借助Temp空间，这就是外排序，Oracle使用多路归并排序算法，按照排序区大小把结果集切分成多个子集，每个子集在内存中完成排序，然后将他们合并起来。排序区大小对归并排序的性能影响很大，排序区应该能至少容纳每个子集中的一条记录，否则性能会急剧下降。

Oracle的排序算法我们并不了解，以上内容很多也是基于Jonathan的实验的猜测，所以大家别较真。对于排序算法本身，我的描述并不一定正确，欢迎大家批评指正。

–EOF–

用ASM和iSCSI实现的另类HA方案

Published
by
jacky
on 2009-12-10
in 大话技术
. 6 Comments

普通PC本地磁盘，没有共享存储，如何实现HA？Dataguard挺好，但是存在数据丢失的可能性，而且很难做到应用透明切换。我们用ASM,Heartbeat和iSCSI可以实现一个廉价的HA方案，如下图：

用iSCSI将本地磁盘输出到对方的机器上，利用ASM的failgroup做mirror，保证数据mirror在两台不同的机器上，就算一台机器完全损坏，数据可以做到百分之百不丢失。用Heartbeat作HA探测，如果发现主机故障，则强行关闭DB和ASM，并在备机启动ASM和DB。如果使用Oracle 11g R2，还可以利用Preferred mirror read的特性，保证主库读自己的本地磁盘，而不是通过iSCSI读备机磁盘，这样可以达到更好的性能。

缺点：Heartbeat作为HA软件，我们并不是十分了解其探测机制，可能出现误判或者无法切换的情况。但是其实IBM hacmp这种HA软件一样有问题，比如Oracle hang住时，现在的hacmp根本无法探测，因为hacmp只是判断Oracle的进程在不在，而不管数据库是否活着。

我想不管什么HA软件，都无法处理所有的异常情况，我们只要有完善的监控和应对措施就可以了。比如我们现在所有的DB都有一个监控，就是定时模拟应用去更新数据库中的数据，如果发现超时或者报错，就认为数据库出现hang的情况，并发出报警。

–EOF–

另：之前我有一篇文章介绍用ASM和iSCSI搭建RAC的文章，在实际测试过程中，发现存在一些问题，因为在11g R2之前，voting disk和OCR都必须放在RAW devices上。因为没有共享存储，如果发生某台机器全部宕机，voting disk可能会丢失一部分，造成RAC的cluster机制发生误判。所以在11g R2之前，这个方案是有问题的，在11g R2中，Oracle几乎所有的东西都可以放在ASM中，这个方案也许可行，我还没有测试过。

在我写完这篇博文后，发现这个方案存在一些问题，通过iscsi将online redo输出到另外一个主机后，log file sync的响应时间需要40-60ms，这个响应时间肯定是无法接受的。现在两台主机的互连是四块千兆网卡直连，通过Linux的Multipath来管理多路径，为什么响应时间这么久，我们还在进一步查找问题。

我爱我家

Published
by
jacky
on 2009-12-07
in 一地鸡毛
. 18 Comments

工作十年，终于有了自己的小窝。其实租房和自己买房并没有什么区别，在中国只是租期长短的差异，但是在自己的家里还是感觉到温暖和安全。

其实家不能房价来衡量，豪华或者简朴也不重要，最重要的是在这个地球上，有一个地方是我的家，不管外面刮风下雨，那里总是温暖的，不管我多晚回家，总是有人为我开门，不管我多么疲惫，一回家就可以听到宝宝喊我爸爸。在家里，我是幸福的。

DSC_1966 DSC_1967 DSC_1965 DSC_1964 DSC_1963 DSC_1962

卧室什么的都没拍了，太乱。欢迎朋友们去家里玩，有个小朋友很爱热闹，最喜欢有人陪他疯。

–EOF–

Oracle hash分区的秘密

Published
by
jacky
on 2009-12-04
in 大话技术
. 3 Comments

在面试时经常会问一个问题，请列举出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
---------- ---------- ---------- ----------
         2          4          4         12

上面的SQL我们看到分区的数量在2，4，8，16时，hellodba这个key分别落在在2，4，4，12号分区，虽然落在不同的分区上，但是分区4和分区12是对应可合并的，这样就保证了数据是不需要移动的。一句话总结就是hash bucket总是2的N次方，如果分区数不足，则会合并数据，产生不均衡的情况，这样增加分区时，只需要对应分区的数据做split即可。同理，减少分区也不是简单的drop，而是合并分区。

再回到我们的项目中，我们为了解决这个问题，采用了更简单的处理方案，直接就做了1024个分区，我们有8个物理数据库，每个数据库中有128个表，以后再分拆时，只要移动这些表，并修改应用中的对应关系就可以了。其实和Oracle合并再拆分的思路是一样的。

这个问题其实在大牛lewis的Practical Oracle8i中讲过，当时我并没有仔细想清楚，现在想清楚了，特此记录。有些东西，明白了就觉得它挺简单的，希望对大家有帮助。

–EOF–

数据库HA方案

Published
by
jacky
on 2009-12-02
in 大话技术
. 3 Comments

我们常用的HA方案有几种：一是用小型机和HA软件作双机热备，这种方案始终有一台设备处于空闲状态，设备利用率很低，而且必须用IBM，HP等厂商的硬件，代价昂贵。二是用Oracle的RAC来做HA，在Linux环境下，Oracle提供了全套的解决方案，是个不错的选择，不过最低也需要一套共享的存储设备。三是用Oracle DG，这种方案成本最低，但是无法做到故障时应用透明切换，我们也曾经尝试过用heartbeat配合DG failover来作一些尝试，但是在测试中发现，在极端情况下，可能存在丢失数据或者无法切换的可能性。

自从使用MySQL数据库以来，我们就一直探索MySQL的HA方案，目前应用最广泛的是用heartbeat作HA，利用MySQL双向复制技术，达到透明切换的目的。但是heartbeat并不是十分的稳定，而且切换的过程也比较长。

是否有更好的解决方案？首先要解决故障探测的问题，如果应用可以自己探测数据库状态，发现数据库出现问题时，可以切换到另外一台备机；其二主备库之间的数据同步问题，如果我们可以解析Oracle或者MySQL的日志，还原成SQL信息并应用到备机，这样就实现了logical standby或者MySQL复制的功能。利用这两个功能，我们可以实现一个更廉价更灵活的HA方案。

目前我们正在做三个工具，第一是日志解析工具，包括Oracle和MySQL，日志解析是将日志文件中的变化还原为SQL或者日志信息；第二是数据同步工具，主要负责将日志信息打包传输，并应用到目标数据库上；第三是数据库探测与路由工具，主要负责探测数据库状态，对应用做透明故障切换。

这个方案中，由于数据库不再有primary和standby之分，仅仅是应用端来作判断连接哪个数据库，所以故障切换的时间非常快，我们测试大概只需要10秒。但是数据同步可能存在一定的延时，也就是说数据库切换后，数据可能存在一定程度的丢失，但是我们可以在切换后再对数据进行补全，这个我们是可以接受的。利用这些工具，我们可以搭建出很多灵活的解决方案，并不一定要依赖IBM，Oracle的解决方案，毕竟适合我们的才是最好的方案。

目前这个方案还在开发与验证中，欢迎大家和我探讨HA这方面的问题。

–EOF–