You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@jackrabbit.apache.org by Thomas Mueller <mu...@adobe.com> on 2010/12/22 09:51:48 UTC

[jr3] Sequential Node Ids

Currently, Jackrabbit uses random node ids (randomly generated UUIDs). For Jackrabbit 3, and possibly Jackrabbit 2.x, I propose to use sequential node ids.

The main advantages for random node ids (the default) are: it's easy to develop, and merging data from multiple repositories is simple.

The disadvantages for random node ids are performance and space. With performance, I don't mean that randomly generated UUIDs are slower to generate (they are). I mean performance to read and write data to disk. The main performance problem is reading and writing (indexing) random keys, which is slow because adjacent (nearby) nodes data aren't adjacent in the index. This slows down index access (read and write) a lot, specially if the data doesn't fit in the buffer cache (file system cache).

I wrote a simple test case for Jackrabbit trunk. I also patched Jackrabbit to allow sequential UUIDs. Creating 1 million nodes is about 80% faster when using sequential UUIDs instead of random UUIDs. I don't have the data yet, but I'm sure the difference is much, much bigger when reading from larger repositories once the data doesn't fit in RAM (10 million nodes or so). I will expand the test case to support reading.

The following diagram is the operations per second (bigger is better) after inserting x nodes (0 to 1 million). With sequential UUIDs, performance gets better and then stays the same (which is expected). For random UUIDs which are now the default, performance first goes up and then down. The resulting database (I used H2 for performance) was about 145 MB for sequential UUIDs and 169 MB for random UUIDs (the reason for this difference is that the b-tree fill factor is better for sequential UUIDs). All the data still fits in the buffer cache of the file system without problem.

[cid:82D27269-8424-4062-B68F-568E482436D3]


Something else I noticed when running the test case was that the Jackrabbit internals are relatively slow.  When profiling the test case, I saw that database access is not an important factor. Creating the nodes with the JCR API took 285 / 526 seconds, and re-creating the database from a SQL script took 55 seconds (this includes reading the 200 MB SQL script file and parsing the SQL statements, one insert statement per row; this is for the random UUIDs). I would expect Jackrabbit is faster than 55 seconds, because it doesn't have to read the SQL script from disk and parse statements.

The test case creates 1 million nodes, saves after each 10'000 nodes, and uses a fan-out of 20 child nodes per node. I disabled the search index in the repository configuration. Source code:



import java.io.File;

import javax.jcr.Node;

import javax.jcr.Session;

import javax.jcr.SimpleCredentials;

import org.apache.commons.io.FileUtils;

import org.apache.jackrabbit.core.TransientRepository;

import org.apache.jackrabbit.core.id.NodeId;


public class TestLoop {


    long start;

    Profiler prof;


    public static void main(String... args) throws Exception {

        new TestLoop().run();

    }


    void startProf() {

//        if(prof != null) {

//            prof.stopCollecting();

//            System.out.println(prof.getTop(3));

//        }

//        prof = new Profiler();

//        prof.interval = 1;

//        prof.depth = 32;

//        prof.startCollecting();

    }


    void run() throws Exception {

        System.setProperty("jackrabbit.sequentialUUIDs", "false");

        startProf();

        FileUtils.deleteDirectory(new File("repository"));

        FileUtils.copyFile(new File("repository copy.xml"),

                new File("repository.xml"));

        TransientRepository rep = new TransientRepository();

        Session s = rep.login(

                new SimpleCredentials("admin", "admin".toCharArray()));

        int nodes = 1000000;

        int nodesPerFolder = 20;

        int saveEach = 10000;

        System.out.println(new NodeId());

        int levels = (int) Math.ceil(Math.log(nodes)

                / Math.log(nodesPerFolder));

        start = System.currentTimeMillis();

        startProf();

        createNodes(s.getRootNode(), 0, nodes,

                saveEach, levels, nodesPerFolder);

        System.out.println("took: " + (System.currentTimeMillis() - start));

        s.logout();

    }


    private int createNodes(Node parent, int x, int nodes,

            int saveEach, int depth, int nodesPerFolder)

