在操作系统内核环境中高速缓存应用数据的系统和方法

摘要

本发明实现了一种独立于应用的内核高速缓存。该内核高速缓存可快速有效地为应用提供常用数据。利用操作系统提供的机构，实现了用于存储内容、高速缓存对象的方法和设备。每种操作系统都具有一个或多个内核扩展可用的内核存储的专用装置。实现了一种为高速缓存对象获得存储的系统。定义了可允许多个不同数据的源的技术。通过使用多种协议，多个数据源可提供专用于应用和/或独立于应用的数据。上述高速缓存对象存储机构独立于数据源，反之亦然。定义了用于快速查找和管理高速缓存对象的技术。实现了用于将数据从数据源移动到高速缓存对象存储机构的机构。

说明书

发明领域

本发明通常涉及操作系统，且具体涉及在操作系统内核环境中高速缓存应用数据。

发明背景

高速缓存已应用于计算机科学的许多领域，它完全与字典中作出的“用于隐藏或存储事物的安全场地”的定义一致(如参见Webster’s New World Dictionary of the American，2nd collegeed.1976)。处理器可具有多种级别的高速缓存(cache)(参见Hennessy，John and David A Patterson，Computer Architecture AQuantitative Approach 2nd ed.San Francisco：Morgan Kaufmann，1996，p.375)，而一些文件系统也能具有高速缓存(参见Solomon，David and Mark Russinovich，Inside Microsoft Windows 2000 3rd ed.Redmond：Microsoft Press，2000，p.646)。诸如HTTP服务器(Fielding，R.，et al.，RFC 2068，1997，p.70，http：//www.ietf.org/rfc/rfc2068.txt)的应用(application)也可具有高速缓存。还存在有更多例子。一些应用甚至在操作系统内核中具有应用专用的高速缓存(Hu，Elbert，et al.，“Adaptive Fast PathArchitecture”，IBM Journal of Research and Development，March2001，p.191-206)。术语“内核”通常指运行在特权模式中的那部分操作系统；它是操作系统实现基本功能和服务的重要部分。

然而，迄今为止，据了解还不存在任何一种独立于数据的源的、通用操作系统内核环境的高速缓存。这样，就产生了克服这种缺陷的需求。

发明内容

根据本发明至少一个现有优选实施例，本发明广泛考虑了一种既能高速缓存专用于应用的数据，又能高速缓存独立于应用的数据，并基本上通过任何应用协议来传递这些数据的通用操作系统内核的高速缓存。数据可来自多个源，并可使用多个内核专用机构(mechanism)将其存储在内核高速缓存中。本发明还广泛考虑了用于管理该高速缓存的系统。

总之，一方面，本发明提供一种用于在操作系统内核环境中高速缓存应用数据的系统，该系统包括：用于创建至少一个高速缓存对象的装置，该高速缓存对象用于在内核环境中存储所缓存的内容；至少一个用于查找至少一个高速缓存对象的装置；和用于从多个数据源收集数据并将所收集的数据赋予至少一个高速缓存对象的装置。

另一方面，本发明提供了一种在操作系统内核环境中高速缓存应用数据的方法，该方法包括以下步骤：创建至少一个用于在内核环境中存储所缓存内容的高速缓存对象；查找至少一个高速缓存对象；以及从多个数据源收集数据并将所收集的数据赋予至少一个高速缓存对象。

此外，又一方面，本发明提供了一种可被机器读取的程序存储装置，具体包括可被机器执行的指令程序，以执行在操作系统的内核环境中高速缓存应用数据的方法步骤，所述方法包括如下步骤：创建至少一个用于在内核环境中存储所缓存内容的高速缓存对象；查找至少一个高速缓存对象；以及从多个数据源收集数据并将所收集的数据赋予至少一个高速缓存对象。

为更好地理解本发明以及其他更多特征和优点，下面将结合附图，详细描述本发明，同时将在所附权利要求中给出本发明的范围。

附图说明

图1的框图表示一运行环境；

图2的示例图表示以示例说明的不同对象及其指针；

图3的框图表示多个模块与对象之间的交互；

图4的示图表示用于高速缓存对象的存储器划分和指针；

图5的示图表示用于数据源的存储器划分和指针；

图6的框图表示在对象与模块之间关于数据请求的通信；

图7的框图表示各种内核组件；

图8的框图表示文件数据源和与之相关联的内核组件之间的通信；

图9的框图表示HTTP数据源和与之相关联的内核组件之间的通信；

图10的框图表示用户空间与内核空间之间的通信。

具体实施方式

通常，本发明至少一个现有优选实施例涉及用于构建高性能网络服务器的内核运行环境。本发明的一个方面涉及一种N源内核高速缓存(NICache，N-source In-kernel Cache)。NICache使得一个或多个应用(application)有可能为获得高性能而对操作系统进行扩展。这里所述的通过NICache增强的应用为自适应快速路径体系结构(AFPA，Adaptive Fast Path Architecture)。AFPA是一种为来自多个分散源的数据提供服务的内核网络服务器加速器。应该将其理解为，NICache不是一个独立的应用，它必须为一个或多个应用所使用。

下面将给出本发明所用一些术语的具体定义。

“回调函数(callback function)”，可将其理解为一种指向不连续编码的指针(reference)，即，所指定的并且在以后所需某一时刻被调用的函数。对于由于一事件而希望调用函数或不想同时调用多个函数的程序员，通常使用这种技术。例如，当信号发生时，信号处理程序会执行由程序员编写的函数。

“散列表(hash table)”，可将其理解为程序员用于存储数据的一种数据结构。散列表提供了对表中元素快速直接的寻址(addressing)，而不必使用足够存储一组K元素的存储机构。散列表通常对每一数据元素应用一种函数(一般称之为散列函数)以确定对表的索引。散列表通常长度是固定的。

“链表(linked list)”，可将其理解为程序员用于存储数据的一种数据结构。链表线性地存储数据，通常从表的前端或后端进行访问。链表长度不固定且易于增加。检索链表所需的时间量通常随表中项的数量线性地增加。

下面将描述本发明的优选实施例，如图1所示，本机内核环境(native kernel environment)110可包括通常对用户级应用隐藏的操作系统的地址空间、执行文本、安全属性等。本机内核环境将实现用户空间中的应用可用的服务，并可为写入内核扩展提供服务。

术语“本机(native)”，用于对“内核环境”进行限制，专指一具体内核环境。例如，AIX，Linux和Windows操作系统都具有截然不同的本机内核环境。这种不同性是由于它们都具有专用的一组用于写入子系统(如网络适配器驱动器，视频驱动器，或内核扩展)的应用接口(API)。Windows在其本机内核环境中提供数百个API。AIX和Linux各具有不同的API。此外，在文件系统与TCP/IP子系统如何交互方面，这些操作系统之间的运行环境也有所不同。

N源内核高速缓存(NICache)130使用这些API作为内核扩展。通常将NICache与一个或多个应用120一起使用，或在一个或多个应用120内使用。一个应用，无论其目的如何，也在本机内核环境110中运行。在本发明一优选实施例中，HTTP服务器加速器是所述应用，NICache与该应用相链接。即，不能将NICache作为独立的执行单元在该应用外执行。应用本身可具有多个执行单元，包括运行在用户空间中的扩展。应用扩展140最好不运行在本机内核环境中而运行在用户空间中。

应用扩展140可以是HTTP服务器的一部分，HTTP服务器可基于所接收到的HTTP请求来产生动态内容。对于应用，将服务器划分为内核和用户部分是有利的。这种方法允许服务器写入器拾取和选择服务器的哪些部分需要在用户空间中，哪些部分需要在内核中。例如，由于CGI需要用户空间保护，因而HTTP服务器总是希望在用户空间运行客户通用网关接口(CGI)请求，而不是在内核中。

在本发明的优选实施例中，应用处理包括GET，HEAD和POST请求的HTTP请求。如果高速缓存中存在一响应，那么该请求是从内核被提供的。然而，如果HTTP请求是对动态内容的请求(如CGI请求)，那么它将由应用扩展140来处理。应用扩展执行需要用户空间执行环境(context)的任何部分请求。

NICache 130对其相关(accompanying)应用120提供API。所有到API的调用通过高速缓存对象管理器210(如图2所示)。在图2中，高速缓存对象管理器210最好代理到NICache的所有调用(call)，以及管理所有的内部组件和逻辑。为了最优地实现其功能，高速缓存对象管理器可查询260诸如物理存储器利用(utilization)或CPU利用之类的机器硬件状态。它还可查询260本机内核环境的状态，即非分页池(non-paged pool)的使用和空闲页数描述符的数量。

所缓存的内容是NICache为应用高速缓存的数据。更具体说，它是应用所需的要保存在易于检索(retrieve)数据的系统中的数据。这种数据可以为任何源生成的任何格式，如ASCII或二进制。对缓存内容的限制是本机内核环境的限制。每一部分数据由其源而确定。这些源可包括来自用户级程序的输出，对HTTP GET请求作出的响应，或本地或远端文件的内容。高速缓存内容存储在高速缓存对象230，231，232中。高速缓存对象是使用专用内核机构存储和缓存所需数据的结构和程序。这些机构可包括文件系统高速缓存，插针存储器(pinned memory)，或可分页存储器以及表示多个高速缓存对象的类型和类。可将每个高速缓存对象与应用可能提供的描述符或检索键相关联。

为了保持和定位高速缓存内容，高速缓存对象管理器210使用任意一个容器数据结构220。这些容器最好以各自特定的方式保存指向高速缓存对象230的指针。例如，容器可包括链表221，散列表220，二叉树，或数组。链表容器221最好具有指向双向链表头部高速缓存对象的指针250。散列表容器220具有指向散列表中存储的所有高速缓存对象的指针270。必须将指向每个高速缓存的指针存储在至少一个容器中。对于哪些容器保持哪些高速缓存对象，高速缓存对象管理器210最好具有惟一的判断。可基于数据源，系统资源的使用量，或其他标准，将其他容器用于对高速缓存对象分类。

每个高速缓存对象最好与单个数据源相联系。数据源描述了高速缓存对象的数据来自何处，后面将对数据源做详细描述。数据源代表高速缓存对象与本机内核环境110进行通信215，225，235。为了对其数据源240，241，242进行定位，每一高速缓存对象230，231，232最好保持指向该数据源的指针280。同样，该数据源具有指回高速缓存对象的指针290。

NICache 130最好可同时支持任何类型的任意多个高速缓存对象。此外，NICache 130可同时支持来自多个源的数据。从任何源都可对任何类型的高速缓存对象赋值(populate)。例如，将其内容存储在插针存储器中的高速缓存对象，可从本地文件接收内容，或可从HTTP响应来接收内容。为清楚起见，高速缓存对象存储高速缓存的内容。数据的源识别出那些内容来自何处，并且被配置用于检索该内容。每个高速缓存对象都与单个数据源相关联，反之亦然。对于哪种类型的高速缓存对象能与哪种类型的数据源相配最好不要有任何限制，反之亦然。

下面，如图3所示，NICache 130通常可对来自一个或多个应用120的请求作出响应。作为高速缓存，NICache 130响应查找/查寻310，存储/创建350和去除/删除380的请求。对于高速缓存对象操作的所有请求，诸如上述的请求，最好是被发送到高速缓存对象管理器210中。高速缓存对象管理器210最好管理所有高速缓存对象，从而处理所有外部请求。当应用120需将数据缓存时，它最好向NICache130发送创建命令，并将指向数据源的指针传给它(尽管不是数据)。基于数据源中的字段，收集260的关于系统当前状态以及NICache当前状态的信息，高速缓存对象管理器210最好确定出使用那种存储机构来存储数据(即使用高速缓存对象的类型)。确定出高速缓存对象类型之后，最好创建360该类型的高速缓存对象330，并在一个或多个适当的容器220，221中存储361，362指向该高速缓存象的指针。将指向最新创建的高速缓存对象的指针返回370给应用120。

相反，当应用120打算从高速缓存中移除内容时，它最好向NICache130启动调用通过传递(pass in)指向所要移除的高速缓存对象的指针来删除380该高速缓存对象。高速缓存对象管理器210通过调用在任何包含指向该高速缓存对象指针的容器220，221上的移除程序390，391，而后向高速缓存对象330发送删除命令，来处理来自应用120的请求380。最好是该高速缓存对象将清除它正使用来存储高速缓存内容的任何易失性和非易失性存储器(storage)。实现这些操作之后，高速缓存对象管理器210最好删除被高速缓存对象数据结构本身所使用的所有易失性存储器。

当应用需要在高速缓存NICache 130中存储的数据时，最好基于标识符对高速缓存对象发出查找请求310。在本发明的示例性实施例中，这种标识符包括HTTP统一资源标识符(URI，UniversalResource Identifier)(Berners-Lee，T.，et al.，RFC 1945，1996，http：//www.ieft.org/rfc/rfc1945.txt)。如果高速缓存对象处于至少NICache的容器其中的一个中，则将其返回312到应用120。在本实施例中还包括“快速检索容器”的概念——其为一种容器，在这种容器中在固定时间内完成对标识符的查找，且该高速缓存对象知道如何定位这种容器。为此，NICache的优选实施例使用散列表220。当然，高速缓存对象管理器向这种快速容器发送查找调用320来查找在该标识符下存储的数据。一旦定位，该容器将向高速缓存对象管理器210返回340高速缓存对象，而高速缓存对象管理器210向应用返回高速缓存对象(或未找到)。这些操作可同步进行，或可异步进行。

NICache 130的优选实施例包括作为容器221，220两者之一的链表容器221。最好使用加权的最近最少使用的(LRU，LeastRecently Used)算法对该链表进行分类。每次将高速缓存对象作为查找请求310的结果返回时，最好将该高速缓存对象移到该链表的头部。这会确保将最近最少访问的高速缓存对象逼近该表的尾部。例如在资源有限的环境中，当必须将高速缓存对象从高速缓存移除时，这些信息将会有用。

高速缓存对象多个不同的类会导致高速缓存对象多个不同的实现方式；然而，所有高速缓存对象都通常需要具有某些部分。如图4和图5所示，在高速缓存对象需要通知高速缓存对象管理器数据的源已被移除从而高速缓存对象本身也必须被移除的情况下，最好保持指向高速缓存对象管理器210的指针450。元数据结构410最好具有描述这种高速缓存对象的信息。在此将找到生成网络协议头所需的信息。每个高速缓存对象最好包含有指向单个元数据的指针。同样，每个高速缓存对象最好保持指向利用420的指针，该利用420描述了与其相应的高速缓存对象230的系统资源利用。高速缓存对象最好包含指向一列被包含的高速缓存对象430的指针。当应用请求用于高速缓存对象的数据时，则将来自被包含的高速缓存对象的数据以及原始高速缓存对象的数据一起返回。被包含的高速缓存对象结构430可包含用于发送被包含的高速缓存对象数据的规则，如排序。高速缓存对象的专用类型部分(type-specific portion)430最好包含高速缓存对象使用的任意和所有数据与指针以以定义类型的方式保持缓存内容。数据源240可保持指向各自高速缓存对象230的指针290，反之亦然。图4和图5显示出这种联系。

除指向高速缓存对象的指针290外，每个数据源最好还保存有数据的大小(若有的话)和数据到期的时间(若有的话)。在数据源240的专用类型510部分中最好包含有对数据源专用的信息和如何从源检索内容的信息。

下面如图6所示，当应用120准备从高速缓存对象230提取信息时，它最好发出对数据的请求610，该请求可选择性地包括偏移量和长度。在NICache该优选实施方式中，当需要内容以发送到客户机时，应用将仅发送这种请求610。此外，高速缓存对象不会预填充该内容。因此，当对数据的请求610传到高速缓存对象时，可能数据不存在(即未存储在高速缓存对象内)。如果数据存在的话，则该高速缓存对象立即将内容返回620。然后，基于高速缓存对象的所包含的高速缓存对象结构430的规则，高速缓存对象可将请求620转发到被包含的高速缓存对象。如果在高速缓存对象中内容不存在的话，则调用610以未定状态编码返回，并且该高速缓存对象向其数据源启动调用来请求数据，该调用可选择地包括偏移量和长度。当数据源已具有来自源的请求的信息时，就立即将请求630返回，从而将数据传回到应用120。然而，在一些情况下，数据源必须经由内核机构来接触615数据的源以取得数据的最新副本。在这种情况下，高速缓存对象的调用630被返回以未定(pending)状态编码，而数据源等待源返回数据。一旦数据源接收到高速缓存对象所需的一些或所有内容，就将数据回调640给高速缓存对象，并使高速缓存对象将数据返回620给应用120。对于单次到数据源的请求630可调用多次高速缓存对象回调640。这种双层异步接口可防止应用和高速缓存对象处于等待。这允许应用120在中断级或较高中断请求级(IRQL)提交对数据610的请求。

如上所述，数据源与本机内核环境110进行通信以获取最新数据的副本，如附图标记615所示。图7重点讲述在本机内核环境110中的不同子组件。尽管在操作系统之间其名称以及可能的分组会有所不同，但这些组件都以各自的特性在商业操作系统如AIX，Linux和Windows中存在。NICache可能会使用多个这样的组件。

文件系统710是处理向非易失性存储器和非易失性存储器传输数据的操作系统的一部分。该存储器可以是位于同一物理机器中的物理或逻辑的磁盘驱动器，或位于通过网络相连的物理或逻辑的磁盘驱动器。可将来自这些文件的数据赋予高速缓存对象。NICache数据源可使用这些文件系统的API进行通信，以创建文件，打开文件，检索文件句柄(handler)，读取数据和写入数据。图8显示出在示例性实施例中文件数据源800如何向文件系统710发送文件打开请求810，以及如何返回文件句柄820。

存储器管理器720是一组负责分配、解除分配和管理虚拟存储器，  解析硬件存储器异常和管理页表(参见Solomon andRussinovich，supra，p.380)的系统服务。为了满足高速缓存对象的索取数据(Get Data)请求630，数据源可能需要分配725存储器(插针存储器，非分页池等)或访问共享存储器。

内核的网络栈(stack)730通常通过网络发送和接收数据，详细解释请参见W.Richard Stevens，TCP/IP Illustrated，Volume 1 TheProtocols Addison-Wesley，1994。数据源可通过与网络栈730的交互735来获取其数据。图9表示在NICache的示例性实施例中HTTP数据源900利用内核的网络栈730向HTTP服务器发送HTTP请求910(参见Berners-Lee，T..et al.，RFC1945，1996，http：//www.ietf.org/rfc/rfc1945.txt)。对这些HTTP请求的响应以数据流920的形式被路由返回到HTTP数据源900。基于其他网络协议需使用网络栈730可创建多个数据源。

进程和线程740是指运行在与NICache相同的机器上但在不同的范围(context)的程序。通过由本机内核环境110提供的内部进程通信机构，数据源可与另一进程或线程通信745。

图10显示一类数据源与另一执行程序或线程1030的交互，在示例性实施例中该类数据源为User Level Data Source 1000。数据请求1010和含有数据的响应1020通过用于内部进程通信的内核机构来通信，该内核机构包括套接字、数据流、共享存储器、信令或管道。

应该理解，根据至少一个现有优选实施例，本发明包括，用于创建至少一个用于在内核环境中存储所缓存内容的高速缓存对象的装置，至少一个用于查找至少一个高速缓存对象的装置，和用于从多个数据源收集数据并将所收集的数据赋予至少一个高速缓存对象的装置。综合起来，可在至少一台运行适合的软件程序的通用计算机上实现这些组件。也可以在至少一块集成电路或至少一块集成电路的部分上实现这些组件。从而，应当理解本发明可以以硬件、软件，或在二者的组合来实现。

如果不另外声明，则认为此处提到和引用的所有专利，专利申请，专利公开和其他出版物(包括基于Web的出版物)，在此全部引作参考。

尽管在此参照附图描述了本发明说明性的实施例，但应该理解本发明不限于那些具体的实施例，本领域技术人员在不脱离本发明的范围或精神的条件下可进行各种其他修改和变化。