Notes for backup implementation

Backup index database (one per user):

chunk:

int id
timestamp ts
int offset
int length
text file_sha1              -> sha1 of (compressed) data prior to this chunk
text data_sha1              -> sha1 of (uncompressed) data contained in this chunk

mailbox:

int id
int last_chunk_id           -> chunk that knows the current state
char uniqueid               -> unique
char mboxname               -> altered by a rename
char mboxtype
int last_uid
int highestmodseq
int recentuid
timestamp recenttime
timestamp last_appenddate
timestamp pop3_last_login
timestamp pop3_show_after
timestamp uidvalidity
char partition
char acl
char options
int sync_crc
int sync_crc_annot
char quotaroot
int xconvmodseq
char annotations
timestamp deleted           -> time that it was unmailbox'd, or NULL if still alive

message:

int id
char guid
char partition              -> this is used to set the spool directory for the temp file - we might not need it
int chunk_id
int offset                  -> offset within chunk of dlist containing this message
int size                    -> size of this message (n.b. not length of dlist)

mailbox_message:

int mailbox_id
int message_id
int last_chunk_id           -> chunk that has a RECORD in a MAILBOX for this
int uid
int modseq
timestamp last_updated
char flags
timestamp internaldate
int size
char annotations
timestamp expunged          -> time that it was expunged, or NULL if still alive

subscription:

int last_chunk_id           -> chunk that knows the current state
char mboxname               -> no linkage to mailbox table, users can be sub'd to nonexistent
timestamp unsubscribed      -> time that it was unsubscribed, or NULL if still alive

seen:

int last_chunk_id           -> chunk that knows the current state
char uniqueid               -> mailbox (not necessarily ours) this applies to
timestamp lastread
int lastuid
timestamp lastchange
char seenuids               -> a uid sequence encoded as a string

sieve:

int chunk_id
timestamp last_update
char filename
char guid
int offset                  -> offset within chunk of the dlist containing this script
timestamp deleted           -> time that it was deleted, or NULL if still alive

sieve scripts and messages are both identified by a GUID but APPLY SIEVE doesn't take a GUID, it seems to be generated locally? the GUID in the response to APPLY SIEVE is generated in the process of reading the script from disk (sync_sieve_list_generate)

can't activate scripts because only bytecode files are activated, but we neither receive bytecode files over sync protocol nor do we compile them ourselves.

possibly reduce index size by breaking deleted/expunged values into their own tables, such that we only store a deleted value for things that are actually deleted. use left join + is null to find undeleted content

messages

APPLY MESSAGE is a list of messages, not necessarily only one message. Actually, it's a list of messages for potentially multiple users, but we avoid this by rejecting GET MESSAGES requests that span multiple users (so that sync_client retries at USER level, and so we only see APPLY MESSAGE requests for a single user).

Cheap first implementation is to index the start/end of the entire APPLY MESSAGE command identically for each message within it, and at restore time we grab that chunk and loop over it looking for the correct guid.

Ideal implementation would be to index the offset and length of each message exactly (even excluding the dlist wrapper), but this is rather complicated by the dlist API.

For now, we just index the offset of the dlist entry for the message, and we can parse the pure message data back out later from that, when we need to. Slightly less efficient on reads, but works->good->fast. We need to loop over the entries in the MESSAGE dlist to find the one with the desired GUID.

The indexed length needs to be the length of the message, not the length of the dlist wrapper, because we need to know this cheaply to supply RECORDs in MAILBOX responses.

renames

APPLY RENAME %(OLDMBOXNAME old NEWMBOXNAME new PARTITION p UIDVALIDITY 123)

We identify mboxes by uniqueid, so when we start seeing sync data for the same uniqueid with a new mboxname we just transparently update it anyway, without needing to handle the APPLY RENAME. Not sure if this is a problem... Do we need to record an mbox's previous names somehow?

I think it's possible to use this to rename a USER though, something like:

APPLY RENAME %(OLDMBOXNAME example.com!user.smithj NEWMBOXNAME example.com!user.jsmith ...)

-- in which case, without special handling of the RENAME command itself, there will be a backup for the old user that ends with the RENAME, and a backup of the new user that (probably) duplicates everything again (except for stuff that's been expunged).

And if someone else gets given the original name, like

APPLY RENAME %(OLDMBOXNAME example.com!user.samantha-mithj NEWMBOXNAME example.com!user.smithj ...)

Then anything that was expunged from the original user but still available in backup disappears? Or the two backups get conflated, and samantha can "restore" the original smithj's old mail?

Uggh.

if there's a mailboxes database pointing to the backup files, then the backup file names don't need to be based on the userid, they could e.g. be based on the user's inbox's uniqueid. this would make it easier to deal with user renames because the backup filename wouldn't need to change. but this depends on the uniqueid(s) in question being present on most areas of the sync protocol, otherwise when starting a backup of a brand new user we won't be able to tell where to store it. workaround in the meantime could be to make some kind of backup id from the mailboxes database, and base the filename on this.

actually, using "some kind of backup id from the mailboxes database" is probably the best solution. otherwise the lock complexity of renaming a user while making sure their new backup filename doesn't already exist is frightful.

maybe do something with mkstemp()?

furthermore: what if a mailbox is moved from one user to another? like:

APPLY RENAME %(OLD... example.com!user.foo.something NEW... example.com!user.bar.something ...)

when a different-uid rename IS a rename of a user (and not just a folder being moved to a different user), what does it look like? * does it do a single APPLY RENAME for the user, and expect their folders to shake out of that? * does it do an APPLY RENAME for each of their folders?

in the latter case, we need to append each of those RENAMEs to the old backup so they can take effect correctly, and THEN rename the backup file itself. but how to tell when the appends are finished?

how can we tell the difference between folder(s) moved to a different user vs user has been renamed?

there is a setting: 'allowusermoves: 0' which, when enabled, allows users to be renamed via IMAP rename/xfer commands. but the default is that this is disabled. we could initially require this to be disabled while using backups...

not sure what the workflow looks like for renaming a user if this is not enabled.

not sure what the sync flow looks like in either case.

looking at sync_apply_rename and mboxlist_renamemailbox, it seems like we'll see an APPLY RENAME for each affected mbox when a recursive rename is occurring.

there doesn't seem to be anything preventing user/a/foo -> user/b/foo in the general (non-INBOX) case.

renames might be a little easier to handle if the index replicated the mailbox hierarchy rather than just being a flat structure. though this adds complexity wrt hiersep handling. something like:

mailbox:

mboxname

# just the name of this mbox

parent_id

# fk to parent mailbox

full_mboxname

# cached value, parent.full_mboxname + mboxname

locking

just use a normal flock/fcntl lock on the data file and only open the index if that lock succeeded

  • backup: needs to append foo and update foo.index

  • reindex: only needs to read foo, but needs a write lock to prevent

    writes while it does so. needs to write to (replace) foo.index

  • compact: needs to re-write foo and foo.index

  • restore: needs to read

verifying index

how to tell whether the .index file is the correct one for the backup data it ostensibly represents?

one way to do this would be to have backup_index_end() store a checksum of the corresponding data contents in the index.

when opening a backup, verify this checksum against the data, and refuse to load the index if it doesn't match.

  • sha1sum of (compressed) contents of file prior to each chunk

how to tell whether the chunk data is any good? store a checksum of the chunk contents along with the rest of the chunk index

  • sha1sum of (uncompressed) contents of each chunk

mailboxes database

bron reckons use twoskip for this userid -> backup_filename

lib/cyrusdb module implements this, look into that

look at conversations db code to see how to use it

need a tool: * given a user, show their backup filename * dump/undump * rebuild based on files discovered in backup directory

where does this fit into the locking scheme?

reindex

  • convert user mailbox name to backup name

  • complain if there's no backup data file?

  • lock, rename .index to .index.old, init new .index

  • foreach file chunk:

  • timestamp is from first line in chunk

  • complain if timestamp has gone backwards?

  • index records from chunk

  • unlock

  • clean up .index.old

on error: * discard partial new index * restore .index.old * bail out

backupd

cmdloop: * (periodic cleanup) * read command, determine backup name * already holding lock ? bump timestamp : obtain lock * write data to gzname, flush immediately * index data

periodic cleanup: * check timestamp of each held lock * if stale (define: stale?), release * FIXME if we've appended more than the chunk size we would compact to, release

sync restart: * release each held lock

exit: * release each held lock

need a "backup_index_abort" to complete the backup_index_start/end set. _start should create a transaction, _end should commit it, and _abort should roll it back. then, if backupd fails to write to the gzip file for some reason, the (now invalid) index info we added can be discarded too.

flushing immediately on write results in poor gzip compression, but for incremental backups that's not a problem. when the compact process hits the file it will recompress the data more efficiently.

questions

  • what does it look like when uidvalidity changes?

restore

restoration is effectively a reverse-direction replication (replicating TO master), which means we can't necessarily supply things like uid, modseq, etc without racing against normal message arrivals. so instead we add an extra command to the protocol to restore a message to a folder but let the destination determine the tasty bits.

protocol flow looks something like:

c: APPLY RESERVE ... # as usual s: * MISSING (foo bar) s: OK c: APPLY MESSAGE ... # as usual s: OK c: RESTORE MAILBOX ... # new sync proto command s: OK

we introduce a new command, RESTORE MAILBOX, which is similar to the existing APPLY MAILBOX. it specifies, for a mailbox, the mailbox state plus the message records relevant to the restore.

the imapd/sync_server receiving the RESTORE command creates the mailbox if necessary, and then adds the message records to it as new records (i.e. generating new uid etc). this will end up generating new events in the backup channel's sync log, and then the messages will be backed up again with their new uids, etc. additional wire transfer of message data should be avoided by keeping the same guid.

if the mailbox already exists but its uniqueid does not match the one from the backup, then what? this probably means user has deleted folder and contents, then made new folder with same name. so it's probably v common for mailbox uniqueid to not match like this. so we don't care about special handling for this case. just add any messages that aren't already there.

if the mailbox doesn't already exist on the destination (e.g. if rebuilding a server from backups) then it's safe and good to reuse uidvalidity, uniqueid, uid, modseq etc, such that connecting clients can preserve their state. so the imapd/sync_server receiving the restore request accepts these fields as optional, but only preserves them if it's safe to do so.

  • restore: sbin program for selecting and restoring messages

restore command needs options: + whether or not to trim deletedprefix off mailbox names to be restored + whether or not to restore uniqueid, highestmodseq, uid and so on + whether or not to limit to/exclude expunged messages + whether or not to restore sub-mailboxes + sync_client-like options (servername, local_only, partition, ...) + user/mailbox/backup file(s) to restore from + mailbox to restore to (override location in backup) + override acl?

can we heuristically determine whether an argument is an mboxname, uniqueid or guid?

=> libuuid uniqueid is 36 bytes of hyphen (at fixed positions) and hex digits => non-libuuid uniqueid is 24 bytes of hex digits => mboxname usually contains at least one . somewhere => guid is 40 bytes of hex digits

usage:

restore [options] server [mode] backup [mboxname | uniqueid | guid]...

options:
-A acl

# apply specified acl to restored mailboxes

-C alt_config

# alternate config file

-D

# don't trim deletedprefix before restoring

-F input-file

# read mailboxes/messages from file rather than argv

-L

# local mailbox operations only (no mupdate)

-M mboxname

# restore messages to specified mailbox

-P partition

# restore mailboxes to specified partition

-U

# try to preserve uniqueid, uid, modseq, etc

-X

# don't restore expunged messages

-a

# try to restore all mailboxes in backup

-n

# calculate work required but don't perform restoration

-r

# recurse into submailboxes

-v

# verbose

-w seconds

# wait before starting (useful for attaching a debugger)

-x

# only restore expunged messages (not sure if useful?)

-z

# require compression (abort if compression unavailable)

mode:
-f

# specified backup interpreted as filename

-m

# specified backup interpreted as mboxname

-u

# specified backup interpreted as userid (default)

compact

# finding messages that are to be kept (either exist as unexpunged somewhere, # or exist as expunged but more recently than threshold) # (to get unique rows, add "distinct" and remove mm.expunged from fields) sqlite> select m.*, mm.expunged from message as m join mailbox_message as mm on m.id = mm.message_id and (mm.expunged is null or mm.expunged > 1437709300); id|guid|partition|chunk_id|offset|length|expunged 1|1c7cca361502dfed2d918da97e506f1c1e97dfbe|default|1|458|2159| 1|1c7cca361502dfed2d918da97e506f1c1e97dfbe|default|1|458|2159|1446179047 1|1c7cca361502dfed2d918da97e506f1c1e97dfbe|default|1|458|2159|1446179047

# finding chunks that are still needed (due to containing last state # of mailbox or mailbox_message, or containing a message) sqlite> select * from chunk where id in (select last_chunk_id from mailbox where deleted is null or deleted > 1437709300 union select last_chunk_id from mailbox_message where expunged is null or expunged > 1437709300 union select chunk_id from message as m join mailbox_message as mm on m.id = mm.message_id and (mm.expunged is null or mm.expunged > 1437709300)); id|timestamp|offset|length|file_sha1|data_sha1 1|1437709276|0|3397|da39a3ee5e6b4b0d3255bfef95601890afd80709|6836d0110252d08a0656c14c2d2d314124755491 3|1437709355|1977|2129|fee183c329c011ead7757f59182116500776eaaf|a5677cfa1f5f7b627763652f4bb9b99f5970748c 4|1437709425|2746|1719|3d9f02135bf964ff0b6a917921b862c3420e48f0|7b64ec321457715ee61fe238f178f5d72adaef64 5|1437709508|3589|2890|0cee599b1573110fee428f8323690cbcb9589661|90d104346ef3cba9e419461dd26045035f4cba02

remember: a single APPLY MESSAGE line can contain many messages!

thoughts:

  • need a heuristic for quickly determining whether a backup needs to be compacted

    • sum(chunks to discard, chunks to combine, chunks to split) > threshold

    • can we detect chunks that are going to significantly reduce in size as result of discarding individual lines?

  • "quick" vs "full" compaction

settings:

  • backup retention period

  • chunk combination size (byte length or elapsed time)

combining chunks: * size threshold below which adjacent chunks can be joined * size threshold above which chunks should be split * duration threshold below which adjacent chunks can be joined * duration threshold above which chunks should be split backup_min_chunk_size: 0 for no minimum backup_max_chunk_size: 0 for no maximum backup_min_chunk_duration: 0 for no minimum backup_max_chunk_duration: 0 for no maximum priority: size or duration??

data we absolutely need to keep:

  • the most recent APPLY MAILBOX for each mailbox we're keeping (mailbox state)

  • the APPLY MAILBOX containing the most recent RECORD for each message we're keeping (record state)

  • the APPLY MESSAGE for each message we're keeping (message data)

data that we should practically keep:

  • all APPLY MAILBOXes for a given mailbox from the chunk identified as its last

  • all APPLY MAILBOXes containing a RECORD for a given message from the chunk identified as its last

  • the APPLY MESSAGE for each message we're keeping

four kinds of compaction (probably at least two simultaneously):

  • removing unused chunks

  • combining adjacent chunks into a single chunk (for better gz compression)

  • removing unused message lines from within a chunk (important after combining)

  • removing unused messages from within a message line

"unused messages"

messages for which all records have been expunged for longer than the retention period

"unused chunks"

chunks which contain only unused messages

algorithm:

  • open (and lock) backup and backup.new (or bail out)

  • use backup index to identify chunks we still need

  • create a chunk in backup.new

  • foreach chunk we still need:

  • foreach line in the chunk:

  • next line if we don't need to keep it

  • create new line

  • foreach message in line:

  • if we still need the message, or if we're not doing message granularity

  • add the message to the new line

  • write and index tmp line to backup.new

  • if the new chunk is big enough, or if we're not combining

  • end chunk and start a new one

  • end the new chunk

  • rename backup->backup.old, backup.new->backup

  • close (and unlock) backup.old and backup

command line locking utility

command line utility to lock a backup (for e.g. safely poking around in the .index on a live system).

example failure: $ctl_backups lock -f /path/to/backup * Trying to obtain lock on /path/to/backup... NO some error <EOF>

example success: $ctl_backups lock -f /path/to/backup * Trying to obtain lock on /path/to/backup... [potentially a delay here if we need to wait for another process to release the lock] OK locked [waits for its stdin to close, then unlocks and exits]

if you need to rummage around in backup.index, run this program in another shell, do your work, then ^D it when you're finished.

you could also call this from e.g. perl over a bidirectional pipe - wait to read "OK locked", then you've got your lock. close the pipe to unlock when you're finished working. if you don't read "OK locked" before the pipe closes then something went wrong and you didn't get the lock.

specify backups by -f filename, -m mailbox, -u userid default run mode as above -s to fork an sqlite of the index (and unlock when it exits) -x to fork a command of your choosing (and unlock when it exits)

reconstruct

rebuilding backups.db from on disk files

scan each backup partition for backup files:

  • skip timestamped files (i.e. backups from compact/reindex)

  • skip .old files (old backups from reindex)

  • .index files => skip???

  • skip unreadable files

  • skip empty files

  • skip directories etc

what's the correct procedure for repopulating a cyrus database? keep copy of the previous (presumably broken) one?

trim off mkstemp suffix (if any) to find userid can we use a recognisable character to delimit the mkstemp suffix?

what if there's multiple backup files for a given userid? precedence?

verify found backups before recording. reindex?

locking? what if something has a filename and does stuff with it while reconstruct runs?

backupd always uses db for opens, so as long as reconstruct keeps the db locked while it works, the db won't clash. but backupd might have backups still open from before reconstruct started, which it will write to quite happily, even though reconstruct might decide that some other file is the correct one for that user...

a backup server would generally be used only for backups, and sync_client is quite resilient when the destination isn't there, so it's actually no problem to just shut down cyrus while reconstruct runs. no outage to user-facing services, just maybe some sync backlog to catch up on once cyrus is restarted.

ctl_backups

sbin tool for mass backup/index/database operations

needs:

  • rebuild backups.db from disk contents

  • list backups/info

  • rename a backup

  • delete a backup

  • verify a backup (check all sha1's, not just most recent)

not sure if these should be included, or separate tools:

  • reindex a backup (or more)

  • compact a backup (or more)

  • lock a backup

  • some sort of rolling compaction?

usage:

ctl_backups [options] reconstruct # reconstruct backups.db from disk files ctl_backups [options] list [list_opts] [[mode] backup...] # list backup info for given/all users ctl_backups [options] move new_fname [mode] backup # rename a backup (think about this more) ctl_backups [options] delete [mode] backup # delete a backup ctl_backups [options] verify [mode] backup... # verify specified backups ctl_backups [options] reindex [mode] backup... # reindex specified backups ctl_backups [options] compact [mode] backup... # compact specified backups ctl_backups [options] lock [lock_opts] [mode] backup # lock specified backup

options:
-C alt_config

# alternate config file

-F

# force (run command even if not needed)

-S

# stop on error

-v

# verbose

-w

# wait for locks (i.e. don't skip locked backups)

mode:
-A

# all known backups (not valid for single backup commands)

-D

# specified backups interpreted as domains (nvfsbc)

-P

# specified backups interpreted as userid prefixes (nvfsbc)

-f

# specified backups interpreted as filenames

-m

# specified backups interpreted as mboxnames

-u

# specified backups interpreted as userids (default)

lock_opts:
-c

# exclusively create backup

-s

# lock backup and open index in sqlite

-x cmd

# lock backup and execute cmd

-p

# lock backup and wait for eof on stdin (default)

list_opts:

-t [hours] # "stale" (no update in hours) backups only (default: 24)

cyr_backup

sbin tool for inspecting backups

needs:

  • better name?

  • list stuff

  • show stuff

  • dump stuff

  • restore?

  • should lock/move/delete (single backup commands) from ctl_backups be moved here?

usage:

cyr_backup [options] [mode] backup list [all | chunks | mailboxes | messages]... cyr_backup [options] [mode] backup show chunks [id...] cyr_backup [options] [mode] backup show messages [guid...] cyr_backup [options] [mode] backup show mailboxes [mboxname | uniqueid]... cyr_backup [options] [mode] backup dump [dump_opts] chunk id cyr_backup [options] [mode] backup dump [dump_opts] message guid cyr_backup [options] [mode] backup json [chunks | mailboxes | messages]...

options:
-C alt_config

# alternate config file

-v

# verbose

mode:
-f

# backup interpreted as filename

-m

# backup interpreted as mboxname

-u

# backup interpreted as userid (default)

commands:

list: table of contents, one per line show: indexed details of listed items, one per paragraph, detail per line dump: relevant contents from backup stream json: indexed details of listed items in json format

dump options:
-o filename

# dump to named file instead of stdout

partitions

not enough information in sync protocol to handle partitions easily?

we know what the partition is when we do an APPLY operation (mailbox, message, etc), but the initial GET operations don't include it. so we need to already know where the appropriate backup is partitioned in order to find the backup file in order to look inside it to respond to the GET request

if we have a mailboxes database (indexed by mboxname, uniqueid and userid) then maybe that would make it feasible? if it's not in the mailboxes database then we don't have a backup for it yet, so we respond accordingly, and get sent enough information to create it.

does that mean the backup api needs to take an mbname on open, and it handles the job of looking it up in the mailboxes database to find the appropriate thing to open?

can we use sqlite for such a database, or is the load on it going to be too heavy? locking? we have lots of database formats up our sleeves here, so even though we use sqlite for the backup index there isn't any particular reason we're beholden to it for the mailboxes db too

if we have a mailboxes db then we need a reconstruct tool for that, too

what if we support multiple backup partitions, but don't expect these to necessarily correspond with mailbox partitions. they're just for spreading disk usage around.

  • when creating a backup for a previously-unseen user we'd pick a random partition to put them on

  • ctl_backups would need a command to move an existing backup to a given partition

  • ctl_backups would need a command to pre-create a user backup on a given partition for initial distribution

  • instead of "backup_data_path" setting, have one-or-more "backuppartition-<name>" settings, ala partition- and friends

see imap/partlist.[ch] for partition list management stuff. it's complicated and doesn't have a test suite, so maybe save this implementation until needed.

but... maybe rename backup_data_path to backuppartition-default in the meantime, so that when we do add this it's not a complicated reconfig to update?

partlist_local_select (and lazy-loaded partlist_local_init) are where the mailbox partitions come from (see also mboxlist_create_partition), do something similar for backup partitions

data corruption

backups.db:

  • can be reconstructed from on disk files at any time

  • how to detect corruption? does cyrus_db detect/repair on its own?

backup indexes:

  • can be reindexed at any time from backup data

  • how to detect corruption? assume sqlite will notice, complain?

backup data:

  • what's zlib's failure mode? do we lose the entire chunk or just the corrupt bit?

  • verify will notice sha1sum mismatches

  • dlist format will reject some kinds of corruption (but not all)

  • reindex: should skip unparseable dlist lines

  • message data has its own checksums (guid)

  • reindex: should skip messages that don't match their own checksums

  • compact: "full" compact will only keep useful data according to index

  • backupd: will sync anything that's in user mailbox but not in backup index

i think this means that if a message or mailbox state becomes corrupted in the backup data file, and it still exists in the user's real mailbox, you recover from the corruption by reindexing and then letting the sync process copy the missing data back in again. and you can tidy up the data file by running a compact over it.

you detect data corruption in most recent chunk reactively as soon as the backup system needs to open it again (quick verify on open)

you detect data corruption in older chunks reactively by trying to restore from it. may be too late: if a message needs restoring it's because user mailbox no longer has it

you detect data corruption preemptively by running the verify tool over it. recommend scheduling this in EVENTS/cron?

if data corruption occurs in message that's no longer in user's mailbox, that message is lost. it was going to be deleted from the backup after $retention period anyway (by compact), but if it needs restoring in the meantime, sorry

installation instructions

(obviously, most of this won't work at this point, because the code doesn't exist. but this is, approximately, where things are heading.)

on your backup server:

  • compile with --enable-backup configure option and install

  • imapd.conf:

    backuppartition-default: /var/spool/backup # FIXME better example backup_db: twoskip backup_db_path: /var/imap/backups.db backup_staging_path: /var/spool/backup backup_retention_days: 7

  • cyrus.conf SERVICES:

    backupd cmd="backupd" listen="csync" prefork=0 (remove other services, most likely) (should i create a master/conf/backup.conf example file?)

  • cyrus.conf EVENTS:

    compact cmd="ctl_backups compact -A" at=0400

  • start server as usual

  • do i want a special port for backupd?

on your imap server:
  • imapd.conf:

    sync_log_channels: backup sync_log: 1 backup_sync_host: backup-server.example.com backup_sync_port: csync backup_sync_authname: ... backup_sync_password: ... backup_sync_repeat_interval: ... # seconds, smaller value = livelier backups but more i/o backup_sync_shutdown_file: ....

  • cyrus.conf STARTUP:

    backup_sync cmd="sync_client -r -n backup"

  • cyrus.conf SERVICES:

    restored cmd="restored" [...]

  • start/restart master

files and such:

{configdirectory}/backups.db - database mapping userids to backup locations {backuppartition-name}/<hash>/<userid>_XXXXXX - backup data stream for userid {backuppartition-name}/<hash>/<userid>_XXXXXX.index - index into userid's backup data stream

do i want rhost in the path?

  • protects from issue if multiple servers are trying to back up their own version of same user (though this is its own problem that the backup system shouldn't have to compensate for)

  • but makes location of undifferentiated user unpredictable

  • so probably not, actually

chatting about implementation 20/10

09:54 @elliefm
here's a fun sync question
APPLY MESSAGE provides a list of messages
can a single APPLY MESSAGE contain messages for multiple mailboxes and/or users?
my first hunch is that it doesn't cross users, since the broadest granularity for a single sync run is USER
10:06 kmurchison
We'd have to check with Bron, but I *think* messages can cross mailboxes for a single user
10:06 @brong
yes
APPLY MESSAGE just adds it to the reserve list
10:07 @elliefm
nah apply message uploads the message, APPLY RESERVE adds it to the reserve list :P
10:07 @brong
same same
APPLY RESERVE copies it from a local mailbox
APPLY MESSAGE uploads it
10:07 @elliefm
yep
10:07 @brong
they both wind up in the reserve list
10:07 @elliefm
ahh i see what you mean, gotcha
10:07 @brong
until you send a RESTART
ideally you want it reserve in the same partition, but it will copy the message over if it's not on the same partition
there's no restriction on which mailbox it came from/went to
good for user renames, and good for an append to a bunch of mailboxes in different users / shared space all at once
(which LMTP can do)
10:10 @elliefm
i can handle the case where a single APPLY MESSAGE contains messages for multiple mailboxes belonging to the same user
but i'm in trouble if a single APPLY MESSAGE can contain messages belonging to different users
10:14 @brong
@elliefm: why?
10:14 @brong
you don't have to keep them if they aren't used
10:15 @elliefm
for backups - when i see the apply, i need to know which user's backup to add it to.  that's easy enough if it doesn't cross users but gets mega fiddly if it does
i'm poking around in sync client to see if it's likely to be an issue or not
11:00 @brong_
@elliefm: I would stage it, and add it to users as it gets refcounted in by an index file
11:07 @elliefm
that's pretty much what we do for ordinary sync and delivery stuff yeah?
11:08 @brong_
yep
and it's what the backup thing does
11:09 @elliefm
i'm pretty sure that APPLY RESERVE and APPLY MESSAGE don't give a damn about users, they're just "here's every message you might not have already had since last time we spoke" and it lets the APPLY MAILBOX work out where to attach them later
11:09 @brong_
yep
11:09 @elliefm
so yeah, i'll need to do something here
i've been working so far on the idea that a single user's backup consists of 1) an append-only gzip stream of the sync protocol chat that built it, and 2) an index that tracks current state of mailboxes, and offsets within (1) of message data
that gets us good compression (file per user, not file per message), and if the index gets corrupted or lost, it's rebuildable purely from (1), it doesn't need a live copy of the original mailbox
11:12 @brong
yep, that all works
11:12 @elliefm
(so if you lose your imap server, you're not unable to rebuild a broken index on the backup)
11:13 @brong
it's easy enough to require the sync protocol stream to only contain messages per user
though "apply reserve" is messy
because you need to return "yes, I have that message"
11:13 @elliefm
with that implementation i can't (easily) keep user.a's messages from not existing in user.b's data stream (though they won't be indexed)
11:14 @brong
I'm not too adverse to the idea of just unpacking each message as it comes off the wire into a temporary directory
11:14 @elliefm
(because at the time i'm receiving the sync data i don't know which it needs to go in, so if they come in in the same reserve i'd need to append them to both data streams)
which isn't a huge problem, just… irks me a bit
11:14 @brong
and then reading the indexes as they come in, checking against the state DB to see if we already have them, and streaming them into the gzip if they aren't there yet
what we can do is something like the current format, where files go into a tar
11:16 @elliefm
i guess the fiddly bit there is that there's one more moving part to keep synchronised across failure states
a backup for a single user becomes 1) data stream + 2) any messages that were uploaded but not yet added to a mailbox + 3) index (which doesn't know what to do with (2))
which in the general case is fine, the next sync will update the mailboxes, which will push (2) into (1) and index it nicely, and on we go
but it's just a little bit more mess if there's a failure that you need to recover from between those states — it's no longer a simple case of "it's in the backup and we know everything about it" or "it doesn't exist", there's a third case of "well we might have the data but don't really know what to do with it"
the other fiddly bit is that the process of appending to the data stream is suddenly in the business of crafting output rather than simply dumping what it gets, which isn't really burdensome, but it is one more little crack for bugs to crawl into
i guess in terms of sync protocol, one thing i could do on my end is identify apply operations that seem to contain multiple users' data, and just return an error on those.  the sync client on the other end will promote them until they're eventually user syncs, which i think are always user granularity
11:50 @elliefm
i think for now, first stage implementation will be to stream the reserve/message commands in full to every user backup they might apply to.  and optimising that down so that each stream only contains messages belonging to that user can be a future optimisation

todo list

  • clean up error handling

  • perl tool to anonymise sync proto talk

  • verification step to check entire data stream for errors (even chunks that aren't indexed)

  • prot_fill_cb: extra argument to pass back an error string to prot_fill

  • ctl_backups verify: set level

  • backupd: don't block on locked backups, return mailbox locked -- but sync_client doesn't handle this

  • test multiple backup partitions

  • configure: error if backups requested and we don't have zlib

  • valgrind

  • finish reconstruct

  • compact: split before append?

compact implementation steps:

1 remove unused chunks, keep everything else as is 2 join adjacent chunks if small enough, split large chunks 3 parse/rebuild message lines 4 discard unused mailbox lines