            throws Exception {

        for (int i = 0; x < nodes && i < nodesPerFolder; i++) {

            if (depth > 1) {

                Node n = parent.addNode("f" + x, "nt:unstructured");

                x = createNodes(n, x, nodes,

                        saveEach, depth - 1, nodesPerFolder);

            } else {

                parent.addNode("n" + i, "nt:unstructured");

                x++;

                if ((x % saveEach) == 0) {

                    parent.getSession().save();

                    long t = System.currentTimeMillis() - start;

                    startProf();

                    System.out.println((x * 1000L / t) + " op/s at " + x);

                }

            }

        }

        return x;

    }

}





Re: [jr3] Sequential Node Ids

Posted by Thomas Mueller <mu...@adobe.com>.
Hi,

I agree this is not a real world test. I will try to create one. It's true, with many CRUD operations applied randomly over the whole repository the difference is much smaller, but I doubt that this would be a real world use case. I would expect some kind of clustered access (create a few nodes at a time, so that so nodes that are created within the same transaction are also often accessed at a similar time later on).

I made another test with 10 million nodes and Apache Derby. In the diagrams below, higher is better. This time I measured writing, reading, and additionally purging the buffer cache (using "purge" on Mac OS) and then reading. The lines show the cumulative number of operations per second (I know, I should have used local number of operations per second, my fault). The weird "L" in the first diagram means there was some kind of pause after about 3.6 million rows, which I can't explain (maybe my computer froze for a few seconds, or maybe a Derby issue). It doesn't mean the database got slower from then on, it only means there was a pause then.

When appending nodes, using random node ids (like we do now) is a clear disadvantage (when using a regular database to store data). The larger the repository, the worse. When using sequential node ids, performance stays the same. This alone would be enough reason to use sequential node ids.

Reading from the repository is slower, much slower in fact if the buffer cache is empty (after a restart).

I suggest that we support sequential node ids for Jackrabbit 2.x (support both random node ids and sequential ids), and use sequential ids by default in future versions. We need to support clustering in some way. A simple solution is to use a factor plus a cluster id by default (nodeId = nextNodeIdForThisClusterNode++ * clusterNodeCount + clusterNodeId) or a "next node id" sequence generator (when a cluster node needs a new id, it increased the global stored sequence generator value by 100 or so).

For Jackrabbit 3.x we might want to provide more features, for example let the persistence layer plus the session decide what node ids (if at all) to use. And we might want to allow changing the node ids later on (defragmentation) to improve performance. Or use less node ids (group nodes together).

Regards,
Thomas



[cid:2EA7FC83-C087-44E8-9C24-35604DCEE675]





On 12/23/10 3:00 PM, "Michael Dürig" <md...@apache.org>> wrote:


Hi Thomas,

I think these are interesting graphs and they show that we do not
exploit locality sufficiently when persisting nodes. However, your
results base on the underlying assumption that sequential node ids lead
to better locality than random node ids do. In general this will depends
on the access pattern and the underlying persistence store: While for
the append only case sequential node ids might exhibit good locality,
for large repositories with many random CRUD operations this approach
might eventually degenerate to behavior similar to random node ids.

I suggest to abstract node ids from storage ids: the node id is an
identifier for retrieving nodes from JCR. A storage id is an identifier
which is used by the persistence store to retrieve a certain piece of
data (which could contain a node, part of a node or multiple nodes). A
mapping from nodes ids to storage ids can then be used to tune locality:
i.e. sequential vs. random, optimal block size etc.

Michael

On 22.12.10 9:51, Thomas Mueller wrote:
Currently, Jackrabbit uses random node ids (randomly generated UUIDs).
For Jackrabbit 3, and possibly Jackrabbit 2.x, I propose to use
sequential node ids.

The main advantages for random node ids (the default) are: it's easy to
develop, and merging data from multiple repositories is simple.

The disadvantages for random node ids are performance and space. With
performance, I don't mean that randomly generated UUIDs are slower to
generate (they are). I mean performance to read and write data to disk.
The main performance problem is reading and writing (indexing) random
keys, which is slow because adjacent (nearby) nodes data aren't adjacent
in the index. This slows down index access (read and write) a lot,
specially if the data doesn't fit in the buffer cache (file system cache).

I wrote a simple test case for Jackrabbit trunk. I also patched
Jackrabbit to allow sequential UUIDs. Creating 1 million nodes is about
80% faster when using sequential UUIDs instead of random UUIDs. I don't
have the data yet, but I'm sure the difference is much, much bigger when
reading from larger repositories once the data doesn't fit in RAM (10
million nodes or so). I will expand the test case to support reading.

