System for change notification and persistent caching of dynamically computed membership of rules-based lists in LDAP

[0001] In large enterprises the need for membership lists management is significant. The number of potential applications of such lists is vast. Some example applications are authorization systems that use lists to represent “Role Assignments” or email systems that use lists for the purpose of maintaining a “Mailing List.” The costs, both administrative and performance, associated with use of membership groups are significant. There are two general methods for administration and use of membership groups—static lists and rules-based lists.

[0002] Static lists are one method for managing membership lists. A static list is a physical listing of user names. No other attributes of the user are included in a static list. Accessing static lists is inexpensive. To access the list, a simple fetch operation is used. On the other hand, modifications to the list are statically maintained, creating an enormous administration workload to maintain the lists. For example, the membership lists must be individually identified and edited each time an individual is added, deleted, or modified.

[0003] For example, if a new employee joins a human resources department in an organization, that new employee is added to several membership groups. The new employee may be added to the “all employee” e-mail list, the “human resource department” e-mail list, the “benefits software” application permission list, the “performance review software” access list, the “compensation software” application permission list, or any number of lists that the organization has created. If this new employee leaves the organization, the employee may need to be removed from all the groups to which he was added. If the employee changes departments within the organization, the employee may need to be removed from some or all of his current lists and added to new lists. The nature of these changes when static membership lists are employed is administratively burdensome.

[0004] Rules-based lists are another method for managing membership lists. Memberships of rules-based lists are built each time they are accessed by the execution of one or more rules and are sometimes referred to as dynamic lists. There is no physically stored membership, hence there is no physical list to update and therefore there is no administrative burden of maintaining such lists. For example, the rules are executed to have a new employee added to the membership list. Such a rule can be stated as “all individuals whose manager attribute value directly or indirectly references ManagerA” where ManagerA is the name of the manager of the Human Resources Department.

[0005] While rules-based lists offer a significant advantage in administration, the performance costs are a major hindrance to their widespread application. The dynamic nature of these lists mandates that the membership be computed each time the groups are accessed, in contrast, the static nature of static lists allows quick retrievals. Rules-based lists do not persistently store membership, thus, queries such as “return all the roles of User1” become computationally expensive since this requires that the membership of User1 be determined for all rules-based lists.

[0006] An additional limitation of the rules-based lists is that it is difficult to provide change notifications to other applications related to the changes in membership of the list without incurring additional computational expenses. Such is the case because the membership is not explicitly administered and hence changes in membership are unknown. Therefore, the membership must be built by executing the rules each time the list is accessed to obtain the most up to date membership.

[0007] Such limitations have resulted in restricted use of the rules-based lists. In situations where performance is critical, rules-based lists are not deployed in favor of static lists that are efficient, albeit they require significant effort in terms of administration.

[0008] A solution has been provided for a membership lists that provides the management benefits of a rules-based list with the efficient lookup of a static list. An example, method of managing a membership list includes: executing a set of membership rules to create a membership list, caching the created membership list in storage, and updating the membership list cache as and when member objects are modified. An example system for managing membership lists includes a set of rules, a cache, a cache accessing module, a rule modification module, a cache updating module, and a change notification module.

[0016] A method, system, and computer program product for change notification and persistent caching of dynamically computed membership of rules-based lists in LDAP is described. This solution provides the administration benefits of a rules-based list with the efficient lookup of a static list. To accomplish this, in one embodiment, a method of managing a membership list includes executing a set of membership rules to create the membership of a dynamically computed membership list, caching the computed membership in storage allowing efficient access to the list via the persistent cache, and modifying the membership cache when member objects are updated. The embodiments of this disclosure describes the membership node structure, access, and change management in detail.

Node Structure

[0017] Lightweight Directory Access Protocol (LDAP) is an online directory service protocol defined by the Internet Engineering Task Force (IETF). An LDAP directory entry is a collection of attributes with a unique identifier, called a distinguished name (DN). An LDAP directory organizes the entries or objects (i.e., member objects) in a hierarchical structure of nodes, sometimes referred to as a tree. Member objects include a user name and all attributes of that user. Some example user attributes can include “area code,” “department,” “Manager,” “role,” etc.

[0018] Each rules-based membership list can have one or more rules associated with it. The membership of the list is based on the rules. In some embodiments each rule has a base, scope, and a filter criterion. The base identifies highest level of criteria for that rule (i.e., which node in the LDAP tree does this rule associate with), the scope identifies a second level of criteria for that rule (i.e., how deep from the base), and the filter specifies the selection criteria for membership objects. Scope can be specified, for example, as base level, a child of base level but not including the base, or all entries below and including the base.

