Fair queueing for payment batches

In the previous article of this series, which aims at exploring ways to optimize instant payments and banking, Oleksii Pylypenko, CaaS Tech Lead, wrote how Kyriba has improved upon the pooling process for instant payments. In this second article, Oleksii dives into batch payments.

Kyriba provides connectivity to a myriad of banks all over the world, including over 1000 bank groups for reporting and over 440 bank groups for payments. To understand the scale, Kyriba processed over 2.4 billion transactions in the last 12 months. Such connectivity can be established via multiple protocols and formats, supporting payments and reporting integration. It can also be achieved via connecting to specific Bank APIs provided by the banks (some examples: Bank of America, CITI and US Bank.

With such volume of transactions how do we ensure that large batches of payments from one customer are not blocking smaller and less intensive ones of other customers.

Let’s explore how it is possible to leverage fair queuing to solve this problem.

Fair queueing

Fair queuing is an approach that deliberately picks items from the queue when congestion occurs. For this purpose let’s limit reasoning to one bank and N customers that want to submit payment batches to this bank. If no congestion occurs, a fair queue is basically the same as the first-input-first-output approach.

But once a queue consumer (bank) is slower than a queue producer (customer), to be able to fairly pick the next item from the queue algorithm picks items with minimum virtual finish time. The virtual finish time is a metric emulating the amount of time occupied by processing batches for one customer and is established once the payment batch is added to the queue.

For this purpose per each customer a counter of virtual time is introduced. Once an item is added to the fair queue virtual time is updated. This way virtual time is a monotonic sequence that gives an approximation to the amount of real time payment batch may take to process calculated at the moment before item is added to the queue, typically it is just based on the size of the payment batch.

By picking from the queue the item with minimum virtual finish time we guarantee that customers are dealt equally fair and big batches for one customer are not occupying whole bandwidth and intertwined with batches from other customers.

One problem with the approach described just above is that consumers that tend to send less amounts of data will always have a priority in such a system. To remove such memory effects we should adjust the virtual time of each consumer to jump towards the virtual time that is being processed on the consumer side. We can do the adjustment on each payment batch addition by taking the minimum out of the current time observed on a consumer and current virtual time for the customer. This way we will tend to not accumulate information about the past of message transfers, but rather move virtual time forward for each consumer and rebalance fairly at congestion moments.

In this article we will focus on building Proof of Concept that simulates fair queuing based on Redis cache and coded in Kotlin. We will skip the current time adjustment for sake of simplicity. This approach is easily scalable and gives lot’s of freedom to customize the algorithm by introduction of weights to customers, weights of specific payments, possibility to calculate virtual time metric in more precise fashion based on measurements e.t.c.

From an engineering point of view we’d like to use Redis Sorted Set structure ordering items based on virtual finish time calculated for each payment batch.

Producer code

To implement producer we need to use two Redis operations incrby and zadd. First to update counters of virtual time for specific customer/bank pairs by size of payment batch and second to submit a payment to Redis sorted set with score = virtual finish time, which equals to virtual time just after update of a counter and returned as a value by incrby.

There are no algorithmic limitations on the number of concurrent producers, so service that is producing batches can be scaled horizontally once redis infrastructure is scaled appropriately.

data class PaymentOrder(val transactionCount: Int, val customer: Int, val bank: Int)

val client = RedisClient.create("redis://localhost:6379/0")
       .connect()
       .async()

repeat (1000) {

   val order = PaymentOrder(
           transactionCount = Random.nextInt(1, 100),
           customer = Random.nextInt(1, 100),
           bank = Random.nextInt(1, 10)
   )

   val virtualTimeCounterName = "virtual-time:" + order.bank + ":" + order.customer
   val priorityQueueName = "bank-queue:" + order.bank

   val virtualFinishTime = client.incrby(virtualTimeCounterName, order.transactionCount.toLong())
           .wait()?.toLong() ?: 0

   client.zadd(
           priorityQueueName,
           ScoredValue.just(virtualFinishTime.toDouble(), order.asString())
   ).wait()
}

Consumer code

Consumer code is even simpler, just calls Redis zpopmin operation to remove minimum item from the sorted set.

It is possible that several consumers consuming items from the same bank queue thus such service is horizontally scalable.

val client = RedisClient.create("redis://localhost:6379/0")
       .connect()
       .async()

val bankN = args[0].toInt()// bank that consumer is serving
val priorityQueueName = "bank-queue:$bankN"

while (true) {
   val item = client.zpopmin(priorityQueueName)
           .wait()

   if (item.isEmpty) {
       delay(100)
       continue
   }

   val order = PaymentOrder.fromString(item.value)

   println(order) // do processing i.e. send order to bank
}

Simulation

In simulation we would like to confirm that the fairness concept works.

Let’s simulate a case when one customer submitted at a time 5 big transaction batches, right after that second customer submitting the same set of transactions.

This might be quite probable if for example a customer is doing payroll and submitting a few batches at a time.

For FIFO this case is going to result in the following sequence. Basically first customer is served first and second customer served just after:

PaymentOrder(transactionCount=10, customer=1, id=0)
PaymentOrder(transactionCount=10, customer=1, id=1)
PaymentOrder(transactionCount=10, customer=1, id=2)
PaymentOrder(transactionCount=10, customer=1, id=3)
PaymentOrder(transactionCount=10, customer=1, id=4)
PaymentOrder(transactionCount=10, customer=2, id=5)
PaymentOrder(transactionCount=10, customer=2, id=6)
PaymentOrder(transactionCount=10, customer=2, id=7)
PaymentOrder(transactionCount=10, customer=2, id=8)
PaymentOrder(transactionCount=10, customer=2, id=9)

For fair queueing the situation is totally different, customers are treated equally and transaction batches are intertwined:

PaymentOrder(transactionCount=10, customer=1, id=0)
PaymentOrder(transactionCount=10, customer=2, id=5)
PaymentOrder(transactionCount=10, customer=1, id=1)
PaymentOrder(transactionCount=10, customer=2, id=6)
PaymentOrder(transactionCount=10, customer=1, id=2)
PaymentOrder(transactionCount=10, customer=1, id=3)
PaymentOrder(transactionCount=10, customer=2, id=7)
PaymentOrder(transactionCount=10, customer=1, id=4)
PaymentOrder(transactionCount=10, customer=2, id=8)
PaymentOrder(transactionCount=10, customer=2, id=9)

This shows how it is possible to schedule transactions fairly and distribute processing power among customers equally.

In future articles, we will explore additional ways to optimize instant payments and banking. Future installments will include:

Autoscaling instant payment processors based on request, queue length and throughput
Leveraging backpressure to schedule requests
Using webhooks for payment status updates

Documentation

API

Community

Fair queueing for payment batches

Fair queueing

Producer code

Consumer code

Simulation