The following diagram is the operations per second (bigger is better)
after inserting x nodes (0 to 1 million). With sequential UUIDs,
performance gets better and then stays the same (which is expected). For
random UUIDs which are now the default, performance first goes up and
then down. The resulting database (I used H2 for performance) was about
145 MB for sequential UUIDs and 169 MB for random UUIDs (the reason for
this difference is that the b-tree fill factor is better for sequential
UUIDs). All the data still fits in the buffer cache of the file system
without problem.



Something else I noticed when running the test case was that the
Jackrabbit internals are relatively slow. When profiling the test case,
I saw that database access is not an important factor. Creating the
nodes with the JCR API took 285 / 526 seconds, and re-creating the
database from a SQL script took 55 seconds (this includes reading the
200 MB SQL script file and parsing the SQL statements, one insert
statement per row; this is for the random UUIDs). I would expect
Jackrabbit is faster than 55 seconds, because it doesn't have to read
the SQL script from disk and parse statements.

The test case creates 1 million nodes, saves after each 10'000 nodes,
and uses a fan-out of 20 child nodes per node. I disabled the search
index in the repository configuration. Source code:


*import* java.io.File;

*import* javax.jcr.Node;

*import* javax.jcr.Session;

*import* javax.jcr.SimpleCredentials;

*import* org.apache.commons.io.FileUtils;

*import* org.apache.jackrabbit.core.TransientRepository;

*import* org.apache.jackrabbit.core.id.NodeId;


*public* *class* TestLoop {


*long* start;

Profiler prof;


*public* *static* *void* main(String... args) *throws* Exception {

*new* TestLoop().run();

}


*void* startProf() {

// if(prof != null) {

// prof.stopCollecting();

// System.out.println(prof.getTop(3));

// }

// prof = new Profiler();

// prof.interval = 1;

// prof.depth = 32;

// prof.startCollecting();

}


*void* run() *throws* Exception {

System.setProperty("jackrabbit.sequentialUUIDs", "false");

startProf();

FileUtils.deleteDirectory(*new* File("repository"));

FileUtils.copyFile(*new* File("repository copy.xml"),

*new* File("repository.xml"));

TransientRepository rep = *new* TransientRepository();

Session s = rep.login(

*new* SimpleCredentials("admin", "admin".toCharArray()));

*int* nodes = 1000000;

*int* nodesPerFolder = 20;

*int* saveEach = 10000;

System.out.println(*new* NodeId());

*int* levels = (*int*) Math.ceil(Math.log(nodes)

/ Math.log(nodesPerFolder));

start = System.currentTimeMillis();

startProf();

createNodes(s.getRootNode(), 0, nodes,

saveEach, levels, nodesPerFolder);

System.out.println("took: " + (System.currentTimeMillis() - start));

s.logout();

}


*private* *int* createNodes(Node parent, *int* x, *int* nodes,

*int* saveEach, *int* depth, *int* nodesPerFolder)

*throws* Exception {

*for* (*int* i = 0; x < nodes && i < nodesPerFolder; i++) {

*if* (depth > 1) {

Node n = parent.addNode("f" + x, "nt:unstructured");

x = createNodes(n, x, nodes,

saveEach, depth - 1, nodesPerFolder);

} *else* {

parent.addNode("n" + i, "nt:unstructured");

x++;

*if* ((x % saveEach) == 0) {

parent.getSession().save();

*long* t = System.currentTimeMillis() - start;

startProf();

System.out.println((x * 1000L / t) + " op/s at " + x);

}

}

}

*return* x;

}

}








Re: [jr3] Sequential Node Ids

Posted by Michael Dürig <md...@apache.org>.
Hi Thomas,

I think these are interesting graphs and they show that we do not 
exploit locality sufficiently when persisting nodes. However, your 
results base on the underlying assumption that sequential node ids lead 
to better locality than random node ids do. In general this will depends 
on the access pattern and the underlying persistence store: While for 
the append only case sequential node ids might exhibit good locality, 
for large repositories with many random CRUD operations this approach 
might eventually degenerate to behavior similar to random node ids.

