Open thinkjrs opened 4 years ago
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:
(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):
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):
@RKoulikova 💯 especially on iterators.
Write out naive unit tests in in the pytest
format, per what we have in backend/tests.
DemandQueue
Class
Query on slack if you have any questions/thoughts!Underlying datastructure thoughts:
Your thinking of deque
is the right direction so run with it.
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.
Basic Implementation (depends on data structure of order coming in)
Checkout entities.py
. Think of these as glorified dictionaries.
@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.
Consider three different self-balancing BST data structures for an order book for both that asset and investor class:
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
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.
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.
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.
Insert
, Delete
, Search
, and Modify
an order with a single user
Search should work for a single order!
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)
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.
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.
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)
Test cases for splay tree demand queue: test_splay.py.zip
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.A
user
and theirorder
(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:Asset user parameters
A minimal
asset-user
will have the following: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
APIAssume 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.Tasks
Tests
Tests for this are located under
backend/application/test
. We usepy.test
for the test-suite runner and unit testing.Filename targets:
test_DemandQueue.py
is the unit test file for this particular portion.