Virtual replication for a computer directory system

[0002] This invention relates generally to computers and computer software, and more specifically to a virtual replication system and method for a distributed data network.

[0003] Personal computers or workstations may be linked in a computer network to facilitate the sharing of data, applications, files, and other resources. One common type of computer network is a client/server network, where some computers act as servers and others as clients. In a client/server network, the sharing of resources is accomplished through the use of one or more servers. Each server includes a processing unit that is dedicated to managing centralized resources and to sharing these resources with other servers and/or various personal computers and workstations, which are known as the “clients” of the server.

[0004] Directories and directory services are often provided to enable a digital environment for a particular resource. One example of a directory service is Novell Directory Services (“NDS”) for Novell Netware networks, as provided by Novell, Inc. of Provo, Utah. NDS provides a logical tree-structure view of all resources on the network so that clients can access them without knowing where they are physically located. For a given resource, an entry is made in a directory such as NDS. Specific entries of a directory are only available by directly accessing the directory.

[0005] Typically, applications operate against a single, non-distributed directory to access information that is pertinent to the application. In this manner the application can access all of the information it needs from this single source. From an administrative perspective, this presents a problem since the information is stored on an application by application basis and the administrator is forced to often manage duplicate sets of data stored in multiple locations

[0006] To solve this administrative problem, distributed directory environments such as NDS, have been developed to allow for the partitioning of the data into sets that given applications may be interested in, then distributing copies of these sets to where these applications can locally access them. The separate copies, or Replicas, are kept current through an automated process called Replication. In this manner administrators can place specific information where it is most needed, yet are still able to centrally manage this information.

[0007] However, distribution of this data brings its own set of problems. For instance, if the set of information that is of interest to a given application spans the entire distributed network, the application would have to either maintain a local replica of all of the sets of data in the network or would be forced to remotely access replicas of the sets of data that do not reside locally. Either solution is undesirable. Maintaining a local replica of all of the data sets would require a lot more storage capacity and network bandwidth, and much of the data that would be stored and replicated would not be of interest to the application. Remotely accessing nonlocal sets of data would be slow and there would be a chance that the application may not be able to access all of the data it needs all of the time.

[0008] It is desired to have a distributed directory maintained such that multiple applications could use it as though they were working on a single, centralized directory.

[0009] It is also desired to be able to filter out subsets of data from a given replica in order to allow for the storage of only the data that is of interest to a given application and to reduce the amount of network traffic caused by replication events in a distributed data environment.

[0010] In response to these and other problems, an improved system, method and software program is provided for facilitating the use of components running in a computer network. To this end, the improvement provides virtual replication of a distributed directory in a computer system. The system includes at least two servers, each including a processor connected to a network for executing computer code, and a memory system. The memory of the first server can store, among other things, a partition of information. In some embodiments, the partition may be distributed across the network. The memory of the second server can store, among other things, a virtual replica of the partition. The virtual replica includes a filtered view, or subset, of the information in the partition.

[0011] In some embodiments, the virtual replica provides an application using the second server with a centralized copy of specific information from the directory in which the application is interested (the filtered view). The application can then access all of the information that it needs via a local read to the second server. Also, with certain replication technology, such as is found in NDS directories, the virtual replica can be dynamically updated as modifications are made elsewhere in the directory.

[0012] In some embodiments, the second server also includes an inbound replication software process for receiving events from the partition and then filtering the events according to the filtered view.

[0013] In some embodiments, the first server includes an outbound replication software process for filtering events from the partition and transferring the filtered events to the virtual replica.

[0014] An advantage of the present invention is that most of the difficulties that arise when applications have to access a distributed directory are reduced and/or eliminated.

[0015] Other advantages can be readily seen by further examination of the attached figures and the following description.

[0016] FIG. 1 illustrates a simplified computer system including three computers and a network, the system being used for implementing one embodiment of the present invention.

[0017] FIG. 2 is a diagram of an exemplary distributed directory system used in the computer system of FIG. 1.

