You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@jackrabbit.apache.org by "Jukka Zitting (JIRA)" <ji...@apache.org> on 2010/09/28 18:08:33 UTC

[jira] Created: (JCR-2760) Use hash codes instead of sequence numbers for string indexes

Use hash codes instead of sequence numbers for string indexes
-------------------------------------------------------------

                 Key: JCR-2760
                 URL: https://issues.apache.org/jira/browse/JCR-2760
             Project: Jackrabbit Content Repository
          Issue Type: Improvement
          Components: jackrabbit-core
            Reporter: Jukka Zitting
            Priority: Minor


We use index numbers instead of namespace URIs or other strings in many places. The two-way mapping between namespace URIs and index numbers is by default stored in the repository-global ns_idx.properties file, and the index numbers are allocated using a linear sequence. The problem with this approach is that two repositories will easily end up with different string index mappings, which makes it practically impossible to make low-level copies of workspace content across repositories.

The ultimate solution for this problem would be to store the namespace URIs closer to the stored content, ideally as an implementation detail of a persistence manager.

An easier short-term solution would be to decrease the chances of two repositories having different string index mappings. A simple (and backwards-compatible) way to do this is to use the hash code of a namespace URI as the basis of allocating a new index number. Hash collisions are fairly unlikely, and can be handled by incrementing the intial hash code until the collision is avoided. In the common case of no collisions (with a uniform hash function the chance of a collision is less than 1% even with tousands of registered namespaces) this solution allows workspaces to be copied between repositories without worrying about the namespace index mappings.

-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


[jira] Commented: (JCR-2760) Use hash codes instead of sequence numbers for string indexes

