50.003 - Concurrency and Concurrent Testing

Learning Outcomes

Eliminate race condition in web application via transaction
Perform concurrent testing

Concurrency

Concurrency is ubiquitous in modern software systems, web application, mobile applications, chat bots, etcs are required to support multiple and concurrent users acess. As we learned from other modules, such 50.001 and 50.005, software concurrency imposes many challenges, e.g. race conditions, deadlock, starvation and etc.

Codes that exhibits correct behavior when being executed sequentially are not necessarily correct when being executed concurrently or interleaved by instructions. This implies that we need a different testing strategy when hunting for bugs in concurrent software system.

Race condition in JavaScript

Racing condition examples found in the literatures involve the usage of threads and shared resources. Since JavaScript does not offer multi-threading operation, one may optimistically think that programs written in JavaScript will not suffer from the curse of race condition and its related consequences. Unfortunately, such a optimism is 100% wrong in reality.

let a = { bal : 100 }
let b = { bal : 200 }
let c = { bal : 150 }

function get_bal(acc) {
    return new Promise((resolve, reject) => {
        resolve(acc.bal);
    })
}

function set_bal(acc, new_bal) {
    return new Promise((resolve, reject) => {
        acc.bal = new_bal;
        resolve(new_bal);
    })
}

In the above we instantiate three objects to simulate some separates accounts. We define

a get_bal() promise builder function which returns a promise that resolves on the account's balance.
a set_bal() promise builder function which returns a promise that updates the account's balance.

Next we define a transfer() function which transfer some amount from two accounts, by calling get_bal() and set_bal()

async function transfer(src, dst, amt) {
    let src_bal = await get_bal(src);
    let dst_bal = await get_bal(dst);
    if (src_bal > amt) {
        await set_bal(dst, dst_bal + amt); 
        await set_bal(src, src_bal - amt);
    }
}

Finally, we define our main function and the aftermath observation

async function main() {
    await transfer(b, a, 100);
    await transfer(c, a, 50);
}

main().then(
    async function () {
        let bal_b = await get_bal(b);
        let bal_a = await get_bal(a);
        let bal_c = await get_bal(c);
        console.log(bal_a,bal_b,bal_c);
    }
)

In the main() function, we sequentially transfer 100 from b to a then transfer 50 from c to a.

We observe the closing balances as 250 100 100.

This is fine because the two transfer operations were carried out in sequence, (enforced by two await).

Suppose we change the main function as follows,

async function main() {
    transfer(b, a, 100);
    await transfer(c, a, 50);
}

or

async function main() {
    await Promise.all([
        transfer(b, a, 100),
        transfer(c, a, 50)
    ]);
}

In either way, the two transfer operations are performed concurrently, i.e. the promises are now interleaved. When we observe the closing balances as 150 100 100. A racing condition is triggered.

One may argue that the above variants of main() are unusual, after some code review, we perhaps can eliminate the bugs. However, in the event that the two transfer operations are triggered from separate server events, e.g. from two different HTTP request handlers, such a racing condition is inevitable.

Concurrent Testing

Now we are convinced that the racing condition is ubiqitious, the next question is to how to test our codes such that we can unearth the potential critical sections with racing condition.

For instance, in the echo app model file message.js we would like to define a new operation which first search for a message by the timestamp in the database, update it if the message exists.

async function update(time, appendMsg) {
    try {
        const [rows, fieldDefs] = await db.pool.query(`
            SELECT * FROM ${tableName} where time = ?`, [time]
        );
        if (rows.length > 0) {
            var message = new Message(rows[0].msg, rows[0].time)
            await db.pool.query(`
                UPDATE ${tableName} SET msg = ? WHERE time = ?`, [message.msg + appendMsg, message.time]
            );
        }
    } catch (error) {
        console.error("database connection failed. " + error);
        throw(error);
    } 
}

In the event of concurrent access, such a find-and-update operation can lead to a racing condition.