[0018] FIG. 3 is a functional description of the computer system of FIG. 1 and the distributed directory system of FIG. 2. The functional description of FIG. 3 also illustrates a routine, such as can be implemented by a software program, for implementing one embodiment of the present invention.

[0019] The present invention provides a unique system and method that bridges the gap between the benefits of having a distributed, replicated data store and the benefits of having a centralized data store. It is understood that the following disclosure provides many different embodiments, or examples, for implementing different features of this invention. Techniques and requirements that are only specific to certain embodiments should not be imported into other embodiments. Also, specific examples of networks, components, and formats are described below to simplify the present disclosure. These are, of course, merely examples and are not intended to limit the invention from that described in the claims.

[0020] Referring now to FIG. 1, three similar computers, designated 10a, 10b, and 10c, are illustrated as a representative example of an operating environment for the present invention. Each computer 10a, 10b, 10cincludes a central processing unit (“cpu”) 12a, 12b, 12c, a memory unit 14a, 14b, 14c, an input/output (“I/O”) device 16a, 16b, 16c, and a network interface 18a, 18b, 18c, respectively. The components 12a, 14a, 16a, and 18aare interconnected by a bus system 20a, the components 12b, 14b, 16b, and 18bare interconnected by a bus system 20b, and the components 12c, 14c, 16c, and 18care interconnected by a bus system 20c. It is understood that each of the listed components may actually represent several different components. For example, the cpu 12amay actually represent a multi-processor or a distributed processing system; the memory unit 14bmay include different levels of cache memory, main memory, hard disks, and remote storage locations; and the I/O device 16cmay include monitors, keyboards, and the like.

[0021] The computers 10a, 10b, 10care also commonly connected to a network 30. The network 30 may be representative of several networks, such as a local area network, a company wide intranet, and/or the internet. Because the computers 10a, 10b, 10care connected to the network 30, certain components may, at times, be shared between the computers. Therefore, a wide range of flexibility is anticipated in the configurations of the computers. Furthermore, it is understood that, in many implementations, the computers 10a, 10b, 10cmay be configured differently from each other, may have different components, and/or one computer may act as a server to the other computer.

[0022] The present invention facilitates many different operational scenarios of the computers 10a, 10b, 10cand the network 30. Single server environments and multi-server environments, as well as distributed and non-distributed environments, may benefit from the present invention. A distributed, multi-server environment will be discussed below to provide just one example of how the present invention operates.

[0023] Referring now to FIG. 2, the computers 10a, 10b, 10cand the network 30 are used to provide a hierarchical distributed directory system 50. Software running on one or more of the computers 10a, 10b, 10cprovides the directory service, while applications running on these computers (or other computers) utilize the directory service. The software may be stored on a recordable medium, such as one or both of the memory units 14a, 14b, 14cthe network 30, or other medium. Reference to the directory 50 includes the hierarchical directory (the tree structure) itself and the software running to implement and maintain the directory.

[0024] For the sake of example, the directory 50 is a NDS having a logical “tree-structure” view of all resources on the network. As a result, the computers 10a, 10b, 10ccan access the resources without knowing where the resources are physically located (be it computer 10a, computer 10b, computer 10c, the network 30, or some other entity). For the sake of example, the directory 50 uses an online directory service protocol called LDAP, or Lightweight Directory Access Protocol. The directory includes one or more entries, each of which is a collection of attributes with a unique identifier.

[0025] In the present example, the directory 50 is broken into exclusive, non-overlapping “containers.” A top level container A is connected to different lower containers 1, 2, 3, which are then connected to even lower containers a, b, c, etc. In furtherance of the present example, the top level container A may represent the overall directory structure for a large company; the containers 1, 2, 3 represent various cities that the company is located; and the lowest containers a, b, c represent different entities of the company, e.g., container a is for sales, container b is for marketing, and container c is for engineering. By combining the container names for more definite reference, sales 1a, 2a, 3ais in every city, marketing 1b, 3bis in two cities, and engineering 1cis only in one city.