Posted by "Sébastien Launay (JIRA)" <ji...@apache.org>.
    [ https://issues.apache.org/jira/browse/JCR-2760?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12918447#action_12918447 ] 

Sébastien Launay commented on JCR-2760:
---------------------------------------

These changes are interesting for low-level copies of workspace content across repositories but also for clustering because it was possible to have collision between indexes for the same namespace on two nodes. 

I agree with Thomas that a different solution should be considered in JR 3  for sharing namespaces (maybe also for nodetypes) especially for cluster nodes (see JCR-1558).


> Use hash codes instead of sequence numbers for string indexes
> -------------------------------------------------------------
>
>                 Key: JCR-2760
>                 URL: https://issues.apache.org/jira/browse/JCR-2760
>             Project: Jackrabbit Content Repository
>          Issue Type: Improvement
>          Components: jackrabbit-core
>            Reporter: Jukka Zitting
>            Assignee: Jukka Zitting
>            Priority: Minor
>             Fix For: 2.2.0
>
>         Attachments: 0001-JCR-2760-Use-hash-codes-instead-of-sequence-numbers.patch
>
>
> We use index numbers instead of namespace URIs or other strings in many places. The two-way mapping between namespace URIs and index numbers is by default stored in the repository-global ns_idx.properties file, and the index numbers are allocated using a linear sequence. The problem with this approach is that two repositories will easily end up with different string index mappings, which makes it practically impossible to make low-level copies of workspace content across repositories.
> The ultimate solution for this problem would be to store the namespace URIs closer to the stored content, ideally as an implementation detail of a persistence manager.
> An easier short-term solution would be to decrease the chances of two repositories having different string index mappings. A simple (and backwards-compatible) way to do this is to use the hash code of a namespace URI as the basis of allocating a new index number. Hash collisions are fairly unlikely, and can be handled by incrementing the intial hash code until the collision is avoided. In the common case of no collisions (with a uniform hash function the chance of a collision is less than 1% even with tousands of registered namespaces) this solution allows workspaces to be copied between repositories without worrying about the namespace index mappings.

-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


[jira] Commented: (JCR-2760) Use hash codes instead of sequence numbers for string indexes

Posted by "Thomas Mueller (JIRA)" <ji...@apache.org>.
    [ https://issues.apache.org/jira/browse/JCR-2760?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12917912#action_12917912 ] 

Thomas Mueller commented on JCR-2760:
-------------------------------------

+1

looks good to me for Jackrabbit 2.x. I think for Jackrabbit 3 we should use a different solution (if we still want to use a name index it shouldn't be global). But that's something we can discuss later.

I guess in most cases there are only few namespaces (typically less than 100). For the name index (property names) I'm not sure.

> Use hash codes instead of sequence numbers for string indexes
> -------------------------------------------------------------
>
>                 Key: JCR-2760
>                 URL: https://issues.apache.org/jira/browse/JCR-2760
>             Project: Jackrabbit Content Repository
>          Issue Type: Improvement
>          Components: jackrabbit-core
>            Reporter: Jukka Zitting
>            Assignee: Jukka Zitting
>            Priority: Minor
>             Fix For: 2.2.0
>
>         Attachments: 0001-JCR-2760-Use-hash-codes-instead-of-sequence-numbers.patch
>
>
> We use index numbers instead of namespace URIs or other strings in many places. The two-way mapping between namespace URIs and index numbers is by default stored in the repository-global ns_idx.properties file, and the index numbers are allocated using a linear sequence. The problem with this approach is that two repositories will easily end up with different string index mappings, which makes it practically impossible to make low-level copies of workspace content across repositories.
> The ultimate solution for this problem would be to store the namespace URIs closer to the stored content, ideally as an implementation detail of a persistence manager.
> An easier short-term solution would be to decrease the chances of two repositories having different string index mappings. A simple (and backwards-compatible) way to do this is to use the hash code of a namespace URI as the basis of allocating a new index number. Hash collisions are fairly unlikely, and can be handled by incrementing the intial hash code until the collision is avoided. In the common case of no collisions (with a uniform hash function the chance of a collision is less than 1% even with tousands of registered namespaces) this solution allows workspaces to be copied between repositories without worrying about the namespace index mappings.

-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


[jira] Commented: (JCR-2760) Use hash codes instead of sequence numbers for string indexes

Posted by "Marcel Reutegger (JIRA)" <ji...@apache.org>.
    [ https://issues.apache.org/jira/browse/JCR-2760?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12916157#action_12916157 ] 

Marcel Reutegger commented on JCR-2760:
---------------------------------------

+1

looks good to me.

> Use hash codes instead of sequence numbers for string indexes
> -------------------------------------------------------------
>
>                 Key: JCR-2760
>                 URL: https://issues.apache.org/jira/browse/JCR-2760
>             Project: Jackrabbit Content Repository
>          Issue Type: Improvement
>          Components: jackrabbit-core
>            Reporter: Jukka Zitting
>            Priority: Minor
>         Attachments: 0001-JCR-2760-Use-hash-codes-instead-of-sequence-numbers.patch
>
>
> We use index numbers instead of namespace URIs or other strings in many places. The two-way mapping between namespace URIs and index numbers is by default stored in the repository-global ns_idx.properties file, and the index numbers are allocated using a linear sequence. The problem with this approach is that two repositories will easily end up with different string index mappings, which makes it practically impossible to make low-level copies of workspace content across repositories.
> The ultimate solution for this problem would be to store the namespace URIs closer to the stored content, ideally as an implementation detail of a persistence manager.
> An easier short-term solution would be to decrease the chances of two repositories having different string index mappings. A simple (and backwards-compatible) way to do this is to use the hash code of a namespace URI as the basis of allocating a new index number. Hash collisions are fairly unlikely, and can be handled by incrementing the intial hash code until the collision is avoided. In the common case of no collisions (with a uniform hash function the chance of a collision is less than 1% even with tousands of registered namespaces) this solution allows workspaces to be copied between repositories without worrying about the namespace index mappings.

-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


[jira] Resolved: (JCR-2760) Use hash codes instead of sequence numbers for string indexes

Posted by "Jukka Zitting (JIRA)" <ji...@apache.org>.
     [ https://issues.apache.org/jira/browse/JCR-2760?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Jukka Zitting resolved JCR-2760.
--------------------------------

       Resolution: Fixed
    Fix Version/s: 2.2.0
         Assignee: Jukka Zitting

Patch committed in revision 1004568.

The restriction to 24 bits is an unfortunate side-effect of the way the bundle serialization format chops off the first eight bits from the namespace index of the name of the primary type of a node. As mentioned by Thomas, this has a notable effect on the likelihood of collisions, but that seems OK since this only affects the non-standard use case of copying raw workspace data between repositories and even there the chance of problems is pretty low for reasonably sized repositories.

A more complete solution would be to drop the use of namespace and name indexes in favour of a more efficient serialization format.

> Use hash codes instead of sequence numbers for string indexes
> -------------------------------------------------------------
>
>                 Key: JCR-2760
>                 URL: https://issues.apache.org/jira/browse/JCR-2760
>             Project: Jackrabbit Content Repository
>          Issue Type: Improvement
>          Components: jackrabbit-core
>            Reporter: Jukka Zitting
>            Assignee: Jukka Zitting
>            Priority: Minor
>             Fix For: 2.2.0
>
>         Attachments: 0001-JCR-2760-Use-hash-codes-instead-of-sequence-numbers.patch
>
>
> We use index numbers instead of namespace URIs or other strings in many places. The two-way mapping between namespace URIs and index numbers is by default stored in the repository-global ns_idx.properties file, and the index numbers are allocated using a linear sequence. The problem with this approach is that two repositories will easily end up with different string index mappings, which makes it practically impossible to make low-level copies of workspace content across repositories.
> The ultimate solution for this problem would be to store the namespace URIs closer to the stored content, ideally as an implementation detail of a persistence manager.
> An easier short-term solution would be to decrease the chances of two repositories having different string index mappings. A simple (and backwards-compatible) way to do this is to use the hash code of a namespace URI as the basis of allocating a new index number. Hash collisions are fairly unlikely, and can be handled by incrementing the intial hash code until the collision is avoided. In the common case of no collisions (with a uniform hash function the chance of a collision is less than 1% even with tousands of registered namespaces) this solution allows workspaces to be copied between repositories without worrying about the namespace index mappings.

-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


[jira] Commented: (JCR-2760) Use hash codes instead of sequence numbers for string indexes

Posted by "Thomas Mueller (JIRA)" <ji...@apache.org>.
    [ https://issues.apache.org/jira/browse/JCR-2760?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12916051#action_12916051 ] 

Thomas Mueller commented on JCR-2760:
-------------------------------------

I'm not sure if this is really a big problem, so this is just FYI: With 24 bit, the probability of collision is higher. With 1024 entries, the probability is about 3%. The 1% Jukka mentioned is correct for 32 bit. The same formula as for UUIDs applies, see also http://en.wikipedia.org/wiki/Universally_unique_identifier and http://www.h2database.com/html/advanced.html#uuid

2^5=32 probability: 0.003051711246848665%
2^6=64 probability: 0.012206286222260498%
2^7=128 probability: 0.04881620601105974%
2^8=256 probability: 0.19512188925244756%
2^9=512 probability: 0.7782061739756485%
2^10=1024 probability: 3.076676552365587%
2^11=2048 probability: 11.750309741540455%
2^12=4096 probability: 39.346934028736655%
2^13=8192 probability: 86.46647167633873%
2^14=16384 probability: 99.96645373720975%

double x = Math.pow(2, 24);
for (int i = 5; i < 15; i++) {
    double n = Math.pow(2, i);
    double p = 1 - Math.exp(-(n * n) / 2 / x);
    System.out.println("2^" + i + "=" + (1L << i) +
            " probability: " + (p * 100) + "%");
}



> Use hash codes instead of sequence numbers for string indexes
> -------------------------------------------------------------
>
>                 Key: JCR-2760
>                 URL: https://issues.apache.org/jira/browse/JCR-2760
>             Project: Jackrabbit Content Repository
>          Issue Type: Improvement
>          Components: jackrabbit-core
>            Reporter: Jukka Zitting
>            Priority: Minor
>         Attachments: 0001-JCR-2760-Use-hash-codes-instead-of-sequence-numbers.patch
>
>
> We use index numbers instead of namespace URIs or other strings in many places. The two-way mapping between namespace URIs and index numbers is by default stored in the repository-global ns_idx.properties file, and the index numbers are allocated using a linear sequence. The problem with this approach is that two repositories will easily end up with different string index mappings, which makes it practically impossible to make low-level copies of workspace content across repositories.
> The ultimate solution for this problem would be to store the namespace URIs closer to the stored content, ideally as an implementation detail of a persistence manager.
> An easier short-term solution would be to decrease the chances of two repositories having different string index mappings. A simple (and backwards-compatible) way to do this is to use the hash code of a namespace URI as the basis of allocating a new index number. Hash collisions are fairly unlikely, and can be handled by incrementing the intial hash code until the collision is avoided. In the common case of no collisions (with a uniform hash function the chance of a collision is less than 1% even with tousands of registered namespaces) this solution allows workspaces to be copied between repositories without worrying about the namespace index mappings.

-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


[jira] Updated: (JCR-2760) Use hash codes instead of sequence numbers for string indexes

Posted by "Jukka Zitting (JIRA)" <ji...@apache.org>.
     [ https://issues.apache.org/jira/browse/JCR-2760?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Jukka Zitting updated JCR-2760:
-------------------------------

    Attachment: 0001-JCR-2760-Use-hash-codes-instead-of-sequence-numbers.patch

The attached patch implements the proposed solution.

It turned out that the BundleBinding class uses only 24 bits of the index number, so this implementation does the same when allocating the index numbers.

The solution is fully backwards compatible with existing repositories (existing index numbers are used as-is), and avoids hash collisions by explicitly incrementing the index number until no collision occurs.

> Use hash codes instead of sequence numbers for string indexes
> -------------------------------------------------------------
>
>                 Key: JCR-2760
>                 URL: https://issues.apache.org/jira/browse/JCR-2760
>             Project: Jackrabbit Content Repository
>          Issue Type: Improvement
>          Components: jackrabbit-core
>            Reporter: Jukka Zitting
>            Priority: Minor
>         Attachments: 0001-JCR-2760-Use-hash-codes-instead-of-sequence-numbers.patch
>
>
> We use index numbers instead of namespace URIs or other strings in many places. The two-way mapping between namespace URIs and index numbers is by default stored in the repository-global ns_idx.properties file, and the index numbers are allocated using a linear sequence. The problem with this approach is that two repositories will easily end up with different string index mappings, which makes it practically impossible to make low-level copies of workspace content across repositories.
> The ultimate solution for this problem would be to store the namespace URIs closer to the stored content, ideally as an implementation detail of a persistence manager.
> An easier short-term solution would be to decrease the chances of two repositories having different string index mappings. A simple (and backwards-compatible) way to do this is to use the hash code of a namespace URI as the basis of allocating a new index number. Hash collisions are fairly unlikely, and can be handled by incrementing the intial hash code until the collision is avoided. In the common case of no collisions (with a uniform hash function the chance of a collision is less than 1% even with tousands of registered namespaces) this solution allows workspaces to be copied between repositories without worrying about the namespace index mappings.

-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.