高效的数据结构

我们有一个看起来像下面高效的数据结构

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; 
}

我们已经创建了一个代理，因为数据源缓存这些服务可能来自数据库或RPC调用一个服务层。

当前缓存实现清除整个缓存并在修改操作后重建缓存。这导致了可以通过同步呼叫来解决的竞争状况。然而这是非常低效的。

相反，我们想修改每个操作的结构。

我不知道是否有一个良好的，最好是锁定少，已知的Java实现，可以用此方案帮助。

我们在谷歌应用程序引擎上使用memcache作为后端，因此使用键值对存储每个条目可能会有帮助。

来源

2011-11-23 jontro

如果你的结构是文件夹树/文件尝试获取从根锁的叶子，然后执行该操作。为每个项目使用ReadAndWriteLock。

如果您正在阅读使用readlock。如果您正在为家长编写使用读锁，除了中间父项和项目本身。与他们一起使用写锁。

当你获得某些东西获得锁（如果需要的话创建它），获取数据（如果不在缓存中则读取它），执行该操作并释放锁。

树状锁获取父母的读取锁，并且只修改正在修改的项的锁可以让您在并发访问但修改时正确锁定。

样品

更新/ 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

创建/删除/ 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

列表/ 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

注意

我真的不知道什么是在GAE中实现这一点的最佳方式。它适用于如果你有每个项目独特的锁。在GAE的情况下...我不知道你是否可以拥有。

来源

2011-11-23 12:12:51 helios

是的，我认为这将很难在谷歌应用引擎上实现。您无法以这种方式同步memcache中的调用。尽管谢谢你的回答！ – jontro

@Bengt：谢谢 – helios

嗯...也许，如果你正在使用锁定一些任意对象...你可以随心所欲的使用ReadWriteLocks ......我的意思是，如果你有上同步化是由一些静态的对象（同步” ed方法或者在静态对象上同步），你可以使用类似的东西。但我认为假设一个唯一过程是危险的。这种锁对于JVM/ClassLoader是本地的。 – helios

高效的数据结构

回答

相关问题