Create the demand queues

[thinkjrs]

Creating the DemandQueue

Each dealer in our scheme has a queue of demand where a sim-exchange user's
order is placed after clicking "Accept My Deal." A user's order remains in this
queue while they have unmatched cash flows; if there is not a resulting
cash-flow match, the user's order stays in the queue.

Note: Because of the nature of what's being traded--the cash flows between individuals with varying certainty--the concepts user and order are often interchangeable. We will be specific whenever possible. This will become more apparent as more of sim-exchange is built out.

A user and their order(s)

A user is a person, robot, or generally, a client of the dealer. Very tangibly
this is the initial JSON web request with data from the "Accept My Deal."

In sim-exchange, there are two types of users: investor-users & asset-users. Each has its own set of parameters, prior to arriving on the
platform as a potential dealer client. For our purposes here, consider the
user's order live (and in the demand queue) once that respective user has
agreed to do a deal via an HTTP POST request form submission from the frontend.

Investor user parameters

A minimal investor-user will have the following:

mu: float
sigma: float
total_toFund: float
remaining_toFund: float
genre: str
time_horizon: datetime.datetime
investments: dict # more on this in a moment

Asset user parameters

A minimal asset-user will have the following:

mu: float
sigma: float
ranking: float
genre: str
total_funding: float
remaining_funding: float
expiration_date: datetime.datetime
investors: dict # more on this below

An order on sim-exchange

Though we won't need FIX for sim-exchange, we might as well utilize
the most fundamental aspects to its protocol. So for communicating orders
between dealers and the platform operator via the signaler we'll use
the modern FIX protocol for messaging.

DemandQueue API

Assume you have an Order class which stores/holds/updates individual users'
order data. The demand queue is part of order management, similar to the
Order Manager you've probably touched in developing a FIX exchange.

class DemandQueue:
    """
    Each dealer inherits DemandQueue.
    """
    def __init__(self):
        self.queue = # some type of python queue

    def insert(self):
        pass
    def cancel(self):
        pass
    def update(self):
        pass
    def view(self):
        pass

class InvestorDemandQueue(DemandQueue):
    def __init__(self):
        pass

class AssetDemandQueue(DemandQueue):
    def __init__(self):
        pass

Tasks

Add to these as/if requirements evolve!

• Choose & justify a Python queue
  • link to docs
  • discuss underlying queue datastructure considerations herein
• Implement a basic DemandQueue capable of basic CRUD operations
• Full test coverage

Tests

Tests for this are located under backend/application/test. We use py.test
for the test-suite runner and unit testing.

Filename targets: test_DemandQueue.py is the unit test file for this
particular portion.

[RKoulikova]

Possible Implementations:

Consider also a deque simply to transfer orders to the main book/exchange (or a priority queue depending on the functionality
and purpose of allowing orders to sit in the queue).

CURRENT STRUCTURE:

--> Double linked list. Orders will sit here however no functionality
exists in matching orders. Next step to create structure for specifically matching orders:

• lists of orders from both users
• tree of orders from both users (one OrderTree for each side)

(This is where orders will sit until the matching takes place).

Does a difference exits in investor and asset demand queues?
Does a difference exist in investor and asset order book?

Basic Implementation (depends on data structure of order coming in):

demand_queue.py.zip

[thinkjrs]

Possible Implementations:

Consider also a deque simply to transfer orders to the main book/exchange (or a priority queue depending on the functionality
and purpose of allowing orders to sit in the queue).

CURRENT STRUCTURE:

--> Double linked list. Orders will sit here however no functionality
exists in matching orders. Next step to create structure for specifically matching orders:

• lists of orders from both users
• tree of orders from both users (one OrderTree for each side)

(This is where orders will sit until the matching takes place).

Does a difference exits in investor and asset demand queues? Does a difference exist in investor and asset order book?

Basic Implementation (depends on data structure of order coming in):

demand_queue.py.zip

@RKoulikova 💯 especially on iterators.

Next steps

1. Write out naive unit tests in in the pytest format, per what we have in backend/tests.

   • Just a few tests needed to make sure things are working.
   • Make a separate test for each function and/or dynamic parameter in your DemandQueue Class
     Query on slack if you have any questions/thoughts!

2. Underlying datastructure thoughts:
   Your thinking of deque is the right direction so run with it.

Thinking long-term

We might want to explore/develop something down the road that uses some type of hashing for O(1) access (dequeue is O(n)). Each dealer has a DemandQueue which it will update periodically as users arrive and/or receive cash-flow "matches" (assuming it is trading with the other dealer).

I do not think this is important now. We'll likely store a reference to a redis client caller anyways, for each 'user' object (dataclass) stored in the queue.

