维护文件系统客户端目录高速缓存的方法、系统和装置

摘要

本发明涉及一种维护文件系统客户端目录高速缓存的方法、系统和装置。在分布式文件系统中，将文件系统目录的缓存的版本与所述目录的服务器版本同步。服务器和客户端都指定其目录版本的版本号。从客户端接收指定目录更新的请求时，服务器更新其版本，递增其版本号，并向客户端传送包含具有递增后的版本号的更改日志的回复。接收到回复时，客户端将所接收的版本号与其缓存的版本的版本号相比较。如果版本号与下一预期更新的版本号匹配，则客户端将更新应用于其缓存的版本并递增其版本号。否则，其将所接收的更改日志添加到所述目录的更改日志队列而不递增最新应用的版本。提供了用于在不等待来自服务器的回复的情况下处理并行读取和更新请求的机制。

说明书

技术领域

本发明涉及分布式文件系统领域，其中一个或多个客户端机器通过通信网络与特定文件系统的服务器机器通信。具体地说，本发明涉及当客户端机器上的一个或多个任务更新目录时维护缓存的文件系统目录的一致性。

背景技术

作为讨论本发明所针对的问题的初步准备，讨论一些基本概念将是很有用的，所述概念通常与操作系统、文件系统相关，具体与分布式文件系统相关。

操作系统是为在计算机系统上运行的应用程序执行基本系统服务的软件组件。操作系统管理应用程序对各种系统资源(例如数据文件、可执行程序文件)、硬件资源(例如处理器和存储器)等的使用。操作系统的一个重要子集是基于UNIX的操作系统，如此称谓是因为它们在不同程度上符合由贝尔电话实验室(AT&T Bell Laboratories)创建的具有此名称的原始操作系统所建立的一组标准。基于UNIX的操作系统包括Linux操作系统以及IBM AIX操作系统和IBM z/OS操作系统的UNIX SystemServices组件。基于UNIX的操作系统在诸如“The UNIX Operating System(UNIX操作系统)”(K.Christian，1988年)和“Modern Operating Systems(现代操作系统)”(A.S.Tanenbaum，1992年，具体在第265-314页)之类的出版物中更详细地讨论，这两种出版物都在此引入作为参考。

操作系统使用文件系统组织数据和程序文件，以便它们可以由应用访问。文件系统主要在上述Tanenbaum参考资料(1992年)的第145-204页中讨论；UNIX文件系统具体在上述Christian参考资料(1988年)的第49-62页以及Tanenbaum的第287-290页中讨论。通常，此类文件系统采用分层文件系统(HFS)的形式，其中文件在逻辑上包含在目录中，每个目录可以是根目录或父目录中包含的子目录。

分布式文件系统通常如文件系统那样在本领域中是公知的。如在“IBMDictionary of Computing(IBM计算字典)(1994年)”的第209页所定义的，分布式文件系统(DFS)是“由物理上位于通信网络中的多个计算机上的文件或目录组成的”文件系统。存在多种本领域公知的常用分布式文件系统产品。这些分布式文件系统中的某些文件系统将缓存文件系统目录的内容，某些则不缓存。(在此，术语“目录”指作为标准UNIX文件系统树的一部分的文件名称目录。)

大多数UNIX文件系统目录包含此目录中的所有子文件和子目录的名称。UNIX文件系统中的每个对象还由称为索引节点(inode)号的数字和唯一生成号来标识。(因为许多UNIX文件系统保留对象表，并且索引节点是此表的索引，唯一生成号用于检测对文件的引用是否是由表槽(tableslot)描述的当前文件。)因此，目录针对此目录中包含的每个对象保留名称/索引节点/唯一三元组的列表。但是，在其中客户端缓存目录内容的所有这些情况中(在分布式系统中)，如果同一客户端机器上的用户任务进行更新(例如将名称插入目录中以创建文件)，则客户端将使缓存的目录内容无效。这将导致缓存的数据丢失，并且指向目录的未来读取请求必须将消息发送到服务器以在客户端上重新建立缓存的目录内容。

现有技术的分布式文件系统的一些实例包括以下内容：

服务器消息块/通用网际文件系统(SMB/CIFS)-此分布式文件系统不缓存目录内容，并且所有目录读取都被发送到服务器。因此，此协议的效率远低于在客户端机器上保留缓存的目录数据的协议。

分布式文件服务/分布式计算环境(DFS/DCE)-此分布式文件系统使用令牌管理方案以允许客户端缓存目录内容。但是，只要客户端机器上的任务试图更新目录内容(例如在目录中创建文件)，DFS/DCE客户端就将目录内容抛出存储器。这意味着未来的readdir()(读取目录)操作需要调用服务器。

DFS/DCE客户端确实具有目录的名称到索引节点查找高速缓存。基本上对于每个目录，客户端保留名称到索引节点对的散列表，这允许在lookup()操作期间确定索引节点号。此散列表还跟踪否定搜索；因此，它还会记住特定名称是否存在于目录中。当DFS/DCE客户端从其高速缓存删除包含目录内容的缓冲区时，此方案仍导致将不必要的消息发送到服务器。

最常用的文件系统函数之一是此lookup()操作，它用于确定特定文件名称是否存在于目录中，并且如果文件名称存在于目录中，则提供表示子对象(通常称为虚拟节点(vnode))的数据结构的地址。通常，当创建文件时，首先进行查找以确定名称是否存在(并且通常名称不存在，因为用户正在试图使用给定名称创建新文件)，然后如果名称不存在，则做出创建调用以创建新文件。

当客户端机器上的用户请求对目录的更新时，分布式文件系统客户端通常将取消缓存目录页的内容。这将由于下一查找或读取目录操作产生的高速缓存未命中而导致服务器业务增加。更具体地说，假设对目录的任何更新(例如创建调用)将使目录内容无效，如果用户正在试图创建多个文件，则在第一个创建之后发生的任何查找都必须被发送到服务器，因为目录缓冲区不再在高速缓存中，并且名称查找高速缓存(仍)没有新名称的表项。因此，假设任何更新请求立即使客户端的缓存的目录缓冲区无效，针对不在查找高速缓存中的名称的任何未来readdir()和lookup()请求都需要调用服务器。如果用户一次删除或创建许多文件，则这可能使对服务器的调用的数量不止增加一倍：一个调用用于创建或删除，一个调用用于中间查找。

网络文件系统(NFS)版本4客户端的行为非常类似于DFS/DCE，只是它不缓存否定查找，因此在这方面它略微不如DFS/DCE那么高级。

