You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@directory.apache.org by sa...@apache.org on 2011/10/27 16:11:03 UTC
svn commit: r1189768 - in /directory/apacheds/branches/apacheds-txns:
core-api/src/main/java/org/apache/directory/server/core/txn/
core/src/main/java/org/apache/directory/server/core/txn/
Author: saya
Date: Thu Oct 27 14:11:02 2011
New Revision: 1189768
URL: http://svn.apache.org/viewvc?rev=1189768&view=rev
Log:
Changes to add conflict detection service to the txn manager.
DnSet: keeps track of the base dn and the scope a read depends on or a write afffects.
For a txn, readset is always a superset of writeset.
When txn tries to commit, its read set is checked against the writeset of the txns that committed after it started. If conflict is found, a txnconflict exception is thrown.
Added:
directory/apacheds/branches/apacheds-txns/core-api/src/main/java/org/apache/directory/server/core/txn/TxnConflictException.java
directory/apacheds/branches/apacheds-txns/core/src/main/java/org/apache/directory/server/core/txn/DnSet.java
Modified:
directory/apacheds/branches/apacheds-txns/core-api/src/main/java/org/apache/directory/server/core/txn/TxnLogManager.java
directory/apacheds/branches/apacheds-txns/core-api/src/main/java/org/apache/directory/server/core/txn/TxnManager.java
directory/apacheds/branches/apacheds-txns/core/src/main/java/org/apache/directory/server/core/txn/DefaultTxnLogManager.java
directory/apacheds/branches/apacheds-txns/core/src/main/java/org/apache/directory/server/core/txn/DefaultTxnManager.java
directory/apacheds/branches/apacheds-txns/core/src/main/java/org/apache/directory/server/core/txn/ReadWriteTxn.java
Added: directory/apacheds/branches/apacheds-txns/core-api/src/main/java/org/apache/directory/server/core/txn/TxnConflictException.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-txns/core-api/src/main/java/org/apache/directory/server/core/txn/TxnConflictException.java?rev=1189768&view=auto
==============================================================================
--- directory/apacheds/branches/apacheds-txns/core-api/src/main/java/org/apache/directory/server/core/txn/TxnConflictException.java (added)
+++ directory/apacheds/branches/apacheds-txns/core-api/src/main/java/org/apache/directory/server/core/txn/TxnConflictException.java Thu Oct 27 14:11:02 2011
@@ -0,0 +1,51 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+package org.apache.directory.server.core.txn;
+
+/**
+ * An exception used when the txn conflict is detected.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class TxnConflictException extends Exception
+{
+ public TxnConflictException()
+ {
+ }
+
+
+ public TxnConflictException( String s )
+ {
+ super( s );
+ }
+
+
+ public TxnConflictException( Throwable cause )
+ {
+ super( cause );
+ }
+
+
+ public TxnConflictException( String s, Throwable cause )
+ {
+ super( s, cause );
+ }
+
+}
\ No newline at end of file
Modified: directory/apacheds/branches/apacheds-txns/core-api/src/main/java/org/apache/directory/server/core/txn/TxnLogManager.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-txns/core-api/src/main/java/org/apache/directory/server/core/txn/TxnLogManager.java?rev=1189768&r1=1189767&r2=1189768&view=diff
==============================================================================
--- directory/apacheds/branches/apacheds-txns/core-api/src/main/java/org/apache/directory/server/core/txn/TxnLogManager.java (original)
+++ directory/apacheds/branches/apacheds-txns/core-api/src/main/java/org/apache/directory/server/core/txn/TxnLogManager.java Thu Oct 27 14:11:02 2011
@@ -27,6 +27,8 @@ import org.apache.directory.server.core.
import org.apache.directory.shared.ldap.model.entry.Entry;
import org.apache.directory.shared.ldap.model.name.Dn;
+import org.apache.directory.shared.ldap.model.message.SearchScope;
+
import java.io.IOException;
/**
@@ -42,4 +44,8 @@ public interface TxnLogManager<ID>
Entry mergeUpdates(Dn partitionDN, ID entryID, Entry entry );
IndexCursor<Object, Entry, ID> wrap( Dn partitionDn, IndexCursor<Object, Entry, ID> wrappedCursor, IndexComparator<Object,ID> comparator, String attributeOid, boolean forwardIndex, Object onlyValueKey, ID onlyIDKey ) throws Exception;
+
+ void addRead( Dn baseDn, SearchScope scope );
+
+ void addWrite( Dn baseDn, SearchScope scope );
}
Modified: directory/apacheds/branches/apacheds-txns/core-api/src/main/java/org/apache/directory/server/core/txn/TxnManager.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-txns/core-api/src/main/java/org/apache/directory/server/core/txn/TxnManager.java?rev=1189768&r1=1189767&r2=1189768&view=diff
==============================================================================
--- directory/apacheds/branches/apacheds-txns/core-api/src/main/java/org/apache/directory/server/core/txn/TxnManager.java (original)
+++ directory/apacheds/branches/apacheds-txns/core-api/src/main/java/org/apache/directory/server/core/txn/TxnManager.java Thu Oct 27 14:11:02 2011
@@ -31,7 +31,7 @@ public interface TxnManager<ID>
{
void beginTransaction( boolean readOnly ) throws IOException;
- void commitTransaction() throws IOException;
+ void commitTransaction() throws IOException, TxnConflictException;
void abortTransaction() throws IOException;
Modified: directory/apacheds/branches/apacheds-txns/core/src/main/java/org/apache/directory/server/core/txn/DefaultTxnLogManager.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-txns/core/src/main/java/org/apache/directory/server/core/txn/DefaultTxnLogManager.java?rev=1189768&r1=1189767&r2=1189768&view=diff
==============================================================================
--- directory/apacheds/branches/apacheds-txns/core/src/main/java/org/apache/directory/server/core/txn/DefaultTxnLogManager.java (original)
+++ directory/apacheds/branches/apacheds-txns/core/src/main/java/org/apache/directory/server/core/txn/DefaultTxnLogManager.java Thu Oct 27 14:11:02 2011
@@ -30,6 +30,7 @@ import org.apache.directory.server.core.
import org.apache.directory.server.core.api.partition.index.IndexComparator;
import org.apache.directory.shared.ldap.model.entry.Entry;
+import org.apache.directory.shared.ldap.model.message.SearchScope;
import org.apache.directory.shared.ldap.model.name.Dn;
import org.apache.directory.server.core.txn.logedit.LogEdit;
@@ -148,4 +149,53 @@ public class DefaultTxnLogManager<ID> im
{
return new IndexCursorWrapper<ID>( partitionDn, wrappedCursor, comparator, attributeOid, forwardIndex, onlyValueKey, onlyIDKey );
}
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public void addRead( Dn baseDn, SearchScope scope )
+ {
+ addDnSet( baseDn, scope, true );
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public void addWrite( Dn baseDn, SearchScope scope )
+ {
+ addDnSet( baseDn, scope, true );
+ }
+
+
+ private void addDnSet( Dn baseDn, SearchScope scope, boolean read )
+ {
+ Transaction<ID> curTxn = txnManager.getCurTxn();
+
+ if ( ( curTxn == null ) )
+ {
+ throw new IllegalStateException( "Trying to add dn set wihout txn" );
+ }
+
+ // No need to do anything for read only txns
+ if ( !( curTxn instanceof ReadWriteTxn ) )
+ {
+
+ return;
+
+ }
+
+ DnSet dnSet = new DnSet( baseDn, scope );
+ ReadWriteTxn txn = ( ReadWriteTxn ) curTxn;
+
+ if ( read )
+ {
+ txn.addRead( dnSet );
+ }
+ else
+ {
+ txn.addWrite( dnSet );
+ }
+ }
}
\ No newline at end of file
Modified: directory/apacheds/branches/apacheds-txns/core/src/main/java/org/apache/directory/server/core/txn/DefaultTxnManager.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-txns/core/src/main/java/org/apache/directory/server/core/txn/DefaultTxnManager.java?rev=1189768&r1=1189767&r2=1189768&view=diff
==============================================================================
--- directory/apacheds/branches/apacheds-txns/core/src/main/java/org/apache/directory/server/core/txn/DefaultTxnManager.java (original)
+++ directory/apacheds/branches/apacheds-txns/core/src/main/java/org/apache/directory/server/core/txn/DefaultTxnManager.java Thu Oct 27 14:11:02 2011
@@ -146,7 +146,7 @@ public class DefaultTxnManager<ID> imple
/**
* {@inheritDoc}
*/
- public void commitTransaction() throws IOException
+ public void commitTransaction() throws IOException, TxnConflictException
{
Transaction<ID> txn = getCurTxn();
@@ -375,7 +375,7 @@ public class DefaultTxnManager<ID> imple
}
- private void commitReadWriteTxn( ReadWriteTxn<ID> txn ) throws IOException
+ private void commitReadWriteTxn( ReadWriteTxn<ID> txn ) throws IOException, TxnConflictException
{
UserLogRecord logRecord = txn.getUserLogRecord();
@@ -410,7 +410,27 @@ public class DefaultTxnManager<ID> imple
verifyLock.lock();
- // TODO verify txn here throw conflict exception if necessary
+ //Verify txn and throw conflict exception if necessary
+ Iterator<ReadWriteTxn<ID>> it = committedQueue.iterator();
+ ReadWriteTxn toCheckTxn;
+ long startTime = txn.getStartTime();
+
+ while ( it.hasNext() )
+ {
+ toCheckTxn = it.next();
+
+ // Check txns that committed after we started
+ if ( toCheckTxn.getCommitTime() < startTime )
+ {
+ continue;
+ }
+
+ if ( txn.hasConflict( toCheckTxn ) )
+ {
+ verifyLock.unlock();
+ throw new TxnConflictException();
+ }
+ }
writeTxnsLock.lock();
@@ -421,6 +441,7 @@ public class DefaultTxnManager<ID> imple
txn.commitTxn( logRecord.getLogAnchor().getLogLSN() );
latestVerifiedTxn.set( txn );
+ committedQueue.offer( txn );
// TODO when sync is done outside the locks, advance latest commit outside the locks
latestCommittedTxn.set( txn );
Added: directory/apacheds/branches/apacheds-txns/core/src/main/java/org/apache/directory/server/core/txn/DnSet.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-txns/core/src/main/java/org/apache/directory/server/core/txn/DnSet.java?rev=1189768&view=auto
==============================================================================
--- directory/apacheds/branches/apacheds-txns/core/src/main/java/org/apache/directory/server/core/txn/DnSet.java (added)
+++ directory/apacheds/branches/apacheds-txns/core/src/main/java/org/apache/directory/server/core/txn/DnSet.java Thu Oct 27 14:11:02 2011
@@ -0,0 +1,59 @@
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+package org.apache.directory.server.core.txn;
+
+import org.apache.directory.shared.ldap.model.name.Dn;
+import org.apache.directory.shared.ldap.model.message.SearchScope;
+
+/**
+ * A class representing the set of Dns a read operation depends or the set of Dns a write
+ * operation affects.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class DnSet
+{
+ /** Base Dn */
+ private Dn baseDn;
+
+ /** Scope of the set */
+ SearchScope dnScope;
+
+
+ public DnSet( Dn base, SearchScope scope )
+ {
+ baseDn = base;
+ dnScope = scope;
+ }
+
+
+ public Dn getBaseDn()
+ {
+ return baseDn;
+ }
+
+
+ public SearchScope getScope()
+ {
+ return dnScope;
+ }
+}
Modified: directory/apacheds/branches/apacheds-txns/core/src/main/java/org/apache/directory/server/core/txn/ReadWriteTxn.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-txns/core/src/main/java/org/apache/directory/server/core/txn/ReadWriteTxn.java?rev=1189768&r1=1189767&r2=1189768&view=diff
==============================================================================
--- directory/apacheds/branches/apacheds-txns/core/src/main/java/org/apache/directory/server/core/txn/ReadWriteTxn.java (original)
+++ directory/apacheds/branches/apacheds-txns/core/src/main/java/org/apache/directory/server/core/txn/ReadWriteTxn.java Thu Oct 27 14:11:02 2011
@@ -52,6 +52,8 @@ import org.apache.directory.shared.ldap.
import org.apache.directory.shared.ldap.model.constants.SchemaConstants;
+import org.apache.directory.shared.ldap.model.message.SearchScope;
+
/**
*
* @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
@@ -73,14 +75,25 @@ class ReadWriteTxn<ID> extends AbstractT
/** User record used to communicate data with log manager */
private UserLogRecord logRecord = new UserLogRecord();
+ /** A summary of forward index adds */
private Map<Dn, Map<String, TreeSet< IndexEntry<Object,ID> >>> forwardIndexAdds =
new HashMap<Dn, Map<String, TreeSet< IndexEntry<Object,ID> >>>();
+ /** A summary of reverse index adds */
private Map<Dn, Map<String, TreeSet< IndexEntry<Object,ID> >>> reverseIndexAdds =
new HashMap<Dn, Map<String, TreeSet< IndexEntry<Object,ID> >>>();
+ /** A summary of index deletes */
private Map<Dn, Map<String, TreeSet< IndexEntry<Object,ID> >>> indexDeletes =
new HashMap<Dn, Map<String, TreeSet< IndexEntry<Object,ID> >>>();
+
+
+ /** List of Dn sets this txn depends */
+ private List<DnSet> readDns = new LinkedList<DnSet>();
+
+ /** List of Dn sets affected by the write operations of this txn */
+ private List<DnSet> writeDns = new LinkedList<DnSet>();
+
public AtomicInteger getRefCount()
{
@@ -350,4 +363,93 @@ class ReadWriteTxn<ID> extends AbstractT
return txnIndexCursor;
}
+
+ public void addRead( DnSet readSet )
+ {
+ readDns.add( readSet );
+ }
+
+ public void addWrite( DnSet writeSet )
+ {
+ writeDns.add( writeSet );
+
+ // Changing a dn means also read dependency
+ readDns.add( writeSet );
+ }
+
+ public List<DnSet> getWriteSet()
+ {
+ return writeDns;
+ }
+
+ public boolean hasConflict( ReadWriteTxn txn )
+ {
+ boolean result = false;
+
+
+ List<DnSet> txnWriteDns = txn.getWriteSet();
+ Iterator<DnSet> writeIt = txnWriteDns.iterator();
+ Iterator<DnSet> readIt = readDns.iterator();
+
+ DnSet readDnSet;
+ SearchScope readScope;
+ DnSet writeDnSet;
+ SearchScope writeScope;
+
+ while ( readIt.hasNext() )
+ {
+ readDnSet = readIt.next();
+ readScope = readDnSet.getScope();
+
+ while ( writeIt.hasNext() )
+ {
+ writeDnSet = writeIt.next();
+ writeScope = writeDnSet.getScope();
+
+ if ( readScope.equals( SearchScope.OBJECT ) )
+ {
+ if ( writeScope.equals( SearchScope.OBJECT ) )
+ {
+ if ( readDnSet.getBaseDn().equals( writeDnSet.getBaseDn() ) )
+ {
+ result = true;
+ break;
+ }
+ }
+ else //one level or subtree scope for the write.
+ {
+ // Even if one level scope, conservatively check the whole subtree
+ if ( readDnSet.getBaseDn().isDescendantOf( writeDnSet.getBaseDn() ) )
+ {
+ result = true;
+ break;
+ }
+ }
+ }
+ else //one level or subtree scope for the read.
+ {
+ if ( writeScope.equals( SearchScope.OBJECT ) )
+ {
+ if ( readDnSet.getBaseDn().isAncestorOf( writeDnSet.getBaseDn() ) )
+ {
+ result = true;
+ break;
+ }
+ }
+ else //one level or subtree scope for the write.
+ {
+ // Even if one level scope, conservatively check if any basedn is descendent of the other
+ if ( ( readDnSet.getBaseDn().isDescendantOf( writeDnSet.getBaseDn() ) ) ||
+ ( readDnSet.getBaseDn().isAncestorOf( writeDnSet.getBaseDn() ) ) )
+ {
+ result = true;
+ break;
+ }
+ }
+ }
+ } // end of inner while loop
+ } // end of outer while loop
+
+ return result;
+ }
}