You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@directory.apache.org by ji...@apache.org on 2004/04/19 18:46:53 UTC
[jira] Created: (DIRRMS-22) Need mechanism to find index holes in the bit vector
Message:
A new issue has been created in JIRA.
---------------------------------------------------------------------
View the issue:
http://issues.apache.org/jira/browse/DIRRMS-22
Here is an overview of the issue:
---------------------------------------------------------------------
Key: DIRRMS-22
Summary: Need mechanism to find index holes in the bit vector
Type: Task
Status: Open
Priority: Major
Project: Directory RMS
Components:
Berkeley JE
Assignee: Alex Karasulu
Reporter: Alex Karasulu
Created: Mon, 19 Apr 2004 9:46 AM
Updated: Mon, 19 Apr 2004 9:46 AM
Description:
Right now it's not all that simple to rapidly find the next available bit index to occupy. One would think the secondary indices would help and they do but since all permissions from all applications are involved the problem is not as simple as it seems. At first glance it might appear as though a join would work but we still need to find the smallest available index and so order creeps into the picture taking the option of a join out.
Keep in mind this operation is for write and it need not be that fast since we're optimized for reads. However it still needs to be efficient regardless and fairly straight forward. The most sensible option is to scan the appName:rowId secondary for duplicate appName records on a specific app and build a map to use for finding wholes. What does this map look like?
We need the map to find holes with the smallest index where we can place new BitPermissions. There is no simple means to do this without building the map then scanning it in the order of ascending indices. The map should be sorded by the bit vector index where the index is the key. Since we search for and fill holes we can use the index into an array as the bit vector index without wasting space. Hence the best structure for the map is an int[] or even a String[]. If its an int[] then the map is an index:rowId mapping. If it is a String[] it is an index:name mapping. For the int[] some none viable int value like -1 must be used as the hole marker. In the String[] we can just use null. Yet another option is to just build a BitPermission[].
There are pro's and cons to using the int[] verses the String[]. First off the String[] is and excellent mapping which is needed for Applications anyway. Its like killing to birds with one stone. However it is less efficient. Basically the permissions
---------------------------------------------------------------------
JIRA INFORMATION:
This message is automatically generated by JIRA.
If you think it was sent incorrectly contact one of the administrators:
http://issues.apache.org/jira/secure/Administrators.jspa
If you want more information on JIRA, or have a bug to report see:
http://www.atlassian.com/software/jira
[jira] Updated: (DIRRMS-22) Need mechanism to find index holes in the bit vector
Posted by ji...@apache.org.
The following issue has been updated:
Updater: Alex Karasulu (mailto:aok123@bellsouth.net)
Date: Mon, 19 Apr 2004 6:54 PM
Comment:
Picture of the component we will use for tracking holes and occupied indices within the bit permission vector. The BitPermissionIndexDAO and the BitPermissionIndexManager are depicted in this diagram with their interface methods. The methods are drawn as interface circles even though each circle represent one method on the respective interface.
Changes:
Attachment changed to BitPermissionIndexManager.png
---------------------------------------------------------------------
For a full history of the issue, see:
http://issues.apache.org/jira/browse/DIRRMS-22?page=history
---------------------------------------------------------------------
View the issue:
http://issues.apache.org/jira/browse/DIRRMS-22
Here is an overview of the issue:
---------------------------------------------------------------------
Key: DIRRMS-22
Summary: Need mechanism to find index holes in the bit vector
Type: Task
Status: Open
Priority: Major
Project: Directory RMS
Components:
Berkeley JE
Assignee: Alex Karasulu
Reporter: Alex Karasulu
Created: Mon, 19 Apr 2004 9:46 AM
Updated: Mon, 19 Apr 2004 6:54 PM
Description:
Right now it's not all that simple to rapidly find the next available bit index to occupy. One would think the secondary indices would help and they do but since all permissions from all applications are involved the problem is not as simple as it seems. At first glance it might appear as though a join would work but we still need to find the smallest available index and so order creeps into the picture taking the option of a join out.
Keep in mind this operation is for writes and it need not be that fast since we're optimized for reads. However it still needs to be efficient regardless and fairly straight forward.
---------------------------------------------------------------------
JIRA INFORMATION:
This message is automatically generated by JIRA.
If you think it was sent incorrectly contact one of the administrators:
http://issues.apache.org/jira/secure/Administrators.jspa
If you want more information on JIRA, or have a bug to report see:
http://www.atlassian.com/software/jira
[jira] Commented: (DIRRMS-22) Need mechanism to find index holes in the bit vector
Posted by ji...@apache.org.
The following comment has been added to this issue:
Author: Alex Karasulu
Created: Mon, 19 Apr 2004 6:56 PM
Body:
We're going to use another database all together to manage bit indices. This database needs to be separate because it maps the application name to an index. Entries represent claimed indices that are occupied by valid permissions. The lack of an entry or an index discontinuity represents holes where indices can be claimed for new permissions.
---------------------------------------------------------------------
View this comment:
http://issues.apache.org/jira/browse/DIRRMS-22?page=comments#action_35157
---------------------------------------------------------------------
View the issue:
http://issues.apache.org/jira/browse/DIRRMS-22
Here is an overview of the issue:
---------------------------------------------------------------------
Key: DIRRMS-22
Summary: Need mechanism to find index holes in the bit vector
Type: Task
Status: Open
Priority: Major
Project: Directory RMS
Components:
Berkeley JE
Assignee: Alex Karasulu
Reporter: Alex Karasulu
Created: Mon, 19 Apr 2004 9:46 AM
Updated: Mon, 19 Apr 2004 6:56 PM
Description:
Right now it's not all that simple to rapidly find the next available bit index to occupy. One would think the secondary indices would help and they do but since all permissions from all applications are involved the problem is not as simple as it seems. At first glance it might appear as though a join would work but we still need to find the smallest available index and so order creeps into the picture taking the option of a join out.
Keep in mind this operation is for writes and it need not be that fast since we're optimized for reads. However it still needs to be efficient regardless and fairly straight forward.
---------------------------------------------------------------------
JIRA INFORMATION:
This message is automatically generated by JIRA.
If you think it was sent incorrectly contact one of the administrators:
http://issues.apache.org/jira/secure/Administrators.jspa
If you want more information on JIRA, or have a bug to report see:
http://www.atlassian.com/software/jira
[jira] Updated: (DIRRMS-22) Need mechanism to find index holes in the bit vector
Posted by ji...@apache.org.
The following issue has been updated:
Updater: Alex Karasulu (mailto:aok123@bellsouth.net)
Date: Mon, 19 Apr 2004 12:23 PM
Changes:
description changed from Right now it's not all that simple to rapidly find the next available bit index to occupy. One would think the secondary indices would help and they do but since all permissions from all applications are involved the problem is not as simple as it seems. At first glance it might appear as though a join would work but we still need to find the smallest available index and so order creeps into the picture taking the option of a join out.
Keep in mind this operation is for write and it need not be that fast since we're optimized for reads. However it still needs to be efficient regardless and fairly straight forward. The most sensible option is to scan the appName:rowId secondary for duplicate appName records on a specific app and build a map to use for finding wholes. What does this map look like?
We need the map to find holes with the smallest index where we can place new BitPermissions. There is no simple means to do this without building the map then scanning it in the order of ascending indices. The map should be sorded by the bit vector index where the index is the key. Since we search for and fill holes we can use the index into an array as the bit vector index without wasting space. Hence the best structure for the map is an int[] or even a String[]. If its an int[] then the map is an index:rowId mapping. If it is a String[] it is an index:name mapping. For the int[] some none viable int value like -1 must be used as the hole marker. In the String[] we can just use null. Yet another option is to just build a BitPermission[].
There are pro's and cons to using the int[] verses the String[]. First off the String[] is and excellent mapping which is needed for Applications anyway. Its like killing to birds with one stone. However it is less efficient. Basically the permissions
to Right now it's not all that simple to rapidly find the next available bit index to occupy. One would think the secondary indices would help and they do but since all permissions from all applications are involved the problem is not as simple as it seems. At first glance it might appear as though a join would work but we still need to find the smallest available index and so order creeps into the picture taking the option of a join out.
Keep in mind this operation is for writes and it need not be that fast since we're optimized for reads. However it still needs to be efficient regardless and fairly straight forward.
---------------------------------------------------------------------
For a full history of the issue, see:
http://issues.apache.org/jira/browse/DIRRMS-22?page=history
---------------------------------------------------------------------
View the issue:
http://issues.apache.org/jira/browse/DIRRMS-22
Here is an overview of the issue:
---------------------------------------------------------------------
Key: DIRRMS-22
Summary: Need mechanism to find index holes in the bit vector
Type: Task
Status: Open
Priority: Major
Project: Directory RMS
Components:
Berkeley JE
Assignee: Alex Karasulu
Reporter: Alex Karasulu
Created: Mon, 19 Apr 2004 9:46 AM
Updated: Mon, 19 Apr 2004 12:23 PM
Description:
Right now it's not all that simple to rapidly find the next available bit index to occupy. One would think the secondary indices would help and they do but since all permissions from all applications are involved the problem is not as simple as it seems. At first glance it might appear as though a join would work but we still need to find the smallest available index and so order creeps into the picture taking the option of a join out.
Keep in mind this operation is for writes and it need not be that fast since we're optimized for reads. However it still needs to be efficient regardless and fairly straight forward.
---------------------------------------------------------------------
JIRA INFORMATION:
This message is automatically generated by JIRA.
If you think it was sent incorrectly contact one of the administrators:
http://issues.apache.org/jira/secure/Administrators.jspa
If you want more information on JIRA, or have a bug to report see:
http://www.atlassian.com/software/jira
[jira] Closed: (DIRRMS-22) Need mechanism to find index holes in the bit vector
Posted by ji...@apache.org.
Message:
The following issue has been closed.
Resolver: Alex Karasulu
Date: Wed, 21 Apr 2004 6:15 PM
Goods checked in with revision 10160.
---------------------------------------------------------------------
View the issue:
http://issues.apache.org/jira/browse/DIRRMS-22
Here is an overview of the issue:
---------------------------------------------------------------------
Key: DIRRMS-22
Summary: Need mechanism to find index holes in the bit vector
Type: Task
Status: Closed
Priority: Major
Resolution: FIXED
Project: Directory RMS
Components:
Berkeley JE
Assignee: Alex Karasulu
Reporter: Alex Karasulu
Created: Mon, 19 Apr 2004 9:46 AM
Updated: Wed, 21 Apr 2004 6:15 PM
Description:
Right now it's not all that simple to rapidly find the next available bit index to occupy. One would think the secondary indices would help and they do but since all permissions from all applications are involved the problem is not as simple as it seems. At first glance it might appear as though a join would work but we still need to find the smallest available index and so order creeps into the picture taking the option of a join out.
Keep in mind this operation is for writes and it need not be that fast since we're optimized for reads. However it still needs to be efficient regardless and fairly straight forward.
---------------------------------------------------------------------
JIRA INFORMATION:
This message is automatically generated by JIRA.
If you think it was sent incorrectly contact one of the administrators:
http://issues.apache.org/jira/secure/Administrators.jspa
If you want more information on JIRA, or have a bug to report see:
http://www.atlassian.com/software/jira
[jira] Updated: (DIRRMS-22) Need mechanism to find index holes in the bit vector
Posted by ji...@apache.org.
The following issue has been updated:
Updater: Alex Karasulu (mailto:aok123@bellsouth.net)
Date: Mon, 19 Apr 2004 6:51 PM
Changes:
Comment was deleted.
---------------------------------------------------------------------
For a full history of the issue, see:
http://issues.apache.org/jira/browse/DIRRMS-22?page=history
---------------------------------------------------------------------
View the issue:
http://issues.apache.org/jira/browse/DIRRMS-22
Here is an overview of the issue:
---------------------------------------------------------------------
Key: DIRRMS-22
Summary: Need mechanism to find index holes in the bit vector
Type: Task
Status: Open
Priority: Major
Project: Directory RMS
Components:
Berkeley JE
Assignee: Alex Karasulu
Reporter: Alex Karasulu
Created: Mon, 19 Apr 2004 9:46 AM
Updated: Mon, 19 Apr 2004 6:51 PM
Description:
Right now it's not all that simple to rapidly find the next available bit index to occupy. One would think the secondary indices would help and they do but since all permissions from all applications are involved the problem is not as simple as it seems. At first glance it might appear as though a join would work but we still need to find the smallest available index and so order creeps into the picture taking the option of a join out.
Keep in mind this operation is for writes and it need not be that fast since we're optimized for reads. However it still needs to be efficient regardless and fairly straight forward.
---------------------------------------------------------------------
JIRA INFORMATION:
This message is automatically generated by JIRA.
If you think it was sent incorrectly contact one of the administrators:
http://issues.apache.org/jira/secure/Administrators.jspa
If you want more information on JIRA, or have a bug to report see:
http://www.atlassian.com/software/jira
[jira] Commented: (DIRRMS-22) Need mechanism to find index holes in the bit vector
Posted by ji...@apache.org.
The following comment has been added to this issue:
Author: Alex Karasulu
Created: Mon, 19 Apr 2004 12:35 PM
Body:
Holes need to be filled within bit permissions database.
rowIds values
| |
| |
V V Hole at index 2
--
|1|*|---> perm at index 0
|2|*|---> perm at index 1
|4|*|---> perm at index 3
|5|*|---> perm at index 4
| | |
| | |
--
rowIds values
| |
| |
V V Hole filled!
--
|1|*|---> perm at index 0
|2|*|---> perm at index 1
|4|*|---> perm at index 3
|5|*|---> perm at index 4
|6|*|---> perm at index 2
| | |
--
---------------------------------------------------------------------
View this comment:
http://issues.apache.org/jira/browse/DIRRMS-22?page=comments#action_35152
---------------------------------------------------------------------
View the issue:
http://issues.apache.org/jira/browse/DIRRMS-22
Here is an overview of the issue:
---------------------------------------------------------------------
Key: DIRRMS-22
Summary: Need mechanism to find index holes in the bit vector
Type: Task
Status: Open
Priority: Major
Project: Directory RMS
Components:
Berkeley JE
Assignee: Alex Karasulu
Reporter: Alex Karasulu
Created: Mon, 19 Apr 2004 9:46 AM
Updated: Mon, 19 Apr 2004 12:35 PM
Description:
Right now it's not all that simple to rapidly find the next available bit index to occupy. One would think the secondary indices would help and they do but since all permissions from all applications are involved the problem is not as simple as it seems. At first glance it might appear as though a join would work but we still need to find the smallest available index and so order creeps into the picture taking the option of a join out.
Keep in mind this operation is for writes and it need not be that fast since we're optimized for reads. However it still needs to be efficient regardless and fairly straight forward.
---------------------------------------------------------------------
JIRA INFORMATION:
This message is automatically generated by JIRA.
If you think it was sent incorrectly contact one of the administrators:
http://issues.apache.org/jira/secure/Administrators.jspa
If you want more information on JIRA, or have a bug to report see:
http://www.atlassian.com/software/jira