Proposal: it's time to think about Record Locking

[Luca Garulli]

Hi guys,

it's time to start discussing about the record locking strategies we'll support in OrientDB. I prefer to open this thread to all the users here, instead of talk about it internally in Orient Technologies, because I'm confident we could receive good idea and contributions.

Even tough Optimistic approach (CAS like) is great for many use cases, sometimes users need a more "Pessimistic" approach by locking resources. This is the case of persistent queues or any other operation I need to be sure no other thread/client is fetching the same record.

Few of the issues related to this topic:

- Pessimistic TX: https://github.com/orientechnologies/orientdb/issues/12

- Non-TX Atomic ops: https://github.com/orientechnologies/orientdb/issues/1056

Now we've the ORecordLockManager that extends the OLockManager (that has been developed more than 2 years ago, so probably it would need a refresh about better synchronization policies?) that does the job: locking RID in read or write mode.

We already use it internally, but I'd like to let to the user to expressly lock resources. I don't know if I'd like the classic RDBMS way to just use the transaction (or some variant of SQL like SELECT FOR UPDATE) or better to offer a more explicit way to lock resources giving more control/power to developers.

Below my initial proposal.

Support LOCK/UNLOCK directly in SELECT, UPDATE AND DELETE

Examples:

SELECT FROM Client WHERE city.name = 'London' LOCK SHARED

UPDATE Client SET local = true WHERE city.name = 'London' LOCK EXCLUSIVE

DELETE FROM Client WHERE local = true LOCK EXCLUSIVE

New SQL LOCK command

Syntax: LOCK <cluster-name|rid|(select-statement)> SHARED|EXCLUSIVE

New SQL UNLOCK command

Syntax: UNLOCK <cluster-name|rid|(select-statement)|*> SHARED|EXCLUSIVE

- "*" means release all the acquired locks

Automatic releasing of locks

Locks are kept by ODatabase instance that represents a client connection. Once the server disconnects a database it should close it. The ODatabase.close() should free all the acquired locks.

Real use cases: FIFO queue management

Even though we could provide better way to manage a queue, this would work. Push a message into a queue (class Queue):

INSERT INTO Queue SET payload = 'yeah', date = sysdate()

