Actually, I believe that Transarc is right that it will be a performance degradation, with the current protection database layout. Reason: the most-often called function is GetCPS, which basically gets the group membership of a user. This is called by the fileserver LOTS of times. Basically, the structure of the protection database is such that you will have to seek once to get the list of primary groups the user is in, and then seek to each part of the database and retrieve any groups that each of those groups are a member of, etc. We are now down >From an O(1) to worse than O(n). It would make sense if the prdb were restructured so that memberships were not just groups, but also a tag. The tag could then indicate whether this group was a member of other groups, and avoid unnecessary searching of leaf nodes. It would be even better if the prdb encodes the membership as a flattened list of direct and indirect memberships. This would keep the O(1) property, and only slow down updating the prdb, but that is ok since updates are in the noise compared with CPS retrievals. By the way, I have implemented groups within groups locally, but have not yet decided whether it is safe to turn on given our protection database load (command-line switch). It is very easy to write code that will avoid recursion. The basic functions that will need to be modified in the protection server are: PR_AddToGroup, PR_RemoveFromGroup, IsAMemberOf, and PR_GetCPS. -Richard ------- Forwarded transaction [1605] [EMAIL PROTECTED] (Peter Lister, Cranfield Computer C) Info-AFS_Redistribution 05/04/93 07:45 (45 lines) Subject: Groups of groups (and efficiency thereof) To: [EMAIL PROTECTED] Cc: [EMAIL PROTECTED] Date: Tue, 04 May 93 10:57:51 BST From: "Peter Lister, Cranfield Computer Centre" <[EMAIL PROTECTED]> Those of you with long memories may remember discussing groups of groups in July last year, when I asked Transarc to consider the problem. The answers I got from most people seemed to try to tell me that while GOGs might be nice from the management point of view, they would slow the pt server unacceptably. This has been repeated recently I don't agree. GOGs reduce system administration and should make the protection database SMALLER and (if anything) FASTER. It's a basic characteristic of efficient search algorithms that they arrange items in trees so that search times depend on the log of the number of elements. Please don't tell me that arranging my AFS users in a sensible tree structure will make it significantly slower to use. OK, so it's possible to have a build pathologically bad group structure which would be slow to search, but I'm not going to do that, am I? There's no point. Similarly, it would be possible for Transarc to implement the above inefficiently, but I hope they wouldn't do that either. Furthermore, the vast majority of our users are students whose activity is almost solely within a particular group, department or school. In terms of applying ACLs, they rarely exist as individuals. It makes no sense to add individual users repeatedly to different groups for (say) access to a particular package when they will only ever be managed in bulk as part of their department or project group. Eliminating this repetition makes a smaller database. Yes, GOGs will probably require more work as each entry needs more consistency checking as it is added to the db. BUT since the total number of entrys in large groups will fall drastically, so will the number of db additions. For large groups, this will drop from thousands to dozens, so I'm quite happy with this tradeoff. Anyone care to prove me wrong? Please, Transarc, we really need this, and we can't hack AFS source like UMich. Peter Lister [EMAIL PROTECTED] Computer Centre, Cranfield Institute of Technology, Voice: +44 234 754200 ext 2828 Cranfield, Bedfordshire MK43 0AL England Fax: +44 234 750875 --[1605]-- ------- End forwarded transaction