要总结它们在这方面的缺点，如果DFS/DCE或NFS文件系统客户端上的用户创建100个文件，则最少具有200次对服务器的调用。更具体地说，对于每个此类文件，一个调用用于前期查找以检查文件的存在性(其通常指示文件仍不存在)，此情况将发送到服务器，因为目录缓冲区被取消缓存，并且一个调用用于每个创建。

发明内容

本发明构想了针对其中同一客户端机器上的一个或多个任务更新目录的情况的改进；它与上述文件系统中存在的现有技术的多机器一致性方法结合使用。

提供了一种用于允许客户端在进行更新时使其目录被完全缓存的方法；此外，它允许针对同一目录将更新和读取请求并行发送到服务器以避免在到服务器的传送时等待。

本发明针对在任何更新之后由客户端机器上的本地用户更新的目录保持目录内容缓存。这确保了任何未来readdir()或lookup()请求通常能够在无需服务器调用的情况下进行处理。

一种允许保持目录的解决方案是锁定客户端处的目录，并将更新请求发送到服务器，然后使用更改更新缓存的内容并解除锁定目录。但是，这将导致客户端仅能够针对特定目录每次最多将一个消息发送到服务器。因此，如果并行任务正在写入客户端处的目录，则它们将通过网络通信被串行化。这将是不可接受的，因为不仅需要保持缓存的目录，而且还需要可以将对此目录的读取和更新操作并行发送到服务器以减少目录操作的响应时间。

本发明通过将目录的服务器副本与更新版本(由更新计数器维护)关联并针对客户端机器上的缓存的目录版本使用更改日志队列，允许并行读取和更新操作以确保按照在服务器上处理目录更新的顺序将目录更新应用于存储器中的客户端缓冲区。此外，本发明针对缓存的目录版本使用计数器和标志以跟踪读取器和更新器。因此，本发明允许针对特定目录将消息并行发送到服务器，并且还保持客户端缓存的目录内容。它还提供了串行化机制以确保保持POSIX语义。

使用上面创建100个文件的实例，借助本发明，将至多100个消息发送到服务器，每个文件创建一个消息。不需要将目录查找或读取消息发送到服务器，因为在客户端处保持目录高速缓存。在此特定实例中，这将导致服务器消息业务至少减少50％。

因此，本发明减少了当处理客户端机器上的目录时发送到服务器的消息，从而导致响应时间更短并且网络资源使用减少。此外，本发明允许保持缓存，同时不在服务器通信时持有目录的任何锁，因此允许针对同一目录将消息并行传送到服务器。

本发明的方法和装置优选地使用一个或多个硬件机器结合在这些机器上运行的计算机软件实施。此类实现的软件部分包含计算机可读程序形式的逻辑，所述计算机可读程序用于导致计算机(即硬件机器)执行本发明的方法步骤。所述计算机可读程序可以体现为有形计算机可用介质上存储的计算机程序产品，所述有形计算机可用介质包括一个或多个使用半导体、磁、光或其他存储技术的卷。

附图说明

图1示出了其中可以使用本发明的客户端-服务器系统；

图2示出了典型的文件系统目录结构；

图3示出了在更新请求时从服务器返回到客户端的目录更改日志的实例；

图4示出了当代表客户端更新目录时文件系统服务器的逻辑；

图5示出了在文件系统客户端处维护的目录更改日志/缓冲区队列的实例；

图6示出了客户端在执行目录更新请求时使用的逻辑；

图7示出了客户端在执行目录lookup()请求时使用的逻辑；

图8示出了客户端在执行目录readdir()请求时使用的逻辑；

图9示出了在可直接访问盘的分布式文件系统的更新请求时从服务器返回到客户端的目录更改日志的实例；

图10示出了具有直接盘读取能力的客户端机器使用的lookup()逻辑；

图11示出了具有直接盘读取能力的客户端机器使用的readdir()逻辑；以及

图12示出了与可扩展散列格式目录一起使用的多个更改日志队列的实例。

具体实施方式

图1示出了其中可以使用本发明的客户端-服务器系统100。系统100包含通过网络互连106耦合到服务器104的一个或多个客户端102。

如针对图1中的上面客户端102所示，每个客户端可以是包含至少一个中央处理单元(CPU)108、主存储器110以及非易失性盘存储装置112的个人计算机(PC)工作站。一个或多个程序从存储装置112加载到主存储器110并在CPU 108上执行，所述程序包括操作系统(OS)114、文件系统116(在下面更详细地描述)，以及一个或多个使用由操作系统114和文件系统116提供的服务的用户程序118。本发明并不限于任何特定的客户端体系结构。但是，示意性客户端102可以包含Intel体系结构处理器108，例如运行基于UNIX的操作系统114(例如Linux操作系统)的IntelPentium处理器。

服务器104可以包括独立于其他服务器的物理机器、逻辑分区机器的单独逻辑分区，或在基础物理机器的虚拟化层上运行的来宾机器。采用类似于客户端102的方式，服务器104包含至少一个CPU 120、主存储器122以及非易失性盘存储装置124。一个或多个程序从存储装置124加载到主存储器122并在CPU 120上执行，所述程序包括操作系统(OS)126和文件系统128(在下面更详细地描述)。正如本发明并不限于任何特定的客户端体系结构那样，它也并不限于任何特定的服务器体系结构。但是，示意性服务器104包括具有在z/Architecture处理器上运行的IBM z/OS操作系统版本的IBM System z服务器。文件系统128优选地包括IBM z/OSzSeries文件系统(zFS)。除了与本发明相关的各方面之外，zFS在IBM出版物“z/OS Distributed File Service zSeries File System z/OS V1R7Implementation”(SG24-6580-02，2006年1月，在此引入作为参考)中更全面地描述。

现在转到本发明的操作，允许从远程客户端102并行读取和写入目录的主要问题是客户端必须知道在服务器104上处理操作的顺序。zFS当前使用平面目录方案，其中目录只是一组8K(8192字节)页面，每个页面包含此目录中包含的文件或子目录的一个或多个名称。因此，参考图2，服务器102维护包括一组页面204的文件系统目录202，而同样地，客户端104维护组成服务器目录的缓存的版本并包括一组类似页面208的文件系统目录206。

每个页面包含一个散列表以在页面内快速查找名称。注意，更新并不是相互独立的。例如，删除文件将释放目录页面中用于名称的空间，以便随后创建文件可以针对新名称重用同一目录页面中的空间。因此，对目录进行更新的顺序很重要并被传送到客户端102，以便客户端知道如何保持其缓冲区与服务器104同步并正确地应用更新。