I suggest to abstract node ids from storage ids: the node id is an 
identifier for retrieving nodes from JCR. A storage id is an identifier 
which is used by the persistence store to retrieve a certain piece of 
data (which could contain a node, part of a node or multiple nodes). A 
mapping from nodes ids to storage ids can then be used to tune locality: 
i.e. sequential vs. random, optimal block size etc.

Michael

On 22.12.10 9:51, Thomas Mueller wrote:
> Currently, Jackrabbit uses random node ids (randomly generated UUIDs).
> For Jackrabbit 3, and possibly Jackrabbit 2.x, I propose to use
> sequential node ids.
>
> The main advantages for random node ids (the default) are: it's easy to
> develop, and merging data from multiple repositories is simple.
>
> The disadvantages for random node ids are performance and space. With
> performance, I don't mean that randomly generated UUIDs are slower to
> generate (they are). I mean performance to read and write data to disk.
> The main performance problem is reading and writing (indexing) random
> keys, which is slow because adjacent (nearby) nodes data aren't adjacent
> in the index. This slows down index access (read and write) a lot,
> specially if the data doesn't fit in the buffer cache (file system cache).
>
> I wrote a simple test case for Jackrabbit trunk. I also patched
> Jackrabbit to allow sequential UUIDs. Creating 1 million nodes is about
> 80% faster when using sequential UUIDs instead of random UUIDs. I don't
> have the data yet, but I'm sure the difference is much, much bigger when
> reading from larger repositories once the data doesn't fit in RAM (10
> million nodes or so). I will expand the test case to support reading.
>
> The following diagram is the operations per second (bigger is better)
> after inserting x nodes (0 to 1 million). With sequential UUIDs,
> performance gets better and then stays the same (which is expected). For
> random UUIDs which are now the default, performance first goes up and
> then down. The resulting database (I used H2 for performance) was about
> 145 MB for sequential UUIDs and 169 MB for random UUIDs (the reason for
> this difference is that the b-tree fill factor is better for sequential
> UUIDs). All the data still fits in the buffer cache of the file system
> without problem.
>
>
>
> Something else I noticed when running the test case was that the
> Jackrabbit internals are relatively slow. When profiling the test case,
> I saw that database access is not an important factor. Creating the
> nodes with the JCR API took 285 / 526 seconds, and re-creating the
> database from a SQL script took 55 seconds (this includes reading the
> 200 MB SQL script file and parsing the SQL statements, one insert
> statement per row; this is for the random UUIDs). I would expect
> Jackrabbit is faster than 55 seconds, because it doesn't have to read
> the SQL script from disk and parse statements.
>
> The test case creates 1 million nodes, saves after each 10'000 nodes,
> and uses a fan-out of 20 child nodes per node. I disabled the search
> index in the repository configuration. Source code:
>
>
> *import* java.io.File;
>
> *import* javax.jcr.Node;
>
> *import* javax.jcr.Session;
>
> *import* javax.jcr.SimpleCredentials;
>
> *import* org.apache.commons.io.FileUtils;
>
> *import* org.apache.jackrabbit.core.TransientRepository;
>
> *import* org.apache.jackrabbit.core.id.NodeId;
>
>
> *public* *class* TestLoop {
>
>
> *long* start;
>
> Profiler prof;
>
>
> *public* *static* *void* main(String... args) *throws* Exception {
>
> *new* TestLoop().run();
>
> }
>
>
> *void* startProf() {
>
> // if(prof != null) {
>
> // prof.stopCollecting();
>
> // System.out.println(prof.getTop(3));
>
> // }
>
> // prof = new Profiler();
>
> // prof.interval = 1;
>
> // prof.depth = 32;
>
> // prof.startCollecting();
>
> }
>
>
> *void* run() *throws* Exception {
>
> System.setProperty("jackrabbit.sequentialUUIDs", "false");
>
> startProf();
>
> FileUtils.deleteDirectory(*new* File("repository"));
>
> FileUtils.copyFile(*new* File("repository copy.xml"),
>
> *new* File("repository.xml"));
>
> TransientRepository rep = *new* TransientRepository();
>
> Session s = rep.login(
>
> *new* SimpleCredentials("admin", "admin".toCharArray()));
>
> *int* nodes = 1000000;
>
> *int* nodesPerFolder = 20;
>
> *int* saveEach = 10000;
>
> System.out.println(*new* NodeId());
>
> *int* levels = (*int*) Math.ceil(Math.log(nodes)
>
> / Math.log(nodesPerFolder));
>
> start = System.currentTimeMillis();
>
> startProf();
>
> createNodes(s.getRootNode(), 0, nodes,
>
> saveEach, levels, nodesPerFolder);
>
> System.out.println("took: " + (System.currentTimeMillis() - start));
>
> s.logout();
>
> }
>
>
> *private* *int* createNodes(Node parent, *int* x, *int* nodes,
>
> *int* saveEach, *int* depth, *int* nodesPerFolder)
>
> *throws* Exception {
>
> *for* (*int* i = 0; x < nodes && i < nodesPerFolder; i++) {
>
> *if* (depth > 1) {
>
> Node n = parent.addNode("f" + x, "nt:unstructured");
>
> x = createNodes(n, x, nodes,
>
> saveEach, depth - 1, nodesPerFolder);
>
> } *else* {
>
> parent.addNode("n" + i, "nt:unstructured");
>
> x++;
>
> *if* ((x % saveEach) == 0) {
>
> parent.getSession().save();
>
> *long* t = System.currentTimeMillis() - start;
>
> startProf();
>
> System.out.println((x * 1000L / t) + " op/s at " + x);
>
> }
>
> }
>
> }
>
> *return* x;
>
> }
>
> }
>
>
>
>
>