3. Users dataclass

Basic Implementation (depends on data structure of order coming in)

Checkout entities.py. Think of these as glorified dictionaries.

[thinkjrs]

@RKoulikova Let's be sure to chat about the red-black tree Seb sent around, in addition to tradeoffs around usage of dequeue versus other options.

[RKoulikova]

Consider three different self-balancing BST data structures for an order book for both that asset and investor class:

1. AVL tree

• rebalances after an insertion, the difference between heights of left and right subtrees cannot be more than one for all nodes

2. Red Black Tree

• balance is preserved by painting each node

• path from root to farthest leaf is no more than twice as long as path from root to nearest leaf

Main Takeaways:

• AVL trees provide faster lookups than Red Black Trees because they are more strictly balanced

• Red Black Trees provide faster insertion and removal operations than AVL trees as fewer rotations are done due to relatively relaxed balancing

3. Splay Tree

• not as balanced as AVL
• fast access to elements accessed recently
• make rotations -> most recently accessed item to root of tree
• goal is to make the entire sequence of operations (insert, search, delete) fast

---

Consider a splay tree for the order book particularly for the problem at hand. By splaying elements (orders), more frequently used or accessed orders are brought closer to the root of the tree. Splaying (bringing node to the top as the root node) is performed while both searching for orders and when adding new orders.

[thinkjrs]

Consider a splay tree for the order book particularly for the problem at hand. By splaying elements (orders), more frequently used or accessed orders are brought closer to the root of the tree. Splaying (bringing node to the top as the root node) is performed while both searching for orders and when adding new orders.

@RKoulikova Excellent overview of the possible trees we can use here, since we have the frequent order access requirement. The next steps are very basic implementation.

If you're going with splay trees

I found this and it helped show the differences (really additions) between a standard binary search tree and the splay tree. I think I 👀 your plan: we have ourselves a fancy dictionary that will auto-balance behind-the-scenes according to our "price" and "time" metrics attached to an incoming and then "sitting" user order.

Per our discussion over the weekend, price/time will likely be some bar we set and update globally based on market prices. See #16 comment for some deets on the SDF.

Let's focus on testing tasks

• Write a test to meet a single Insert, Delete, Search, and Modify an order with a single user

Search should work for a single order!