为了便于此操作，使用存储在目录的索引节点的状态部分中的数据版本。索引节点的状态部分保存有关文件或目录的信息，例如POSIX属性mtime(修改时间)、ctime(更改时间)、文件大小等。每次对目录进行更新时，将递增数据版本。注意，按照POSIX规则，对目录的每次更新都需要更新mtime和ctime。因此，任何目录更新已经需要更新目录的状态，所以除mtime和ctime以外更新数据版本将导致非常小的开销。重要的是指出，此数据版本存储在目录的盘索引节点中；它没有缓存在服务器104处的存储器中，因为目录的结构可能在客户端调用之间被取消缓存，从而丢失最新数据版本。

此外，服务器104保存它对目录缓冲区进行的更改的日志，并对更新请求进行回复时将此日志发送回客户端102。客户端102使用此日志将更改应用于其缓存的目录缓冲区，因此保持其缓冲区与服务器104同步。

最后，服务器104在每次回复客户端102做出的目录更新或读取请求时始终返回目录的状态，因此客户端可以始终检查进行读取请求时返回的目录页面的数据版本。更改日志是描述对目录进行的更改的记录序列。记录可以指定删除目录页面、将目录页面添加到目录，或者它可以指定现有目录页面的偏移以及要存储在页面中的该位置的新字节。每个回复分组都具有一个标头，其指示更改日志中具有多少个记录以及更改日志的开头的回复分组中的偏移。

图3示出了目录更改日志。

参考图3，左侧的长方形示出了样例回复分组302。用于服务器调用的每个回复分组302都具有一个公共标头304。标头304的count字段指示目录更改日志中具有多少个记录，offset字段指示分组中更改日志306的开头的偏移(以字节为单位)。更改日志306是一组可变长度的记录308。

图3的右侧示出了采用C编程语言的更改日志记录308的样例实施例。len字段是记录308的长度(必需，因为记录的长度可变)，page字段是受更新影响的逻辑目录页面编号。更改可以是添加新的目录页面或删除目录页面。如果记录308指定要进行更新，则offset和dlen字段指定从指定目录页面的开头的偏移(以字节为单位)以及要在此偏移处更改的字节长度。如果记录308是DELPAGE(删除页面)或NEWPAGE(新页面)类型，则data字段包含零个字节；如果记录308是UPDPAGE(更新页面)类型，则包含要在指定偏移处存储在页面中的dlen个字节的新数据。在UPDPAGE的情况下，data包括要存储在页面中的此位置处的实际字节。

应注意的是，替代指定要更改的页面中的确切字节，或除了指定要更改的页面中的确切字节以外，可以使用更改的逻辑描述(例如将名称添加到页面X)。客户端102将采用逻辑描述，并应用服务器104更新页面所应用的相同算法，保证客户端的目录页面版本与服务器的目录页面版本匹配。在此描述的本发明的特定实现使用两种方法的混合。

图4示出了用于文件系统服务器目录更新的逻辑。

服务器104首先获取存储装置以保存更改日志(步骤401)。注意，任何目录操作通常都导致简单的名称添加或删除，例外是重命名操作，它可能导致两个目录(源和目标目录)的添加/删除/更新；因此更改日志不需要非常大，即使对于最大的可能目录更新也是如此。服务器104首先获取目录的写入锁(步骤402)，然后才更新目录(步骤403)。目录如文件系统通常所执行的那样被更新，只是任何更改还被记录在输出更改日志中。服务器104然后递增数据版本(步骤404)，并将递增后的版本连同更新后的mtime和ctime一起存储在目录索引节点的状态部分中。注意，在随后的某些时间，索引节点内容被写入盘。服务器104然后解除锁定目录(步骤406)，并在发送回客户端102的回复分组302(图3)的更改日志字段306中包括更改日志(步骤407)。

客户端102将更新请求并行发送到服务器104(无需在传送时持有锁并等待回复)。客户端102可将更新U1和U2发送到服务器104，但服务器104可能在U1之前处理U2。此外，客户端102可不按顺序接收回复。虽然服务器104在请求U1之前处理更新请求U2，但是客户端102实际上可在看到U2的回复之前看到U1的回复。客户端102需要按顺序应用目录更新，因此它使用队列，同时使用锁来保护队列，并记住应用于存储器内的目录缓冲区的最新版本。如果在先前更新的回复之前接收到后续更新的回复，则其被排队。

客户端102将目录页面保存在存储器中(或者客户端102可将其存储在本地盘驱动器上)。由于高速缓存空间有限，因此许多客户端102(包括zFS客户端)在高速缓存已满并需要缓存新页面时使用最近最少使用(LRU)方案。因此，任何给定目录可能在高速缓存中具有其全部、部分页面或没有任何页面。在POSIX文件系统中具有两种类型的读取目录的调用：lookup()和readdir()。lookup()操作用于在目录中搜索给定名称并返回文件的索引节点/唯一标识符(“uniquifier”)对。readdir()操作用于获取目录中包含的部分或全部名称的名称/索引节点/唯一标识符三元组的列表。因此，如果没有缓存对应的目录页面(多个)，则目录读取操作可能需要调用服务器104；在这种情况下，希望使服务器104在回复分组中将页面内容返回到客户端102，并且客户端然后可将此页面保存在其高速缓存中并避免未来调用服务器104。还希望尽可能使执行目录读取操作的任务不等待此目录的任何正在进行的更新。因此，希望在向服务器104发出目录更新请求的同时，尽可能将目录读取请求并行发送到服务器104。由于此原因，对于任何目录读取请求，服务器104始终在服务器104处进行读取时发送目录的数据版本。客户端102可以使用此信息知道缓存它在来自服务器104的回复中接收的目录缓冲区是否安全。

进行目录读取而将目录缓冲区从服务器104返回到客户端时，客户端102要考虑三种可能的情况。

第一，读取请求的回复分组302中的数据版本可与更改日志队列中的最新应用的版本匹配。这是很容易的情况；目录页面可安全地缓存在客户端存储器高速缓存中。

第二，回复分组302中的数据版本可小于更改日志队列中的最新应用的版本；在这种情况下，缓冲区不能被缓存，因为缓存的目录版本晚于获取缓冲区的时间。这应很少见，因为通常按照服务器104处理请求的顺序接收回复，但是当然需要逻辑来处理不按顺序时的情况。

第三，回复分组中的数据版本可大于更改日志队列中的最新应用的版本。在这种情况下，目录缓冲区本身可被排队在更改日志队列中的适当位置并在先前更新回复到达并处理更改日志队列时被缓存。

这样，保存在客户端的高速缓存中的目录页面始终处于某个一致的版本。例如，某个目录在版本X没有第0页，同一目录在版本Y没有第1页。

图5示出了特定目录的客户端更改日志队列500。更改日志队列包含标头(CLQUEUE)502以及一个或多个表项(CLENTRY)504。标头502包含以下与本发明相关的字段。

