一种基于Rsync算法的数据库备份方案设计

Rsync介绍

Rsync(remote synchronize)是一款开源的Linux/Unix远程数据同步工具，可以通过网络快速同步多台服务器主机之间的文件与目录。其核心为“Rsync算法”，它由澳大利亚计算机工程师Andrew Tridgell发明。算法思路利用差分计算两个文件不同编码值，并将该编码值传给同步源文件，来获取两个文件在不进行文件内容直接网络传输的情况下知道两个文件的不同和相同之处，从而仅仅对文件的不同内容进行同步传输，以减少网络数据传输量，进而提高传输效率达到同步文件的效果。算法核心包括了Checksum算法、传输算法、Checksum searching算法、对比算法。

Checksum算法首先会把同步目标文件平均切分成若干个小块，比如每块512个字节（最后一块会小于这个数），然后对每块计算两个校验和（Checksum）：

• 一个叫滚动校验和（rolling checksum），为32位弱校验和，使用adler-32算法；
• 另一个为强校验和（md5 checksum），采用128位的md5 Hash算法；

通过弱滚动校验和来快速计算出两文件块的不同，但该算法碰撞概率较高。因此，通过引入强checksum校验和来计算两文件块的相同。

文件块的校验和计算完毕后，会将一个checksum列表传输给同步源文件，包括rolling checksum(32bits)、md5 checksum(128bits)、文件块编号。源文件会进行同样的校验和算法计算，并与列表进行对比发现文件的不同和相同之处。

同步源文件通过采用checksum searching算法来查找，将目标文件的checksum列表数据存放在一个16bits的hash table中，采用rolling checksum做hash值，以便获得时间复杂度的查找性能。Hash table的大小为216，对rolling checksum的hash会被散列到0到216-1中的某个整数值。对hash值发生碰撞的则做成一个链表进行存放。

最复杂关键的为文件块的对比算法。同步源文件将自身的文件块进行checksum计算后，从hash table中进行查找。如果查到了则说明发现了相同的文件块信息，再计算比较md5的checksum，如果md5 checksum再相同则说明目标文件中存在相同的文件块，并记录文件块编号。如果没有查找到则说明文件块信息不同，也不用再计算md5 checksum值。总之，只要rolling checksum或md5 checksum其中有不匹配的项，那么对比算法就会对文件块进行rolling动作，算法会往后跳1个字节，取2-513字节的文件块计算checksum，重复进行相关的查找对比，直到完成整个源同步文件的对比。通过对比算法可以找出相邻两次匹配中的那些文本字符不同，则需要同步传输给目标文件。对比算法流程如图1所示：

图1.对比算法流程说明

同步源文件通过Rsync算法后会得到一个数据数组表，如图2所示。其中绿色文件块为在目标文件端已匹配上，不用再进行传输。而白色文件块则是匹配不上，需要通过传输进行同步的数据内容，这些数据内容是不定长的字节。最终，同步源文件把这个数据内容和数组表一起压缩传给目标文件端，在目标文件端的Rsync算法会根据这个表重新生成文件，这样同步完成。

图2.数据数组表示例

Rsync是一个客户端与服务端架构部署的网络结构。Rsync服务端指运行rsync deamon守护进程的服务器，并设置备份目录来保存同步目标文件；Rsync客户端则发起rsync连接的服务器，存放备份的同步源文件。Rsync的备份服务器体系结构如图3。

图3.Rsync备份服务器体系结构

Rsync工具不仅提供了高效快速的增量同步算法，对于数据库备份还具备许多完善、灵活的功能特性：

• 支持备份更新目录和文件；
• 适合数据存储结构大文件的增量同步备份，减少备份传输耗时；
• 对多个同步文件内部以流水线减少文件等待延时；
• 支持多种网络环境下rsh、ssh、nfs、socket端口等传输方式，可灵活支持数据库的加密、压缩等文件特性；
• 适合数据库镜像备份，支持匿名传输；
• 支持数据库备份数据可灵活保持连接、文件属性、权限、设备以及时间等；

数据库备份思路

一个数据库的数据库备份必须是一个数据库的完整的映像，在这个映像的时间点上，没有部分完成的事务存在。因此，数据库备份设计方案必须要求数据库支持在某时刻数据库的静止状态或不会对数据镜像文件进行刷新，希望对数据库系统完成在线数据库备份操作，实现数据库系统高性能的应用级备份。

方案设计思路采用Rsync工具对备份数据库各节点的数据从生产数据库系统上进行增量同步，由于生产数据库系统和备份数据库系统是拓扑结构完全相同的两个环境，因此生产数据库和备份数据库之间节点存在相对应的关系。如果在对应节点之间建立起同步关系，只要保证每个节点上的表结构、数据、日志记录等保持一致，那么整个数据库系统环境总体的表结构、数据和日志等也会一致。整个备份方案设计流程分为备份初始化、增量同步备份、备份恢复。以此来实现数据库系统的在线备份，并支持应用系统通过网络对备份数据库系统的切换和请求。

备份方案设计

通过以数据库集群的在线备份为例对设计方案和实施流程进行说明。

数据库备份方案一般主要考虑到数据库系统备份、应用系统访问切换、ETL数据业务流程备份等，整体网络拓扑结构可简单如下图所示。