Testing PowerSync with Jepsen for Causal Consistency and More

Testing PowerSync with Jepsen for Causal Consistency, Atomic transactions, and Strong Convergence.

PowerSync is a full featured active/active sync service for a backend PostgreSQL, MongoDB, or MySQL database and supports a diverse variety, language/platform, of local SQLite3 clients. It offers a rich API for developers to configure and define the sync behavior.

Our primary goal is to test the sync algorithm, its core implementation, and develop best practices for:

• Causal Consistency
  • read your writes
  • monotonic reads and writes
  • writes follow reads
  • happens before relationships
• Atomic transactions
• Strong Convergence

Operating under:

• normal environmental conditions
• environmental failures
• diverse user behavior
• random property based conditions and behavior

PowerSync is to be commended for sponsoring the development of a Jepsen test:

• with no holds barred, e.g. go ahead and kill a random majority of nodes, occasionally at 1ms intervals, now while the node is coming up and mid-connection, now do it again..., and again..., and again..., etc
• testing every transaction for Causal Consistency, Strong Convergence, and Atomicity
• completely in public

PowerSync has shown:

• continuous improvement, no regressions, during test development
• evolved to no observable data loss (tests can occasionally stall replication)
• full Causal Consistency, Strong Convergence, and Atomicity in a no-fault environment

And handled:

• active/active, simultaneous backing database and client transactions
• process pauses and kills

out of the box better than most similar systems that have been privately tested.

The documentation, both architectural and API, is well written and easy to understand. The development team is responsive on the Discord chat and responding to issues.

PowerSync would benefit from attention to:

• network partitioning and timely sync recovery and resumption
• the remaining corner cases where more frequent, longer duration, environmental faulting can lead to occasional sync pauses

The tests would benefit from:

• adding a post fault/quiescence option to resume user activity to further understand/confirm sync resumption
• adding options to configure the backing databases, e.g. MySQL
• adding options to test raw tables, schema migrations, and the other new features added during test development
• improving usability for new users, Jepsen is a heavy lift

• graph shows a 10 mode cluster at 100 transactions per second in an under provisioned environment

• all transactions Ok

• periodically checking the upload que on each client and finding it to be current, i.e. usually empty, occasionally small:

  :nemesis :info :upload-queue-count {"n1" 0, "n10" 0, "n2" 0, "n3" 0, "n4" 0, "n5" 0, "n6" 0, "n7" 0, "n8" 0, "n9" 4}

GitHub issue history for the jepsen-powersync project.

Tests generate random multi operation transactions on each client and randomly introduce environmental faults and challenging user behaviors. At the end of test all transactions are analyzed for consistency and correctness.

Every transaction is checked for Causal Consistency:

• Read Your Writes: clients always read all of their previous writes
• Monotonic Reads: all reads read the same or greater state
• Monotonic Writes: clients read other clients writes in write order
• Writes Follow Reads: a read of a value includes all of the known state at the time the value was written

The test generates transactions that contain multiple random reads and writes.

All reads are checked to insure that both local and replicated writes are atomically read.

All reads from all clients are checked to insure that everyone is always converging towards the same state.

A final read at the end of the test on each client confirms Strong Convergence, i.e. the same state.

The initial implementations of the PowerSync client and backend connector take a safety first bias:

• stay as close as possible to direct SQLite3/PostgreSQL transactions
• replicate at this transaction level
• favors consistency and full client syncing over immediate performance

clients do straight ahead SQL transactions:

backend replication is transaction based:

PostgreSQL transactions are executed at a Repeatable Read isolation level.

SQLite3 transactions are executed at its default isolation level of Serializable.

The tests have been developed in a progressive step by step fashion.

We start with an isolated single user using SQLite3 locally and evolve to a fully distributed multi user environment requiring extensive sync and replication behavior.

Each step is extensively tested and must reliably pass, ✔️, before continuing development.

✔️ Single user, generic SQLite3 db, no PowerSync:

• tests the tests
• demonstrates test fidelity, i.e. accurately represent the database
• 🗸 as expected, tests show totally availability with strict serializability

✔️ Multi user, generic SQLite3 shared db, no PowerSync:

• tests the tests
• demonstrates test fidelity, i.e. accurately represent the database
• 🗸 as expected, tests show totally availability with strict serializability

✔️ Single user, PowerSync db, local only:

• expectation is total availability and strict serializability
• SQLite3 is tight and using PowerSync APIs should reflect that
• 🗸 as expected, tests show totally availability with strict serializability

✔️ Single user, PowerSync db, with replication:

• expectation is total availability and strict serializability
• SQLite3 is tight and using PowerSync APIs should reflect that
• 🗸 as expected, tests show total availability with strict serializability

✔️ Multi user, PowerSync db, with replication, using getCrudBatch() backend connector:

• expectation is
  • read committed vs Causal
  • non-atomic transactions with intermediate reads
  • strong convergence
• 🗸 as expected, tests show read committed, non-atomic with intermediate reads transactions, and all replicated databases strongly converge

✔️ Multi user, PowerSync db, with replication, using newly developed Causal getNextCrudTransaction() backend connector:

• expectation is
  • Atomic transactions
  • Causal Consistency
  • Strong Convergence
• 🗸 as expected, tests show Atomic transactions with Causal Consistency, and all replicated databases strongly converge

✔️ Multi user, Active/Active PostgreSQL/SQLite3, with replication, using newly developed Causal getNextCrudTransaction() backend connector:

• mix of clients, some PostgreSQL, some PowerSync
• expectation is
  • Atomic transactions
  • Causal Consistency
  • Strong Convergence
• 🗸 as expected, tests show Atomic transactions with Causal Consistency, and all replicated databases strongly converge

Database is a Max Write Wins key/value register of integer/integer:

On writes, the maximum, transaction or row, value wins. The BackendConnector updates PostgreSQL:

The conflict/merge algorithm isn't important to the test. It just needs to be:

• consistently applied
• consistently replicated

Values:

• written in a transaction are monotonic per key
• read in a transaction are monotonic per key

The client will be a simple Dart CLI PowerSync implementation.

Clients are expected to have total sticky availability:

• throughout the session, each client uses the
  • same API
  • same connection
• clients are expected to be totally available, liveness, unless explicitly stopped, killed or paused

Observe and interact with the database:

• PowerSyncDatabase driver
• single db.writeTransaction() with multiple SQL statements
  • tx.getAll('SELECT')
  • tx.execute('UPDATE')
• PostgreSQL driver
  • most used Dart pub.dev driver
  • single pg.runTx() with multiple SQL statements
    • tx.execute('SELECT')
    • tx.execute('UPDATE')

The client will expose an endpoint for SQL transactions and PowerSyncDatabase API calls:

• HTTP for Jepsen
• Isolate ReceivePort for Dart Fuzzer

Tests can use a mix of clients:

• active/active, replicate central PostgreSQL and local client activities
  • some clients read/write PostgreSQL database
  • some clients read/write local SQLite3 databases
• replicate central PostgreSQL activity to local clients
  • some clients read/write PostgreSQL database
  • some clients read only local SQLite3 databases
• replicate local clients to local clients
  • some clients read only PostgreSQL database (to check for consistency)
  • some clients read/write local SQLite3 databases

PowerSync tests 100% successfully in no fault environments using a test matrix of:

• 5-10 clients
• 10-50 transactions/second
• active/active, simultaneous PostgreSQL and/or local SQLite3 client transactions
• local SQLite3 client transactions
• complex transactions that read 100 keys and write 4 random keys in a single transaction

LoFi and distributed systems live in a rough and tumble environment.

Successful applications, applications that receive a meaningful amount or duration of use, will be exposed to faults. Reality is like that.

Faults are applied:

• to random clients
• at random intervals
• for random durations

Even during faults, we still expect:

• total sticky availability (unless the client has been explicitly stopped/paused/killed)
• Atomic transactions
• Causal Consistency
• Strong Convergence

In both powersync_fuzz and Jepsen use PowerSyncDatabase.disconnect()/connect().

Test choreography:

• repeatedly
  • wait a random interval
  • 1 to all clients are randomly disconnected
  • wait a random interval
  • connect disconnected clients

At the end of the test:

• connect any disconnected clients
• quiesce for 3s, i.e. no further transactions
• wait for db.uploadQueueStats.count: 0 for all clients
• wait for db.SyncStatus.downloading: false for all clients
• do a final read on all clients and check for Strong Convergence

Jepsen example of 3 clients being disconnected for ~1.6s and then the same clients being reconnected:

Test choreography:

• repeatedly
  • wait a random interval
  • 1 to all clients are randomly disconnected
  • wait a random interval
  • 1 to all clients are randomly connected

At the end of the test:

• connect any disconnected clients
• quiesce for 3s, i.e. no further transactions
• wait for db.uploadQueueStats.count: 0 for all clients
• wait for db.SyncStatus.downloading: false for all clients
• do a final read on all clients and check for Strong Convergence

Jepsen example of 3 clients being disconnected, waiting ~2.5s, then only 1 of the disconnected clients and 1 other random client being reconnected:

• repeatedly
  • wait a random interval
  • query the upload que count

Jepsen example of observing differing queue counts for disconnected/connected clients:

Without disconnect/connect, all test runs are successful.

There's no obvious differences between the Dart and Rust sync implementations.

In a small, fraction of a percent, of tests it is possible to fuzz into a state where:

• UploadQueueStats.count appears to be stuck:
  • for a single client
  • for a single transaction

which leads to incomplete replication for that client and divergent final reads.

As the error behavior always presents as a single stuck transaction, is it theorized that:

• replication occasionally gets stuck, is not triggered
• sometimes the test ends during this stuck phase
• sometimes the test is ongoing and replication is restarted by further transactions

In no cases have the tests been able to drop any data or reorder the transactions in a non Causally Consistent fashion.

The bug is hard enough to reproduce, due to its lower frequency and longer run times, that GitHub actions are a more appropriate test bed than the local fuzzing environment:

• using Dart Isolates: fuzz-disconnect
• using Jepsen: jepsen-disconnect

The update to PowerSync: 1.12.3, PR #267, shows significant improvements when fuzzing disconnect/connect.

See issue #253 comment.

The new release eliminates all occurrences of:

• multiple calls to BackendConnector.uploadData() for the same transaction id
• SyncStatus.lastSyncedAt goes backwards in time
• reads that appear to go back in time, read of previous versions
• select * reads that return [], empty database

And the remaining bug is less frequent requiring more:

• demanding transaction rates
• total run times
• occurrences of disconnecting/connecting

The update to PowerSync: 1.14.1, PR #294, brings the Rust implementation to parity with the Dart implementation.

See issue #253 comment.

In powersync_fuzz use PowerSyncDatabase api and Dart's Isolate api:

In Jepsen use PowerSyncDatabase api and Jepsen's control/util/grepkill! and start-daemon! utilities:

Test choreography:

• repeatedly
  • wait a random interval
  • 1 to all clients are randomly closed then killed
  • wait a random interval
  • clients that were closed/killed are restarted reusing existing SQLite3 files

At the end of the test:

• restart any clients that are currently closed/killed reusing existing SQLite3 files
• quiesce for 3s, i.e. no further transactions
• wait for db.uploadQueueStats.count: 0 for all clients
• wait for db.SyncStatus.downloading: false for all clients
• do a final read on all clients and check for Strong Convergence

Sample Jepsen log:

Without stop/start, all test runs are successful.

There's no obvious differences between the Dart and Rust sync implementations.

Stop/start behaves the same as disconnect/connect but with a significantly smaller frequency of the "stuck queue" bug.

For both powersync_fuzz and Jepsen use iptables to partition client hosts from the PowerSync sync service.

powersync_fuzz Dart partition implementation:

Test choreography:

• repeatedly
  • 0 to all client hosts are randomly partitioned from the PowerSync sync service host
    • the client network failure is randomly selected to be none, inbound, outbound, or all traffic
  • wait a random interval, 0-10s
  • heal network partition
  • wait a random interval, 0-10s

At the end of the test:

• insure network is healed for all clients
• quiesce for 3s, i.e. no further transactions
• wait for db.uploadQueueStats.count: 0 for all clients
• wait for db.SyncStatus.downloading: false for all clients
• do a final read on all clients and check for Strong Convergence

During successful runs you can see:

Latency graph showing local read/write latency/thruput unaffected by partitioning:

As expected, network errors exist in sync service logs:

Without partitioning, all test runs are successful.

There's no obvious differences between the Dart and Rust sync implementations.

Transient network partitions can disrupt replication.

Most commonly, the client stops uploading, just indefinitely queuing local writes.

In other cases, less frequently, the tests complete without any indication of errors, local writes are uploaded to PostgreSQL, but only replicated to 0 or a subset of clients.

At the end of the test with:

• healed partitions
• no transactions

uploading remains true, but the upload queue never clears:

• note lack of updated SyncStatus, or other messages
• db.UploadQueueStats.count is wedged/stuck, never changes
• we wait 11 seconds with no upload activity before ending the test, but the wait can be indefinite. i.e. client never recovers

Unexpectedly, there are no network errors in the logs:

At the end of the test with:

• healed partitions
• no transactions
• db.uploadQueueStats.count: 0 for all clients
• db.SyncStatus.downloading: false for all clients
• no errors

there can be divergent final reads:

Unexpectedly, there are no network errors in the logs:

Fuzzing with a test matrix of:

• 5 | 10 clients
• 10 | 20 | 30 | 40 transactions/second
• 100 | 200 | 300 second run times

will generate errors in ~30-40% of the tests.

In powersync_fuzz, use Dart's Isolate.pause()/resume():

In Jepsen, use Jepsen's control/util/grepkill! utility:

Test choreography:

• repeatedly
  • wait a random interval
  • 1 to all clients are randomly paused
  • wait a random interval
  • resume all clients

At the end of the test:

• resume all clients
• quiesce for 3s, i.e. no further transactions
• wait for db.uploadQueueStats.count: 0 for all clients
• wait for db.SyncStatus.downloading: false for all clients
• do a final read on all clients and check for Strong Convergence

PowerSync tests 100% successful when injecting client process pause/resumes for both the Dart and Rust clients.

Client application process kills can happen when:

• someone's phone running out of battery
• a user turning off their laptop without shutting down
• force quitting an app
• etc

Not available in powersync_fuzz as Isolate.kill()'s behavior appears to be heavy handed, have side effects that are not fully understood, so use Jepsen to test kill/start.

In Jepsen, use Jepsen's control/util/grepkill! and start-daemon! utilities:

Test choreography:

• repeatedly
  • 1 to a majority of clients are randomly killed
  • wait a random interval, 0-10s
  • restart/reconnect clients that were killed reusing existing SQLite3 files
  • wait a random interval, 0-10s

At the end of the test:

• insure all clients are started/connected
• quiesce for 3s, i.e. no further transactions
• wait for db.uploadQueueStats.count: 0 for all clients
• wait for db.SyncStatus.downloading: false for all clients
• do a final read on all clients and check for Strong Convergence

Without kill/start, all test runs are successful.

There's no obvious differences between the Dart and Rust sync implementations.

PowerSync is usually quite resilient with a full recovery after client is restarted and reconnects to the sync service:

• quickly/fully downloads to catch up with the other clients
• resumes uploading, including any pending pre-kill transactions
  • even for transactions that were in progress, only partially uploaded, when client was killed
• continues with normal operation as if nothing happened

With process kills, occasionally, ~0.5%, the test will end with:

• db.currentStatus.downloading staying indefinitely true
• db.currentStatus.progress counting to #/# but never nulling

and local transactions committed after the kill not being uploaded to the sync service.

There's a lot going on in the logs during a kill/restart/reconnect sequence, but here's a commented snippet from the end of a test that illustrates the issue:

As expected, network errors exist in sync service logs:

There's a suite of GitHub Actions with an action for every type of fault.

Each action uses a test matrix for:

• number of clients
• rate of transactions
• fault characteristics
• and other common configuration options

Oddly, GitHub Actions can fail:

• pulling Docker images from the GitHub Container Registry
• building images
• pause in the middle of a test run and timeout

Ignorable failure status messages:

• "GitHub Actions has encountered an internal error when running your job."
• "The action '5c-20tps-100s...' has timed out after 25 minutes."
• "Process completed with exit code 255."

These failures are Microsoft resource allocation and infrastructure issues and are not related to the tests.

The action will fail with an exit code of 255 and "no logs available" log file contents when this happens.

In general, one will want to use the GitHub Actions and their test matrixes as errors can be hard to find.

As Jepsen is a heavy lift, a pure Dart fuzzer with a Docker environment and helper Bash scripts have been developed to support local host testing if desired.

powersync_fuzz help.

• auth - using a permissive JWT

• sync filtering - using SELECT *

• Byzantine/Malicious Behavior - natural faults and well intentioned API use

Once again, props to PowerSync for:

• being easy to work with
• sponsoring a demanding test of their sync logic and implementations
• and doing it completely in public

🙏