lastAppliedVersion字段指示对应目录的缓存页面的当前版本。在优选实施例中，此结构可包含在表示文件系统对象zFS虚拟节点的结构中。

cacheLock字段用于串行化到队列500的更新以及与本发明范围之外的目录操作相关的其他处理(例如缓存安全性信息和进行安全性检查)。在到服务器104的传送时从不持有此锁。

queuedLogs字段锚定一系列队列表项(CLENTRY)504，这些表项是排队的更改日志或目录缓冲区。

readers字段和updaters字段用于串行化其中多页面readdir()请求因关联的目录页面不在高速缓存中而必须调用服务器104的情况。由于readdir()请求在大多数客户工作负载中非常少见(与通常是最常见的操作的lookup()相比)，因此遇到高速缓存未命中或确定存在排队的更改日志的readdir()请求将简单地等待从服务器104返回正在进行的更新回复。然后它将阻止发生未来更新(通过递增读取器计数)，直到它可以获取缺失的目录页面的一致快照为止。

countsLock字段用于串行化对计数的更新，前提是仅在读取模式中持有主cacheLock，其是针对lookup()和readdir()的情况，因为只要它们在目录高速缓存中，它们通常只是读取缓冲区。rdWaiters和updWaiters字段用于串行化当具有高速缓存未命中的readdir()操作等待正在进行的更新时的情况。这些字段用于休眠和唤醒操作，这些操作在本质上等同于POSIX pthread mutex和条件变量锁定机制。

更改日志队列表项(CLENTRY)504描述目录更新的排队更改日志或数据版本大于缓存的目录缓冲区的当前版本的排队目录缓冲区。每个队列表项504包含以下字段：

dataVersionNumber是服务器104在对应的更新或读取调用时返回的数据版本。表项按排序后的顺序保存，具有相同版本的更改日志在缓存的目录缓冲区之前。

next字段仅是指向队列500中的下一个表项504的指针。

type字段指示表项是表示排队的更改日志506(类型＝CL)还是目录缓冲区508(类型＝BF)。如果表项类型是CL，则dlen和numents指示更改日志506的长度以及更改日志中的记录数。如果表项类型是BF，则dlen被设置为目录页面的大小(对于zFS为8K)，numents未定义。在图5所示的实例中，队列500中的第一和第三个表项504用于更改日志506，而第二个表项504用于目录页面508。

clptr指向对应的更改日志506(类型＝CL)或目录缓冲区508(类型＝BF)。

descriptor是更改的逻辑描述，例如描述更改日志表示什么的“创建文件，名称＝xxxx，索引节点＝y，唯一标识符＝z”。这由lookup()用于确保它提供正确的POSIX语义，并且其使用在下面更详细地描述。

图6示出了当任务在客户端机器102上执行目录更新操作(例如文件创建、重命名文件、创建子目录)时，客户端侧文件系统执行的步骤。图6的流程图仅示出了目录更新操作中与本发明相关的逻辑。

在步骤601，在写入模式中获取高速缓存锁(cacheLock)。然后在步骤602进行检查以查看是否具有readdir()等待器(rdWaiters＞0)或正在进行的服务器目录readdir()操作(readers＞0)。如果是，则设置updWaiters(步骤603)并且任务自动释放高速缓存锁并休眠(步骤604)。在这种情况下，readdir()具有正在进行的高速缓存未命中，使readdir()完成以便它具有目录缓冲区的一致快照。注意，由于readdir()远比lookup()少见，并且由于本发明的系统在可能时保持缓存目录缓冲区，因此对于大多数工作负载，readdir()应很少具有高速缓存未命中。(例外是当多个系统更新同一目录时，但这是具有或没有本发明都可以发生的现象。)如果没有正在进行的readdir()操作，则递增updaters字段(步骤605)并释放高速缓存锁(步骤606)。此处的主要概念是在到服务器104的传送时不持有高速缓存锁。这允许将对此同一目录的其他更新或lookup()操作立即传送到服务器104；任何锁都不会阻止传送，从而允许并行。

在从服务器104接收到回复(步骤607)之后，在写入模式中重新获取高速缓存锁(步骤608)。如果操作成功，则将在回复分组中返回的data Version与CLQUEUE中的lastAppliedVersion相比较(步骤609)。如果dataVersion等于lastAppliedVersion+1，则可以将此更改日志立即应用于目录高速缓存缓冲区(步骤610)。应用更改日志意味着处理日志中的每个记录，并按照每个记录的指示创建、删除或更新页面。注意，某些页面可能不存在于高速缓存中，因此不进行更新(必须在进行未来lookup()或readdir()时从服务器104取回所述页面)。如果dataVersion不等于lastAppliedVersion+1，则其在更改日志队列中按顺序排队(步骤617)，递减updaters(步骤618)，并释放高速缓存锁(步骤619)，因为操作已完成(因为它与本发明相关)。

在步骤610之后(在应用更改日志之后)继续，递增iastAppliedVersion(步骤611)。一旦应用此更改日志，就进行检查以判定是否已准备好处理队列中的下一个更改日志(步骤612)。如果CLENTRY描述排队的更改日志(类型＝CL)并且dataVersion等于lastAppliedVersion+1，或者CLENTRY描述目录页面(类型＝BF)的未决缓存并且data Version等于lastAppliedVersion，则准备好处理。如果准备好处理(步骤613)，则从队列移除CLENTRY，处理更改日志(类型＝CL)，或在目录页面的高速缓存中缓存缓冲区(类型＝BF)。在CLENTRY中将lastAppliedVersion设置为dataVersion。重复此操作，直到不再有CLENTRY满足处理准则。一旦不再有可供处理的CLENTRY，就递减updaters字段(步骤614)，并进行检查以查看是否具有readdir()等待器以及这是否是目录的最新更新器(步骤615)。如果为真(步骤616)，则唤醒readdir()等待器。最后，释放cacheLock。

图7示出了客户端机器102针对目录查找操作使用的逻辑。lookup()函数采用名称作为输入；如果名称存在于目录中，则它返回表示子文件或子目录的数据结构，如果名称不存在，则返回POSIX返回代码ENOENT。图7的算法示出了与本发明相关的部分(目录搜索和缓存)。

