database simple DBMS

The objective of the project is to implement a simple replicated database management system (DBMS)

using C and one of the technologies (e.g. semaphores, fork, sockets and/or RPC).

The DBMS must be implemented as a collection of distributed processes.

Each process is assigned a unique numeric ID (not consecutive) and each process knows about the

existence of any other process. Let us assume that the processes IDs can be ordered in an array (pi) such

that pi < pi+1. You can hardcode this information in your implementation.

0 5 15

insert:

<key=2; value=5>

new data: <key=2; value=5>

query:

<key=2; value=?>

Figure 1: Insert and query for key 2.

Your DBMS must store mappings (key; value) where both elds are 32bits integers. The database acts

like a dictionary: a client searches using a numerical key and obtains as result the data that it wants.

Mappings can only be inserted, queried and deleted from the database

insert A client makes an insert operation for a pair (key; value) by contacting a process pi such that

pi key < pi+1. The data is then replicated on all other processes. A server must reject an insert

operation if the key does not correspond to its ID.

For instance, assume that you have three servers with IDs 0, 5, and 15. If a client wants to insert some

data with key 2, he will request this operation to server 0. Similarly, if a client wants to insert data

with key 6, this operation will be requested to server 5.

However, if the request with key 6 would have been addressed to server 0, this request must fail.

Moreover, the insert is idempotent, i.e., if there is already an entry (key; val1), and someone does

insert(key; val2), the previous entry is overwritten all over.

delete A client can delete a key from the database by making a request to a process pi such that pi key < pi+1. The delete operations must also be replicated on all processes.

Similarly to insert, the delete for key 2 will be requested to server 0, while the delete for key 6 will

be requested to server 5. If the delete for key 6 would have been addressed to server 0, this operation

must fail.

If delete(key; val) is issued and key does not exist, the operation succeeds.

1

query A client can query any process pi regarding the value mapped to a key. The DBMS is consistent if

all replicas return the same value for the same query.

For instance, a client can request replica 15 the value bound to key 2.

The system must keep a consistent view of the database, e.g. at any point in time the replicas must hold

the same data. To ensure this, it is acceptable that operations can fail due to con

icts among them (see tip

2 below). Moreover, you can assume that the data inserted in the database is put immediately on stable

storage: operations can simply fail if consistency cannot be ensured, so there is no need for recovery. Finally,

only crash failures can occur.

1. The insertion and delete operation are actually the atomic commit problem. Any of the algorithms for

two-phase or three-phase commit will work as a solution.

2. Make sure that if two (or more) operations on the same key originating from dierent clients are

concurrent, at most one is executed.

For instance, if one client issues \insert(key=2, value=5)" and at the same time another client issues

\delete(key=2)", at most one of these should be performed.

However, if a \insert(key=2, value=5)" and a \delete(key=3)" are concurrent, these can be safely

performed.

Technology: You are free to implement this project using either plain sockets or RPC. The use of RPC IS PREFERRED.

.NET C 编程 Python

项目ID： #415465

关于项目