Re: ids and locality

Posted by Thomas Mueller <mu...@adobe.com>.
Hi,

>If the memory cost is too big, you could also use an LRU mechanism to
>only keep the most recently accessed identifiers indexed in memory.

That would increase the memory footprint of the index significantly. Also,
maintaining the LRU cache on an item / entry level is relatively slow.
Instead, I would cache index _pages_ (or index 'blocks').

>I think an append-only or at least journaled storage is pretty much a
>requirement for any modern media that benefits from locality of access
>(and thus is relevant to this discussion), so it should be no problem
>to write incremental index updates only occasionally.

For Jackrabbit 3, I wouldn't bet everything on append-only storage. I
think we should support relational databases, in-memory repositories, and
append-only storage. Relational databases, because this is the only viable
option for some (due to business, hardware or software restrictions - I
would like to see Jackrabbit 3 on Android using SQLite). In-memory
repositories for testing and specialized use cases. Append-only storage
for performance and simplicity.

For certain storage systems, locality of data access (accessing the data)
is not as important, for example for solid state disks. But I don't think
we can bet on SSDs currently.

Regards,
Thomas


Re: ids and locality

Posted by Jukka Zitting <ju...@gmail.com>.
Hi,

On Wed, Jan 12, 2011 at 11:40 AM, Thomas Mueller <mu...@adobe.com> wrote:
> For specialized use cases this might work. In-memory repositories are
> nice, specially for testing. They are very fast. But for normal uses
> cases, this would be expensive. For a regular repository, one million
> nodes is not that much. Even 10 million nodes is not a lot depending on
> the use case. If we keep secondary indexes in the repository, the number
> of nodes will further increase.

If the memory cost is too big, you could also use an LRU mechanism to
only keep the most recently accessed identifiers indexed in memory.
And to avoid having to read too many non-cached index blocks during a
cache miss, you could use a Bloom filter to predict whether an index
entry is found within a given block.

> Even if the index is kept in memory, it still needs to be persisted once
> in a while. If you have an append-only storage, then you can afford only
> storing the index after x changes, because to re-build the index, you can
> use an old index and re-apply at most x-1 changes. But without append-only
> storage, re-building the index from the data takes time (linear to the
> size of the repository, or possibly linear to the size of the repository
> including old versions).

I think an append-only or at least journaled storage is pretty much a
requirement for any modern media that benefits from locality of access
(and thus is relevant to this discussion), so it should be no problem
to write incremental index updates only occasionally.

BR,

Jukka Zitting

Re: ids and locality

Posted by Thomas Mueller <mu...@adobe.com>.
Hi,

>Why don't you simply keep the entire index in memory?

For specialized use cases this might work. In-memory repositories are
nice, specially for testing. They are very fast. But for normal uses
cases, this would be expensive. For a regular repository, one million
nodes is not that much. Even 10 million nodes is not a lot depending on
the use case. If we keep secondary indexes in the repository, the number
of nodes will further increase.

