Rawkhet Algorithms: Trade Queue

Technical piece! Rawkhet Pokemon gets about 100 orders a day, and prepares Pokemon in batches. At the end of each preparation batch, about 50 emails get sent out for collection. This poses an interesting problem – how do we handle the trade queue in the most efficient manner? Is first-come-first-serve, or FIFO (first-in-first-out) the best solution?

We actually use a custom data structure called a Priority Queue. This gives each order a “weight” or priority which we base off how large the order is (in terms of number of Pokemon to trade). When customers respond to get added to the queue, something like this happens:

int orderWeight = (order.getSize() / 10);
order.getPq().EnqueueOrUpdate(order, orderWeight);

The size is divided by 10 because it would allow us to group orders better. Integer data types in programming languages represent whole numbers, meaning an “int” given a value 0.5 would in fact be 0 and one given a value 1.5 would in fact be 1. Dividing by 10 means orders that have 3 or 6 Pokemon for example would be in the same weight of 0. 12 or 18 would be in the same weight of 1. 22 or 26 would be in the same weight of 2, and so on. This is important because it allows the algorithm to be more fair – or large orders like a Gigantamax Package (26x) will always have to wait for all Past-Gen Legendaries (22x) orders to finish first despite being of comparable size. This is illustrated in the later example.

Each order also stores a reference to which queue it falls under. There are 7 queues in total, representing each device in use.

A Priority Queue automatically sorts an “enqueued” object. What this means here is a queue is processed in order of how fast an order can be completed, followed by first-come-first-serve.

Here’s an example. Assume this is one specific queue, and elements are added to the queue in this sequence, simultaneously:
Order A: Gigantamax Package (26x)
Order B: Custom Pokemon (6x)
Order C: Past-Gen Legendaries Package (22x)
Order D: Galar Fossil Package (4x)

The resulting processing order will be B, D, A, C (assuming no race condition).

There are also interesting things to handle. Sometimes, the weight can be 0 for many orders in the queue (multiple customers buying single Pokemon). We therefore have to implement a way to “Peek” (get element with the lowest weight) multiple orders at once so we can cut down time on waiting for customers to respond or set up their trade.

Another interesting side effect here is a customer who messages when already in the queue ends up getting their position “bumped” backwards. In the above example, let’s say we’ve just finished with B and are starting to trade with D, and A messages again. The queue process will move A behind C for a final sequence of D, C, A.

After a lot of consideration we’ve decided this is probably the best way to handle a Trade Queue for now, efficiently handling most customers as fast as possible. Unfortunately some orders do suffer, such as some with 300 Pokemon at once (we usually block out the entire console for such large orders though) having a wait time of 3-4 hours, but is definitely the lesser evil compared to placing 20 other orders on hold.

Technology is incredible!

Leave a Reply

Your email address will not be published. Required fields are marked *