CODEWITHSUNDEEP
javagoogle-app-enginecaching
jontro
jontro

Reputation: 10628

Efficient data structure for caching folder and files

We have a service layer that looks like the following

interface StructureService {
    void create(FileEntry entry, EntryType type) throws IOException;
    Collection<FileEntry> getChildren(FileEntry entry)  throws IOException;
    void delete(FileEntry entry) throws IOException;
    void rename(FileEntry file, FileEntry newFile) throws IOException;
    void copy(FileEntry source, FileEntry destination) throws IOException;
    EntryType getType(FileEntry entry);
    long getLastModified(FileEntry entry) throws IOException;
    long getSize(FileEntry entry) throws IOException;
}

We have created a proxy for caching these services since the data source might come from the database or a rpc call.

Currently the cache implementation clears the whole cache and rebuilds it after a modifying operation. This has resulted in race conditions which could be solved by synchronizing the calls. However this is very inefficient.

Instead we would like to modify the structure for each operation.

I wonder if there is a good, preferably lock less, known java implementation that can help with this scenario.

We are using memcache on google app engine as a back-end, so storing each entry with key-value pairs could help.

Upvotes: 2

Views: 524

Answers (1)

helios
helios

Reputation: 13841

If your structure is a tree of folders/files try acquiring a lock from the root to the leafs and then execute your operation. Use ReadAndWriteLock's for each item.

If you are reading use readlock. If you are writing use read lock for parents except for inmediate parent and item itself. With them use write lock.

When you obtain something acquire the lock (creating it if necessary), grab the data (reading it if not in cache), do the thing, and release the lock.

The tree-like lock acquiring read locks for parents and only write locks for items being modified lets you concurrent access but correct locking when modifying.

Samples

Update /a/b/c/d

lock for a - grab read lock
lock for b - grab read lock
lock for c - gran read lock
lock for d - grab write lock

create/delete /a/b/c/d

lock for a - grab read lock
lock for b - grab read lock
lock for c - gran **write** lock // you are modifying c's list of files

list /a/b/c/d

lock for a - grab read lock
lock for b - grab read lock
lock for c - gran read lock
lock for d - grab read lock

Note

I don't really know what's the best way to implement this in GAE. It works if you have unique locks for every item. In GAE case... I don't know if you can have that.

Upvotes: 1

Related Questions