Pop the first message (returning is a new keyword part of the issue https://github.com/orientechnologies/orientdb/issues/1056):

DELETE FROM Queue ORDER BY date LIMIT 1 LOCK exclusive RETURNING before

WDYT?

Luca Garulli

CEO at Orient Technologies

the Company behind OrientDB

http://about.me/luca.garulli

[Andrey Lomakin]

Hi,

Couple of thought which come into my mind.

At first seems approach proposed for FIFO queues will not work with record locking.

I mean that we can pop first message from queue in "multithreading correct way" only in the case when the whole cluster not records will be locked during execution of last query, does not it ?

Also atomic operations this is not only locking they mean that during server crash we have record at the start or end state not in the middle and record locking does not guarantee it.

So why do not implement original proposal with ONCE key word to ensure operation atomicity ?

I mean record locking is not bad, but it does not solve issues related to atomic updates or queues (of course may be I miss something).

About pessimistic tx, personally I do not support them, because they have very pure multi core support. 

Also I did not find any comments from users which want them to be implemented.

The last note,. it is minor but still valuable I think, proposed approach means that records will be locked and releases using different threads (if we use remote storage, we can execute lock/unlock query from different connections)  OLockManager does not support such approach because that is map of java.util.concurrent.locks.Lock-s which require that lock and unlock should be performed in the same thread.

It can be overcomed but we should keep this in mind if we will decide to implement record level locks. 

--
 
---
You received this message because you are subscribed to the Google Groups "OrientDB" group.
To unsubscribe from this group and stop receiving emails from it, send an email to orient-databa...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

--

Best regards,
Andrey Lomakin.

[odbuser]

I would like optimistic and pessimistic locking.  In fact I would like it if you could specify the duration of the lock as well.
e.g. it would be nice to have write locks like the following:
LOCK -1 (INDEFINITE)
LOCK 800ms
LOCK 3m

Of course, this could be handled using a lock "table" but it would be nice to have this enforced as a feature of the database.

I have some general questions:

Does this imply that SQL will now participate in transactions?
How will this work in a distributed environment?
Will there be queries to determine who owns the locks?
How granular are the locks?  Is it vertex/document based or will we be able to lock properties?

[Emrul Islam]

I'll chime in my 2 cents here. Traditional lock management creates a lot of issues in modern distributed systems so I rather like CouchDB's approach of allowing applications the ability to detect and resolve conflicts.  I know its difficult for people to get their heads around it but I do think it provides superior approach (application designers get flexibility) and removes much of the complexity of lock management from the database.

However, I know there are so many use cases for locks that traditional lock management has a place too so I'll leave it to you guys to weigh this up.

[Pawel K.]

I tried to simulate queue based on current version.

In one thread I am able to reach 140 messages/s using following SQL

UPDATE #49:0 SET Applications.QueueItems = UNION(Applications.Items,[#54:2])

when I tried to use it in multi-thread scenario (5 threads). OConcurrentModificationException and retrying via network roundtrips killed performance to 50 msg/sec.

It was tested via remote protocol with loopback network. I assume in real multi server scenario the result would be even worse (higher cost of network retrying roundtrips).

     In such case I think that record locking would increase anyway overall performance (no network roundtrips retrying).

Now we can't even do simply increments like

UPDATE #54:2 INCREMENT Age = 1

without being exposed to OConcurrentModificationException 

When I do mentioned increments via remote COMMAND without providing my Version I would expect to get result without such exeptions because in that scenario I don't care about whole document and Version.

Reaching 170 increments on 5 threads (based on current CAS) is really poor and can't compete with MongoDB ($inc).

My suggestion is to keep record locking for one operation (TX_COMMIT,SQL_COMMAND). In multi-documents updates per record-update operation.

Pawel

[Luca Garulli]

Hi,

the pessimistic approach opened a lot of pros/cons. What Pawel suggests is very easy to implement with or without locking. We could manage this cases also with an optimistic automatic retry because you're not updating based on a version, but you're just asking an update against last version of the document:

UPDATE #54:2 INCREMENT Age = 1

Obviously this could work ONLY when no transactions are running, otherwise the entire tx should be re-executed but this should be delegated to the user application.

With pessimistic locks we could execute the SELECT statement (SQL Update executes an asynchronous SELECT under the hood to retrieve the records) with a lock = EXCLUSIVE and once updated the record the lock could be released, so the lock time would be very very short. These 2 approaches will improve update times on concurrent environment because:

- Optimistic approach will do the retry like before, but this would be only at server-side, so no network roundtrip for each retry

- Pessimistic approach will lock resources, so if multiple threads/clients will update the same record the pessimistic approach is usually faster

The same could be done with SQL DELETE statement.

So if we agree to procede on this, what's the best syntax? I can't find a similar approach with RDBMS. Some product allow to set the concurrency mode at table level, but no one allows to change strategy per COMMAND. So I was thinking to let the Optimistic approach the default one, but with auto-management of retry in case of OConcurrentModificationException. Pessimistic approach, instead, should be enforced with a new keyword:

UPDATE #54:2 INCREMENT Age = 1 USE LOCKING

Any other better proposal?

Lvc@

[Luca Garulli]

Hi Andrey,

if the goal would be creating the fastest concurrent persistent queue/topic on top of OrientDB we would need a better strategy by using ad-hoc structures (I've a couple of ideas on it, but it's off topic).

About OLockManager you're right, we should support a different implementation...

Lvc@

[Andrey Lomakin]

Hi Luca,

if the goal would be creating the fastest concurrent persistent queue/topic on top of OrientDB we would need a better strategy by using ad-hoc structures (I've a couple of ideas on it, but it's off topic).

My point is  not performance but  correctness of proposed approach in multi threading  environment.

The FIFO queue can not be implemented using locking of single of whole cluster records if we use order by query, because this approach will work only if whole cluster will be locked.

But implementation of queue embedded in document, not presented by several records (like Pawel proposed for example) is possible of course.

[Andrey Lomakin]

Hi,

It seems I miss some points, could someone explain me

why original proposal which allows to implement any operations like atomic till it is performed on single document is not acceptable I mean, now following syntax is proposed

"UPDATE #54:2 INCREMENT Age = 1 USE LOCKING"

original proposal has following example:

"UPDATE ONCE Person SET name = "Luca" WHERE name = "Tal" "

So introduction of ONCE or ATOMIС keyword will allow to perform any operation on atomic level for single document.

It allows to implement queues, sets, auto increment fields and so on.

So proposed autoincrement example can be written like this:

UPDATE ATOMIC #54:2 Age = Age + 1 USE LOCKING

or even better

UPDATE ATOMIC #54:2 Age = Age + ? USE LOCKING

queue can be implemented like this :

UPDATE ATOMIC #49:0  add queueItems = #54:2

and 

UPDATE ATOMIC #49:0  remove queueItems = queueItems[queueItems.length] RETURNING queueItems[queueItems.length]

and so on ....

Actually it opens a lot of possibilities.

P.S. Still would like to note that implementation of this feature only on SQL level means that it will be not durable, some projects can accept it some can not.

--

Best regards,
Andrey Lomakin.

[Andrey Lomakin]

Sorry skip my P.S. any changes on single document are durable by design in plocal. 

[Pawel K.]

I personally really like ATOMIC or USE LOCKING approach.

I also would like to show you second common scenario when ConcurrentModificationException is a pain and maybe pessimistic locking or atomic operation whould solve common performance issues.

Typical use case in applications is to create couple of new vertices and link them with each other (it's easy&quick part without concurrent modification) and link them with EXISTING vertices via edges. Existing vertices usually are shared among many updates (out_ in_).

Example:

NEW_ORDER'S ITEMS->NEW_ORDER -> CUSTOMER (high concurrent modification exposure)

                                                           ->  ORDER_TYPE (very high concurrent modification exposure)

I can store data using two approaches:

#1.

     Roundtrip 1: CREATE VERTEX NEW_ORDERITEM1.....

     Roundtrip 2: CREATE VERTEX NEW_ORDERITEM2.....

     Roundtrip 3: CREATE VERTEX NEW_ORDER.....

     Roundtrip 4: CREATE EDGE HAS_ITEMS...

     Roundtrip 5: CREATE EDGE HAS_ITEMS...

     Roundtrip 6: CREATE EDGE HAS_ORDERS...

     Roundtrip 7: CREATE EDGE HAS_TYPE

cons:

         - roundtrips,chatty

         - it's not transactional 

         - orphaned vertices in case of errors

#2 TX

     Roundtrip 1: SELECT FROM ORDER_TYPE_RID

     Roundtrip 2: SELECT FROM CUSTOMER_RID

     Roundtrip 3: COMMIT  

                              INSERT:NEW_ITEM,NEW_ITEM,NEW_ORDER

                              UPDATE: CUSTOMER, ORDER_TYPE

pros:

    - fully transactional

    - no orphaned vertices in case of errors

    - in theory should be faster, less roundtrips

    - less chatty

cons:

    - higher exposure to concurrent modifications exception--> TX always has to send FULL newest document (CUSTOMER,ORDER_TYPE)

    - cost of retrying is expensive especially if additional loading of fresh data is needed

    - poor performance if there is many edges to CUSTOMER,ORDER_TYPE ( big serialized,deserialized objects via network)--> even higher chance for concurrent exception

PROPOSED SOLUTION:

If we could only send sql commands (like CREATE EDGE FROM #TEMP_RID TO CUSTOMER_RID) in TX_COMMIT, the OConncurentModificationException wouldn't be a huge problem and performance would be in theory optimal.

Second way, maybe more elegant and consistent is possibility to add UPDATE_TYPE for updates to TX_COMMIT (SET or MERGE) and execute updates as locked atomic record operation. If we do so, mentioned case can be done in ONE roundtrip even without loadings CUSTOMER,ORDER_TYPE preserving all advantages.

Best regards,

Pawel

[Kai Londenberg]

Hi,

just my 2 cents:

- If I were you, I would focus on quality and documentation first, vertex centric queries next. A new locking mechanism seems like a  potential diversion and source of new bugs to me.

- Whatever you do, Locking mechanisms can be a performance killer. Make sure it's possible to completely disable the locking machinery, especially in bulk load scenarios.

best,

Kai Londenberg

[pieter]

+1

[Luca Garulli]

Hi Kai,

we've priorities and this lock is not the most important thing right now. We like to share ideas and implementation details with users in early stage to understand what they need.

So we don't know yet if/when this will be done, it's just an idea shared with users at this stage.

About the performance killer we're talking about additional strategies to address daily problems on concurrent environment. All the existent modes will remain.

Lvc@