[0019] One embodiment organizes the membership lists in a hierarchical structure based on the base specified in the rules of all the rules-based membership lists. Each node in the hierarchical structure has one or more membership lists associated with it. In some embodiments the hierarchical structure includes a plurality of hierarchical structures of sparse trees.

[0020] As mentioned above, in some embodiments, each rule of the membership list includes a base, a scope or level, and a filter. The base of the rule determines with which node in an LDAP tree hierarchy the membership list is associated. Each node in the in the tree structure maintains a list of all the membership lists within the node (by a List ID) along with associated levels and filters in the form of a Link List. A filter specifies criteria that may be used in a query. For example, to build memberships lists of all users based on their area codes in California, a tree structure may have a node regarding “California” as a base node, membership lists including membership ID and filter information as nodes in the linked list associated with the California node in the tree, and each node in the link list specifying the specific area code as filter for that membership list (e.g. “415,” “650,” “408,” and “all users”). In this example, the filter for the “area code” node Link List includes “List ID1-area code=415, List ID2-area code=650, List ID3-area code=408, and List ID4-all users”. The base, level, and filter associated with the membership List ID in the Link List provide a mechanism to quickly identify and locate membership lists. This is discussed further in the change management section.

[0021] In some embodiments, attributes of each membership list includes a cache enabled state, and a cache state. The cache enabled state indicates if the membership list can be cached, or not. The cache state indicates the current status of the cache. In some embodiments the cache state can be valid, invalid, or being updated.

Overview

[0022] FIG. 1A shows an embodiment of a system for change notification and persistent caching of dynamically computed membership of rules based lists in LDAP. Processor 101 executes rules 125. The resulting calculated membership list is stored in cache 105. A membership request will cause cache access module 110 to retrieve membership lists from cache 105. A membership object change will cause cache update module 115 to make changes to membership lists in cache 105 and record the changes into change log 130. Change notification module 135 sends change notices to subscribing applications based on the change log 130. A rule change will cause rule modifying module 120 to make change to the rules 125.

[0023] An example embodiment of process 150, an overview of caching rules-based membership lists and change management, is shown in FIG. 1B. In process action 155 the rules are executed to build a membership list. The built membership list is cached in process action 165. Determining if the membership list has been modified occurs in process action 165. Process action 175 updates the previously cached membership list. Further information detailing these steps is below.

Caching and Access

[0024] Caching and access are interrelated as the membership list is not built and cached until the first query request for the list is received. An embodiment of process 200, which is a receiving a membership list query process, is shown in FIG. 2. A membership list query is received in process action 202. Process action 204 determines if this is the first time this membership list has been queried. If not, process action 206 reads the previously cached membership list. If yes, process action 208 determines if the membership list is cache enabled. If the membership list is not cache enabled, process action 210 executes the rules to compute the membership list. Process action 216 returns the membership list to the requester. If the membership list is cache enabled, process action 212 executes the rules to compute the membership list, process action 214 stores the membership list in a storage structure, and process action 216 returns the list to the requestor. In some embodiments the storage structure is persistent. A persistent membership list allows the system to continue from where any processing left off in the event of down time (e.g., power loss) without having to re-execute all the changes made to the membership list.

[0025] One example of the use of this process is an enterprise implementing a new software application prompting the use of a new rules-based membership list for application access rights. When a user tries to access the application, the application sends a query requesting the membership list. If the request is the first request, the rule(s) for the list are executed, building the list. The application reads the membership list to determine if the user has the appropriate rights. The list is cached in storage if cache enabled. The next user to access the application, causes another access query. This query, and each subsequent query, can access the cached membership list instead of having to execute the membership rules to build the list. One embodiment of the accessing process is explained in more detail below.

[0026] When process action 206 of FIG. 2 reads the membership list, process 300 is triggered. An embodiment of process 300, which is the read the cached membership list process, is shown in FIG. 3. In process action 302 a read the cached membership list request is received. Process action 304 determines the state of the cache to be “being updated,” “valid,” or “invalid.” The setting of these states is further described in the Change Management section below. If the cache state is “being updated,” process action 306 executes the rules to compute the membership so that the processing of the membership update does not delay the request. If the cache state is “valid,” process action 308 accesses/reads the membership list from the cache. If the state of the cache is “invalid,” process action 310 purges the membership list from the cache, process action 312 executes the rules to compute the membership list, and process action 314 stores the recomputed membership list in the cache and sets the cache state to valid.