[0026] One or more contiguous containers can be grouped into a single partition. A partition is a logical construct that is not limited to a single physical location. In the present example, container A is in a partition 52; containers 1 and 1aare in a partition 54; container 1bis in a partition 56; containers 1cis in a partition 58; containers 2 and 2aare in a partition 60; and containers 3, 3a, and 3bare in a partition 62.

[0027] A computer, such as the computer 10a, can be configured as a server for storing a replica of one or more partitions. Although replicas may be stored in one or more servers, any changes to data in a replica will replicate to the other servers storing the same data.

[0028] A problem arises when an application running in one or more of the computers 10a, 10b, 10cneeds to get information from everywhere in the tree, i.e., a central “view” of the tree, and not just the local partition. The traditional solution is to “walk the tree” by going from partition to partition, bouncing from server to server. When the application requests information that is not resident on a specific server to which it is currently attached, the application gets referred to a different server that (potentially) holds the desired information. Walking the tree can be a very long and tedious process, bogging down various computers in the distributed network. Distributed network systems are often undesirable because it is difficult to get a central view of the network tree.

[0029] One solution is to allow a user to define a “view” of specific information. A view is defined by a “filter set” and a “partition scope.” A filter set is an enumerated set of classes and attributes in which the particular application is interested. The partition scope is a set of partitions that hold the specific information. The partition scope can include any number of partitions. For example, a user may select user objects consisting only of a first name, last name, and telephone number of each person in the company A. The user may also define a partition scope by identifying specific partitions to view, in this example, the user is looking for marketing, so the user identifies partitions 56 and 62. Once the user has defined a filter set and a partition scope, a filtered view is stored on a specified server by setting up a virtual replica for each of the partitions specified in the partition scope. Therefore, the server has a filtered copy of every selected partition. In this way, the selected server does not have to replicate and store large amounts of data that the application does not want. This aggregates a centralized view across an entire distributed network.

[0030] The virtual replicas provide the application with a centralized copy of only the specific information from the directory that is of interest to the application. The application can then access all of the information that it needs via a local read to the given server, thereby eliminating the need to remotely walk the tree. Also, with certain replication technology, such as is found in NDS directories, the generated “view” is dynamically updated as modifications are made elsewhere in the directory.

[0031] The creation of a view may utilize one or more of the following items:

[0032] Directory systems typically have various “types” of partitions and replicas. In some embodiments of the present invention, a new type of replica is created to accommodate virtual replicas. The virtual replica type indicates that the replica only contains the information that is allowed by the replication filters. There are two version of this new type replica: read/write, and read only. (In NDS, these versions are similar to the existing “secondary replica” types.) A read/write replica is a writeable replica that can be updated from the client. A read-only replica can not be changed from the client. Instead, it will only be updated from another read/write replica (or a master replica).

[0033] A server storing a virtual replica may have an inbound replication filter. An inbound replication filter enumerates the classes and attributes to be stored on the server. These classes and attributes are determined by an application (or set of applications) that utilizes the server, such as a client to the server. This filter is defined on a server-by-server basis, and its definition resides on the server to which it applies. In the embodiment described in FIG. 2, the directory 50 uses a replication process which is modified to enforce the inbound replication filter for replicas of the virtual type. All local modifications, as well as inbound replication events, are screened through the filter to determine if those events are changes for the virtual replica(s)

[0034] An outbound replication process enumerates the classes and attributes that a particular partition administrator will allow to be replicated to a server holding virtual replicas (the virtual replica server). The outbound replication process uses an outbound replication filter, residing on a server other than the virtual replica server (a source server), that is defined on a partition by partition basis. This allows the administrator to restrict the flow of information to the virtual replica server. The outbound replication process thereby “enforces” the outbound replication filter. This outbound replication filter is checked before the outbound replication process applies the virtual replica server's inbound replication filter.

[0035] In some embodiments, the source server enforces the outbound replication process only if the virtual replica server has specified that it holds a virtual replica of that partition. In this way, the events from the outbound replication process are of the appropriate size and content, and are limited to the information that the virtual replica server desires.