在读取模式中获取高速缓存锁(cacheLock)以允许并行任务对目录缓冲区执行查找(步骤701)。如果具有排队的更改日志506(步骤702)，则检查更改日志队列500以确定是否具有带有描述符(指示添加或删除与输入名称匹配的名称)的队列表项(CLENTRY)504(步骤703)。这很重要；例如，如果用户创建新文件并随后查找该文件，但被告知文件不存在，则用户将感到困惑。更改日志队列500中的任何表项504都表示目录中的某个对象的先前已完成的创建、删除或重命名，因此重要的是未来查找将检查此队列以确保正确的POSIX语义。如果找到名称(步骤704)，则释放高速缓存锁(cacheLock)(步骤706)。如果未在排队的更改日志表项中找到名称，则搜索缓存的目录缓冲区(步骤705)。如果目录高速缓存中具有缺失的页面，则它可能不知道特定名称是否存在于目录中，在这种情况下，必须调用服务器104。

步骤707进行检查以查看更改日志或目录缓冲区是否针对名称是否存在于目录中而提供明确的回答。如果高速缓存提供明确的回答，则与本发明相关的处理结束。如果目录高速缓存中具有缺失的页面，并且无法提供回答，则设置lookup()消息的格式并将其发送到服务器104(步骤708)。在本发明的优选实施例中，向服务器104发出的lookup()请求将要求服务器104发送包含名称(如果名称存在于目录中)的页面或目录的缺失页面，以使客户端102可以通过填充目录的缺失页面优化服务器104处的名称查找。本领域的技术人员可以在此基础上扩展以返回更多或更少的目录页面，或提供唯一目的是获取目录页面的单独服务器函数，但通过名称查找填充缺失页面被认为是确保在客户端机器处缓存活动目录的缺失页面的最佳方法。

一旦接收到来自服务器104的回复，则在写入模式中获取cacheLock(步骤709)以允许搜索/修改更改日志队列并缓存在服务器回复中传递的任何目录页面。如果服务器104没有提供任何目录缓冲区(步骤710)，则释放cacheLock并且与本发明相关的处理结束。如果服务器104提供了一个或多个目录页面，则将CLQUEUE中的lastAppliedVersion与服务器104在回复分组中指定的数据版本相比较(步骤711)。如果版本相同，则简单地将目录页面缓存在客户端机器高速缓存中(步骤712)。如果服务器回复分组数据版本大于lastAppliedVersion(步骤713)，则将缓冲区添加到更改日志队列(步骤715)。如果服务器回复分组数据版本小于lastAppliedVersion，则无法缓存目录页面。最后，释放cacheLock(步骤714)。

图8示出了用于readdir()函数的与本发明相关的逻辑。readdir()操作被设计为将偏移带入目录(起始点，其可以是目录的开头或目录中的某一其他点)和用户缓冲区内，并使用名称填充用户的缓冲区，直到缓冲区已满或到达目录的结尾。

readdir()操作首先在读取模式中锁定cacheLock(步骤801)。注意，最常见的情况(尤其是因为本发明用于试图尽可能保持缓存目录页面)是相关目录页面将在存储器中，并且可简单地从高速缓存满足操作。因此，需要读取锁，因为它允许同时对目录进行并行查找和读取目录。如果可从高速缓存满足操作(步骤802和803)，这意味着数据位于高速缓存中并且没有排队的更改日志(因为已向用户返回成功的目录更新操作并且这些更改尚未在目录缓冲区中)，则以本地操作系统可识别的格式将来自缓存的目录页面的数据(名称/索引节点/唯一标识符)复制到用户的缓冲区。然后将释放锁(步骤804)并且操作完成。

如果高速缓存中缺失目录数据，则进行检查以判定updaters是否大于0(步骤805)。如果是，这意味着具有正在进行的目录更新，并且由于在将名称复制到用户的缓冲区时需要目录的一致快照，因此设置rdWaiters标志(步骤806)，并且自动释放锁并休眠(步骤807)，等待正在进行的更新完成。这仅是使任务等待针对同一目录的先前传送的情况，并且它实际上应是很少见的情况。一旦唤醒，将重新获取锁(步骤808)，并且处理从其停止处继续。注意，由于任务休眠(可能是现在缓存目录缓冲区的情况)，因此对算法进行的细微但不严格必需的改进是重新检查目录高速缓存以判定现在是否缓存了所需页面。

如果没有正在进行的目录更新，则递增readers(步骤809)。这通过在写入模式中获取countsLock，递增计数，然后释放countsLock以确保安全地更新计数来完成。这是必需的，因为仅在读取模式中持有cacheLock。然后释放cacheLock(步骤810)并将指示客户端102在其高速缓存中缺失哪个页面的readdir()请求分组发送到服务器104(步骤811)。一旦从服务器104接收到回复，将在写入模式中获取cacheLock(步骤812)以便可以缓存返回的页面数据(步骤813)。注意，如果用户任务提供大型缓冲区，则它们可能需要访问许多目录页面，因此提供循环以允许将尽可能多的名称存储在输出调用方缓冲区中(步骤814)。一旦使用名称填充用户的缓冲区，就递减readers计数(步骤815)，并且进行检查以判定readers计数是否为0以及是否具有任何正在等待的对目录的更新请求(步骤816)。如果为真，则清除updWaiters位并且唤醒所有等待的更新任务(步骤817)。最后，释放cacheLock(步骤818)。

因此，当客户端102机器上的一个或多个用户任务更新目录时，上述发明在客户端102上保持缓存的目录缓冲区的同时提供了正确的POSIX语义。此外，在传送更新请求或目录读取请求时几乎从不持有目录的锁，从而允许针对同一目录将多个请求从客户端102并行发送到服务器104。上述发明以最小的额外开销提供所有这些操作。当用户在客户端机器上更新目录时，性能增益非同寻常。如果目录很大，这尤其重要，因为取消缓存目录需要通过未来lookup()和readdir()请求从服务器104读取此目录。

将本发明应用于更复杂的目录组织和分布式文件系统环境

本发明的上述实现应用于被组织为名称的平面文件的目录。目录基本上是一个或多个页面，其中每个页面包含目录中的子文件的零个或多个名称。如果目录很大，则此类型的组织可以导致延缓查找时间，因为必须检查每个页面直到找到名称或到达目录结尾为止。本发明本身并不限于此简单方案；将通过以下实例阐述此事实。

B+树

B+树在本领域中是公知的，它基本上是平衡的分类树，其中树的叶节点包含指向树中的实际数据元素的指针。所述树允许快速搜索名称，因为树中的索引保持平衡并且查找时间是树中数据元素数的对数函数。许多文件系统都使用B+树，并且典型的组织是将名称保存在平面文件(其可以是稀疏的)中，并将目录的索引页面保存在单独的文件中。基本上，目录的索引节点的状态部分指向另一个维护目录的索引页面的索引节点。树中的每个节点刚好占用一个盘块。每个节点具有从N到2N的可变数量的指针和键值，其中N是基于盘块大小的某一预定数量。对于内部节点，指针将指向树中较低级别的节点，键将是对应指针所引用的子树中的最大值。对于叶节点，指针将指向对应页面以及对应表项的这些页面中的偏移。