• Write tests to Insert a list of users, delete a few, search through the DemandQueue, and modify several.
• Do these sequentially and open a pull-request (the below is something between pseudo-code and what you'll want to actually write:

def test_DQ_access(DemandQueue, AssetUser, InvestorUser):
    # check that accessing a user works prior to checking other function as we need it to test those
    pass

def test_DQ_insertion(DemandQueue, AssetUser, InvestorUser):
     dq = DemandQueue(...)
     dq.insert(AssetUser)
     # check it isn't nothing
     assert dq[AssetUser] is not None
     # check that it's what we expect
     assert isinstance(dq[AssetUser], AssetUser)
     # check that it's the data we expect
     assert dq[AssetUser] == AssetUser
     
...and so on and so forth

Dictionary-like client use

Since this is a tree in the background, let's make it as close to a dictionary as possible, down the road. Want to say that now so that we're thinking long-term for implementation.

[RKoulikova]

A basic implementation of the OrderBook is shown below. A splay tree class from AlgorithmTutor: Bibeknam is used/modified to perform necessary operations on orders.

Consider an Order() class:

@dataclass
class Order(DataClassJsonMixin):
    def __init__(self, mu, sigma, cash, time_stamp):
        self.mu = mu
        self.sigma = sigma
        self.cash = cash
        self.time_stamp = time_stamp
        
    def __str__(self):
        return 'Order(mu='+str(self.mu)+', sigma='+str(self.sigma)+ ', cash=' + str(self.cash)+', time='+str(self.time_stamp)+  ')'

Each Order will be represented as a Node in the Splay Tree:

class Node:
    def  __init__(self, order):
        self.data = order.cash
        self.order = order.__str__()
        self.parent = None
        self.left = None
        self.right = None

The OrderBook() class is constructed as a splay tree. For initial stages of developing a splay tree class, AlgorithmTutor: Bibeknam's implementation of splay trees is used and modified for taking in orders.

class OrderBook:#SplayTree
    def __init__(self):
        self.root = None

    def __delete_node_helper(self, node, key):
        x = None
        t = None 
        s = None
        while node != None:
            if node.data == key:
                x = node

            if node.data <= key:
                node = node.right
            else:
                node = node.left

        if x == None:
            print ("Couldn't find key in the tree")
            return

        # split operation
        self.__splay(x)
        if x.right != None:
            t = x.right
            t.parent = None
        else:
            t = None

        s = x
        s.right = None
        x = None

        # join operation
        if s.left != None:
            s.left.parent = None

        self.root = self.__join(s.left, t)
        s = None
        
    """
    Join() and maximum() will assist with deleting nodes.
    
    """
    # joins two trees s and t
    def __join(self, s, t):
        if s == None:
            return t

        if t == None:
            return s

        x = self.maximum(s)
        self.__splay(x)
        x.right = t
        t.parent = x
        return x  
    
    # find the node with the maximum key
    def maximum(self, node):
        while node.right != None:
            node = node.right
        return node
    
    """
    ZAG-ROTATION:
    
    This is similar to a LEFT rotation. Every node moves a position to the left. 
    We can do a zag rotation if a node is a right child of the root node. 

    """
    def __left_rotate(self, x):
        y = x.right
        x.right = y.left
        if y.left != None:
            y.left.parent = x

        y.parent = x.parent
        if x.parent == None:
            self.root = y
        elif x == x.parent.left:
            x.parent.left = y
        else:
            x.parent.right = y
        y.left = x
        x.parent = y

    """
    ZIG-ROTATION:
    
    This is similar to a RIGHT rotation. Every node moves a position to the right. 
    We can do a zig rotation if a node is a left child of the root node. 

    """
    def __right_rotate(self, x):
        y = x.left
        x.left = y.right
        if y.right != None:
            y.right.parent = x

        y.parent = x.parent;
        if x.parent == None:
            self.root = y
        elif x == x.parent.right:
            x.parent.right = y
        else:
            x.parent.left = y

        y.right = x
        x.parent = y

    """
    By "splaying" a tree, necessary operations (zig/zag) are performed to bring a node to the root of the tree. 
    """    
    # Splaying operation. Move x to the root of the tree
    def __splay(self, x):
        while x.parent != None:
            if x.parent.parent == None:
                if x == x.parent.left:
                    # zig rotation
                    self.__right_rotate(x.parent)
                else:
                    # zag rotation
                    self.__left_rotate(x.parent)
            elif x == x.parent.left and x.parent == x.parent.parent.left:
                # zig-zig rotation
                self.__right_rotate(x.parent.parent)
                self.__right_rotate(x.parent)
            elif x == x.parent.right and x.parent == x.parent.parent.right:
                # zag-zag rotation
                self.__left_rotate(x.parent.parent)
                self.__left_rotate(x.parent)
            elif x == x.parent.right and x.parent == x.parent.parent.left:
                # zig-zag rotation
                self.__left_rotate(x.parent)
                self.__right_rotate(x.parent)
            else:
                # zag-zig rotation
                self.__right_rotate(x.parent)
                self.__left_rotate(x.parent)
                
    def __search_tree_helper(self, node, key):
        if node == None or key == node.data:
            return node

        if key < node.data:
            return self.__search_tree_helper(node.left, key)
        return self.__search_tree_helper(node.right, key)
            

    # search the tree for the key k
    # and return the corresponding node
    def search_tree(self, Node):
        x = self.__search_tree_helper(self.root, Node.data)
        if x != None:
            self.__splay(x)

            
    # insert the key to the tree in its appropriate position
    def insert(self, Node):
        node =  Node
        y = None
        x = self.root

        while x != None:
            y = x
            if node.data < x.data:
                x = x.left
            else:
                x = x.right

        # y is parent of x
        node.parent = y
        if y == None:
            self.root = node
        elif node.data < y.data:
            y.left = node
        else:
            y.right = node
        # splay the node
        self.__splay(node)

    # delete the node from the tree
    def delete_node(self, Node):
        self.__delete_node_helper(self.root, Node.data)

Now consider testing these classes with orders.

• Create order objects
• Create nodes for these orders
• Insert/delete/search in OrderBook()

o1 = Order(mu=.05, sigma=.10, cash = 100, time_stamp=datetime.date.today())
o2 = Order(mu=.15, sigma=.20, cash = 200, time_stamp=datetime.date.today())
o3 = Order(mu=.25, sigma=.30, cash = 150, time_stamp=datetime.date.today())
o4 = Order(mu=.25, sigma=.30, cash = 50, time_stamp=datetime.date.today())

n1 = Node(o1)
n2 = Node(o2)
n3 = Node(o3)
n4 = Node(o4)

tree = OrderBook()
tree.insert(n1)
tree.insert(n2)
tree.insert(n3)
tree.insert(n4)

#visualize the splay tree
treeviz(tree)

tree.search_tree(n3)

treeviz(tree)

tree.delete_node(n1)

treeviz(tree)

[RKoulikova]

Test cases for splay tree demand queue:
test_splay.py.zip