[0036] Methods used for object resolution may be modified to allow for the specification of whether the resolution should be made to a full replica or a virtual replica. It may be necessary to make this distinction so that applications that require a full view of all objects and attributes in a given partition can be guaranteed to still resolve to a full replica. However, if an application would like to operate against a customized “view,” it can specify that it would like to resolve to a virtual replica that holds that view.

[0037] So in the present embodiment, there is a process in the directory 50 that handles replication. The process provides a limited “view” of one or more partitions in the directory using a virtual replica “type.” The process may also include two processes: one that issues outbound replication events, and one that receives inbound replication events. The directory 50 enforces the replication filter on the inbound side to ensure that the server holding the virtual replica(s) will only store information that is allowed through the filter. The directory 50 enforces the replication filter of the virtual replica server on the outbound side of the replication process on a source server to reduce any unnecessary replication traffic.

[0038] Referring now to FIG. 3, a flow diagram 100 provides several exemplary flow descriptions for one embodiment of a virtual replication process. The flow diagram 100 uses the three computers 10a, 10b, 10cof FIG. 1. All three computers are part of a replica ring 102. A replica ring describes a set of replicas for a given partition. The replica ring may not be an actual “ring,” such as a token ring. Instead, a replica ring describes a logical grouping of replicas, so that when one entry of a replica (or the given partition) is changed in some way, the remaining replicas in the group will get updated accordingly. It is understood that in some embodiments, any computer may be able to communicate directly with any other computer.

[0039] In the present example, computers 10aand 10care “new” servers, in that they include inbound and/or outbound replication filter capabilities, such as described above. The computer 10bis an “old” server which supports replication, but does not implement certain benefits of the present invention used for virtual replication. One advantage of the present invention is that in certain embodiments, both new and old servers are able to effectively coexist in a common directory system.

[0040] Each of the computers 10a, 10b, 10cincludes a data store, represented by memories 14a, 14b, 14c, respectively. For the sake of further example, the server 10aincludes a partition of data in its data store 14a. The server 10bincludes a replica of that partition in its data store 14b. The server 10cincludes a virtual replica of the partition in its data store 14c. The virtual replica in server 10chas a subset of the objects and/or attributes that exist in the partition at server 10a.

[0041] In the replica ring 102, whenever changes occur to any objects or attributes in a partition (or replica), those changes are replicated to the other servers in the replica ring by one or more replication events. For the sake of example, a change to the partition in server 10bmay occur. The server 10bthen replicates those changes by sending replication events to the destination server 10a. The replication events are represented by the three arrows 104a, 104b, 104c.

[0042] The server 10areceives the replication events 104a, 104b, 104cand makes the necessary changes to the data in its data store 14a. The server 10athen replicates the events to another destination server (this process is referred to as transitive replication). However, in the present example, the destination server 10chas specified that it holds a virtual replica of the partition. Therefore, a software administrator on the server 10aexercises an outbound replication filter process to enumerate the classes and attributes that will be replicated to the destination server 10c. In the present example, the outbound replication process in the server 10aonly replicates the event 104cto the server 10c. Since the events 104a, 104bare not replicated, network traffic is reduced.

[0043] In another example, the server 10bmay replicate the events 104a, 104b, 104cdirectly to the destination server 10c. In the present example, the server 10bdoes not have an outbound replication process. However, an inbound replication filter on the server 10creceives all the replication events 104a, 104b, 104cand filters out the events needed for the virtual replica. In continuance with the above example, the inbound replication filter would filter out replication events 104a, 104band only provide replication event 104cto the virtual replica. Therefore, the new server 10ccan still work directly with the old server 10b.

[0044] It is understood that modifications, changes and substitutions are intended in the foregoing disclosure and in some instances some features of the disclosure will be employed without corresponding use of other features. For example, a “new” server may only have the inbound replication filter but will not have the outbound replication process. Accordingly, it is appropriate that the appended claims be construed broadly and in a manner consistent with the scope of the disclosure.