Even if the index is kept in memory, it still needs to be persisted once
in a while. If you have an append-only storage, then you can afford only
storing the index after x changes, because to re-build the index, you can
use an old index and re-apply at most x-1 changes. But without append-only
storage, re-building the index from the data takes time (linear to the
size of the repository, or possibly linear to the size of the repository
including old versions).

Regards,
Thomas


Re: ids and locality

Posted by Jukka Zitting <ju...@gmail.com>.
Hi,

On Wed, Jan 12, 2011 at 9:29 AM, Thomas Mueller <mu...@adobe.com> wrote:
> No. In fact, using a persistence manager that stores the *data* in an
> append only way, the main performance problem (more than 80%) is index
> access (for large repositories).

Why don't you simply keep the entire index in memory? You should be
able to squeeze an index entry with all the overhead to something like
32 bytes (for example 16 bytes for the node id, 8 for storage location
and 8 bytes for other data). That's just 32MB for a repository with a
million nodes. Big database servers nowadays come with hundreds of
gigabytes of memory, so even the 3GB memory cost for a repository with
a hundred million nodes is not excessive.

BR,

Jukka Zitting

Re: ids and locality

Posted by Thomas Mueller <mu...@adobe.com>.
Hi,

>If the node id would directly map the storage location on a media, then
>you would either need to do in-place-updates (which are very problematic
>for many reasons), or you would always need to update all parent nodes
>(including the root) if you update a node, which is also problematic,
>specially if you store the data in a relational database.

I forgot: if the node id would directly map the storage location on a
media, and the node is changed (therefore stored somewhere else), you
would also have to update all nodes that reference the given node in some
way. And / or the node id couldn't be used as the node identifier (like we
do now).

Regards,
Thomas





Re: ids and locality

Posted by Thomas Mueller <mu...@adobe.com>.
Hi,

>Only when the node id directly mapped to a storage location on a media
>that benefits from locality of access.

No. In fact, using a persistence manager that stores the *data* in an
append only way, the main performance problem (more than 80%) is index
access (for large repositories). That means, the order of (bundle) writes
closely matches the access order. Otherwise, accessing the data would take
a lot more time than accessing the index.

If the node id would directly map the storage location on a media, then
you would either need to do in-place-updates (which are very problematic
for many reasons), or you would always need to update all parent nodes
(including the root) if you update a node, which is also problematic,
specially if you store the data in a relational database.

Regards,
Thomas


Re: ids and locality

Posted by Jukka Zitting <ju...@gmail.com>.
Hi,

On Tue, Jan 11, 2011 at 12:14 PM, Thomas Mueller <mu...@adobe.com> wrote:
> It will always work, but the performance *might* not be optimal for common
> use cases. With random node ids, performance is actually *guaranteed* to
> be very close to the worst case, for *all* use cases.

Only when the node id directly mapped to a storage location on a media
that benefits from locality of access.

BR,

Jukka Zitting

Re: ids and locality

Posted by Thomas Mueller <mu...@adobe.com>.
Hi,

>>It's also not necessarily incorrect :-)
>
>... which means it won't always work

It will always work, but the performance *might* not be optimal for common
use cases. With random node ids, performance is actually *guaranteed* to
be very close to the worst case, for *all* use cases.

Regards,
Thomas


Re: ids and locality

Posted by Michael Dürig <mi...@gmail.com>.

On 11.1.11 11:35, Thomas Mueller wrote:
> Hi,
>
>> This exposes another implicit assumption underlying 'sequential node
>> ids': temporal locality implies spacial locality. This is not
>> necessarily correct however.
>
> It's also not necessarily incorrect :-)

... which means it won't always work

Michael


Re: ids and locality

Posted by Thomas Mueller <mu...@adobe.com>.
Hi,

>This exposes another implicit assumption underlying 'sequential node
>ids': temporal locality implies spacial locality. This is not
>necessarily correct however.

It's also not necessarily incorrect :-)

Regards,
Thomas



Re: ids and locality

Posted by Michael Dürig <mi...@gmail.com>.
> I think we should leverage the locality information
> that is available in the path of an item and use
> this information also in the persistence layer.
> while sequential ids give you a hint when nodes
> were created, paths provide you a much better
> hint on locality. access patterns I've seen so
> far in applications are usually along the ancestor
> or descendant nodes axis.