实质上，每当试图将新项目添加到叶节点(其中叶节点已包含2N个使用中的项目)时，必须拆分叶节点，这可能导致进一步拆分树以保持树平衡。相反，如果从叶节点中删除项目导致使用中的项目数低于N个项目，则可合并叶节点，从而导致进一步合并树。

由于树的索引节点保存在单独索引节点中，因此可通过逻辑页面号引用索引树的节点，基本上与也通过逻辑页面号引用目录的页面相同。

将本发明应用于B+树相当简单。任何更新的更改日志不仅描述对数据页面的更改，而且还记录对关联的树的索引页面(内部节点)的更改。将添加两个新的更改日志记录：

NODE_SPLIT-用于指示应拆分节点，较低值的N个键保留在当前页面中，并且新页面包含较高的N个键。NODE_SPLIT记录指示节点

的原始页面和拆分的新页面两者。(实质上这是在索引树中创建新页面。)

NODE_MERGE-用于指示节点合并，它指示将合并为一个页面的两个原始页面。(实质上这是从索引树删除页面。)

更改日志的应用和更改日志的排队类似于图6中提供的算法。

lookup()例程不仅请求服务器104返回包含名称的缺失数据页面，而且还可能返回一个或多个内部索引节点，以便客户端102可以“填充”树的缺失部分。这些页面的缓存将遵循图7中所述的相同算法。

客户端102可能需要知道目录的数据页面中的空页面。一种方法是使用初始设置为1的位掩码，并且当客户端102确定页面不存在(通过调用服务器104)时，它可以清除与页面编号对应的关联位。在readdir()请求时，如果客户端102试图读取未分配给目录的页面，则服务器104可在回复中指示此情况并返回下一个分配的页面，以避免客户端102在未来读取未分配的页面。

因此，本领域的技术人员可以将本发明应用于存储为B+树的目录。

直接盘访问

基本的分布式文件系统是其中具有一个或多个服务器以及一个或多个客户端102的文件系统，其中客户端不能直接访问存储文件系统内容的盘驱动器。上述的NFS版本4、DFS/DCF以及zFS产品就是如此。但是，存在某些分布式文件系统，其中客户端102可具有直接读取或写入包含文件系统数据的盘驱动器的能力。在许多此类情况下，仍存在用于诸如本文中所述的目录之类的特定文件系统对象的服务器104。但是，客户端系统可直接从盘读取目录内容。因此，zFS可被增强为在客户端机器具有直接盘访问的环境中运行。

在这种情况下，客户端机器将直接从盘读取目录内容，但首先要确保它可以从服务器104处获取正确的分布式串行化(通常通过分布式锁定机制或令牌方案实现)。一旦从服务器104处获得保证，客户端机器便可以直接从盘读取和缓存目录内容。如果必须更新目录，则客户端机器将更新请求发送到服务器104并将设置更新位以指示已对服务器104进行更新。如果已对服务器104进行更新，并且发现特定的目录页面不在高速缓存中，它将“同步”请求发送到服务器104以便将目录内容写入和同步到盘，从而可以直接从盘读取目录内容。这样便无需使用发送到服务器的readdir()和lookup()请求来读取目录页面，现在可以直接从盘读取页面。这可以减少发送到服务器的分组数，并显著减少在通信信道上传送的字节数，因为目录页面内容不再经过线路。

但是，由于目录更新通常与对同一目录的查找请求混杂，因此对于目录页面而言，在客户端102将目录更新请求发送到服务器104之后保持缓存是非常重要的。在不保持目录高速缓存的情况下，如本发明所述，每次更新目录时；都会取消缓存目录页面。这意味着客户端机器上的未来查找或readdir()请求可能需要将“同步”请求发送到服务器104以便写入和同步目录内容，从而使客户端102随后可以从盘重新读取目录内容。这将针对服务器104和客户端102产生额外的服务器消息(用于同步)以及额外的盘IO。

因此，对于其中将目录更新发送到服务器并在客户端机器处缓存目录内容的任何分布式文件系统而言，在服务器104后完成更新之后使用本发明更新缓存的客户端目录缓冲区对于良好的性能非常重要。

在大多数文件系统中，任何给定对象(例如目录)在概念上都是逻辑块阵列，所述逻辑块编号为0、1、2...一直到N-1。这些逻辑块通过被锚定在对象的索引节点中的间接块树而被映射到它们在盘上的物理位置。例如，zFS列出目录的索引节点中前8个逻辑块的位置，并且它具有3个用于定位高于8的块的间接块树。例如，存在一个间接1级树，它具有作为一个大型阵列的块，所述阵列直接定位编号8到2047的块。对于高于2047的块，使用2级树，该树的顶级块具有指向低级间接块的阵列，所述低级间接块又指向对象的对应逻辑页面的实际位置。因此，2级树用于定位编号从2048到4,163,647的块的物理位置。编号高于4,163,647的块使用3级树，以此类推。因此，逻辑块的位置和存在通过读取定位该逻辑块的间接块树部分来确定。

对于执行直接盘读取的客户端102，需要从盘读取和缓存间接块以定位目录页面的物理位置，以便可以直接从盘读取这些页面。因此，对本发明所用的更改日志方案的增强也是提供在创建或删除目录页面时对间接块进行更新的指示。

最后，存在许多文件系统，zFS是其中之一，其中可以产生文件系统的一个或多个快照。在这种情况下，对象(例如目录)的只读备份副本包含在快照时的指向目录的指针，并且目录的可写版本变为写时复制(COW)。COW对象意味着对对象的特定页面或对象的间接块的任何第一次更新都必须分配新的块以包含所述页面或间接块的内容，将原始内容从该页面的备份复制到新分配的块，然后更新该新的块。这确保了备份版本保持备份时的原状。zFS用于指示页面或间接块是COW的惯例是设置索引节点或间接块中的页面指针内的高阶位。

针对直接盘访问情况的对本发明的增强如下所示(同时参考图9)：

1.更改日志记录中具有更多的详细信息以显示在分配新页面或从目录删除页面时所需的间接块更新。它还提供了所有指定页面的逻辑页面及物理页面。这非常有用，因为客户端102从盘读取直接物理页面并且通常通过盘上的物理块编号(而非目录中的相对页面)来引用页面。

2.新的名为COWPAGE的更改日志记录，它指示从写时复制页面分配新页面，以便客户端机器可以执行从旧页面到新页面的复制。

