Where does Time Machine store its cache? Mine is sometimes corrupted.

It's not a cache. Time Machine normally uses the File System Event Store, a hidden log that OSX keeps on each Mac-formatted disk or partition. That tells TM every folder that was changed; TM then compares the files in that folder to the most recent backup, to see what's changed and needs to be backed-up. Since OSX and apps consist of hundreds of thousands of folders that are rarely changed, it's a quick process.

Sometimes, however, it can't use the Event Log, and must compare every file on your system to the backups, so can take quite a while. Longer if your backups are on a network. This is called a "deep scan."

A number of things can cause that; a failed or cancelled backup; an abnormal shutdown; an abnormal shutdown or disconnection of the TM drive; a very large volume of changes that overwhelms the Event Log (entries aren't kept forever), such as an OSX update; and, sometimes, booting from another partition.

Bottom line: there's not much you can do to prevent it when booting back and forth between OSX and Windows when using Boot Camp.

See How Time Machine works its Magic for more details.

GaryKing wrote:

Okay thanks. I notice that it doesn't ALWAYS perform a deep scan when moving between OSes. However, because I have MacDrive installed in Windows 7, I am able to edit HFS+ partitions and so sometimes when I modify it, I assume that's when a deep scan is required.

Yup, that'll do it. Apparently, MacDrive is modifying the files, but since it doesn't go through the OSX kernel, OSX isn't aware of it, so there aren't any entries in the File System Event Store. Fortunately, however, OSX does figure out that things were missed, and notifies Time Machine (and Spotlight, and any other processes using it).

It's rather dated, so may not apply exactly to Lion, but see this extract from the FSEvents design and implementation section of the Ars Technica review of Leopard:

As with all kernel-based file system notification mechanisms, including /dev/fsevents, there's still the possibility of file system changes occurring without going through the kernel. For example, a removable disk may be mounted on another non-Leopard computer and modified there. When it returns, the local kernel has no idea what's changed.

The FSEvents API includes callbacks for these situations, effectively telling the client, "Unknown changes have occurred. You'll have to do a full rescan yourself, then pick up on the new event stream going forward."