Re-partitioning directories

• US 8,037,181 B2
• Filed: 06/28/2002
• Issued: 10/11/2011
• Est. Priority Date: 06/28/2002
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Brown, Mark, Parham, Jeffrey
• Primary Examiner(s): Follansbee; John
• Assistant Examiner(s): MADAMBA, GLENFORD J
• Application Number:
  US10/184,870
• Publication Number:
  US 20040003086A1
• Time in Patent Office: 3,392 Days
• Field of Search: 709/226, 709/229
• US Class Current: 709/226
• CPC Class Codes: H04L 61/4552 Lookup mechanisms between a plurality of directories; Synchronisation of directories, e.g. metadirectories
• CPC Class Codes: H04L 67/02 based on web technology, e.g. hypertext transfer protocol [HTTP]
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1023 based on a hash applied to IP addresses or costs
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]

Abstract

A new method and framework for re-partitioning directory servers supporting user services in a site that receives access requests from users. According to the present invention, a management server transfers groups of directory objects from original directory servers to newly added directory servers without service interruption to users of the site. The directory objects are stored in categorical groups such that the directory objects in each group share an attribute. According to the present invention, certain groups in the original directory servers are identified for migration to the newly added servers based on a load-balancing scheme. In one embodiment, the identified groups are marked for migration to limit access to the directory objects therein. After successfully being migration, the groups are unmarked and access is resumed. In another embodiment, the management server includes a table storing location information that is updated to indicate successful transfer of the identified group of directory objects from the original server to the newly added server.

Claims

1. In a distributed network directory, a method for re-partitioning directory servers supporting user services in a site receiving access requests from users for user data, the site comprising the directory servers, where at least a first directory server stores directory objects that include the user data, the directory objects being stored in categorical groups such that the directory objects in each group share an attribute, and a management server communicatively coupled to the directory servers having a table storing information identifying a location for each group of objects, the method comprising the steps of:

identifying a group of directory objects in one of the directory servers for migration to another directory server;

selecting a second directory server capable of storing the identified group of directory objects;

marking the identified group of directory objects to limit, for requests from users directed to reading and/or writing user data stored within respective directory objects, access to the directory objects while transferring the identified group of directory objects to the second directory server, which limits read and/or write access to user data stored in the directory objects of the identified group during a period of time during which the identified group of directory objects is temporarily marked;

transferring the identified group of directory objects from the first directory server to the second directory server;

updating the location information in the table to indicate the identified group of directory objects is located at the second directory server; and

deleting the identified group of directory objects from the first directory server.

2. The method of claim 1 wherein the identified group of directory objects is transferred to the second directory server without service interruption to the users of the site.

3. The method of claim 2 further comprising:

unmarking the identified group of directory objects to permit read and/or write access to the user data within the directory objects after transfer of the identified group of directory objects to the second directory server is completed.

4. The method of claim 3 wherein write access is further limited prior to transferring the identified group of directory objects by denying all requested writes and updates to user data within the directory objects in the identified group of directory objects while the identified group of directory objects is marked.

5. The method of claim 3 wherein read access and write access is limited prior to transferring the identified group of directory objects.

6. The method of claim 1 wherein the step of selecting the second directory server comprises the steps of:

analyzing a distribution of directory objects across the directory servers; and

selecting the second directory server so that the distribution of directory objects is balanced.

7. The method of claim 1 wherein the directory objects comprise user authorization information, the user authorization information comprising user data relating to the users requesting access to the site.

8. The method of claim 7 wherein the user data comprises a unique user ID and password.

9. The method of claim 8 wherein the user data further comprises a notice indicating whether the user requesting access is authorized to access the site.

10. The method of claim 1 wherein the management server further comprises a mapping algorithm utilized to partition the directory objects across the directory servers.

11. The method of claim 10 wherein the mapping algorithm utilizes the user ID to distribute the directory objects across the directory servers.

12. The method of claim 1 wherein the site further comprises a firewall located between the management server and the directory servers, the firewall comprising a security component that filters the access requests from the users.

13. The method of claim 1 wherein the site is a customer oriented management site accessible over the Internet.

14. The method of claim 13 wherein the customer oriented management site accessible over the Internet is a shopping management site.

15. The method of claim 13 wherein the customer oriented management site accessible over the Internet is an e-mail management site.

34. A method as recited in claim 1, wherein identifying a group of directory objects in one of the directory servers for migration to another directory server is done in response to first determining that a number of directory objects in said one of the directory servers has increased to a level that negatively affects usability by users of a corresponding site, wherein the users are accessing user data in the group of directory objects.

