distributed-exchange

Application

• A distributed central database which implements the 'Saga' protocol to facilitate distributed transactions.
  • Users which will interact with the servers via HTTPS.
  • Each node hold multiple accounts.
  • Each process manage one accounts.
• There are < 10^4 stocks.
• There are < 19^9 accounts.
• Each account have roughly 0.1 unmatched buy or sell order at any given time.

Running instructions

• Refresh the directories: ./refresh_dirs.sh
• Launch a single coordinator: cargo run -p coordinator -- -p <port>
• Launch at least 2 market database servers: cargo run -p node -- -c <coordinator address & port> -p <port>
• Launch at least 2 clients: cargo run -p client -- -c <coordinator address & port>

Running example

• Any terminal: ./refresh_dirs.sh
• Terminal 1 ./run_coord.sh
• Terminal 2: cargo run -p node -- -a 127.0.0.1:8001 -c 127.0.0.1:8000 -p ./node1/
• Terminal 3: cargo run -p node -- -a 127.0.0.1:8002 -c 127.0.0.1:8000 -p ./node2/
• Terminals 4 and 5: ./run_client.sh

Approaches

1. Each node have local database (CHOSEN)
   • Each Node have its own copy of all buy and sell order on the market.
   • Every buy and sell order updates that database.
   • Every time the database is updated, the Node tries to create a match where at least one of the buyer or seller is an account that they own.
   • For every buy or sell order, the Node that owns the account where the order came from is the source of truth.
   • Upon matching, the Node takes away the money or stock and quantity in the order and account that they own (do they want to send out that update?) and send out a trade offer to the Node that owns the other account.
   • Upon receiving a trade offer, the Node deducts that money or stock and quantity in the order and account they own and send broadcast a trade confirm. (At this point the trade is confirmed)
     • If upon receiving a trade offer, the Node does not have enough money or stock in the order then they reply with a declined message and the other Node rollback (Roll back is also an update to the database so will attempt to be matched).
   • Both Nodes add stock OR money to the account that they own.
2. MD sends request, awaits replies from all servers for potential match. If successful, execute. Else, hold on to request.
   • Not good because we lose the ability to see a stats of the whole market.

Example runs of the protocol

Assume M1 and M2 are nodes.

e.g. M1 receives a SELL order from a user. It tries to match locally and fails, so it sends a SELL to all M. => M messages M1 receives a BUY order from a user. It matches locally with the SELL. It sends a TRADE_CONFIRMED to all M. => M messages

e.g. M1 receives a SELL order from a user. It tries to match locally and fails, so it sends a SELL to all M. => M messages M2 receives a BUY order from a user. It matches locally with the SELL. It sends a TRADE_OFFER to M1. => 1 message M1 sends a TRADE_CONFIRMED to all M. => M messages.

Fault tolerance

When a node crashes, it'll be restarted.
We store everything important: money, stock, order, pending transaction from their own account.
When a node restart, or is first started, it'll query every other node to build the local database, and also ask the other node to add it to the update list of database update.
TODO: update the protocol for crash failure

If a Node already sent out a trade offer, it can't commit or abort without a trade reply.
If a Node receives a trade offer, it can commit or abort immediately before sending the trade reply. When a node crash, all the transactions that involve that node can't be committed or aborted. But all the account that node owns can't do anything as well, so it's not that much worse.

Coordinator

One single dedicated server will listen on an IP address. All Nodes will contact that server for a list of IP address of the other servers and register its own address. User login with the coordinator and get IP address from the server. User establish TCP connection with the Node.

Messaging protocol

We have 3 executable: Coordinator, Node, Client. Client is optional.

types:

• UserID is a json object of the following structure:

  {
    "id": 5,
    "node_id": 3
  }

• TradeID is an integer.
• Ticker is a string.
• All price are in unit of cents

Node2Node

There are 3 kinds of message:

• Order: Buy/Sell, ticker, userid, quantity, price.
• TradeOffer: TradeId, ticker, userid_buyer, userid_seller, quantity, price
• TradeRep: Confirmed/Declined, TradeId

Communication channel: TCP stream.

Message format one line per json message:

• Establish connection

• Send node_id (json number)

• If recovered: // UNIMPLEMENTED

  • Both side (recovered side first) send list of all user buy orders and sell orders
  • Both side poll answer for pending request