3.将updates位添加到CLQUEUE结构以指示自上一同步操作之后，或自客户端102首次在目录上建立分布式锁之后，已将更新发送到服务器104。

4.更新后的readdir()和lookup()例程以处理从盘的直接读取，如图9中所示。

5.COWPAGE-新的标志位，指示由于目录正在被写时复制，因此必须分配一个或多个新页面(图9)。

6.physPage一指示文件系统中的目录页面的物理位置(图9)。

7.ibs-将逻辑映射到目录页面的物理页面的零个或多个(对于zFS，最多为三个)间接块的物理位置。

8.cowPage-目录页面的原始物理页面编号，在原始页面被写时复制的情况下指示新分配页面的源页面(图9)。

9.Indexes-指向下级间接块或物理页面位置的槽的ibs中列出的对应(一对一)间接块的索引。

10.cowIbs-在进行更新时被写时复制的间接块的原始物理页面编号。

更新请求遵循与图6中示出的更新逻辑几乎完全相同的算法。具体地说，步骤5(图6中的605)将更改为除了递增updaters字段以外，还设置CLQUEUE中的updates位。应用更改日志的步骤10和13(图6中的610和613)也更改为更新间接块以及处理写时复制情况。具体地说，如果存在更改日志所指示的新分配的间接块(NEWPAGE、DELPAGE或COWPAGE实例)；将在高速缓存中创建这些块。如果这些间接块是其原始备份块(backing block)的写时复制版本，则从盘读取原始备份块(此操作很安全，因为备份块无法更改)并将其复制到新块。如果从备份间接块创建新的间接块，则新的间接块将被更新，以设置所有阵列槽中的高阶位，因为间接块定位的块全部为写时复制。每个间接块中的特定指针也都被更新，以指向新的数据页面或新的下级间接块。与间接块类似，将在高速缓存中创建新页面或写时复制目录页面。如果目录页面为COW，则读取备份页面并将其复制到新页面。最后，使用更改日志的dlen、offset和data字段所描述的更改来更新新的或现有的目录页面。

图10示出了用于对具有直接盘访问的客户端102进行目录查找的新逻辑。

步骤1001到1004完全遵循图7中的步骤701-704的逻辑。对于步骤1005，如果updates位被清除，则客户端102不仅可使用存储器中的其缓存的目录以及间接块页面，而且还可以安全地从盘的高速缓存读取任何缺失的块。如果updates位未被清除，则只能使用存储器中的缓冲区。因此，如果updates位未被清除，并且存在缺失页面，其将是无法从高速缓存满足查找的情况(步骤1006)。如果从更改日志或高速缓存满足查找，则简单地释放cacheLock(步骤1007)。如果否，并且updaters计数为非0(步骤1008)，则设置rdWaiters位(步骤1009)，自动释放锁并且任务一直等待，直到updaters计数为0为止(步骤1010)，然后查找过程从步骤1001重新开始。如果updaters计数为0，则将同步请求发送到服务器104以将任何脏页面(如果有)与目录的盘同步(步骤1011)。然后清除updates位并且控制返回步骤1005，现在可以保证此步骤成功，因为updates位被清除。

图11示出了具有直接盘访问的客户端102的readdir()逻辑。

readdir()代码与cacheLock的读取锁一起运行(步骤1101)。然后进行检查以查看目录缓冲区是否针对被读取的目录区域被完全缓存以及是否具有任何排队的更改日志(步骤1102a)。如果具有未缓存的目录缓冲区或具有排队的更改日志，则进行检查以查看是否具有目录更新器(步骤1102b)。如果具有目录更新器，则设置rdWaiters位(步骤1103)并且任务自动释放锁并休眠(步骤1105)。然后在唤醒任务时(当没有更多正在进行的目录更新时)，处理返回步骤1101以重新开始。如果步骤1102b的测试结果为否，则处理在步骤1104重新开始，此步骤将尽可能多的数据复制到调用方缓冲区。类似地，如果步骤1102的结果为真，则还可以安全地尝试从高速缓存读取目录页面。步骤1104将目录数据从高速缓存复制到调用方缓冲区；如果updates位被清除，则代码可以从盘读取目录页面，如果未被清除，则需要同步请求。(作为一种可能的优化，为了减少发送到服务器的同步调用数，可以跟踪最近更新的目录页面和间接块。如果未读取更新后的块，则可以直接读取它；如果正在读取更新后的块，则将同步请求发送到服务器)。如果步骤1104发现需要从盘读取数据并且updates位为启用(步骤1106)，则将同步请求发送到服务器104(步骤1108)以同步目录的数据并清除updates位(步骤1109)。处理将再次在步骤1104重新开始，此步骤保证成功，因为updates位被清除。一旦将目录数据复制到调用方缓冲区，就释放cacheLock(步骤1107)。

上述算法示出了本发明可应用于客户端102具有直接盘访问的情况。这降低了任何后续查找或readdir()操作需要服务器同步以同步目录数据的可能性或减少了从盘读取目录页面的需求。因此，服务器通信、服务器同步盘IO以及客户端盘IO减少，并且如果用户在客户端机器上对目录进行大量更改，则这种减少可非常显著。此外，仍可将更新请求并行发送到服务器104，并且如果所需的目录缓冲区未进行缓存(由于发明本身的原因，很少出现这种情况)，则readdir()和查找请求仅需要等待正在进行的更新。

可扩展散列

在此结合作为参考的美国专利5,893,086中介绍了使用可扩展散列算法作为存储文件系统目录数据的方法。如Schmuck等人的标题为“GPFS：A Shared-Disk File System for Large Computing Cluster”(USENIX协会，FAST 2002 Conference on File and Storage Technologies会议纪要，2002年1月，在此引入作为参考)的论文所述：

对于占用多个盘块的目录，可以通过将散列函数应用于特定名称以及使用散列值的n个低阶位作为块编号来查找包含该名称的目录表项的块，其中n取决于目录大小。

随着目录的增大，可扩展散列一次添加一个新目录块。当创建操作发现由新名称的散列值指定的目录块中没有更多空间时，会将此块一分为二。新目录块的逻辑块编号从旧的块编号中导出，方法是在第n+1位的位置添加‘1’，并且其散列值的第n+1位中具有‘1’的目录表项被移动到新的块。其他目录块保持不变。因此，大型目录通常被表示为稀疏文件，且文件中的空缺表示尚未被拆分的目录块。通过检查目录文件中的稀疏区域，文件系统可确定拆分目录块的频率，以及因此使用散列值的多少个位来定位包含给定名称的目录块。因此，查找始终需要具有单个目录块的访问权限，与目录文件的大小和结构无关。