[0027] In another embodiment, the membership cache contains static members in addition to the rules-based members. When the cache state is found to be invalid during execution of process 300, only the rules-based members are purged from the cache in process action 310, and added back in to the cache in process action 314. The static members remain in the cache throughout the process.

Change Management

[0028] Among other things, managing membership lists involves handling changes. Example changes include membership object changes such as adding a member or modifying a member attribute, this results from a change in the member object and not in the rules-based list explicitly and membership rule changes such as changing the name of ManagerA in the example rule “all individuals whose manager attribute value directly or indirectly references ManagerA.” When a membership object is changed, the cache state is set to “being updated.” When a membership rule is changed, the cache state is set to “invalid.”

[0029] In some embodiments, when a member object is modified membership lists are examined to see which lists are affected. An embodiment of process 400, which is the membership object modification process, is shown in FIG. 4. A membership list object change has been requested in process action 402. Process action 404 determines the potentially affected nodes based on the List ID of the object in the request. The DN or List ID of the member object should have the same base as, or be a child node to, the potentially affected nodes. For each potentially affected node, process action 406 compares the level of the request to the level of each entry in the Link List for the node. Recall that the Link List stores the level and filters associated with each membership list in a node. If the level of the object does not match the level of the entry in the Link List, then the membership list associated with the entry is not affected by the modification. Process action 416 determines if there are more entries in the Link List of that node to check. If yes, process action 418 moves on to the next Link List entry. If there are no more Link List entries to check in that node, the process moves onto the next node in process action 420. If the level of the object does match the level of an entry in the Link List in process action 406, then process action 408 determines if the filter of the entry in the linked list applies to the object If the filters do not apply to the object process action 416 determines if there are more Link List entries to check in this node. If yes, process action 418 moves on to the next entry. If the filter in the linked list entry applies to the object, then process action 410 updates the cache of the membership list associated with the matched Link List level and filter entry.

[0030] In process action 410, the state of the cache is set to “being updated” while the member is physically added, deleted, or modified in the membership cache, and the state is returned to “valid” upon completion of the change. If a query to access the list is received during the update, the query executes the rules to build the membership list so as not to delay the query (as shown in process action 306 of FIG. 3). In process action 412 the change is submitted to the change log. Subscribers (e.g. applications and specific groups) of the change log are notified of changes. Process action 414 determines if there are more potentially affected nodes. If yes, process action 420 moves on to the next node to check the Link Lists of those nodes. If there are no more nodes, the process stops.

[0031] Another example change is when a membership rule is modified. An example embodiment of process 500, which is the rule modification process, is shown in FIG. 5. In process action 502 a rule modification is requested. In process action 504, the membership List ID contained in the request is used to locate the effected list. The cache state of the effected membership lists is set to “invalid” in process action 504. The next time one of these effected membership lists are accessed (process 300 in FIG. 3), the cache state is detected as “invalid” (310). As stated above, when the cache state is determined to be “invalid” in process 300, the cache is purged, the modified rules are executed to build the membership list, and the list is cached.

[0032] When a rule is modified the modifications may effect the hierarchy of the tree. For example, nodes may have to be created or moved. This possibility of a tree structure change is handled in element 530, the Update Hierarchical Structure section of FIG. 5. Process action 506 determines if a rule was deleted. If the rule was deleted, process action removes the corresponding node from the link list. If the rule was not deleted, process action 508 determines if a new rule was added. If a rule was added, process 516 adds a node to the appropriate link list. If a rule was not added, process action 510 determines if the base of a rule has changed. If the base of a rule has changed, process action 518 removes the corresponding node from the appropriate link list, process action 520 locates the new base node, and process action 522 adds a node to the link list of the new base node. If the base of the rule has not changed, this indicates that a filter criterion of the rule has changed (e.g., changing area code 650 to 707). In this case, process action 524 modifies the filter information of the node in the link list to reflect the change.

System Architecture Overview

[0033] The execution of the sequences of instructions required to practice the invention may be performed in embodiments of the invention by a computer system 1400 as shown in FIG. 6. In an embodiment of the invention, execution of the sequences of instructions required to practice the invention is performed by a single computer system 1400. According to other embodiments of the invention, two or more computer systems 1400 coupled by a communication link 1415 may perform the sequence of instructions required to practice the invention in coordination with one another. In order to avoid needlessly obscuring the invention, a description of only one computer system 1400 will be presented below; however, it should be understood that any number of computer systems 1400 may be employed to practice the invention.

[0034] A computer system 1400 according to an embodiment of the invention will now be described with reference to FIG. 6, which is a block diagram of the functional components of a computer system 1400 according to an embodiment of the invention. As used herein, the term computer system 1400 is broadly used to describe any computing device that can store and independently run one or more programs.

