You are viewing a plain text version of this content. The canonical link for it is here.
Posted to oak-dev@jackrabbit.apache.org by Joel Richard <jo...@adobe.com> on 2014/02/27 15:29:43 UTC
Oak Scalability: Load Distribution
Hi,
During the TechFair I have talked with Marcel about the MongoDB
Microkernel and asked some questions about clustering. He explained that
the nodes are distributed over the clusters based on the key which
consists of the path depth and node path. The path depth is prepended to
the path to ensure that the nodes are distributed more equally. However, I
fear that this will cause troubles since often only some kind of data is
written heavily. In our current project, for example, we will have a lot
of card and comment writes and all cards and comments are on the same
level (the paths are simplified):
Cards: /content/<tenant>/<board>/<card>
Comments: /content/<tenant>/<board>/<card>/comments/<comment>
As you can see, all cards and all comments are saved on the same level and
hence end up on the same cluster node. If we assume that every card gets
10 comments, this will cause 10 times more write load on the “comments”
cluster node than on the “cards” cluster node. And again, the same is true
for cards compared to other content.
A much better distribution could be achieved if the hash/checksum of the
parent node path would be used instead of the path depth. Children would
still be saved on the same cluster node, but the cards/comments would be
saved on different clusters for every board/card. I strongly recommend to
reconsider the choice of the path depth as the prefix of the MongoDB key
since this will lead to really bad load distribution.
Regards, Joel
Re: Oak Scalability: Load Distribution
Posted by Thomas Mueller <mu...@adobe.com>.
Hi,
>>> Agreed, I think we should give it a try and compare how the two key
>> >formats perform.
>>
>> Yes. This is specially interesting as it is a simple solution for
>>OAK-333
>> (1000 byte path limit in MongoMK). Even if we find out performance is
>>much
>> worse than with the current solution, we could still use the hash
>>approach
>> for long paths.
>
>hmm, isn't that a different problem? so far we only discussed replacing
>the
>depth prefix with a hash prefix. AFAIU the full path would still be part
>of the
>key.
Sorry, my mistake. I wouldn't do that.
I would do is: from the parent of the path, calculate the SHA-256 hash
code, and replace that part of the key with the hash, and then maybe
convert that to Base64. So that:
/test/node1 -> swbZ+4R8Eg3X6wD86+XxGLmHWwnbZ62PCDSup6DYy4w/node1
/test/node2 -> swbZ+4R8Eg3X6wD86+XxGLmHWwnbZ62PCDSup6DYy4w/node2
/test2/node1 -> vcSCrX3V8DBPLZUNs6yowJeYbRUyU8wbLqDtg+oefHc/node1
/test2/node2 -> vcSCrX3V8DBPLZUNs6yowJeYbRUyU8wbLqDtg+oefHc/node2
That way, we have the same load distribution as with just replacing the
depth prefix, and at the same time we solved JCR-333 (except for cases
where the node name itself is extremely large).
I would only do that if the path of the parent is longer than 700
characters. That way, a node name has a limit of about 260 bytes (which I
_think_ should be a reasonable limit for node names - but I might be
wrong).
If we have that implementation, we can run some tests with using a
threshold of 1 characters, so that every node except for the root node is
stored like above.
Regards,
Thomas
RE: Oak Scalability: Load Distribution
Posted by Marcel Reutegger <mr...@adobe.com>.
Hi,
> > Agreed, I think we should give it a try and compare how the two key
> >formats perform.
>
> Yes. This is specially interesting as it is a simple solution for OAK-333
> (1000 byte path limit in MongoMK). Even if we find out performance is much
> worse than with the current solution, we could still use the hash approach
> for long paths.
hmm, isn't that a different problem? so far we only discussed replacing the
depth prefix with a hash prefix. AFAIU the full path would still be part of the
key.
Regards
Marcel
Re: Oak Scalability: Load Distribution
Posted by Thomas Mueller <mu...@adobe.com>.
Hi,
> Agreed, I think we should give it a try and compare how the two key
>formats perform.
Yes. This is specially interesting as it is a simple solution for OAK-333
(1000 byte path limit in MongoMK). Even if we find out performance is much
worse than with the current solution, we could still use the hash approach
for long paths.
Even if we use the hash code, we should still store the full path in each
document, so that recovery tools can easily dump the repository contents
even if some (parent) node documents are missing.
Regards,
Thomas
Re: Oak Scalability: Load Distribution
Posted by Joel Richard <jo...@adobe.com>.
Hi Thomas,
I am not that familiar with database internals, so please forgive me if it
is a stupid question ;-)
What is the difference for B-tree performance between a path and a hash? I
understand that an auto incremented index has an advantage over a hash,
but why should a path be better than a hash? In both cases it has to
insert the record somewhere in the middle of the B-tree. Since hashes are
better spread than paths, I would expect that hashes perform better than
paths for partial in-memory indexes / indexes in general.
Regards, Joel
On 03/03/14 11:11, "Thomas Mueller" <mu...@adobe.com> wrote:
>Hi,
>
>The reason why I believe using the hash code is bad for performance is
>that it locality of nodes in the backend storage (MongoDB, or any kind of
>database) is worse than now. This affects performance when writing, and
>when reading siblings. Let's assume we have the nodes
>/page_1/paragraph_0..2/child_0..2/ (that is, 3 paragraph nodes, and each
>paragraph node has 3 child nodes). With the current approach, the entries
>are stored as follows:
>
>1:/page_1
>...
>2:/page_1/paragraph_0
>2:/page_1/paragraph_1
>
>2:/page_1/paragraph_2
>...
>3:/page_1/paragraph_0/child_0
>3:/page_1/paragraph_0/child_1
>3:/page_1/paragraph_0/child_2
>3:/page_1/paragraph_1/child_0
>3:/page_1/paragraph_1/child_1
>3:/page_1/paragraph_1/child_2
>3:/page_1/paragraph_2/child_0
>3:/page_1/paragraph_2/child_1
>3:/page_1/paragraph_2/child_2
>
>The child documents (child_0 .. child_2) of all paragraphs are stored next
>to each other, likely in the same b-tree page, which means likely in the
>same sector on the hard drive. Even if there are many other pages (page_2,
>page_3,...). That's good for caching.
>
>With a hash based approach, data is distributed over the whole keyspace.
>Even thought child_0 .. child_2 of each paragraph are still next to each
>other, locality is much worse. If we assume 3 child nodes per node on
>average, we almost have the same situation as with Jackrabbit 2.x, where
>node id lookup was by far the biggest performance problem. Because node
>ids are randomly distributed in Jackrabbit 2. And using randomly
>distributed primary keys is one of the worst performance problems when
>using databases. For example, the default object id of MongoDB is
>sequential (time based):
>http://docs.mongodb.org/manual/reference/object-id/. I'm not worried at
>all about the overhead to calculate the hash code of the path. That is
>insignificant. It's the random distribution of the data that is
>problematic. See also:
>
>http://kccoder.com/mysql/uuid-vs-int-insert-performance/ (specially the
>first two charts comparing auto_increment versus uuid)
>
>
>http://www.mysqlperformanceblog.com/2007/03/13/to-uuid-or-not-to-uuid/
>"What is the biggest problem with UUID ? It is the fact inserts are going
>in random locations in index tree which will require a lot of IO in case
>of index tree not fitting into memory"
>
>
>http://stackoverflow.com/questions/2365132/uuid-performance-in-mysql "At
>my job, we use UUID as PKs. What I can tell you from experience is DO NOT
>USE THEM as PKs (SQL Server by the way). It's one of those things that
>when you have less than 1000 records it;s ok, but when you have millions,
>it's the worst thing you can do. Why? Because UUID are not sequential, so
>everytime a new record is inserted MSSQL needs to go look at the correct
>page to insert the record in, and then insert the record. The really ugly
>consequence with this is that the pages end up all in different sizes and
>they end up fragmented, so now we have to do de-fragmentation
>periodic...".
>
>
>https://issues.apache.org/jira/browse/JCR-2857
>
>
>Regards,
>
>Thomas
>
>
>
>
>
>
>
>
>
Re: Oak Scalability: Load Distribution
Posted by Thomas Mueller <mu...@adobe.com>.
Hi,
The reason why I believe using the hash code is bad for performance is
that it locality of nodes in the backend storage (MongoDB, or any kind of
database) is worse than now. This affects performance when writing, and
when reading siblings. Let's assume we have the nodes
/page_1/paragraph_0..2/child_0..2/ (that is, 3 paragraph nodes, and each
paragraph node has 3 child nodes). With the current approach, the entries
are stored as follows:
1:/page_1
...
2:/page_1/paragraph_0
2:/page_1/paragraph_1
2:/page_1/paragraph_2
...
3:/page_1/paragraph_0/child_0
3:/page_1/paragraph_0/child_1
3:/page_1/paragraph_0/child_2
3:/page_1/paragraph_1/child_0
3:/page_1/paragraph_1/child_1
3:/page_1/paragraph_1/child_2
3:/page_1/paragraph_2/child_0
3:/page_1/paragraph_2/child_1
3:/page_1/paragraph_2/child_2
The child documents (child_0 .. child_2) of all paragraphs are stored next
to each other, likely in the same b-tree page, which means likely in the
same sector on the hard drive. Even if there are many other pages (page_2,
page_3,...). That's good for caching.
With a hash based approach, data is distributed over the whole keyspace.
Even thought child_0 .. child_2 of each paragraph are still next to each
other, locality is much worse. If we assume 3 child nodes per node on
average, we almost have the same situation as with Jackrabbit 2.x, where
node id lookup was by far the biggest performance problem. Because node
ids are randomly distributed in Jackrabbit 2. And using randomly
distributed primary keys is one of the worst performance problems when
using databases. For example, the default object id of MongoDB is
sequential (time based):
http://docs.mongodb.org/manual/reference/object-id/. I'm not worried at
all about the overhead to calculate the hash code of the path. That is
insignificant. It's the random distribution of the data that is
problematic. See also:
http://kccoder.com/mysql/uuid-vs-int-insert-performance/ (specially the
first two charts comparing auto_increment versus uuid)
http://www.mysqlperformanceblog.com/2007/03/13/to-uuid-or-not-to-uuid/
"What is the biggest problem with UUID ? It is the fact inserts are going
in random locations in index tree which will require a lot of IO in case
of index tree not fitting into memory"
http://stackoverflow.com/questions/2365132/uuid-performance-in-mysql "At
my job, we use UUID as PKs. What I can tell you from experience is DO NOT
USE THEM as PKs (SQL Server by the way). It's one of those things that
when you have less than 1000 records it;s ok, but when you have millions,
it's the worst thing you can do. Why? Because UUID are not sequential, so
everytime a new record is inserted MSSQL needs to go look at the correct
page to insert the record in, and then insert the record. The really ugly
consequence with this is that the pages end up all in different sizes and
they end up fragmented, so now we have to do de-fragmentation periodic...".
https://issues.apache.org/jira/browse/JCR-2857
Regards,
Thomas
RE: Oak Scalability: Load Distribution
Posted by Marcel Reutegger <mr...@adobe.com>.
Hi,
> >The path depth is prepended to
> >the path to ensure that the nodes are distributed more equally.
>
> Actually, the reason for the prefix is not that the nodes are distributed
> more equally, but so that queries for child nodes are efficient, and so
> that siblings are stored next to each other. Queries for child nodes are
> range queries of the form "id between '2:/content/' and '2:/content0'".
> This is efficient because MongoDB keeps a documents sorted by id. For more
> details about range queries, see
> http://docs.mongodb.org/manual/core/index-single/
with Joel's approach, this would still be the case. all siblings have the same prefix.
I think it's an interesting idea, because the content structures he mentions are
quite common. e.g. think of the way how user information is structured. it is
all stored at the same depth and will likely be located on the same shard. an
alternative distribution is certainly desirable when this kind of content is
modified often.
> >A much better distribution could be achieved if the hash/checksum of the
> >parent node path would be used instead of the path depth.
>
> Sure, we can do some experiments and try it out.
Agreed, I think we should give it a try and compare how the two key formats perform.
Regards
Marcel
Re: Oak Scalability: Load Distribution
Posted by Joel Richard <jo...@adobe.com>.
Tim has forwarded me the email since I was removed from the thread.
On 27/02/14 17:35, "Timothee Maret" <tm...@adobe.com> wrote:
>
>________________________________________
>From: Thomas Mueller
>Sent: Thursday, February 27, 2014 5:12 PM
>To: oak-dev@jackrabbit.apache.org
>Cc: Marcel Reutegger; Ian Boston; Timothee Maret
>Subject: Re: Oak Scalability: Load Distribution
>
>Hi,
>
>>The path depth is prepended to
>>the path to ensure that the nodes are distributed more equally.
>
>Actually, the reason for the prefix is not that the nodes are distributed
>more equally, but so that queries for child nodes are efficient, and so
>that siblings are stored next to each other. Queries for child nodes are
>range queries of the form "id between '2:/content/' and '2:/content0'".
>This is efficient because MongoDB keeps a documents sorted by id. For more
>details about range queries, see
>http://docs.mongodb.org/manual/core/index-single/
Ok, I understand; however, this doesn’t change my statement.
>
>>Cards: /content/<tenant>/<board>/<card>
>>Comments: /content/<tenant>/<board>/<card>/comments/<comment>
>>
>>As you can see, all cards and all comments are saved on the same level
>>and
>>hence end up on the same cluster node.
>
>In this case, cards are stored next to each other, and comments are stored
>next to each other. But not necessarily on the same cluster node.
I agree that this must not always be the case (e.g. if every tenant has a
lot of other data below /content on the same level), but the probability
is way too high.
>
>> If we assume that every card gets
>>10 comments, this will cause 10 times more write load on the ³comments²
>>cluster node than on the ³cards² cluster node.
>
>MongoDB will distribute the nodes evenly accross shards. In the extreme
>case, if there are 10 shards, and if 10% of the data is cards and 90% is
>comments, then one cluster node will have all the cards, while the
>comments are distributed accross the remaining cluster nodes.
Which means that one cluster is much less busy with writes. In reality,
there is a lot of other (often read-only) data which is saved on - let’s
say - another 10 nodes which had then much less write operations too.
>
>>A much better distribution could be achieved if the hash/checksum of the
>>parent node path would be used instead of the path depth.
>
>Sure, we can do some experiments and try it out. My fear is that using an
>index on randomly distributed data will perform poorly, and we might end
>up with similar problems than we had with Jackrabbit 2.x. But I might be
>wrong.
I don’t understand the problem. My suggestion is just to use a hash/short
checksum of the parent node path instead of the node level/path depth:
cc24:/content/a/1
cc24:/content/a/2
0ef7:/content/b/1
0ef7:/content/b/2
09d7:/content/c/1
09d7:/content/c/2
(where the first 4 characters are the first 4 characters of the SHA1 of
the parent node path)
instead of:
3:/content/a/1
3:/content/a/2
3:/content/b/1
3:/content/b/2
3:/content/c/1
3:/content/c/2
The advantage is a much better distribution for all nodes which are in a
bucket (like a tenant, board, artificial bucket and so on).
Regards, Joel
>
>Regards,
>Thomas
>
Re: Oak Scalability: Load Distribution
Posted by Thomas Mueller <mu...@adobe.com>.
Hi,
>The path depth is prepended to
>the path to ensure that the nodes are distributed more equally.
Actually, the reason for the prefix is not that the nodes are distributed
more equally, but so that queries for child nodes are efficient, and so
that siblings are stored next to each other. Queries for child nodes are
range queries of the form "id between '2:/content/' and '2:/content0'".
This is efficient because MongoDB keeps a documents sorted by id. For more
details about range queries, see
http://docs.mongodb.org/manual/core/index-single/
>Cards: /content/<tenant>/<board>/<card>
>Comments: /content/<tenant>/<board>/<card>/comments/<comment>
>
>As you can see, all cards and all comments are saved on the same level and
>hence end up on the same cluster node.
In this case, cards are stored next to each other, and comments are stored
next to each other. But not necessarily on the same cluster node.
> If we assume that every card gets
>10 comments, this will cause 10 times more write load on the ³comments²
>cluster node than on the ³cards² cluster node.
MongoDB will distribute the nodes evenly accross shards. In the extreme
case, if there are 10 shards, and if 10% of the data is cards and 90% is
comments, then one cluster node will have all the cards, while the
comments are distributed accross the remaining cluster nodes.
>A much better distribution could be achieved if the hash/checksum of the
>parent node path would be used instead of the path depth.
Sure, we can do some experiments and try it out. My fear is that using an
index on randomly distributed data will perform poorly, and we might end
up with similar problems than we had with Jackrabbit 2.x. But I might be
wrong.
Regards,
Thomas