понедельник, 14 декабря 2009 г.

The small signature for sqlite3-rdiff

Depends: current test version of sqlite3-rdiff

The sqlite3-rdiff utility produces a signature file of size about 10% of original database size. Yes, it's better than coping an entire database but it's not good enough for production use. So I wrote a new algorithm that can build the small signatures. The algorithm calculates checksums for set of rows and so with N rows in each set the signature size will be decreased by the factor of N! Of course the delta file size will be increased but only a little for most databases.

My code uses a hack


select rowid/N as rowid, sum(murmurhash('$unixepoch',$cols)) from ... group by rowid


This solution is not good and may be used for testing only. This code will fail with N>16.


$ time ./sqlite3-rdiff signature slave.db slave.db.signature
signature slave.db slave.db.signature --table-name % --rows-per-hash 1
=7 system_config
=160 center
=7 role
=1 macroregion
=988 point
=7 region
=1841 user
=2867166 document_status
=25 comment
=250985 document_comment
=0 operation
=16 datatype
=7 type_template
=51 template
=370 template_field
=511335 document
=1593416 document_field
=757015 document_file
=7336 document_photo
=16 status_switch
=491129 message
=7 system_config_history
=160 center_history
=7 role_history
=1 macroregion_history
=988 point_history
=7 region_history
=1841 user_history
=2869992 document_status_history
=25 comment_history
=251191 document_comment_history
=0 operation_history
=16 datatype_history
=7 type_template_history
=51 template_history
=370 template_field_history
=511335 document_history
=1593416 document_field_history
=757015 document_file_history
=7336 document_photo_history
=16 status_switch_history

real 0m55.309s
user 0m53.075s
sys 0m1.444s


$ time ./sqlite3-rdiff delta slave.db.signature master.db slave.db.delta
delta slave.db.signature master.db slave.db.delta --table-name % --rows-per-hash 1
-0 +0 system_config
-0 +0 center
-0 +0 role
-0 +0 macroregion
-0 +0 point
-0 +0 region
-0 +0 user
-687 +2922 document_status
-0 +0 comment
-50 +230 document_comment
-0 +0 operation
-0 +0 datatype
-0 +0 type_template
-0 +0 template
-0 +0 template_field
-0 +550 document
-0 +1348 document_field
-0 +970 document_file
-0 +2 document_photo
-0 +0 status_switch
-0 +4443 message
-0 +0 system_config_history
-0 +0 center_history
-0 +0 role_history
-0 +0 macroregion_history
-0 +0 point_history
-0 +0 region_history
-0 +0 user_history
-0 +4202 document_status_history
-0 +0 comment_history
-0 +230 document_comment_history
-0 +0 operation_history
-0 +0 datatype_history
-0 +0 type_template_history
-0 +0 template_history
-0 +0 template_field_history
-0 +550 document_history
-0 +1348 document_field_history
-0 +970 document_file_history
-0 +2 document_photo_history
-0 +0 status_switch_history

real 4m20.282s
user 3m18.276s
sys 0m5.944s



$ time ./sqlite3-rdiff --rows-per-hash 16 signatureN slave.db slave.db.signature16
signature slave.db slave.db.signature16 --table-name % --rows-per-hash 16
=1 system_config
=19 center
=1 role
=1 macroregion
=90 point
=1 region
=185 user
=179198 document_status
=3 comment
=15687 document_comment
=0 operation
=2 datatype
=1 type_template
=10 template
=57 template_field
=45270 document
=227657 document_field
=63430 document_file
=495 document_photo
=3 status_switch
=30697 message
=1 system_config_history
=11 center_history
=1 role_history
=1 macroregion_history
=62 point_history
=1 region_history
=116 user_history
=179375 document_status_history
=2 comment_history
=15700 document_comment_history
=0 operation_history
=2 datatype_history
=1 type_template_history
=4 template_history
=24 template_field_history
=31959 document_history
=99589 document_field_history
=47314 document_file_history
=459 document_photo_history
=2 status_switch_history

real 3m40.539s
user 1m40.978s
sys 0m8.097s


$ time ./sqlite3-rdiff --rows-per-hash 16 deltaN slave.db.signature16 master.db slave.db.delta16
delta slave.db.signature16 master.db slave.db.delta16 --table-name % --rows-per-hash 16
-0 +0 system_config
-0 +0 center
-0 +0 role
-0 +0 macroregion
-0 +0 point
-0 +0 region
-0 +0 user
-5808 +8042 document_status
-0 +0 comment
-480 +654 document_comment
-0 +0 operation
-0 +0 datatype
-0 +0 type_template
-0 +0 template
-0 +0 template_field
-16 +553 document
-16 +1352 document_field
-16 +974 document_file
-4 +4 document_photo
-0 +0 status_switch
-16 +4452 message
-0 +0 system_config_history
-0 +0 center_history
-0 +0 role_history
-0 +0 macroregion_history
-0 +0 point_history
-0 +0 region_history
-0 +0 user_history
-16 +4211 document_status_history
-0 +0 comment_history
-16 +238 document_comment_history
-0 +0 operation_history
-0 +0 datatype_history
-0 +0 type_template_history
-0 +0 template_history
-0 +0 template_field_history
-16 +558 document_history
-16 +1357 document_field_history
-16 +978 document_file_history
-11 +11 document_photo_history
-0 +0 status_switch_history

real 3m28.369s
user 1m51.347s
sys 0m7.928s



$ ls -lh|grep slave.db|awk '{print $5 "\t" $8}'
1.5G slave.db
3.4M slave.db.delta
4.3M slave.db.delta16
160M slave.db.signature
13M slave.db.signature16

Комментариев нет:


(C) Alexey Pechnikov aka MBG, mobigroup.ru