In other languages like Java, we can create test case with multiple threads running the concurrent section multiple of times and validate the final result is a semantically correct one. In JavaScript, we can construct such a concurrent test case using Promise.all(),

In the above test case, we start off our data base with two messages. In the test case, we define a task which update the message with '2009-01-01:00:00:00' by appending an a. href="#__codelineno-6-1">async function setup() { try { // TODO backup the existing data to a temp table? await db.pool.query(` DELETE FROM message;` ); await db.pool.query(` INSERT INTO message (msg, time) VALUES ('msg a', '2009-01-01:00:00:00') `); } catch (error) { console.error("setup failed. " + error); throw error; } } >test ("testing message.update() concurrently ", async () => { const expected = [ new message.Message('msg aaa', new Date('2009-01-01:00:00:00'))] const concurrent_task = () => message.update('2009-01-01:00:00:00', 'a'); await Promise.all([ // running 2 update concurrently. retry.retry(concurrent_task,2,1000), // (re-)try max twice with 1s delay retry.retry(concurrent_task,2,1000) ]); let result = await message.all(); expect(result.sort()).toEqual(expected.sort()); }); After running instances of the task concurrently, we should have the message msg aaa.

However, running the above test multiple of times, we find it fails sometimes, with the following error.

 FAIL  __test__/models/message.test.js
  ● models.message tests › testing message.update() concurrently 
    expect(received).toEqual(expected) // deep equality

    - Expected  - 1
    + Received  + 1
    @@ -1,8 +1,8 @@
      Array [
        Message {
    -     "msg": "msg aaa",
    +     "msg": "msg aa",
          "time": 2008-12-31T16:00:00.000Z,
        }]

To fix the racing condition on the database level.

We can address such a data racing condition at the database level. In many modern database systems, we find database transaction typically useful in managing concurrent read and update combo operations.

START TRANSACTION;
SELECT ...
UPDATE ...
COMMIT;

In a nutshell, SQL statements enclosed by BEGIN TRANSACTION; ... COMMIT; are to be executed by the datbase systems atomically and in isolation. Informally speaking, the enclosed statements should not be interleaved with other statements that cause a racing condition. In the event a racing condition is detected, a database exception is raised and the query statements are rejected. A retry or an abort is required.

Let's rewrite the above unsafe update as follows,

async function update(time, appendMsg) {
    let connection = null; 
    try {
        connection = await db.pool.getConnection();
        await connection.query(
             "SET SESSION TRANSACTION ISOLATION LEVEL SERIALIZABLE" 
        ); 
        await connection.query("START TRANSACTION");    
        const [rows, fieldDefs] = await connection.query(`
            SELECT * FROM ${tableName} where time = ?`, [time]
        );
        if (rows.length > 0) {
            var message = new Message(rows[0].msg, rows[0].time)
            await connection.query(`
                UPDATE ${tableName} SET msg = ? WHERE time = ?`, [message.msg + appendMsg, message.time]
            );
        }
        await connection.query("COMMIT");
    } catch (error) {
        if (connection) {
            await connection.query("ROLLBACK");
            await connection.release();
        }
        console.error("database connection failed. " + error);
        throw(error);
    } finally {
        if (connection) {
            await connection.release();
        }    
    }
}

In the above version,

we instantiate a specific connection object from the db.pool object. We replace all the use of db.pool.query() by connection.query().

If we use db.pool.query() directly, each time a new connection is instantiated and there is no way to ensure the set of queries are enclosed in the same transaction block.
We then declare the transaction isolation level. SERIALIZABLE means any READ-WRITE operation pairs applied on the same table from different transactions are considered in-conflict. For details please refer to https://dev.mysql.com/doc/refman/8.0/en/innodb-transaction-isolation-levels.html#isolevel_read-uncommitted
We enclose the critical section with the START TRANSACTION and COMMIT. In case of a conflict is deteced, we rollback the transaction.

With the above changes, our concurrent test should be always passed .