This post is somewhat off topic, as you specifically requested responses discussing sharing large data structures between multiple threads.

Generally when things get this big, I turn to a database to do the locking and caching. If you use an SQL database, use transactions to handle the locking, and let the database+OS figure out which items to keep in memory. The DBM style databases probably work well for this, too. (I wouldn't know, as I don't normally use them.)

Of course, you'd need to rewrite chunks of your program to do it this way, which is a disadvantage. If you get stuck, though, and wind up rewriting bits of it, I'd suggest making some functions that abstract away the data structure so you can put in a choice of back ends to handle the storage (memory, database, flat file, etc.).

...roboticus

When your only tool is a hammer, all problems look like your thumb.