Time Machine Full, But Only One Backup (or, what are .RecoverySets and why do they take up so much space?) Something crazy is going on with Time Machine. I upgraded to Mavericks yesterday with no issues. After performing a final backup on Mountain Lion, I disconnected my backup drive out of an abundance of caution, just in case I wanted to use it to roll back to 10.8. I plugged it back in today and let it do its thing, and got an out of space warning. I wasn't too worried about this, since I had been getting these previously (in the past, TM didn't do the best job estimating the space required and removing old backups).

Upon investigation, I discovered that only the most recent backup (from before the upgrade) was available. I double checked this in Finder and Terminal to confirm, and it appears correct. The Time Machine preferences showed the last backup as October 6, which seemed a bit more reasonable, but I saw no evidence of those files actually existing. The only sure thing I could determine was that something was taking up a lot of my backup volume — out of a ~750 GB volume, only 50 GB was free (Time Machine is estimating 154 GB needed, although only ~140 GB are used on my boot drive).

After further digging, I discovered what was taking up all the space. The hidden .RecoverySets folder, within the Backups.backupdb folder on my Time Machine volume. In it are more than 1,200 sequentially numbered folders, each with a com.apple.recovery.boot subfolder, containing a 419 MB BaseSystem.dmg file. Based on the md5 hashes, these dmg files are all identical, and in total add up to nearly 600 GB (or, the vast majority of the space on my Time Machine volume).

tl;dr


Missing Time Machine backups after 10.9 upgrade. Don't appear in Finder or Terminal.
Lots of folders in Backups.backupdb/.RecoverySets taking up the majority of space on my TM drive.


Additional Info


2012 iMac running 10.9 (release build, no developer previews), upgraded from 10.8 via standard App Store install.
Time Machine drive is an encrypted volume, with another volume on the same drive used by SuperDuper (which appears to be unaffected).


Questions


Are my old backups completely gone? (I'm thinking yes.)
What are the folders within the .RecoverySets folder, why have they been gobbling up space, and what can I do to prevent it in the future?
What do you suggest I do now for Time Machine backups? I'm leaning towards scrapping it altogether and starting fresh, but I am concerned about running into this issue again.


I'm not terribly concerned about the data loss at the moment — I have two other separate backups — but I do want to ensure the integrity of my backups in the future. Any info you can provide would be appreciated.
Okay, so I can't fully answer this issue but I'll share what I've found out:


Yes. Unfortunately Time Machine has deleted these, so anything unique that was in the past backups is gone for good.
The contents of .RecoverySets are copies of your Recovery HD. Ordinarily Time Machine shouldn't have more than one of these but, like you, I found the folder contained nearly a thousand identical sets. My best guess is that there is something wrong with my recovery partition that is causing Time Machine to think it has been changed, but that doesn't explain why Time Machine is creating so many copies without discarding any. I've filed a bug report with Apple, and I suggest anyone who encounters the same error does the same.
You can workaround this issue with a bit of light Terminal work:

First type cd /Volumes/{Time Machine Backup}/Backups.backupdb, replacing the part in brackets with the name of your backup volume before hitting return.
Next type sudo rm -fr .RecoverySets and hit return, you'll be asked for your password so that the command can delete your existing recovery sets.
Now run a Time Machine backup as normal using the menubar menu or by entering tmutil startbackup in Terminal and hitting return again. Wait till the backup is finished, as this will recreate your .RecoverySets folder. 
Now type sudo chflags simmutable .RecoverySets and hit return, entering your password again if prompted. This will lock the folder (though it may not show this in the Finder), preventing Time Machine from creating any duplicate recovery sets in future.



The above workaround has a few caveats; firstly you won't gain any new recovery sets, but that's unlikely to be an issue, but if you're worried your set may be outdated you can unlock the folder using sudo chflags nosimmutable .RecoverySets (after cd'ing to your backup volume), delete your recovery sets, run a Time Machine backup, then re-lock it again.
You may also notice errors in your console to the effect of "Could not backup OS X Recovery to…", but that's to be expected as you locked the target folder, it just means this workaround is doing the trick, so you can safely ignore these.

One further note; after deleting your .RecoverySets folder, you may not immediately see any extra free space in the Finder. The easiest way to do so is to open /Applications/Utilities/Disk Utility.app, unmount your backup volume and then mount it again, and you should see the correct free-space value, or you can just ignore it, as the free space should be there. In my case I freed up a massive 750gb by deleting my recovery sets folder, as I had over a thousand completely identical copies of my recovery partition in there (no wonder I only had 483kb of free space left!).

You may also want to investigate methods of repairing your recovery partition, but I'm not certain of the best way to do this; it couldn't hurt to at least try Disk Utility's first aid repair command.