[0035] Each computer system 1400 may include a communication interface 1414 coupled to the bus 1406. The communication interface 1414 provides two-way communication between computer systems 1400. The communication interface 1414 of a respective computer system 1400 transmits and receives electrical, electromagnetic or optical signals, that include data streams representing various types of signal information, e.g., instructions, messages and data. A communication link 1415 links one computer system 1400 with another computer system 1400. For example, the communication link 1415 may be a LAN, in which case the communication interface 1414 may be a LAN card, or the communication link 1415 may be a PSTN, in which case the communication interface 1414 may be an integrated services digital network (ISDN) card or a modem.

[0036] A computer system 1400 may transmit and receive messages, data, and instructions, including program, i.e., application, code, through its respective communication link 1415 and communication interface 1414. Received program code may be executed by the respective processor(s) 1407 as it is received, and/or stored in the storage device 1410, or other associated non-volatile media, for later execution.

[0037] In an embodiment, the computer system 1400 operates in conjunction with a data storage system 1431, e.g., a data storage system 1431 that contains a database 1432 that is readily accessible by the computer system 1400. The computer system 1400 communicates with the data storage system 1431 through a data interface 1433. A data interface 1433, which is coupled to the bus 1406, transmits and receives electrical, electromagnetic or optical signals, that include data streams representing various types of signal information, e.g., instructions, messages and data. In embodiments of the invention, the functions of the data interface 1433 may be performed by the communication interface 1414.

[0038] Computer system 1400 includes a bus 1406 or other communication mechanism for communicating instructions, messages and data, collectively, information, and one or more processors 1407 coupled with the bus 1406 for processing information. Computer system 1400 also includes a main memory 1408, such as a random access memory (RAM) or other dynamic storage device, coupled to the bus 1406 for storing dynamic data and instructions to be executed by the processor(s) 1407. The main memory 1408 also may be used for storing temporary data, i.e., variables, or other intermediate information during execution of instructions by the processor(s) 1407.

[0039] The computer system 1400 may further include a read only memory (ROM) 1409 or other static storage device coupled to the bus 1406 for storing static data and instructions for the processor(s) 1407. A storage device 1410, such as a magnetic disk or optical disk, may also be provided and coupled to the bus 1406 for storing data and instructions for the processor(s) 1407.

[0040] A computer system 1400 may be coupled via the bus 1406 to a display device 1411, such as, but not limited to, a cathode ray tube (CRT), for displaying information to a user. An input device 1412, e.g., alphanumeric and other keys, is coupled to the bus 1406 for communicating information and command selections to the processor(s) 1407.

[0041] According to one embodiment of the invention, an individual computer system 1400 performs specific operations by their respective processor(s) 1407 executing one or more sequences of one or more instructions contained in the main memory 1408. Such instructions may be read into the main memory 1408 from another computer-usable medium, such as the ROM 1409 or the storage device 1410. Execution of the sequences of instructions contained in the main memory 1408 causes the processor(s) 1407 to perform the processes described herein. In alternative embodiments, hard-wired circuitry may be used in place of or in combination with software instructions to implement the invention. Thus, embodiments of the invention are not limited to any specific combination of hardware circuitry and/or software. The term logic is defined as any hardware, software, or combination of hardware and software.

[0042] The term “computer-usable medium,” as used herein, refers to any medium that provides information or is usable by the processor(s) 1407. Such a medium may take many forms, including, but not limited to, non-volatile, volatile and transmission media. Non-volatile media, i.e., media that can retain information in the absence of power, includes the ROM 1409, CD ROM, magnetic tape, and magnetic discs. Volatile media, i.e., media that can not retain information in the absence of power, includes the main memory 1408. Transmission media includes coaxial cables, copper wire and fiber optics, including the wires that comprise the bus 1406. Transmission media can also take the form of carrier waves; i.e., electromagnetic waves that can be modulated, as in frequency, amplitude or phase, to transmit information signals. Additionally, transmission media can take the form of acoustic or light waves, such as those generated during radio wave and infrared data communications.

[0043] In the foregoing specification, the invention has been described with reference to specific embodiments thereof. It will, however, be evident that various modifications and changes may be made thereto without departing from the broader spirit and scope of the invention. For example, the reader is to understand that the specific ordering and combination of process actions shown in the process flow diagrams described herein is merely illustrative, and the invention can be performed using different or additional process actions, or a different combination or ordering of process actions. The specification and drawings are, accordingly, to be regarded in an illustrative rather than restrictive sense.