This exposes another implicit assumption underlying 'sequential node 
ids': temporal locality implies spacial locality. This is not 
necessarily correct however.

Michael


Re: ids and locality (was: [jr3] Sequential Node Ids)

Posted by Thomas Mueller <mu...@adobe.com>.
Hi,

>the assumption that the sequence
>of creating nodes has a great overlap with node
>locality. this may be the case for certain creation
>patterns, but will not work well in general.

This is an assumption as well :-) For adding nodes, sequential node ids
are clearly faster (see the graph). For reading data, we just don't know
how sequential node ids behave for normal use cases, because we couldn't
test it so far. Now we can.

>I think we should leverage the locality information
>that is available in the path of an item and use
>this information also in the persistence layer.

That's a nice idea, however there are some problems. Currently node ids
are fixed in size, so we can't use the path or a formula of the path,
meaning we can't use something like 'hierarchy ids':
http://msdn.microsoft.com/en-us/library/bb677290.aspx - there are related
solutions, one is using the nested set model,
http://en.wikipedia.org/wiki/Nested_set_model - but this also requires
variable size keys. For testing purposes, we may be able to implement a
node id generator that generates hierarchy ids, but it would fail for
certain use cases (where the hierarchy id doesn't fit in 128 bits).

>while sequential ids give you a hint when nodes
>were created, paths provide you a much better
>hint on locality. 

This is an assumption as well, which would need to be tested. Sometimes
related data is stored in different branches. Which method is 'better' or
'faster' is hard to say, if there is no way to test it.

Regards,
Thomas


ids and locality (was: [jr3] Sequential Node Ids)

Posted by Marcel Reutegger <mr...@adobe.com>.
hi,

I somewhat agree with what jukka and michi said about
ids and locality. I think these are separate aspects
and we don't necessarily need to mix them, as it
is the case with the current jackrabbit implementation.

at the moment each node has an identifier that is
visible through all layers (in fact,
even each property has an identifier, but it is
not accessible through the JCR API). I think this
is a good and simple design, but comes with certain
limitations. using sequential ids instead of
random ones helps to work around these limitations
but its basis is the assumption that the sequence
of creating nodes has a great overlap with node
locality. this may be the case for certain creation
patterns, but will not work well in general.

I think we should leverage the locality information
that is available in the path of an item and use
this information also in the persistence layer.
while sequential ids give you a hint when nodes
were created, paths provide you a much better
hint on locality. access patterns I've seen so
far in applications are usually along the ancestor
or descendant nodes axis.

I know this is fundamentally different to what we
have right now, but using the path would also make
the current rather expensive mapping from path to id
and vice versa obsolete (at least on top of the
persistence layer).

regards
 marcel

> -----Original Message-----
> From: Thomas Mueller [mailto:mueller@adobe.com]
> Sent: 22 December 2010 09:52
> To: dev@jackrabbit.apache.org
> Subject: [jr3] Sequential Node Ids
> 
> Currently, Jackrabbit uses random node ids (randomly generated UUIDs).
> For Jackrabbit 3, and possibly Jackrabbit 2.x, I propose to use
> sequential node ids.
> 
> The main advantages for random node ids (the default) are: it's easy to
> develop, and merging data from multiple repositories is simple.
> 
> The disadvantages for random node ids are performance and space. With
> performance, I don't mean that randomly generated UUIDs are slower to
> generate (they are). I mean performance to read and write data to disk.
> The main performance problem is reading and writing (indexing) random
> keys, which is slow because adjacent (nearby) nodes data aren't
> adjacent in the index. This slows down index access (read and write) a
> lot, specially if the data doesn't fit in the buffer cache (file system
> cache).
> 
> I wrote a simple test case for Jackrabbit trunk. I also patched
> Jackrabbit to allow sequential UUIDs. Creating 1 million nodes is about
> 80% faster when using sequential UUIDs instead of random UUIDs. I don't
> have the data yet, but I'm sure the difference is much, much bigger
> when reading from larger repositories once the data doesn't fit in RAM
> (10 million nodes or so). I will expand the test case to support
> reading.
> 
> The following diagram is the operations per second (bigger is better)
> after inserting x nodes (0 to 1 million). With sequential UUIDs,
> performance gets better and then stays the same (which is expected).
> For random UUIDs which are now the default, performance first goes up
> and then down. The resulting database (I used H2 for performance) was
> about 145 MB for sequential UUIDs and 169 MB for random UUIDs (the
> reason for this difference is that the b-tree fill factor is better for
> sequential UUIDs). All the data still fits in the buffer cache of the
> file system without problem.
> 
> 
> 
> 
> Something else I noticed when running the test case was that the
> Jackrabbit internals are relatively slow.  When profiling the test
> case, I saw that database access is not an important factor. Creating
> the nodes with the JCR API took 285 / 526 seconds, and re-creating the
> database from a SQL script took 55 seconds (this includes reading the
> 200 MB SQL script file and parsing the SQL statements, one insert
> statement per row; this is for the random UUIDs). I would expect
> Jackrabbit is faster than 55 seconds, because it doesn't have to read
> the SQL script from disk and parse statements.
> 
> The test case creates 1 million nodes, saves after each 10'000 nodes,
> and uses a fan-out of 20 child nodes per node. I disabled the search
> index in the repository configuration. Source code:
> 
> 
> 
> 
> 
> import java.io.File;
> 
> import javax.jcr.Node;
> 
> import javax.jcr.Session;
> 
> import javax.jcr.SimpleCredentials;
> 
> import org.apache.commons.io.FileUtils;
> 
> import org.apache.jackrabbit.core.TransientRepository;
> 
> import org.apache.jackrabbit.core.id.NodeId;
> 
> 
> 
> 
> public class TestLoop {
> 
> 
> 
> 
>     long start;
> 
>     Profiler prof;
> 
> 
> 
> 
>     public static void main(String... args) throws Exception {
> 
>         new TestLoop().run();
> 
>     }
> 
> 
> 
> 
>     void startProf() {
> 
> //        if(prof != null) {
> 
> //            prof.stopCollecting();
> 
> //            System.out.println(prof.getTop(3));
> 
> //        }
> 
> //        prof = new Profiler();
> 
> //        prof.interval = 1;
> 
> //        prof.depth = 32;
> 
> //        prof.startCollecting();
> 
>     }
> 
> 
> 
> 
>     void run() throws Exception {
> 
>         System.setProperty("jackrabbit.sequentialUUIDs", "false");
> 
>         startProf();
> 
>         FileUtils.deleteDirectory(new File("repository"));
> 
>         FileUtils.copyFile(new File("repository copy.xml"),
> 
>                 new File("repository.xml"));
> 
>         TransientRepository rep = new TransientRepository();
> 
>         Session s = rep.login(
> 
>                 new SimpleCredentials("admin", "admin".toCharArray()));
> 
>         int nodes = 1000000;
> 
>         int nodesPerFolder = 20;
> 
>         int saveEach = 10000;
> 
>         System.out.println(new NodeId());
> 
>         int levels = (int) Math.ceil(Math.log(nodes)
> 
>                 / Math.log(nodesPerFolder));
> 
>         start = System.currentTimeMillis();
> 
>         startProf();
> 
>         createNodes(s.getRootNode(), 0, nodes,
> 
>                 saveEach, levels, nodesPerFolder);
> 
>         System.out.println("took: " + (System.currentTimeMillis() -
> start));
> 
>         s.logout();
> 
>     }
> 
> 
> 
> 
>     private int createNodes(Node parent, int x, int nodes,
> 
>             int saveEach, int depth, int nodesPerFolder)
> 
>             throws Exception {
> 
>         for (int i = 0; x < nodes && i < nodesPerFolder; i++) {
> 
>             if (depth > 1) {
> 
>                 Node n = parent.addNode("f" + x, "nt:unstructured");
> 
>                 x = createNodes(n, x, nodes,
> 
>                         saveEach, depth - 1, nodesPerFolder);
> 
>             } else {
> 
>                 parent.addNode("n" + i, "nt:unstructured");
> 
>                 x++;
> 
>                 if ((x % saveEach) == 0) {
> 
>                     parent.getSession().save();
> 
>                     long t = System.currentTimeMillis() - start;
> 
>                     startProf();
> 
>                     System.out.println((x * 1000L / t) + " op/s at " +
> x);
> 
>                 }
> 
>             }
> 
>         }
> 
>         return x;
> 
>     }
> 
> }
> 
> 
> 
>