# 数据库代写 | Assignment 7: Databases—Inside the Blackbox

Description

A financial service provider came to the conclusion that their system, which processes complex money transfers between people, is not fast enough. Hence, they asked an consultant to come up with a higher-performance system. The consultant took a look at the original system and concluded that lock-based access was the main culprit. To deal with these performance issues, the consultant came up with a novel design

that reduces the duration of locks. Next, we detail the proposed design.

In the system, all transactions can be written as a sequence of transfers of the form

transfer(\$𝑥, from, to) = “transfer \$x from account from to account to”,

that should only be executed if each transfer is possible (the from-account has sufficient funds). E.g., the

transaction

𝜏 = [transfer(\$500, Bo, Alicia), transfer(\$300, Eva, Celeste)]

of two such transfers is equivalent to

“if Bo has at-least \$500 and Eva has at-least \$300,

then transfer \$500 from Bo to Alicia and transfer \$300 from Eva to Celeste”.

The consultant wants to execute these transactions with a minimal amount of locking. To do so, the consultant designed the minimal-locking operations update-balance and take-balance-conditional

(see Figure 1 for the pseudo-code of these operations). Using these operations, the consultant proposes

to execute transactions 𝜏 with 𝑛 transfers, e.g., 𝜏 = [transfer(\$𝑥1, from1, to1), . . . , transfer(\$𝑥𝑛, from𝑛, to𝑛)],

using the execute-transaction algorithm (see Figure 2 for the pseudo-code of this algorithm). The execute-transaction algorithm will visit each from-account, check whether that account has sufficient

update-balance(𝜏, account, amount):

1: Loc𝜏 (account).

2: account := account + amount.

3: Release𝜏 (account).

take-balance-conditional(𝜏, account, amount):

4: Lock𝜏 (account).

5: if account ≥ amount then 6: account := account − amount.

7: Release𝜏 (account).

8: return True.

9: else

10: Release𝜏 (account).

11: return False.

12: end if

Figure 1: The pseudo-code for the minimal-locking operations update-balance and take-balance-conditional. funds (at-least the funds required for the transfer), and take away the funds that are to-be transferred (a reservation of funds). This reservation can be used in two ways:

1. If all from-accounts have sufficient funds, then all reserved funds will be transferred to their respective to-accounts (the transaction is successful). To do so, the variable Commit lists all update-balance operations necessary to transfer reserved funds to their respective to-accounts.

2. Otherwise, if a from-account is found without sufficient funds, then all previously reserved funds will be returned to their respective from-accounts (the transaction failed). To do so, the variable Rollback lists all update-balance operations necessary to transfer reserved funds back to their respective from-accounts.

The consultant believes that this setup will reduce locking, but might introduce unwanted interfer-ence between transactions. The financial service provider has already been instructed about the risks of interference, and decided that it can agree to interference as long as the following constraints are never

broken:

C1. No account should ever receive a negative balance (assuming that all accounts start with a positive balance).

C2. As the transfers only move money between accounts, no money should be lost or created. Hence, if at

any time 𝑡 no transactions are being executed, then the sum of the balances of all accounts at that time 𝑡 should be equivalent to the initial sum of the balances of all accounts.

C3. Successful transactions must have their lasting effects, while failed transactions must not have lasting

effects. Hence, if at any time 𝑡 no transactions are being executed, then the balance of each account should reflect the balance updates due to all transactions that executed successfully before 𝑡 .

We note that these constraints do not rule out inconsistencies in the data while transactions are being executed.

Faced with the complexity of the approach proposed by the consultant, the financial service provider has contacted you to evaluate the proposed approach.

execute-transaction(𝜏):

1: Commit, Rollback := ∅, ∅.

2: for each transfer(\$𝑥, from, to) in 𝜏 do

3: if take-balance-conditional(𝜏, from, \$𝑥) then

4: Store the operation “update-balance(𝜏, to, \$𝑥)” in Commit.

5: Store the operation “update-balance(𝜏, from, \$𝑥)” in Rollback. 6: else

7: Perform all operations in Rollback.

8: return failure.

9: end if

10: end for

11: Perform all operations in Commit.

12: return success.

Figure 2: The pseudo-code for the transaction execution algorithm.

To evaluate the approach, the financial service provider asked you to investigate and answer the following questions:

1. Does the proposed approach follow strict two-phase locking? Does the proposed approach follow two-phase locking? Explain your answer. E.g., if the approach does not follow (strict) two-phase locking, then provide a transaction, its execution schedule, and argue that this schedule does not follow the (strict) two-phase locking protocol.

E.g., if there are conflicts, then provide two transactions, a valid interleaved execution schedule for these transactions, and argue that this schedule has these conflicts.

then provide two transactions, a valid interleaved execution schedule for these transactions, and argue that this schedule has dirty reads.

unrepeatable reads, then provide two transactions, a valid interleaved execution schedule for these transactions, and argue that this schedule has unrepeatable reads.

7. Are the constraints C1-C3, as set out by the financial service provider, satisfied? Explain your answer. E.g., if a constraint is satisfied, then argue why that is the case.

Assignment

The goal of the assignment is to help out the financial service provider. To do so, you will write a report in which you answer Questions 1–7. Your submission:

1. must be a PDF file;

2. must have clearly labeled solutions to each of the stated evaluation questions;

3. must include explanations for each of the stated evaluation questions;

4. must be clearly presented;

5. must not be hand-written: prepare your document in Microsoft Word or another word processor (printed or exported to PDF) or in L

ATEX.

Submissions that do not follow the above requirements will get a grade of zero.

The presented solution for Question 1–6 will each account for 12.5% of the maximum grade; the presented solution for Question 7 will account for 25% of the maximum grade.

E-mail: itcsdx@outlook.com  微信:itcsdx