更具体地说，如果具有相同散列值的多个名称(至多使用该值的M个低阶位)填入目录页面，则对可以在散列值中使用的位数M具有限制，溢出块将被链接到该页面以包含附加名称。所以在极少发生的情况中，查找将访问多个块。在逻辑块2^M和更高处分配溢出页面。因此，可以使用目录大小估计要使用多少散列值位。所以，如果确定使用n个散列值位，则对名称执行散列，使用n个低阶位并检查逻辑页面编号。如果该页面不存在，则使用n-1个低阶位定位逻辑页面编号，如果该页面不存在，则使用n-2个低阶位定位逻辑页面编号，以此类推，直到找到应包含该名称的页面。如果找到该页面，则从中搜索名称。如果该页面具有与其链接的溢出块，则也搜索这些溢出块。

由于添加或删除名称通常不需要使用可扩展散列拆分或合并逻辑页面，因此，可允许目录更新的并行性。更具体地说，文件系统目录的服务器机器可以在进行更新时使用多级锁定方案：目录本身上将具有主锁，当读取目录或对目录进行仅影响一个目录页面的更新时，将在读取模式中锁定该锁；如果进行拆分或合并散列表目(hash bucket)(目录页面)或将溢出页面链接到散列表目的更新，将在写入模式中获取该锁。每个目录页面也可具有与其关联的锁，将在读取时在读取模式中获取该锁，并在写入时在写入模式中获取该锁。这允许在更改不改变目录的间接块的情况下执行并行更新。分配或释放目录页面的更新将在写入模式中锁定主锁，从而保证单个访问。

使用平面文件在目录中存储名称会延缓搜索时间，为了使用可扩展散列目录格式提供快速搜索时间，允许从客户端机器到服务器104的并行更新，确保客户端目录页面保持缓存，最大程度上减少查找或readdir()请求需要等待正在进行的更新的概率，可将上述发明稍作修改以处理更复杂的可扩展散列布局。

可以按照下面所述针对具有直接盘读取能力的客户端102，将本发明应用于以可扩展散列方法存储的目录：

1.索引节点中存储的数据版本仅在服务器104在写入模式中持有主锁时才更新。因此，仅当将页面添加到目录或从中删除页面时才递增版本。所以，可将其视为主版本。

2.每个目录页面将包含数据版本字段；在每次更新页面之后将更新该字段。当拆分页面时，将从初始数据版本值(等于其伙伴页面(拆分前的页面)的数据版本值)开始。

3.服务器104在回复分组的索引节点状态中返回主数据版本，如本发明的图4中所述。它将在实际更改日志记录(图3中所述)或使用某些其他便利的方法返回页面数据版本。

4.将具有新的更改日志记录，一个记录用于页面拆分，一个记录用于页面合并，这将与NEWPAGE和DELPAGE记录非常类似，但是它们也告知客户端102在拆分时将表项从旧页面移动到新页面，或在合并时将表项从正在删除的页面移动到其伙伴页面。因此，可以由单个更改日志记录简洁地表示合并或拆分。

5.客户端102保留图5中所示的主更改日志队列，同时也保留存储器中具有未决更新的所有页面的更改日志队列。因此，将缓存目录的更改日志队列，每当必须对未决更新进行排队时，将创建更改日志队列，如果页面的更改日志队列尚不存在，则对更改日志进行排队。更改日志在主队列以及由该日志更新的所有页面上排队。注意，只有主版本更新将影响多个页面。此队列当然按照主版本顺序排列。注意，当多个更改日志命中不同的页面并且必须进行排队时，它们可以具有相同的主版本(因为客户端102尚未收到先前对相应页面的更新)。图12示出了其中使用可扩展散列存储目录的客户端机器的目录更改日志队列的实例。

6.溢出页面将仍更新散列表目中的第一个页面内的次要数据版本并在客户端102处使用与更改日志队列对应的页面。

图12示出了多个更改日志队列的实例。上述实例假设目录最初从3个已定义的页面0、1和3开始。未定义页面2。因此，至多使用2个散列值位在该目录中定位页面。大量更新被并行发送到服务器104。主CLQUEUE(方块1)保存所有未决更改日志更新的列表。存在7个未决更新(从方块2到方块8)。方块1示出lastApplied主版本为6。方块6示出未决主版本更改，此更改是拆分页面3。由于更改日志已在主版本6处排队，因此必须排队主版本7的更改日志。方块9示出页面0的更改日志队列，它的lastApplied次版本为16，因此页面0的更改日志更新(方块2、5和8)必须被排队，因为尚未收到对更新页面0的次版本17的回复。页面1没有未决更改(方块10)。页面3也具有更改日志队列(方块11)；因为该页面的lastApplied次版本为31并且尚未收到服务器104对更新次版本32的回复，所以该页面也具有排队的更新。注意，拆分页面3的更改日志(方块6)将导致创建页面7(下一散列值位用于页面3中的项目，产生位串011和111)并且随后使用3个散列值位执行查找。

上述实例示出了针对可扩展散列的对更改日志的基本要求：需要在主版本更新(也被排队)之后排队的所有更改日志必须进行排队，即使尚未定义相应的页面也是如此(因为主版本更新可能导致拆分和创建新页面)。排队是为了不丢失更新并因而在高速缓存中具有不正确的数据。

所以，当页面0的主版本6、次版本17的回复到达时，可处理方块2和5的更改日志。方块8仍必须等待，直到应用主版本更改日志。当收到主版本6、次版本32的回复时，可应用剩余的更改日志，因为主版本更改将是队列中的下一更改，并且可应用所有剩余的排队更改日志，因为它们将是队列中的下一更改。注意，拆分页面3之后，对于页面7将存在更改日志和目录缓冲区，这意味着可应用方块7中指定的更新并且不会丢失更新。

使用可扩展散列的直接盘访问客户端102的更新逻辑将按照图6中的大部分流程，只是更改日志将置于多个队列中并且更改日志的主版本和次版本需要与主CLQUEUE中的主版本以及关联页面CLQUEUE中的次版本进行比较，以确定是否可立即应用日志或所述日志是否需要排队。当应用排队后的更改日志时，仅当在旧版本级别上没有任何其他次版本在主版本之前更新时，才能应用主版本更新。

使用可扩展散列的直接盘访问客户端102的readdir()和查找逻辑将分别遵循与图11和10相同的逻辑。

因此，本发明可应用于多种分布式文件系统环境。它可以有效地用于为简单和复杂目录数据组织提供显著的性能优势，并可与没有直接盘访问的客户端102以及其中客户端具有直接盘访问的专门环境一起使用。尽管示出和描述了特定的实施例，但是对于本领域的技术人员而言，各种修改将是显而易见的。