very optimistic locking :)

I have an application where a user has a list of tasks. Some of the lists are shared among users. So there are multiple users that may write to multiple lists. I want to make sure that two simultanous writes do not conflict. And I like to avoid a central lock somewhere. Do you know anything that is applicable to this kind of problem when the objects to lock are not known upfront? Let's say we have 10000 users with each having 10 lists at average and 20% of all lists are shared.

I could add all lists that need to be written to a centralized lock list where each action can determine of any of its lists is written at the moment. Is there anything that works like the shared counter? Or would I need in this case to add to central list, commit, doing my action and remove from central list and commit?

Or are there any clever ways to solve this?

thanks,

Norbert

Norbert,

You can use an RcQueue[1] to record operations. With a multiple producers and a single consumer, RcQueues are conflict free. You could have a separate process pull the operations off of the queue and attempt to resolve conflicts automatically - having a last edit wins policy would mean that you wouldn't need a user involved to resolve the conflicts. But this would basically be your "add, commit, perform, remove, commit" process.

Next, what is the problem with locking the objects that are being editted?

I think the basic problem is that without the lock, there is no way to avoid simultaneous updates.

I think you can do a variant of the "add, commit, perform, remove, commit" process, by collapsing the sequence down to a single transaction:

  1) if the commit succeeds there was no conflict
  2) if the commit fails, you can examine the objects involved in
     the transaction:

       - if the object isn't a list object, then do the standard
         retry
       - if the object is a list object, do a retry, but set a flag
         in the request context indicating that the user needs to be
         notified that there change wasn't accepted and that they should
         try again...

If the editing of the list objects is going to span multiple http requests, then I think you might be interested in Johan's framework that he uses in NextPlan...

Dale    

[1] http://gemstonesoup.wordpress.com/2007/12/16/gemstone-101-transaction-conflicts/#rcqueue

----- Original Message -----
| From: "Norbert Hartl" <[hidden email]>
| To: "GemStone Seaside beta discussion" <[hidden email]>
| Sent: Monday, June 27, 2011 9:01:38 AM
| Subject: [GS/SS Beta] very optimistic locking :)
|
| I have an application where a user has a list of tasks. Some of the
| lists are shared among users. So there are multiple users that may
| write to multiple lists. I want to make sure that two simultanous
| writes do not conflict. And I like to avoid a central lock
| somewhere. Do you know anything that is applicable to this kind of
| problem when the objects to lock are not known upfront? Let's say we
| have 10000 users with each having 10 lists at average and 20% of all
| lists are shared.
|
| I could add all lists that need to be written to a centralized lock
| list where each action can determine of any of its lists is written
| at the moment. Is there anything that works like the shared counter?
| Or would I need in this case to add to central list, commit, doing
| my action and remove from central list and commit?
|
| Or are there any clever ways to solve this?
|
| thanks,
|
| Norbert

Dale,

our application has support for conflict resolution. We do updates of the model and resolve condlicts at the client side as the client is the only one that can decide how to resolve a conflict. We do updates as long as there are changes server side. If there aren't any than we do the write operation. That leaves as with a short timeframe of conflict potential. I just recently recognized that a write to the collections happens very fast but the transaction lasts for as long as the request takes. We are doing mobile applications and therefor a user using edge networks could have requests that last a few seconds. So I think I have two choice. Either place the transction brackets close to the write operation instead of the request handling period. Or I could lock the collection of collections for the time something is written. The latter one would need to add the collections-to-be-written in an extra transction so it is world available. That is the two transaction request processing: write locking collection, commit, alter data and remove locking collection and commit again.

> Next, what is the problem with locking the objects that are being editted?

What would be a good way to do this? Where to place the lock? Should every collection has its own lock which is activated before the write operation? How do thousands of monitors affect performance compared to a central lock?

thanks in advance,

Norbert

Below when you say that "the transaction lasts for as long as the request takes", I am not sure what you are referring to.

The transaction starts with an abort when the HTML request is converted into a WARequest and terminates with a commit when the WAResponse is converted into the HTML response. The time spent in transaction should be very short and is not a function of how fast or slow the network transport layer is....The user may see a request lasting multiple seconds, but the actual time spent in transaction in GemStone is very short ...

The general problem in the web, is that a user may be making decisions based on a stale view of the model ... if a page sits open for two days (and the session doesn't time out) before the user hits the submit button, the updates will not be correct if the underlying data has changed over the last few days ... the solution to this particular problem is pretty much application specific and I don't think that gemstone locks will be of help here (they would be of use only during the very short transaction window) ...

The simplest scheme to deal with this problem (I think) is to use a simple counter....the value of the counter (basically a copy) is stashed on the web page (or in the component) and when the request is processed the original value of the counter is compared with the current value of the counter and if they differ, then someone else has made changes since the user had their view refreshed ... if the counter value is the same, then the change can be committed.

At the next level, for a string, let's say, you could copy the original string and compare the original string with the current value of the string before committing the user's changed copy of the string ....

Does this make sense...FWIW, I think Johan's framework is aimed at providing a solution to this type of problem for more complex object graphs (at least that' my interpretation:)

Dale


----- Original Message -----
| From: "Norbert Hartl" <[hidden email]>
| To: "GemStone Seaside beta discussion" <[hidden email]>
| Sent: Monday, June 27, 2011 2:43:36 PM
| Subject: Re: [GS/SS Beta] very optimistic locking :)
|
| Dale,
|
| our application has support for conflict resolution. We do updates of
| the model and resolve condlicts at the client side as the client is
| the only one that can decide how to resolve a conflict. We do
| updates as long as there are changes server side. If there aren't
| any than we do the write operation. That leaves as with a short
| timeframe of conflict potential. I just recently recognized that a
| write to the collections happens very fast but the transaction lasts
| for as long as the request takes. We are doing mobile applications
| and therefor a user using edge networks could have requests that
| last a few seconds. So I think I have two choice. Either place the
| transction brackets close to the write operation instead of the
| request handling period. Or I could lock the collection of
| collections for the time something is written. The latter one would
| need to add the collections-to-be-written in an extra transction so
| it is world available. That is the two transaction request
| processing: write locking collection, commit, alter data and remove
| locking collection and commit again.
|
| > Next, what is the problem with locking the objects that are being
| > editted?
|
| What would be a good way to do this? Where to place the lock? Should
| every collection has its own lock which is activated before the
| write operation? How do thousands of monitors affect performance
| compared to a central lock?
|
| thanks in advance,
|
| Norbert

Hi Norbert,

As Dale mentioned, you might be interested in DALi -- our framework for transactions in web applications.

On 27 Jun 2011, at 18:01, Norbert Hartl wrote:

> I could add all lists that need to be written to a centralized lock list where each action can determine of any of its lists is written at the moment. Is there anything that works like the shared counter? Or would I need in this case to add to central list, commit, doing my action and remove from central list and commit?

Our approach to this kind of problems is to have a layer on top of the GS transactions that still allows to use optimistic locking (i.e. aborting the request on conflict and retrying the same request) when _different_ seaside sessions (aka different application users) are making potentially conflicting changes to the same model objects. Changes to objects are tracked on a per seaside-session basis and this change history is shared between all seaside sessions. So, when a request comes in for a particular seaside session, our transaction mechanism verifies the changes that it makes against the history of changes made by other requests. Because we wrap this functionality in a database abstraction layer and integrate it with the GLASS transactions, it basically boils down to having a transaction mechanism that lies on top of the GS transactions and that verifies conflicting changes between seaside sessions, as opposed to the GLASS tx mechanism that only detects changes between concurrent processed requests (in different gems).

I presented this approach vaguely as a part of our Yesplan app presentation last year at ESUG (when the app was still called Nextplan). It indeed solves the problem as Dale mentions:

> The general problem in the web, is that a user may be making decisions based on a stale view of the model ... if a page sits open for two days (and the session doesn't time out) before the user hits the submit button, the updates will not be correct if the underlying data has changed over the last few days ... the solution to this particular problem is pretty much application specific and I don't think that gemstone locks will be of help here (they would be of use only during the very short transaction window) ...


Now, I planned for releasing DALi earlier on but we have just been kept busy changing its implementation because of subtle errors or performance improvements. I have submitted a talk proposal on the topic to ESUG to give a me firm deadline of writing up about it and releasing the code :-) How about if I give you an early access to it so you can try it out and tell me how much rubbish it is? :-)

cheers,
Johan

Am 28.06.2011 um 02:06 schrieb Dale Henrichs:

> Below when you say that "the transaction lasts for as long as the request takes", I am not sure what you are referring to.
>
> The transaction starts with an abort when the HTML request is converted into a WARequest and terminates with a commit when the WAResponse is converted into the HTML response. The time spent in transaction should be very short and is not a function of how fast or slow the network transport layer is....The user may see a request lasting multiple seconds, but the actual time spent in transaction in GemStone is very short ...
>
Ok, I'm sorry I didn't looked it up. I just assumed it because it wasn't too hard to generate a conficting situation by syncing manually parallel. But I can see that the reason why this is easy is another one.

> The general problem in the web, is that a user may be making decisions based on a stale view of the model ... if a page sits open for two days (and the session doesn't time out) before the user hits the submit button, the updates will not be correct if the underlying data has changed over the last few days ... the solution to this particular problem is pretty much application specific and I don't think that gemstone locks will be of help here (they would be of use only during the very short transaction window) ...
>
> The simplest scheme to deal with this problem (I think) is to use a simple counter....the value of the counter (basically a copy) is stashed on the web page (or in the component) and when the request is processed the original value of the counter is compared with the current value of the counter and if they differ, then someone else has made changes since the user had their view refreshed ... if the counter value is the same, then the change can be committed.
>
> At the next level, for a string, let's say, you could copy the original string and compare the original string with the current value of the string before committing the user's changed copy of the string ....
>
> Does this make sense...FWIW, I think Johan's framework is aimed at providing a solution to this type of problem for more complex object graphs (at least that' my interpretation:)
>
I think sometimes I have problems to describe exactly what I mean. May I take another more concrete try now ? :)

We are doing a little todo app for the iphone where users can share their task lists. The communication is done via command objects with timestamps (let's say chronological click stream). The client produces commands whenever something happens to the model like addList, removeList, AddTask, editAttribute... If the client syncs it fetches the commands the server got since the last update. Now we can have conflicts on the client side. We solve these conflicts by asking the user about which choice to take. If the conflicts are resolved another update from the server is done. We do updates as long as there isn't an empty reply. If an empty  reply is received we push the new and modified commands to the server. This reduces the possible timeframe of conflict (conflict detected by the application, not transaction). Objects have versions and the editAttribute command knows old and new value which is checked. So there is no way of applying the wrong data.  It is just possible that there is a conflict on the server which won't corrupt data but interrupts the update of the user. So I'm looking for a strategy to solve this that fits in the overall concept.
I want to avoid server side conflicts whenever possible. So the question about locking is rather a question about how can I detect that something is done with a list at a particular moment so the second user comes in can be notified? Maybe there is a solution without having to tweak transactions manually. Something like the shared counter that is not transcation bound that can be used? I managed it until now to have the same code base for pharo and gemstone. But I think the solution to the problem will be at least gemstone specific.

Is it clearer now?

thanks,

Norbert

Norbert,

Okay ... you are managing the "stale client data problem" and it appears that you are really only concerned about eliminating the server-side conflicts that can occur during the small windows where two users are updating the same list at the same time....Correct?

If that's the case, then you will want to use one of the Reduced Conflict classes[1]. The exact class to choose depends upon the structure and use of the specific object that is causing the conflict....

To help more I need to have some more detail about the specific data structures where you are expecting/anticipating conflicts to occur.

As an example, I assume that the list of commands is a shared list so there is the potential for concurrent updates to the list that will result in a server-side transaction conflict. Command objects have timestamps, so there is an expectation that the commands must be processed in time order.

The RcQueue[2] class allows multiple sessions to add items to the queue without server-side conflicts. The items in the queue preserve the order in which they were added to the queue. A single consumer can remove items from the queue without server-side conflicts. If more than one session will be removing items from the queue, then I think that locks will be needed ...

The RcIdentityBag[3] class allows multiple sessions to add/remove items to the queue without server-side conflicts, but the items are not ordered. You can add an rc equality index[4] on the timestamp to an RcIdentityBag that would then allow you to access the items in the bag in timestamp order ...

The RcIdentityBag/equality index combo may just be the thing you are looking for, but that really depends upon the the specifics of your application.

Dale

[1] http://gemstonesoup.wordpress.com/2007/12/16/gemstone-101-transaction-conflicts/
[2] http://gemstonesoup.wordpress.com/2007/12/16/gemstone-101-transaction-conflicts/#rcqueue
[3] http://gemstonesoup.wordpress.com/2007/12/16/gemstone-101-transaction-conflicts/#rcidentitybag
[4] http://community.gemstone.com/display/GSS64/Indexes+in+GemStoneS

----- Original Message -----
| From: "Norbert Hartl" <[hidden email]>
| To: "GemStone Seaside beta discussion" <[hidden email]>
| Sent: Tuesday, June 28, 2011 1:46:12 AM
| Subject: Re: [GS/SS Beta] very optimistic locking :)
|
|
| Am 28.06.2011 um 02:06 schrieb Dale Henrichs:
|
| > Below when you say that "the transaction lasts for as long as the
| > request takes", I am not sure what you are referring to.
| >
| > The transaction starts with an abort when the HTML request is
| > converted into a WARequest and terminates with a commit when the
| > WAResponse is converted into the HTML response. The time spent in
| > transaction should be very short and is not a function of how fast
| > or slow the network transport layer is....The user may see a
| > request lasting multiple seconds, but the actual time spent in
| > transaction in GemStone is very short ...
| >
| Ok, I'm sorry I didn't looked it up. I just assumed it because it
| wasn't too hard to generate a conficting situation by syncing
| manually parallel. But I can see that the reason why this is easy is
| another one.
|
| > The general problem in the web, is that a user may be making
| > decisions based on a stale view of the model ... if a page sits
| > open for two days (and the session doesn't time out) before the
| > user hits the submit button, the updates will not be correct if
| > the underlying data has changed over the last few days ... the
| > solution to this particular problem is pretty much application
| > specific and I don't think that gemstone locks will be of help
| > here (they would be of use only during the very short transaction
| > window) ...
| >
| > The simplest scheme to deal with this problem (I think) is to use a
| > simple counter....the value of the counter (basically a copy) is
| > stashed on the web page (or in the component) and when the request
| > is processed the original value of the counter is compared with
| > the current value of the counter and if they differ, then someone
| > else has made changes since the user had their view refreshed ...
| > if the counter value is the same, then the change can be
| > committed.
| >
| > At the next level, for a string, let's say, you could copy the
| > original string and compare the original string with the current
| > value of the string before committing the user's changed copy of
| > the string ....
| >
| > Does this make sense...FWIW, I think Johan's framework is aimed at
| > providing a solution to this type of problem for more complex
| > object graphs (at least that' my interpretation:)
| >
| I think sometimes I have problems to describe exactly what I mean.
| May I take another more concrete try now ? :)
|
| We are doing a little todo app for the iphone where users can share
| their task lists. The communication is done via command objects with
| timestamps (let's say chronological click stream). The client
| produces commands whenever something happens to the model like
| addList, removeList, AddTask, editAttribute... If the client syncs
| it fetches the commands the server got since the last update. Now we
| can have conflicts on the client side. We solve these conflicts by
| asking the user about which choice to take. If the conflicts are
| resolved another update from the server is done. We do updates as
| long as there isn't an empty reply. If an empty  reply is received
| we push the new and modified commands to the server. This reduces
| the possible timeframe of conflict (conflict detected by the
| application, not transaction). Objects have versions and the
| editAttribute command knows old and new value which is checked. So
| there is no way of applying the wrong data.  It is just possible
| that there is a conflict on the server which won't corrupt data but
| interrupts the update of the user. So I'm looking for a strategy to
| solve this that fits in the overall concept.
| I want to avoid server side conflicts whenever possible. So the
| question about locking is rather a question about how can I detect
| that something is done with a list at a particular moment so the
| second user comes in can be notified? Maybe there is a solution
| without having to tweak transactions manually. Something like the
| shared counter that is not transcation bound that can be used? I
| managed it until now to have the same code base for pharo and
| gemstone. But I think the solution to the problem will be at least
| gemstone specific.
|
| Is it clearer now?
|
| thanks,
|
| Norbert
| > ----- Original Message -----
| > | From: "Norbert Hartl" <[hidden email]>
| > | To: "GemStone Seaside beta discussion"
| > | <[hidden email]>
| > | Sent: Monday, June 27, 2011 2:43:36 PM
| > | Subject: Re: [GS/SS Beta] very optimistic locking :)
| > |
| > | Dale,
| > |
| > | our application has support for conflict resolution. We do
| > | updates of
| > | the model and resolve condlicts at the client side as the client
| > | is
| > | the only one that can decide how to resolve a conflict. We do
| > | updates as long as there are changes server side. If there aren't
| > | any than we do the write operation. That leaves as with a short
| > | timeframe of conflict potential. I just recently recognized that
| > | a
| > | write to the collections happens very fast but the transaction
| > | lasts
| > | for as long as the request takes. We are doing mobile
| > | applications
| > | and therefor a user using edge networks could have requests that
| > | last a few seconds. So I think I have two choice. Either place
| > | the
| > | transction brackets close to the write operation instead of the
| > | request handling period. Or I could lock the collection of
| > | collections for the time something is written. The latter one
| > | would
| > | need to add the collections-to-be-written in an extra transction
| > | so
| > | it is world available. That is the two transaction request
| > | processing: write locking collection, commit, alter data and
| > | remove
| > | locking collection and commit again.
| > |
| > | > Next, what is the problem with locking the objects that are
| > | > being
| > | > editted?
| > |
| > | What would be a good way to do this? Where to place the lock?
| > | Should
| > | every collection has its own lock which is activated before the
| > | write operation? How do thousands of monitors affect performance
| > | compared to a central lock?
| > |
| > | thanks in advance,
| > |
| > | Norbert
|
|

Am 28.06.2011 um 19:03 schrieb Dale Henrichs:

> Norbert,
>
> Okay ... you are managing the "stale client data problem" and it appears that you are really only concerned about eliminating the server-side conflicts that can occur during the small windows where two users are updating the same list at the same time....Correct?
>
Right. Our strategy is to update from the server as long as updates come in then write. The critical window is the time between the first client issues the write call (http connection) and the time the transaction is commited. If another client is updating in that window it will get an empty reply and issues a write call itself. This way it depends on the speed of the network somehow. If that is the case and the same object attribute is written than we have a conflict. I know this problem is at the border to be an academic issue but...

> If that's the case, then you will want to use one of the Reduced Conflict classes[1]. The exact class to choose depends upon the structure and use of the specific object that is causing the conflict....
>
> To help more I need to have some more detail about the specific data structures where you are expecting/anticipating conflicts to occur.
>
There a two troublesome cases: changing order in a list concurrently and edit an attribute. Changing order we solve in changing the model data and forcing the client to reload the list to a sane state after the write. So the only troublesome command left is editAttribute. The command has a reference to an object, the name of the attribute to change and contains the old value (expected) and the new value to write. If the situation occurs like decribed above the first client will change that attribute and the second one will fail because the comparison of the old value with the servers value fails.
The best solution could be that the server is able to detect that a list a client wants to write is in a write operation right now. The only thing I can imagine is a central list where each client checks if one of his lists is in. If it is in I would return a message to the client to retry an update->write cycle in a short time frame. If it isn't on the list the clients lists are added to the central list and removed after the data is updated. If gemstone doesn't support this in some way I would need to do it with manual transactions. But I hoped there is something smart anywhere in gemstone that helps solving this.
In one of the last messages you were asking about what is the problem to lock each object that needs to be written. Can you elaborate on this, too.

> As an example, I assume that the list of commands is a shared list so there is the potential for concurrent updates to the list that will result in a server-side transaction conflict. Command objects have timestamps, so there is an expectation that the commands must be processed in time order.
>
Regarding shared list: The list of commands is sort of shared. Each object carries its own history and while an object can be a shared object (because the list is shared) the list is shared also somehow. I don't think the lists are the problem. Explanation follows.

Regarding timestamps: Timestamps aren't that essential. We can assume that each command in a list of commands (a write operation) has the same timestamp but the list is ordered. Each object carries its own history that is ordered. Each command is just added to the objects history after it has been applied to the object. So a command that did not raise an error while being applied is automatically right in the sense of the chronological modifications. Timestamps are more important in ordering the individual lists of commands which is only important when an update  for the client is generated (all lists of history of all objects are collected and sorted while preserving the necessary ordering).  

The critical part is the application of a single command that is not valid.

> The RcQueue[2] class allows multiple sessions to add items to the queue without server-side conflicts. The items in the queue preserve the order in which they were added to the queue. A single consumer can remove items from the queue without server-side conflicts. If more than one session will be removing items from the queue, then I think that locks will be needed ...
>
> The RcIdentityBag[3] class allows multiple sessions to add/remove items to the queue without server-side conflicts, but the items are not ordered. You can add an rc equality index[4] on the timestamp to an RcIdentityBag that would then allow you to access the items in the bag in timestamp order ...
>
> The RcIdentityBag/equality index combo may just be the thing you are looking for, but that really depends upon the the specifics of your application.
>
Yes, I know the RC hierarchy and the possibilities of adding/removing things without conflicts in certain conditions. But I need to actually alter an object and I don't think I can solve it that way.

I hope I could provide enough detail for another around of your awesome helping mails.

Norbert

Norbert,

Okay...I think that I understand what you are asking.

You are managing the the logical conflicts for the edit attribute operation.

When a user edits attribute x of Object A and you record the original value of x and the new value of x. If the original value of x is not the same as the current value of x then you have a logical conflict and you ask the user to submit a new value.

When two users edit the same object and supply different  new values the situation looks like this:

  User 1                           User 2
    Object A                         Object A
      original x = 'a'                 original x = 'a'
      new      x = 'b'                 new      x = 'c'

I assume that both users abort and see the same value of attribute x. The the timeline that follows has two different scenarios. Scenario 1 in which there is no physical conflict and the logical conflict is detected and Scenario 2 where there is a physical conflict:

  Scenario 1
  User 1                           User 2
1   submit request
2                                    submit request
3   server abort (x = 'a')
4   successful update (x := 'b')
5   server commit (x = 'b')
6                                    server abort (x = 'b')
7                                    ask user to submit new value
8                                    server commit

  Scenario 2
  User 1                           User 2
1   submit request
2                                    submit request
3   server abort (x = 'a')
4   successful update (x := 'b')     server abort (x = 'a')
5   server commit (x = 'b')          successful update (x := 'c')
6                                    server failed commit

And presumably you are interested in dealing with the failed commit in Scenario 2.

If this is indeed the situation you are concerned with, then I believe that the default handling of commit failures (i.e. retry http request after failed commit will work just fine). Here's the sequence that would happen by default:

  Scenario 2
  User 1                           User 2
....
5   server commit (x = 'b')          successful update (x := 'c')
6                                    server failed commit (automatic retry)
7                                    server abort (x = 'b')
8                                    ask user to submit new value
9                                    server commit
                                   
Note that in Scenario2 the actions that occur a times 7-9 are identical to the actions that occur in Scenario 6-8 ... that is the beauty of doing a retry of the HTTP request in the event of a commit failure.

Of course this works "correctly" because your framework can deal with the logical conflict when the starting value has changed ... otherwise the default behavior results in last one in wins, which is not always the desired outcome ...

Is this the timeframe that you are interested in, or have I missed the problem...

Dale


----- Original Message -----
| From: "Norbert Hartl" <[hidden email]>
| To: "GemStone Seaside beta discussion" <[hidden email]>
| Sent: Tuesday, June 28, 2011 2:28:04 PM
| Subject: Re: [GS/SS Beta] very optimistic locking :)
|
|
| Am 28.06.2011 um 19:03 schrieb Dale Henrichs:
|
| > Norbert,
| >
| > Okay ... you are managing the "stale client data problem" and it
| > appears that you are really only concerned about eliminating the
| > server-side conflicts that can occur during the small windows
| > where two users are updating the same list at the same
| > time....Correct?
| >
| Right. Our strategy is to update from the server as long as updates
| come in then write. The critical window is the time between the
| first client issues the write call (http connection) and the time
| the transaction is commited. If another client is updating in that
| window it will get an empty reply and issues a write call itself.
| This way it depends on the speed of the network somehow. If that is
| the case and the same object attribute is written than we have a
| conflict. I know this problem is at the border to be an academic
| issue but...
|
| > If that's the case, then you will want to use one of the Reduced
| > Conflict classes[1]. The exact class to choose depends upon the
| > structure and use of the specific object that is causing the
| > conflict....
| >
| > To help more I need to have some more detail about the specific
| > data structures where you are expecting/anticipating conflicts to
| > occur.
| >
| There a two troublesome cases: changing order in a list concurrently
| and edit an attribute. Changing order we solve in changing the model
| data and forcing the client to reload the list to a sane state after
| the write. So the only troublesome command left is editAttribute.
| The command has a reference to an object, the name of the attribute
| to change and contains the old value (expected) and the new value to
| write. If the situation occurs like decribed above the first client
| will change that attribute and the second one will fail because the
| comparison of the old value with the servers value fails.
| The best solution could be that the server is able to detect that a
| list a client wants to write is in a write operation right now. The
| only thing I can imagine is a central list where each client checks
| if one of his lists is in. If it is in I would return a message to
| the client to retry an update->write cycle in a short time frame. If
| it isn't on the list the clients lists are added to the central list
| and removed after the data is updated. If gemstone doesn't support
| this in some way I would need to do it with manual transactions. But
| I hoped there is something smart anywhere in gemstone that helps
| solving this.
| In one of the last messages you were asking about what is the problem
| to lock each object that needs to be written. Can you elaborate on
| this, too.
|
| > As an example, I assume that the list of commands is a shared list
| > so there is the potential for concurrent updates to the list that
| > will result in a server-side transaction conflict. Command objects
| > have timestamps, so there is an expectation that the commands must
| > be processed in time order.
| >
| Regarding shared list: The list of commands is sort of shared. Each
| object carries its own history and while an object can be a shared
| object (because the list is shared) the list is shared also somehow.
| I don't think the lists are the problem. Explanation follows.
|
| Regarding timestamps: Timestamps aren't that essential. We can assume
| that each command in a list of commands (a write operation) has the
| same timestamp but the list is ordered. Each object carries its own
| history that is ordered. Each command is just added to the objects
| history after it has been applied to the object. So a command that
| did not raise an error while being applied is automatically right in
| the sense of the chronological modifications. Timestamps are more
| important in ordering the individual lists of commands which is only
| important when an update  for the client is generated (all lists of
| history of all objects are collected and sorted while preserving the
| necessary ordering).
|
| The critical part is the application of a single command that is not
| valid.
|
| > The RcQueue[2] class allows multiple sessions to add items to the
| > queue without server-side conflicts. The items in the queue
| > preserve the order in which they were added to the queue. A single
| > consumer can remove items from the queue without server-side
| > conflicts. If more than one session will be removing items from
| > the queue, then I think that locks will be needed ...
| >
| > The RcIdentityBag[3] class allows multiple sessions to add/remove
| > items to the queue without server-side conflicts, but the items
| > are not ordered. You can add an rc equality index[4] on the
| > timestamp to an RcIdentityBag that would then allow you to access
| > the items in the bag in timestamp order ...
| >
| > The RcIdentityBag/equality index combo may just be the thing you
| > are looking for, but that really depends upon the the specifics of
| > your application.
| >
| Yes, I know the RC hierarchy and the possibilities of adding/removing
| things without conflicts in certain conditions. But I need to
| actually alter an object and I don't think I can solve it that way.
|
| I hope I could provide enough detail for another around of your
| awesome helping mails.
|
| Norbert
|
| > Dale
| >
| > [1]
| > http://gemstonesoup.wordpress.com/2007/12/16/gemstone-101-transaction-conflicts/
| > [2]
| > http://gemstonesoup.wordpress.com/2007/12/16/gemstone-101-transaction-conflicts/#rcqueue
| > [3]
| > http://gemstonesoup.wordpress.com/2007/12/16/gemstone-101-transaction-conflicts/#rcidentitybag
| > [4]
| > http://community.gemstone.com/display/GSS64/Indexes+in+GemStoneS
| >
| > ----- Original Message -----
| > | From: "Norbert Hartl" <[hidden email]>
| > | To: "GemStone Seaside beta discussion"
| > | <[hidden email]>
| > | Sent: Tuesday, June 28, 2011 1:46:12 AM
| > | Subject: Re: [GS/SS Beta] very optimistic locking :)
| > |
| > |
| > | Am 28.06.2011 um 02:06 schrieb Dale Henrichs:
| > |
| > | > Below when you say that "the transaction lasts for as long as
| > | > the
| > | > request takes", I am not sure what you are referring to.
| > | >
| > | > The transaction starts with an abort when the HTML request is
| > | > converted into a WARequest and terminates with a commit when
| > | > the
| > | > WAResponse is converted into the HTML response. The time spent
| > | > in
| > | > transaction should be very short and is not a function of how
| > | > fast
| > | > or slow the network transport layer is....The user may see a
| > | > request lasting multiple seconds, but the actual time spent in
| > | > transaction in GemStone is very short ...
| > | >
| > | Ok, I'm sorry I didn't looked it up. I just assumed it because it
| > | wasn't too hard to generate a conficting situation by syncing
| > | manually parallel. But I can see that the reason why this is easy
| > | is
| > | another one.
| > |
| > | > The general problem in the web, is that a user may be making
| > | > decisions based on a stale view of the model ... if a page sits
| > | > open for two days (and the session doesn't time out) before the
| > | > user hits the submit button, the updates will not be correct if
| > | > the underlying data has changed over the last few days ... the
| > | > solution to this particular problem is pretty much application
| > | > specific and I don't think that gemstone locks will be of help
| > | > here (they would be of use only during the very short
| > | > transaction
| > | > window) ...
| > | >
| > | > The simplest scheme to deal with this problem (I think) is to
| > | > use a
| > | > simple counter....the value of the counter (basically a copy)
| > | > is
| > | > stashed on the web page (or in the component) and when the
| > | > request
| > | > is processed the original value of the counter is compared with
| > | > the current value of the counter and if they differ, then
| > | > someone
| > | > else has made changes since the user had their view refreshed
| > | > ...
| > | > if the counter value is the same, then the change can be
| > | > committed.
| > | >
| > | > At the next level, for a string, let's say, you could copy the
| > | > original string and compare the original string with the
| > | > current
| > | > value of the string before committing the user's changed copy
| > | > of
| > | > the string ....
| > | >
| > | > Does this make sense...FWIW, I think Johan's framework is aimed
| > | > at
| > | > providing a solution to this type of problem for more complex
| > | > object graphs (at least that' my interpretation:)
| > | >
| > | I think sometimes I have problems to describe exactly what I
| > | mean.
| > | May I take another more concrete try now ? :)
| > |
| > | We are doing a little todo app for the iphone where users can
| > | share
| > | their task lists. The communication is done via command objects
| > | with
| > | timestamps (let's say chronological click stream). The client
| > | produces commands whenever something happens to the model like
| > | addList, removeList, AddTask, editAttribute... If the client
| > | syncs
| > | it fetches the commands the server got since the last update. Now
| > | we
| > | can have conflicts on the client side. We solve these conflicts
| > | by
| > | asking the user about which choice to take. If the conflicts are
| > | resolved another update from the server is done. We do updates as
| > | long as there isn't an empty reply. If an empty  reply is
| > | received
| > | we push the new and modified commands to the server. This reduces
| > | the possible timeframe of conflict (conflict detected by the
| > | application, not transaction). Objects have versions and the
| > | editAttribute command knows old and new value which is checked.
| > | So
| > | there is no way of applying the wrong data.  It is just possible
| > | that there is a conflict on the server which won't corrupt data
| > | but
| > | interrupts the update of the user. So I'm looking for a strategy
| > | to
| > | solve this that fits in the overall concept.
| > | I want to avoid server side conflicts whenever possible. So the
| > | question about locking is rather a question about how can I
| > | detect
| > | that something is done with a list at a particular moment so the
| > | second user comes in can be notified? Maybe there is a solution
| > | without having to tweak transactions manually. Something like the
| > | shared counter that is not transcation bound that can be used? I
| > | managed it until now to have the same code base for pharo and
| > | gemstone. But I think the solution to the problem will be at
| > | least
| > | gemstone specific.
| > |
| > | Is it clearer now?
| > |
| > | thanks,
| > |
| > | Norbert
| > | > ----- Original Message -----
| > | > | From: "Norbert Hartl" <[hidden email]>
| > | > | To: "GemStone Seaside beta discussion"
| > | > | <[hidden email]>
| > | > | Sent: Monday, June 27, 2011 2:43:36 PM
| > | > | Subject: Re: [GS/SS Beta] very optimistic locking :)
| > | > |
| > | > | Dale,
| > | > |
| > | > | our application has support for conflict resolution. We do
| > | > | updates of
| > | > | the model and resolve condlicts at the client side as the
| > | > | client
| > | > | is
| > | > | the only one that can decide how to resolve a conflict. We do
| > | > | updates as long as there are changes server side. If there
| > | > | aren't
| > | > | any than we do the write operation. That leaves as with a
| > | > | short
| > | > | timeframe of conflict potential. I just recently recognized
| > | > | that
| > | > | a
| > | > | write to the collections happens very fast but the
| > | > | transaction
| > | > | lasts
| > | > | for as long as the request takes. We are doing mobile
| > | > | applications
| > | > | and therefor a user using edge networks could have requests
| > | > | that
| > | > | last a few seconds. So I think I have two choice. Either
| > | > | place
| > | > | the
| > | > | transction brackets close to the write operation instead of
| > | > | the
| > | > | request handling period. Or I could lock the collection of
| > | > | collections for the time something is written. The latter one
| > | > | would
| > | > | need to add the collections-to-be-written in an extra
| > | > | transction
| > | > | so
| > | > | it is world available. That is the two transaction request
| > | > | processing: write locking collection, commit, alter data and
| > | > | remove
| > | > | locking collection and commit again.
| > | > |
| > | > | > Next, what is the problem with locking the objects that are
| > | > | > being
| > | > | > editted?
| > | > |
| > | > | What would be a good way to do this? Where to place the lock?
| > | > | Should
| > | > | every collection has its own lock which is activated before
| > | > | the
| > | > | write operation? How do thousands of monitors affect
| > | > | performance
| > | > | compared to a central lock?
| > | > |
| > | > | thanks in advance,
| > | > |
| > | > | Norbert
| > |
| > |
|
|

Dale,

Am 01.07.2011 um 22:09 schrieb Norbert Hartl:

> You got it perfectly giving me the necessary hints to think about it again. I was reluctant to insert transaction handling code so I was too blind to see that using gemstone the solution is straight forward. In Scenario 1 I need to abort the transaction myself telling the client to try again. In Scenario 2 I'm not really sure what to do. Do I need to do a commit myself at the end of the request to get the commit failure or is there another way to get notfied about it? At the end I detect it abort and tell the client to retry.

I can answer it myself. Just now I fully understand how it works :) I always skip the http retry while reading. Basically there is only one failure case for me. If the second request comes late than I the error is recognized by my model. If the second request comes early (which means a commit failure will happen) the http retry will then cause my model to detect the problem. So both are identical from an implementation point of view. That is really great. And in failure case I just return http status code 409 which forces the client to do again update -> commit.
We tested with three devices syncing at the same time and it resolved just nicely.

thanks a lot,

Norbert

Johan,

somehow I skipped your mail. sorry.

Am 28.06.2011 um 08:36 schrieb Johan Brichau:
That sounds good.  I would like to see how you manage the changes to objects and how you share session objects among all sessions.

>> The general problem in the web, is that a user may be making decisions based on a stale view of the model ... if a page sits open for two days (and the session doesn't time out) before the user hits the submit button, the updates will not be correct if the underlying data has changed over the last few days ... the solution to this particular problem is pretty much application specific and I don't think that gemstone locks will be of help here (they would be of use only during the very short transaction window) ...
>
>
> Now, I planned for releasing DALi earlier on but we have just been kept busy changing its implementation because of subtle errors or performance improvements. I have submitted a talk proposal on the topic to ESUG to give a me firm deadline of writing up about it and releasing the code :-) How about if I give you an early access to it so you can try it out and tell me how much rubbish it is? :-)

As you've may read in my other replies the problems I'm facing are slightly different. Biggest differences might be that I don't have a session at hand. But your functionality doesn't sound like it is depend on the session. It is just used there, right? I'm interested to see the code and try it out. I'm quite busy at the moment (well, who's not?) so it is hard to promise anything. But I can try if you like.

Norbert

Hi Norbert,

> As you've may read in my other replies the problems I'm facing are slightly different. Biggest differences might be that I don't have a session at hand. But your functionality doesn't sound like it is depend on the session. It is just used there, right? I'm interested to see the code and try it out.

With 'session', I understand you mean a Seaside session?

We implement our own database session objects that represent a database connection. A Seaside session would typically hold on to one of these. If there is no Seaside session, you would need to hold on to those database sessions for each 'user' of the system. This is because application-level conflicts are detected with respect to the database connections they come from. This is actually the same when you would open a database connection to GOODS/Magma/Glorp/... in another Smalltalk: commit conflicts are detected w.r.t. commits on separate database sessions.

We happen to have modified the Seaside request handling methods that perform the commit/abort on session request such as to abort the request also when a commit conflict is detected between our database connections (and not only the Gemstone-level conflicts). I think it's fits your use as well.

>  I'm quite busy at the moment (well, who's not?) so it is hard to promise anything. But I can try if you like.


