Concurrency, Timing and Relativity

Two operations are said to be concurrent if they happen at the same time, but in fact it doesn't matter whether the operations overlap in time.Due to the complex clock synchronization problem of distributed systems, it is difficult to strictly judge whether two events occur at the same time in reality.

To better define concurrency, it does not depend on the exact time of occurrence, i.e. two operations are said to be concurrent if they do not need to be aware of each other, regardless of the physical time at which they occur.

In a computer system, two operations may be concurrent, even if the speed of light is fast enough to allow one operation to affect the other.If the network is congested or interrupted, it may happen that two operations become concurrent because one operation cannot perceive the other due to network problems.

Identify context

Look at the algorithm for determining whether two operations are concurrent.Start with a database with only one replica.

Figure-13 shows two clients adding items to the shopping cart at the same time.Initially, the cart is empty.The two clients then issue five writes to the DB:

1. Client 1 first adds milk to the shopping cart.This is the first time the value of this K is written, the server successfully stores and assigns it version number 1, and finally returns the value to the client along with the version number 1
2. Client 2 adds eggs to the shopping cart, at this point it does not know that client 1 has added milk (client 2 thinks its eggs are the only items in the shopping cart).The server assigns version number 2 for this write, and stores eggs and milk as two separate values.Finally, both values ​​are returned to client 2 and the version number 2 is attached
3. Similarly, client 1 does not know the writing of client 2 and wants to add flour to the shopping cart, so it thinks that the current shopping cart should be [milk, flour].Send this value to the server along with the version number 1 previously provided by the server to client 1.The server knows from the version number that the new value of [milk, flour] is written to replace the previous value of [milk], but concurrently with the [egg] value.So the server assigns version 3 to [milk, flour] and overwrites version 1's [milk], but keeps the value of version 2 [egg], returning both values ​​to client 1
4. Meanwhile, Client 2 wants to add ham, not knowing that Client 1 just added flour.Client 2 received two values ​​[milk] and [egg] from the server in the last response, so client 2 now merges these values ​​and adds ham to form a new value, [egg, milk, ham].It sends this value to the server with the previous version number 2 .The server detects that the new value overwrites version 2[egg], but the new value is also concurrent with version 3[milk,flour], so the remaining two are v3[milk,flour], andv4: [eggs, milk, ham]
5. Finally, Client 1 wants to add bacon.It used to receive [milk, flour] and [eggs] from the server in v3, so it merged these, added bacon, and sent the final value [milk, flour, eggs, bacon] to the server along with the version number v3.This overwrites v3[milk,flour] (note that [egg] is already overridden in the last step), but is concurrent with v4[egg,milk,ham], so the server keeps both concurrent values

Figure-13 The data flow between operations is shown in Figure-14.The arrows indicate which operations occur before other operations, i.e. later operations know or depend on earlier operations.In this case, the client will never fully grasp the data on the server because there is always another operation going on at the same time.However, the new version value will eventually overwrite the old value, and no loss of the written value will occur.

The basis for the server to judge whether the operation is concurrent or not mainly relies on comparing the version number, without explaining the old and new values ​​themselves (the value can be any data structure).Algorithm Workflow:

• The server keeps a version number for each K, increments the version number each time a new value of K is written, and saves the new version number with the written value
• When the client reads K, the server will return all (uncovered values) current values ​​and the latest version number.And before requesting to write, the client must first send a read request
• When the client writes K, the write request must contain the version number read before and the merged set of all values ​​read before.The response to a write request can be like a read request, returning all current values, so that multiple writes can be concatenated like in the shopping cart example.)
• When the server receives a write pending for a specific version number, overwrites all values ​​of the version number or lower (because they know they have been merged into the new incoming set of values), but must save higherAll values ​​of the version number (since these values ​​are concurrent with the current write)

When the write request contains the version number of the previous read, it means that the modification is based on the previous state.If a write request does not contain a version number, it will be concurrent with all other write operations, will not overwrite any existing values, and the incoming value will be included in the return value list of subsequent read requests.