{
  "type": "order",
  "value": {
    "deduct": false,
    "order_type": "buy|sell",
    "ticker": "Ticker",
    "user_id": "UserID",
    "quantity": 100,
    "price": 1050
  }
}

{
  "type": "offer",
  "value": {
    "id": "TradeID",
    "ticker": "Ticker",
    "buyer_id": "UserID",
    "seller_id": "UserID",
    "quantity": 100,
    "price": 1050,
    "buy_price": 1050,
    "sell_price": 1000
  }
}

{
  "type": "reply",
  "value": {
    "accepted": true,
    "id": "TradeID"
  }
}

Node2Coordinator

• Register (new or recovered) node
  • Establish connection Node -> Coord

  {
    "addr": "<node addr>",
    "state": {
      // null if new node
      "id": 3,
      "account_num": 100
    }
  }

  Coord -> Node

  {
    "id": 3 // null if recovered node
    "others": [ // other nodes
      {
        "id": 1,
        "addr": "<node addr>"
      }
    ]
  }

  Node -> Coord

  "ok" // recieved and prepared to connect with all other nodes

  • req res messages
    • New / recovered node joined: req:

    {
      "type": "joined",
      "id": 3,
      "addr": "<node addr>"
    }

    res: No Reply
    • New account request req:

    { "type": "C account" }

    res:

    "UserID"

Client2Coordinator

• Find Node for account.
  • Establish connection req:

  "UserID"

  res:

  "<node addr>" // to be parsed by SocketAddr::parse()
  

  • Close connection
• Create accounts.
  • Establish connection req:

  "C account"

  res:

  "UserID"

  • Close connection

Client2Node

• Establish connection

  • Client send UserID

• RU for account balance.

  req:

  { "type": "R balance" }

  res:

  100

  req:

  {
    "type": "U balance",
    "value": 100
  }

  res:

  "ok|notEmpty"

• CR for stocks in account.

  req:

  { "type": "R stock" }

  res:

  {
    "tickerID": 100,
    "tickerID2": 200
  }

  req:

  {
    "type": "C stock", // IPO: Should be privileged to admin user of some governing body
    "value": {
      "ticker_id": "tickerID",
      "quantity": 1000
    }
  }

  res:

  "ok"
  

• R for market status. req:

  { "type": "R market" }

  res:

  {
    "tickerID": {
      "sell": [
        {
          "quantity": 100,
          "price": 1050
        }
      ],
      "buy": []
    },
    "tickerID2": {
      "sell": [],
      "buy": []
    }
  }

• CRD for orders. req:

  {
    "type": "C order",
    "value": {
      "order_type": "buy|sell",
      "ticker": "tickerID",
      "price": 1050,
      "quantity": 100
    }
  }

  res:

  "ok|notEnough"

  req:

  { "type": "R order" }

  res:

  {
    "tickerID": {
      "sell": [
        {
          "quantity": 100,
          "price": 1055
        }
      ],
      "buy": []
    },
    "tickerID2": {
      "sell": [],
      "buy": []
    }
  }

  req:

  {
    "type": "D order",
    "value": {
      "order_type": "buy|sell",
      "ticker": "tickerID",
      "price": 1050,
      "quantity": 100
    }
  }

  res:

  90 // quantity deleted (the rest already traded or didn't exist in the first place)

• Delete accounts. req:

  { "type": "D account" }

  res:

  "ok|notEmpty"

• Terminating Connection:

  "bye"

Coordinator failure

TODO

Architecture

• Matcher: one on each node, responsible for matching order where one of the seller or buyer belong to this node.
• Accounts: source of truth, responsible for recording orders, balance, portfolio and stocks.
• There can not be more order than balance / stock in portfolio.

Matcher syncing broadcasting local order deduction

• local matched with remote -> no need to broadcast.
• local matched with local -> broadcast to everyone. TICK
• remote matched with local. -> need to broadcast to everyone. TICK
• offer accept sent.
  • need to broadcast to everyone. TICK
• offer deny received.
  • need to broadcast to everyone. TICK
• Order deducted.
  • need to broadcast. TICK

add order to matcher: (can come from remote or local)

• Matcher matches and broadcast all the other local order deducted (apart from the new one).
  • NEVER implicitly deduct remote orders.
  • If new order is local, broadcast the remaining new order.
• Offers are sent out.
• Offer received and accepted, broadcast local order deducted TO EVERYONE.
• Offer reply rejected, treat it as newly created order.