35. A method as recited in claim 6, wherein selecting the second directory server so that the distribution of directory objects is balanced comprises selecting the second directory server so that the distribution of directory objects is equal into different hash buckets.

36. A method as recited in claim 1, wherein identifying a group of directory objects in one of the directory servers for migration to another directory server and selecting the second directory server so that the distribution of directory objects is done according to a migration strategy that is based at least in part on minimizing a number of directory objects to be moved.

16. A computer readable storage device having computer-executable instructions for facilitating re-partitioning directory servers supporting user services in a site receiving access requests from users for user data within directory objects, the site comprising the directory servers, where at least a first directory server stores directory objects in categorical groups such that the directory objects in each group share an attribute, and a management server communicatively coupled to the directory servers having a table storing information identifying a location for each group of directory objects, the computer-readable medium having computer-executable instructions facilitating performing the steps of:

identifying a group of directory objects in one of the directory servers for migration to another directory server;

selecting a second directory server capable of storing the identified group of directory objects;

marking the identified group of directory objects to limit, for requests from users directed to reading and/or writing user data stored within respective directory objects, access to the directory objects while transferring the identified group to the second directory server, which limits read and/or write access to user data in the directory objects of the identified group during a period of time during which the identified group is temporarily marked;

transferring the identified group of directory objects from the first directory server to the second directory server;

updating the location information in the table to indicate the identified group of directory objects is located at the second directory server; and

deleting the identified group of directory objects from the first directory server.

17. The computer readable storage device of claim 16 wherein the identified group of directory objects is transferred to the second directory server without service interruption to the users of the site.

18. The computer readable storage device of claim 17 further comprising computer-executable instructions facilitating performing the steps of:

unmarking the identified group of directory objects to permit read and/or write access to the user data within directory objects after transfer of the identified group of directory objects to the second directory server is completed.

19. The computer readable storage device of claim 18 wherein write access is limited prior to transferring the identified group by denying all requested writes and updates to the directory objects in the identified group while the identified group of directory objects is marked.

20. The computer readable storage device of claim 18 wherein read access and write access is limited prior to transferring the identified group of directory objects.

21. The computer readable storage device claim 16 wherein the step of selecting the second directory server further comprises computer-executable instructions facilitating performing the steps of:

analyzing a distribution of directory objects across the directory servers; and

selecting the second directory server so that the distribution of directory objects is balanced.

22. The computer readable storage device of claim 16 wherein the directory objects comprise user authorization information, the user authorization information comprising user data relating to the users requesting access to the site.

23. The computer readable storage device of claim 22 wherein the user data comprises a unique user ID and password.

24. The computer readable storage device of claim 23 wherein the user data further comprises a notice indicating whether the user requesting access is authorized to access the site.

25. The computer readable storage device of claim 16 wherein the management server further comprises a mapping algorithm utilized to partition the directory objects across the directory servers.

26. The computer readable storage device of claim 25 wherein the mapping algorithm utilizes the user ID to distribute the directory objects across the directory servers.

27. The computer readable storage device of claim 16 wherein the site further comprises a firewall located between the management server and the directory servers, the firewall comprising a security component that filters the access requests from the users.

28. The computer readable storage device of claim 16 wherein the site is a customer oriented management site accessible over the Internet.

29. In a distributed network directory, a framework in a site for re-partitioning directory servers, the site communicatively coupled to receive and authorize access requests from users of the site to user data contained within one or more directory objects, the framework comprising:

a set of directory servers comprising;

at least a first directory server for storing user data within directory objects in a number of categorical groups such that the directory objects in each group share an attribute, the first directory having an identified group selected for transfer, the identified group also being marked to indicate that read and/or write access requests by users for user data is limited for the directory objects of the identified group during a period of time during which the identified group of directory objects is temporarily marked and prior to being transferred; and

a second directory server for storing the identified group of directory objects; and

a management server communicatively coupled to the set of directory servers, the management server transferring the identified group of directory objects from the first directory server to the second directory server.

30. The framework of claim 29 wherein the management server transfers the identified group of directory objects from the first directory server to the second directory server without service interruption to user requests made by the users of the site.

31. The framework of claim 29 wherein the management server comprises a table storing information identifying a location for each group of directory objects, the table being updated after transfer of the identified group of directory objects.

32. The framework of claim 29 wherein the number of categorical groups is determined by a mapping function.

33. The framework of claim 32 wherein the mapping function comprises an equation for determining the number of groups, the equation being represented as: