You are viewing a plain text version of this content. The canonical link for it is here.
Posted to oak-issues@jackrabbit.apache.org by "Stefan Egli (JIRA)" <ji...@apache.org> on 2015/02/12 19:56:11 UTC
[jira] [Created] (OAK-2513) algorithm with O(n!) in mongoMk rebase
- not finishing in years
Stefan Egli created OAK-2513:
--------------------------------
Summary: algorithm with O(n!) in mongoMk rebase - not finishing in years
Key: OAK-2513
URL: https://issues.apache.org/jira/browse/OAK-2513
Project: Jackrabbit Oak
Issue Type: Bug
Components: core
Affects Versions: 1.0.11, 1.0.9
Environment: oak 1.0.9.r1646300 and 1.0.11 (see further details as to which stack is from which version below)
Reporter: Stefan Egli
Priority: Blocker
In MongoMk/DocumentNodeStore there is an algorithm which is O(n!) meaning that even with few entries (eg 12 or 13 as witnessed) it would result in the order of billion operations (which consist of map.containsKey, map.put for example) - ie it would create an almost infinite loop.
This situation is seen in DocumentNodeStore.merge() and DocumentNodeStore.readNode() where there is a branch with unsaved revisions (and as [~chetanm] pointed out, oak only creates a branch for large commits).
The assumption that it is an O(n!) algorithm are:
* document.Branch.rebase() constructs a RebaseCommit() object, passing it the list of previous commits, adding the resulting commit to that list of previous commits
* this constructs a list of RebaseCommit() objects, that each have the (n-1) previous objects
* later in either document.Branch.applyTo() or isModified() it recursively goes through this list of previous commits - which since that list also consists of RebaseCommit objects and each of those consists (n-1) previous objects, results in n * (n-1) * (n-2) * (n-3) such recursions.
* note that during the 'almost endless loop' there is no activity against the underlying eg mongod - but nevertheless does the cache.load() call keep a lock for the given amount of time (for the affected path at least)
Since n! starts to get big already with a low digit (eg 8!=40,320) you could start seeing burst of rebase operations becoming slow quite soon.
Attaching stacktraces where this has been witness and underlining the issue below.
with oak 1.0.11:
{code}
java.lang.Thread.State: RUNNABLE
at org.mapdb.BTreeMap.findChildren(BTreeMap.java:580)
at org.mapdb.BTreeMap.get(BTreeMap.java:607)
at org.mapdb.BTreeMap.containsKey(BTreeMap.java:1505)
at org.apache.jackrabbit.oak.plugins.document.Branch$BranchCommitImpl.isModified(Branch.java:325)
at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.isModified(Branch.java:366)
at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.isModified(Branch.java:366)
at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.isModified(Branch.java:366)
at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.isModified(Branch.java:366)
at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.isModified(Branch.java:366)
at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.isModified(Branch.java:366)
at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.isModified(Branch.java:366)
at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.isModified(Branch.java:366)
at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.isModified(Branch.java:366)
at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.isModified(Branch.java:366)
at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.isModified(Branch.java:366)
at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.isModified(Branch.java:366)
at org.apache.jackrabbit.oak.plugins.document.Branch.getUnsavedLastRevision(Branch.java:242)
at org.apache.jackrabbit.oak.plugins.document.NodeDocument.getNodeAtRevision(NodeDocument.java:896)
at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStore.readNode(DocumentNodeStore.java:929)
at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStore$3.call(DocumentNodeStore.java:706)
at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStore$3.call(DocumentNodeStore.java:703)
at com.google.common.cache.LocalCache$LocalManualCache$1.load(LocalCache.java:4724)
at com.google.common.cache.LocalCache$LoadingValueReference.loadFuture(LocalCache.java:3522)
at com.google.common.cache.LocalCache$Segment.loadSync(LocalCache.java:2315)
at com.google.common.cache.LocalCache$Segment.lockedGetOrLoad(LocalCache.java:2278)
- locked <0x0000000552d56720> (a com.google.common.cache.LocalCache$StrongAccessEntry)
at com.google.common.cache.LocalCache$Segment.get(LocalCache.java:2193)
at com.google.common.cache.LocalCache.get(LocalCache.java:3932)
at com.google.common.cache.LocalCache$LocalManualCache.get(LocalCache.java:4721)
at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStore.getNode(DocumentNodeStore.java:703)
at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStore.readChildren(DocumentNodeStore.java:785)
at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStore$4.call(DocumentNodeStore.java:733)
at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStore$4.call(DocumentNodeStore.java:730)
at com.google.common.cache.LocalCache$LocalManualCache$1.load(LocalCache.java:4724)
at com.google.common.cache.LocalCache$LoadingValueReference.loadFuture(LocalCache.java:3522)
at com.google.common.cache.LocalCache$Segment.loadSync(LocalCache.java:2315)
at com.google.common.cache.LocalCache$Segment.lockedGetOrLoad(LocalCache.java:2278)
- locked <0x0000000552f25170> (a com.google.common.cache.LocalCache$StrongAccessEntry)
at com.google.common.cache.LocalCache$Segment.get(LocalCache.java:2193)
at com.google.common.cache.LocalCache.get(LocalCache.java:3932)
at com.google.common.cache.LocalCache$LocalManualCache.get(LocalCache.java:4721)
at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStore.getChildren(DocumentNodeStore.java:730)
at org.apache.jackrabbit.oak.plugins.document.DocumentNodeState.getChildNodeCount(DocumentNodeState.java:189)
at org.apache.jackrabbit.oak.spi.state.AbstractNodeState.equals(AbstractNodeState.java:344)
at org.apache.jackrabbit.oak.plugins.document.DocumentNodeState.equals(DocumentNodeState.java:127)
at org.apache.jackrabbit.oak.spi.state.AbstractNodeState.equals(AbstractNodeState.java:377)
at org.apache.jackrabbit.oak.plugins.document.DocumentNodeState.equals(DocumentNodeState.java:127)
at org.apache.jackrabbit.oak.spi.state.AbstractNodeState.equals(AbstractNodeState.java:377)
at org.apache.jackrabbit.oak.plugins.document.DocumentNodeState.equals(DocumentNodeState.java:127)
at org.apache.jackrabbit.oak.spi.state.AbstractRebaseDiff.childNodeDeleted(AbstractRebaseDiff.java:232)
at org.apache.jackrabbit.oak.plugins.memory.ModifiedNodeState.compareAgainstBaseState(ModifiedNodeState.java:389)
at org.apache.jackrabbit.oak.spi.state.AbstractRebaseDiff.childNodeChanged(AbstractRebaseDiff.java:219)
at org.apache.jackrabbit.oak.plugins.memory.ModifiedNodeState.compareAgainstBaseState(ModifiedNodeState.java:396)
at org.apache.jackrabbit.oak.spi.state.AbstractRebaseDiff.childNodeChanged(AbstractRebaseDiff.java:219)
at org.apache.jackrabbit.oak.plugins.memory.ModifiedNodeState.compareAgainstBaseState(ModifiedNodeState.java:396)
at org.apache.jackrabbit.oak.spi.state.AbstractRebaseDiff.childNodeChanged(AbstractRebaseDiff.java:219)
at org.apache.jackrabbit.oak.plugins.memory.ModifiedNodeState.compareAgainstBaseState(ModifiedNodeState.java:396)
at org.apache.jackrabbit.oak.spi.state.AbstractRebaseDiff.childNodeChanged(AbstractRebaseDiff.java:219)
at org.apache.jackrabbit.oak.plugins.memory.ModifiedNodeState.compareAgainstBaseState(ModifiedNodeState.java:396)
at org.apache.jackrabbit.oak.plugins.document.DocumentRootBuilder.rebase(DocumentRootBuilder.java:134)
at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStore.rebase(DocumentNodeStore.java:1345)
at org.apache.jackrabbit.oak.core.MutableRoot.rebase(MutableRoot.java:223)
at org.apache.jackrabbit.oak.jcr.delegate.SessionDelegate.refresh(SessionDelegate.java:548)
at org.apache.jackrabbit.oak.jcr.delegate.SessionDelegate.perform(SessionDelegate.java:284)
at org.apache.jackrabbit.oak.jcr.session.ItemImpl.perform(ItemImpl.java:113)
at org.apache.jackrabbit.oak.jcr.session.ItemImpl.getName(ItemImpl.java:137)
at org.apache.jackrabbit.oak.jcr.session.PropertyImpl.getName(PropertyImpl.java:54)
at org.apache.sling.jcr.resource.JcrPropertyMap.cacheProperty(JcrPropertyMap.java:263)
at org.apache.sling.jcr.resource.JcrPropertyMap.read(JcrPropertyMap.java:352)
at org.apache.sling.jcr.resource.JcrPropertyMap.get(JcrPropertyMap.java:130)
{code}
with oak 1.0.9.r1646300:
{code}
java.lang.Thread.State: RUNNABLE
at org.mapdb.BTreeMap.findChildren(BTreeMap.java:580)
at org.mapdb.BTreeMap.get(BTreeMap.java:607)
at org.mapdb.BTreeMap.get(BTreeMap.java:589)
at org.apache.jackrabbit.oak.plugins.document.UnsavedModifications.put(UnsavedModifications.java:83)
at org.apache.jackrabbit.oak.plugins.document.Branch$BranchCommitImpl.applyTo(Branch.java:288)
at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.applyTo(Branch.java:328)
at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.applyTo(Branch.java:328)
at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.applyTo(Branch.java:328)
at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.applyTo(Branch.java:328)
at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.applyTo(Branch.java:328)
at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.applyTo(Branch.java:328)
at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.applyTo(Branch.java:328)
at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.applyTo(Branch.java:328)
at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.applyTo(Branch.java:328)
at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.applyTo(Branch.java:328)
at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.applyTo(Branch.java:328)
at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.applyTo(Branch.java:328)
at org.apache.jackrabbit.oak.plugins.document.Branch.applyTo(Branch.java:189)
at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStore.merge(DocumentNodeStore.java:1220)
at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStoreBranch.merge(DocumentNodeStoreBranch.java:73)
at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStoreBranch.merge(DocumentNodeStoreBranch.java:39)
at org.apache.jackrabbit.oak.spi.state.AbstractNodeStoreBranch$Persisted$1.call(AbstractNodeStoreBranch.java:617)
at org.apache.jackrabbit.oak.spi.state.AbstractNodeStoreBranch$Persisted$1.call(AbstractNodeStoreBranch.java:612)
at org.apache.jackrabbit.oak.spi.state.AbstractNodeStoreBranch.withCurrentBranch(AbstractNodeStoreBranch.java:745)
at org.apache.jackrabbit.oak.spi.state.AbstractNodeStoreBranch.access$300(AbstractNodeStoreBranch.java:53)
at org.apache.jackrabbit.oak.spi.state.AbstractNodeStoreBranch$Persisted.merge(AbstractNodeStoreBranch.java:612)
at org.apache.jackrabbit.oak.spi.state.AbstractNodeStoreBranch.merge(AbstractNodeStoreBranch.java:318)
at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStoreBranch.merge(DocumentNodeStoreBranch.java:131)
at org.apache.jackrabbit.oak.plugins.document.DocumentRootBuilder.merge(DocumentRootBuilder.java:159)
at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStore.merge(DocumentNodeStore.java:1337)
at org.apache.jackrabbit.oak.core.MutableRoot.commit(MutableRoot.java:247)
at org.apache.jackrabbit.oak.jcr.delegate.SessionDelegate.commit(SessionDelegate.java:390)
at org.apache.jackrabbit.oak.jcr.delegate.SessionDelegate.save(SessionDelegate.java:536)
{code}
and also with oak 1.0.9.r1646300:
{code}
java.lang.Thread.State: RUNNABLE
at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.isModified(Branch.java:335)
at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.isModified(Branch.java:335)
at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.isModified(Branch.java:335)
at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.isModified(Branch.java:335)
at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.isModified(Branch.java:335)
at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.isModified(Branch.java:335)
at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.isModified(Branch.java:335)
at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.isModified(Branch.java:335)
at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.isModified(Branch.java:335)
at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.isModified(Branch.java:335)
at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.isModified(Branch.java:335)
at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.isModified(Branch.java:335)
at org.apache.jackrabbit.oak.plugins.document.Branch.getUnsavedLastRevision(Branch.java:211)
at org.apache.jackrabbit.oak.plugins.document.NodeDocument.getNodeAtRevision(NodeDocument.java:882)
at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStore.readNode(DocumentNodeStore.java:929)
at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStore$3.call(DocumentNodeStore.java:706)
at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStore$3.call(DocumentNodeStore.java:703)
at com.google.common.cache.LocalCache$LocalManualCache$1.load(LocalCache.java:4724)
at com.google.common.cache.LocalCache$LoadingValueReference.loadFuture(LocalCache.java:3522)
at com.google.common.cache.LocalCache$Segment.loadSync(LocalCache.java:2315)
at com.google.common.cache.LocalCache$Segment.lockedGetOrLoad(LocalCache.java:2278)
- locked <0x0000000714588728> (a com.google.common.cache.LocalCache$StrongAccessEntry)
at com.google.common.cache.LocalCache$Segment.get(LocalCache.java:2193)
at com.google.common.cache.LocalCache.get(LocalCache.java:3932)
at com.google.common.cache.LocalCache$LocalManualCache.get(LocalCache.java:4721)
at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStore.getNode(DocumentNodeStore.java:703)
at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStore.readChildren(DocumentNodeStore.java:785)
at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStore$4.call(DocumentNodeStore.java:733)
at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStore$4.call(DocumentNodeStore.java:730)
at com.google.common.cache.LocalCache$LocalManualCache$1.load(LocalCache.java:4724)
at com.google.common.cache.LocalCache$LoadingValueReference.loadFuture(LocalCache.java:3522)
at com.google.common.cache.LocalCache$Segment.loadSync(LocalCache.java:2315)
at com.google.common.cache.LocalCache$Segment.lockedGetOrLoad(LocalCache.java:2278)
- locked <0x0000000714580700> (a com.google.common.cache.LocalCache$StrongAccessEntry)
at com.google.common.cache.LocalCache$Segment.get(LocalCache.java:2193)
at com.google.common.cache.LocalCache.get(LocalCache.java:3932)
at com.google.common.cache.LocalCache$LocalManualCache.get(LocalCache.java:4721)
at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStore.getChildren(DocumentNodeStore.java:730)
at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStore.diffImpl(DocumentNodeStore.java:1666)
at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStore.access$200(DocumentNodeStore.java:105)
at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStore$7.call(DocumentNodeStore.java:1259)
at org.apache.jackrabbit.oak.plugins.document.MongoDiffCache.getChanges(MongoDiffCache.java:88)
at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStore.diffChildren(DocumentNodeStore.java:1254)
at org.apache.jackrabbit.oak.plugins.document.DocumentNodeState.compareAgainstBaseState(DocumentNodeState.java:260)
at org.apache.jackrabbit.oak.plugins.commit.MergingNodeStateDiff.merge(MergingNodeStateDiff.java:70)
at org.apache.jackrabbit.oak.plugins.commit.MergingNodeStateDiff.childNodeChanged(MergingNodeStateDiff.java:92)
at org.apache.jackrabbit.oak.plugins.document.DocumentNodeState.dispatch(DocumentNodeState.java:433)
at org.apache.jackrabbit.oak.plugins.document.DocumentNodeState.compareAgainstBaseState(DocumentNodeState.java:260)
at org.apache.jackrabbit.oak.plugins.commit.MergingNodeStateDiff.merge(MergingNodeStateDiff.java:70)
at org.apache.jackrabbit.oak.plugins.commit.MergingNodeStateDiff.merge(MergingNodeStateDiff.java:65)
at org.apache.jackrabbit.oak.plugins.commit.ConflictHook.processCommit(ConflictHook.java:53)
at org.apache.jackrabbit.oak.spi.commit.CompositeHook.processCommit(CompositeHook.java:60)
at org.apache.jackrabbit.oak.spi.commit.CompositeHook.processCommit(CompositeHook.java:60)
at org.apache.jackrabbit.oak.spi.state.AbstractNodeStoreBranch$Persisted$1.call(AbstractNodeStoreBranch.java:615)
at org.apache.jackrabbit.oak.spi.state.AbstractNodeStoreBranch$Persisted$1.call(AbstractNodeStoreBranch.java:612)
at org.apache.jackrabbit.oak.spi.state.AbstractNodeStoreBranch.withCurrentBranch(AbstractNodeStoreBranch.java:745)
at org.apache.jackrabbit.oak.spi.state.AbstractNodeStoreBranch.access$300(AbstractNodeStoreBranch.java:53)
at org.apache.jackrabbit.oak.spi.state.AbstractNodeStoreBranch$Persisted.merge(AbstractNodeStoreBranch.java:612)
at org.apache.jackrabbit.oak.spi.state.AbstractNodeStoreBranch.merge(AbstractNodeStoreBranch.java:318)
at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStoreBranch.merge(DocumentNodeStoreBranch.java:131)
at org.apache.jackrabbit.oak.plugins.document.DocumentRootBuilder.merge(DocumentRootBuilder.java:159)
at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStore.merge(DocumentNodeStore.java:1337)
at org.apache.jackrabbit.oak.core.MutableRoot.commit(MutableRoot.java:247)
at org.apache.jackrabbit.oak.jcr.delegate.SessionDelegate.commit(SessionDelegate.java:390)
at org.apache.jackrabbit.oak.jcr.delegate.SessionDelegate.save(SessionDelegate.java:536)
{code}
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)