No promises needed. I saw your question and it came to mind immediately that you might be trying to solve the same problem that we did with DALi.
Let me get back to you near the end of the week. I should be able to write something up by then as well and I can put it onto a public repo too.

Johan

Good!

It is really nice that the simple HTTP request retry in the face of commit conflicts works thereby avoiding more complicated solutions ... Of course logical conflict detection is still needed, but that is usually very application specific (what and how much needs to be copied)...

Dale

----- Original Message -----
| From: "Norbert Hartl" <[hidden email]>
| To: "GemStone Seaside beta discussion" <[hidden email]>
| Sent: Monday, July 4, 2011 10:19:19 AM
| Subject: Re: [GS/SS Beta] very optimistic locking :)
|
|
| Am 01.07.2011 um 22:09 schrieb Norbert Hartl:
|
| > You got it perfectly giving me the necessary hints to think about
| > it again. I was reluctant to insert transaction handling code so I
| > was too blind to see that using gemstone the solution is straight
| > forward. In Scenario 1 I need to abort the transaction myself
| > telling the client to try again. In Scenario 2 I'm not really sure
| > what to do. Do I need to do a commit myself at the end of the
| > request to get the commit failure or is there another way to get
| > notfied about it? At the end I detect it abort and tell the client
| > to retry.
|
| I can answer it myself. Just now I fully understand how it works :) I
| always skip the http retry while reading. Basically there is only
| one failure case for me. If the second request comes late than I the
| error is recognized by my model. If the second request comes early
| (which means a commit failure will happen) the http retry will then
| cause my model to detect the problem. So both are identical from an
| implementation point of view. That is really great. And in failure
| case I just return http status code 409 which forces the client to
| do again update -> commit.
| We tested with three devices syncing at the same time and it resolved
| just nicely.
|
| thanks a lot,
|
| Norbert