Optimizations for TicToc (Non-Distributed) and Sundial (Distributed)

TicToc Optimizations.md

After reading a value, Q, a transaction, T, only needs to know the first change to Q's wts to determine how reading Q affects the upper-bound of T's commit time.

T can get notified when the wts of a value it reads changes by adds its id to a list of ids attached to Q. When T2 commits and overwrites Q, it will use the list of ids to send a message to each transaction that read from Q. The message will contain the new wts of Q. After sending all the messages, T2 will clear the list of ids attached to Q.

The list of ids is called tags.

def read(T, key):
    if key in T.WS:
        return WS[key].data
    elif key in T.RS:
        return RS[key].data
    else:
        T.RS[key].[wts, rts, data] = DB[key]
        add_tag(key, T.id)
        return RS[key].data

def write(T, key, data):
    if key not in T.WS:
        n = get_home_node(key)
        [success, rts] = lock(key)
        if not success:
            Abort(T)
        else:
            T.commit_ts = Max(T.commit_ts, rts + 1)
            # Don't need the tag anymore since the value is locked
            if key in T.RS:
                # non-blocking operation
                remove_tag(key, T.id)
    T.WS[key].data = data

def commit(T):
    for key in T.WS.keys():
        n = get_home_node(key)
        if key in T.RS:
            # non-blocking operation
            remove_tag(key, T.id)
        notify_tagged_transactions(key, T.cts)
        update_and_unlock(key, T.WS[key].data, T.cts)
        # non-blocking operation
def abort(T):
    for key in T.WS.keys():
        n = get_home_node(key)
        if key in T.RS:
            # non-blocking operation
            remove_tag(key, T.id)
        unlock(key)

## Auxilary methods

# Assume there is a separate thread for receiving messages
# and this thread can filter out "tag removed" type messages
def ListenerThread::Receive_Tag_Removed_Msg(msg):
    # T is the local transaction that placed this message
    T = DB.Transactions[msg.owner_id]
    if T.status != COMMIT:
        # upper_bound is not just used in this method
        # it can also be used anytime T needs to update its commit timestamp
        # to check if the new commit timestamp is legal
        T.upper_bound = min(T.upper_bound, msg.new_wts)
        if T.upper_bound > T.commit_ts:
            Abort(T)


# owner_id is the id of the transaction that is placing the tag
def add_tag(key, owner_id):
    DB[key].tags.add(owner_id)

def remove_tag(key, owner):
    DB[key].tags.remove(owner_id)

def notify_tagged_transactions(key, cts)
    for owner_id in DB[key].tags:
        msg = (
            owner_id = owner_id
            new_wts = cts
        )
        Send_Msg(msg)

Everytime a transaction wants to write to a value Q, it copies the value of Q into its write set and performs the write. It also requests a write lock for Q. It performs the request by:

1. Sending a message to each tagged transaction requesting permission for a write lock.
   • The message can optionally contain the current minimum commit timestamp of the requesting transaction. If this optional parameter is not specified, then the minimum commit timestamp is set as Q.rts + 1.
2. Waiting until all responses have been received. If
   • All responses say "continue" then check if another transaction has acquired a write lock in the meantime, if not, acquire the write lock, otherwise abort.
   • If any reponse says "abort", then don't acquire the write lock and abort.

A possibly more effecient alternative is acquiring the write lock immediately, then send verification requests. However, the write lock is not "verified" (so the transaction cannot commit), until a "continue" response have been received from all tagged transactions. The transaction can still write to the shadow copy in the meantime.

If a transaction receives a write lock request it

• Responds with abort if the transaction has commited and extended Q's rts past the minimum commit timestamp.
• Otherwise the transaction responds with continue. Since the transaction now knows that the value is locked, it can automatically abort if it needs to extend Q's rts in the future without sending a round-trip message to determine if Q is currently locked.
  • As an alternative, if the receiver has not yet committed but knows it must extend Q's rts past the minimum commit timestamp, then the receiver can respond with abort. This approach gives priority to reads over writes.

If this optimization and the first optimization are implemented then the validation phase can be removed from TicToc, since every transaction will know whether any value (Q) in its read set has been

1. has been overwritten (and if so, the new wts of Q)
2. whether Q is locked by another transaction

def write(T, key, data):
    if key not in T.WS:
        [success, rts] = read_data(key)
        if not success:
            Abort(T)
    else:
        rts = T.WS[key]
    
    # non-blocking operation
    if T.cts is None:
        min_cts = rts + 1
    else:
        min_cts = T.cts

    request_write_lock_from_tagged_transactions(key, min_cts, T.id)

    T.commit_ts = Max(T.commit_ts, rts + 1)
    # Don't need the tag anymore since the value is (going to be) locked
    if key in T.RS:
        # non-blocking operation
        remove_tag(key, T.id)

    T.WS[key].data = data

def request_write_lock_from_tagged_transactions(key, min_cts, sender_id):

    ListenerThread[sender_id][key].num_awaiting = DB[key].tags.length

    for owner_id in DB[key].tags:
        msg = (
            owner_id = owner_id
            key = key
            sender_id = sender_id
            min_cts = min_cts
        )
        Send_Msg(msg)
        
def ListenerThread::Receive_Write_Lock_Request_Msg(msg):
    # Scenario 1 - The local transaction has already committed and
    # extended the value of the timestamp
    T = DB.Transactions[msg.owner_id]
    response = (
        status = None
        original_sender = msg.sender_id
        key = key
    )
    if T.status == COMMIT:
        if T.cts > msg.min_cts:
            response.status = ABORT
        else:
            response.status = OK
        Send_Msg(response)
    else:
        response = OK
        # This information can be used in the validation phase to avoid a 
        # round-trip
        T.RS[msg.key].is_locked_by_other_transaction = True
        Send_Msg(response)

def ListenerThread::Receive_Write_Lock_Request_Response(msg):
    num_awaiting = ListenerThread[msg.original_sender][msg.key]--
    T = DB.Transactions[msg.original_sender]
    if msg.status == ABORT:
        Abort(T)
    elif num_awaiting == 0:
        T.write_lock_request_was_successful(msg.key)

def Transaction::write_lock_request_was_successful(key):
    # Check if the data item was locked by another transaction
    # while this transaction was waiting for a response
    if DB[key].is_locked():
        Abort(T)
    else:
        lock(DB[key])