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:57:11 UTC
[jira] [Commented] (OAK-2513) algorithm with O(n!) in mongoMk
rebase - not finishing in years
[ https://issues.apache.org/jira/browse/OAK-2513?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14318755#comment-14318755 ]
Stefan Egli commented on OAK-2513:
----------------------------------
OAK-1981 introduced Branch.RebaseCommit/BranchCommitImpl so looks related
> 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.9, 1.0.11
> 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)