locks - GitLite

KO | EN

gitlite — search

#hacktoberfest #react #go #golang #machine-learning #deep-learning #linux #macos #nodejs #kubernetes #awesome-list #ios #openai #open-source

locks

(★ 210)

A scalable, deadlock-resolving resource locker

파일 탐색기

최종 버전 다운로드 (.zip)

- - ci.yml
- FUNDING.yml
- edoc-info
- erlang.png
- locks.md
- locks_agent.md
- locks_leader.md
- locks_server.md
- locks_ttb.md
- overview.edoc
- README.md
- stylesheet.css
- - README.md
  - rebar.config
- locks.hrl
- locks_trace.hrl
- locks.app.src
- locks.erl
- locks_agent.erl
- locks_agent.hrl
- locks_agent_lib.erl
- locks_app.erl
- locks_cycles.erl
- locks_debug.hrl
- locks_leader.erl
- locks_pg.erl
- locks_server.erl
- locks_server.hrl
- locks_server_lib.erl
- locks_sup.erl
- locks_ttb.erl
- locks_watcher.erl
- locks_window.erl
- locks_leader_SUITE.erl
- locks_tests.erl
.gitignore
LICENSE
LOCKS_LEADER_IDEAS.md
Makefile
README.md
rebar.config
rebar.config.script
rebar.lock

# 설치 가이드

1. 코드 내려받기

git clone https://github.com/uwiger/locks

깃허브에서 프로젝트 코드 전체를 내 컴퓨터로 내려받습니다.

cd locks

방금 내려받은 프로젝트 폴더 안으로 이동합니다.

2. Make

보통 추천

사전 준비물

Git GitHub에서 프로젝트 코드를 내려받으려면 필요합니다.
Make Linux/macOS는 보통 기본 설치되어 있습니다. Windows는 별도 설치(예: MSYS2, WSL)가 필요합니다.

make

생성된 빌드 설정을 바탕으로 실제 컴파일을 진행해 실행 파일을 만듭니다.

✅ 에러 없이 끝나면 성공입니다. 생성된 실행 파일을 직접 실행해보세요.

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

# The locks application #

[![CI](https://github.com/uwiger/locks/actions/workflows/ci.yml/badge.svg?branch=master)](https://github.com/uwiger/locks/actions/workflows/ci.yml)

__Authors:__ Ulf Wiger ([`ulf@wiger.net`](mailto:ulf@wiger.net)), Thomas Arts ([`thomas@quviq.com`](mailto:thomas@quviq.com)).

Scalable deadlock-resolving locking system

## locks ##

A scalable, deadlock-resolving resource locker

This application is based on an algorithm designed by Ulf Wiger 1993,
and later model-checked (and refined) by Thomas Arts.

Compared to the implementation verified by Thomas Arts, 'locks' has
included a hierarchical lock structure and has both read and write locks.
It is also distributed, supporting multi-node locks and quorum ('majority').

The algorithm is based on computing potential indirect dependencies and
informing dependent transactions in a 'fill-in-the-blanks' manner.

Eventually, one transaction will have enough information to detect a
deadlock, even though no central dependency graph or dependency probes
are used. Resolution happens with a (at least close to) minimal number of
messages, making the algorithm unusually scalable. Since it uses deadlock
detection instead of deadlock prevention, there are no phantom deadlocks.

Note: Unlock has not (yet) been implemented. Once the transaction ends, all
locks held by it are released automatically.

## Resolving deadlocks ##

Deadlocks can be resolved by one agent surrendering a lock to another agent.
The surrendering agent will be put last in the lock queue.

Note that this is a bad idea if the surrendering agent's client has already
acted on the lock. Optionally, the agent can abort whenever it would otherwise
have had to surrender a lock. This might be preferrable in some cases, and
will still only happen if there is an actual deadlock. It is usually possible
to design a system so that deadlocks will not occur during normal operation.

The agent that is told to surrender will do so unless the client has asked
for the transaction to be aborted AND the lock being surrendered has been
reported as held to the client. That is, the `abort_on_deadlock` option
when starting an agent may still allow some surrenders to take place - only
not on locks that the client already thinks it has. See the `locks_leader`
for an example of an application where `abort_on_deadlock=false` is the
desired mode of operation.

## Using 'locks' ##

Call `application:start(locks)` on each node that needs to participate in
locking.

## Structure of locks ##

The lock identifiers used by 'locks' are non-empty lists of key elements.

The lock table is viewed as a tree, and e.g. `[a]` implicitly locks `[a,1]`,
`[a,2]`, etc. Locks can be `read` (shared) or `write` (exclusive). Shared locks
are automatically upgraded to exclusive locks if requested (and if possible).

Using 'locks' in a database system, one might use a lock naming scheme like
`[DbInstance, Table, Lock]`, where `[DbInstance]` would be equivalent to a
schema lock, `[DbInstance, Table]` a table lock, etc.

There is only one lock table per Erlang node, so use prefixed keys, or a
unique top-level key.

## Agents ##

While it is possible to use the `locks_server` API directly to lock single
objects, distributed locking and deadlock detection is done by `locks_agent`.

The official API to use is `locks`.

Agents are started e.g. using `locks_agent:begin_transaction(...)`, and are
separate state machines (processes). The `locks_server` informs agents via
`#locks_info{}` messages (containing not only the ID of the agent that holds
a lock, but also of any agents waiting for one), and each agent keeps track
of a dependency graph. Agents inform each other ('younger' agents inform
'older' agents) of indirect dependencies, using an algorithm that guarantees
that one involved agent will eventually have enough data to detect any deadlock.

If a deadlock is detected, the 'oldest' agent must yield its lock. This is
either done as a 'surrender', where the agent yields the lock and is placed
last in the lock's wait queue, or by aborting. Which behavior is used is
controlled by the option `{abort_on_deadlock, bool()}`, given at the beginning
of the transaction.

## Distributed locking ##

Using the function `locks:lock(Agent, LockID, Mode, Nodes, Req)`, a lock
can be acquired on several nodes at once.

```erlang

Agent  :: pid().
LockID :: [any()].
Mode   :: read | write.
Nodes  :: [node()].
Req    :: all | any | majority.

```

The agent monitors the lock servers on each node. If it determines that too
few lock servers are available to fulfill the lock requirement, it will abort.

## Verification ##

The following text describes the implementation verified by Thomas Arts
during 1999-2000. It contains several explanations of the algorithm,
identifying a number of alternative design choices as unsafe. There are also
some hints regarding optimization potential.

A few comparisons with the current implementation:

* When Arts talks about 'the object' and 'the client', these correspond to
the object_server (which handles all locks on the node) and the agent
respectively.

* The implementation also served read and write requests on the object.
This has been removed, and it is up to the client to ensure that it does
not operate on a resource requiring a lock, without first acquiring the lock.

* Canceling a lock request is not yet implemented.

* Lock update messages do not contain the requesting agent. Instead, a
separate message from the locks_server acknowledges a surrender request,
and the agent will ignore any lock updates for that lock, which precede
the 'surrendered' message.

* The verification did not deal with 'hierarchical' locks (e.g. table and
object locks). The current implementation treats all locks as part of a
hierarchy, and introduces the notion of an 'indirect' lock. Indirect locks
are only of concern to the locks_server; the agents only need to know that
they are waiting for another agent that holds the lock - whether the lock
is held directly or indirectly is of no concern. To wit, if an agent A takes
a lock on [a, b], and it is granted, it will indirectly lock [a]. If another
agent B tries to lock [a, b, c] while A holds [a, b], the locks_server will
infer that A also indirectly locks [a, b, c]. This indirect lock is created
as-needed (if no one tries to lock [a, b, c], no indirect lock needs to be
created - indeed must not, as the domain of potential children is unbounded.

* Multi-node locks are not considered below. The current implementation treats
each lock on each node as an individual lock. For example, locking [a] on
nodes [N1, N2] will result in two lock requests, {[a], N1} and {[a], N2}.
The agent keeps track of which locks belonged to the same request, viz.
we may consider the lock granted only when we have a lock on [a] on all,
or a majority, of the requested nodes. If some of the requested nodes are
not available, the lock may still be considered held if a majority of them
can be claimed. The exact semantics are specified when requesting the lock.
Note also that this introduces the risk of deadlock within a single lock:
If agent A and B both try to claim [a] on [N1, N2], and A gets the lock on N1,
while B gets the lock on N2, this will be a deadlock. However, if the lock
is still considered pending by the agent which needs to surrender, the client
will not notice this, and the conflict will be resolved automatically.

* Even with the above differences, the dependency analysis and deadlock-
related decision-making is the same as in Arts's version - only modified
to accomodate the slightly different data representation.

### Description of the algorithm and some implementation issues. ###

Basically the algorithm consists of two entities, viz. one for the
object and one for the client. These entities are best seen as interfaces
that arrange for the client to get access to an object, and ensure
that the object is only accessed by clients which are allowed to do
so.

The algorithm implementing the object interface should provide read
and write functionality, but also guarantee that such read or write is
guaranteed to be done by a client that has the right to do so
(i.e. holds the lock).

The algorithm implementing the client interface keeps track of the
objects that need to be locked for a read and/or write operation.
The client interface is actively asking the objects for read/write
permission (a lock) and waits for the results supplied by the objects.
The information is gathered, combined with consecutive information
provided by the objects and competing clients and action is taken upon
the received information. The client interface can either conclude that
it has obtained read/write access to all required objects, or, by absence
of all information, wait for more information and/or send information to
competing clients.

In the following we describe the algorithms for both entities in more
detail and motivate the different design decisions. The design seems
optimal within the setting we have in mind, however, other settings
are plausible candidates for practical applications as well.
Therefore, we first describe the setting we work in and sketch alternative
design possibilities for situations that we think are of additional
practical interest.

### The Setting ###

We assume computers to run in a distributed environment, connected with a
communication network of which the speed is slow compared to the computation
speed of the individual computers in the net.

Clients and objects have a unique reference and a total order exists among
these references. The uniqueness of the reference is guaranteed. However,
the set of possible references is finite.

No strong assumption is therefore made about the relationship between
creating a client or object and the assigned reference. As a heuristic we
assume a client that is created later in time has a larger reference than
the earlier created clients (w.r.t. the order on references). This heuristic
is, though, violated now and then and therefore we do not consider it a rule.

We assume enough memory available to store all information about the
relationship between locks and objects of interest to us. Moreover, we assume
the existence of a sequence of numbers as long as we need to attach version
numbers to messages, such that within the lifetime of an object, we do not
run out of numbers.

### The Object Algorithm ###

The algorithm implementing the interface to the object stores requests from
clients for access to certain locks. The requests are stored in a waiting
queue in order of arrival. The first element of the queue is considered to
have granted access to the object. Upon arrival of a request from a client,
it is put at the end of the queue and all clients in the queue are notified
about the new situation of the queue.

Clients are also allowed to cancel their request, in which case they are just
removed from the queue. Again, all clients remaining in the queue are
notified. A cancel request always arrives when a client processes is
somehow killed or unreachable.

The client that holds the lock on the object, i.e., is the first in the
waiting queue may request to surrender, i.e., it is no longer the first in
the queue. Upon a surrender request, the requesting client is placed last
in the queue and all clients are again notified about the new order in
the queue.

Placing a surrendering client at the end of the queue is the only safe
general way of implementing a surrender action. It is not safe to just swap
with the client directly behind it. Moreover, the object cannot oversee what
other place would be safe to surrender to. In some cases the client, however,
could obtain so much information that it would be able to compute  a safe
place in the queue to surrender to.

Nevertheless, having the client ask to surrender to a certain place is
in general unsafe.

Every notification to the clients of the updated state of the queue is
supplied with a version number. The version number is increased after
every change in the queue. Moreover, the notifications are also carrying
the identity of the client that induced the notification to be sent, i.e.
the client that requested access, canceled or surrendered. Both are necessary
items for the client in order to have a safe execution.

The algorithm also implements a read and write operation on the object,
where the read and write are only allowed whenever the requesting client
holds the lock for the object (i.e., is first in the queue).

In case the references assigned to clients reflect their creation, viz.
the reference gets bigger the later a client is created (e.g. absolute
time as reference), the above object can be optimized by having the tail
of the waiting queue (i.e. all elements except for the first one) sorted
with respect to the total order on the references. However, this is unsafe
in case of a finite set of references. One can work around this unsafe
situation in case the set of references is big enough and timeout primitives
are used to deal with starvation.

This alternative implementation method is not optimally efficient in general,
but may be more efficient in cases were negotiation about objects is
relatively fast compared with the time it takes to run out of references.
Clients that do not get served in time, should however restart their
requests, which may take severe overhead for some individual clients,
whereas the other clients are served much faster.

### The Client Algorithm ###

The interface for the client gets activated whenever a client needs some
objects to perform an operation on. Access to the objects is requested
by the client interface and after all objects have been locked, the client
is notified that the operation may take place. After performing the operation,
the client interface is addressed by the client and the interface releases
the locks on all the objects it has acquired for the client.

The communication between client interface and object interface is
already described in the object part. A lock can be requested, surrendered
or a request can be canceled.

The client interface is constantly updated when the queue of an object that
it has requested changes. This information is stored by the client interface,
and as such, the client interface detects easily when all objects are
assigned to it.

The queue information that the object provides has a version number and the
identity of a client attached to it. The client keeps track of this version
information and whenever information is received with a version number
smaller than a version number of earlier received information, this
information is ignored. It is unsafe to disregard the version information,
since because of delays in the network, information could arrive in the
wrong order and the client could cause a deadlock by acting wrongly on the
old information.

The attached client information in the deadlock is used by the client as an
acknowledgment on a surrender request. Whenever the client sends a surrender
request, it should ignore all information coming from the surrendered object,
until it carries its own client identity. The latter is necessary to ensure
a safe operation in case the client surrenders and outdated information
arrives stating that the client just received access again.

Whenever the information about the queues of the objects is such that not
(yet) all the objects are assigned, the client interface computes the
so-called wait-for graph; the graph expressing which client waits for which
other client to get access to an object.

If this graph contains a cycle, then a deadlock situation exists.
The client interface checks for cycles in the graph and if such a cycle exists,
it computes which of the clients in this cycle that holds the lock for an
object has the largest reference (since there exists a total order of the
references, this is uniquely defined). If the client interface does not
represent this largest reference itself, it waits for more object
information to come.

If, however, the client interface represents this largest reference, it
sends a surrender message to the object it holds that caused the deadlock
situation. Note that it is important to select this particular client among
the ones that indeed hold a lock.

In order to be able to surrender only one object, one needs to store
the relation between the object and the clients waiting for that particular
object. It should be clear which object is waited for in the deadlock
situation, since the client that surrenders may very well hold other
objects, which are not involved in a deadlock situation.

In case of only little memory available, one might choose for not storing
all information but surrender all objects the client holds. This is a safe
strategy, but inefficient.

Instead of having the client with largest reference surrendering, one could
also demand the smallest client to surrender. In our setting, the largest is
more optimal, since the reference contains information about the time the
client asked for the object. The smaller the reference, the longer the client
is waiting for the object.

In special circumstances a client interface could compute that surrendering
to the end of the queue is not the most efficient. However, such a
computation needs extra information from the application that the algorithm
is used for. For example, if it is known that every client is at most
claiming three objects at a time, this information could very well be used
to compute more optimal surrendering positions.

When a client interface does not encounter a cycle in the graph, it
reports the graph information to other clients. Note that all clients
only have part of the information of the "global" wait-for graph. By
spreading the information to other clients, one ensures in the end that
at least one client obtains the "global" wait-for graph as its local graph.
Here one has several possibilities in spreading the information around.

The efficiency and optimality of the strategy of which client is sending
this information to which other client(s) depends on the way the objects
and clients relate (how many clients are demanding the same object, how
many objects are demanded by the clients, etc.).

The most naive way of spreading the information is that a client sends its
wait-for graph to all clients that occur in this graph. Optimally a client
only sends part of the graph to another client, if that client does not have
that information and is not getting it from another client.

The latter can partly be achieved by clients only sending information to
clients that have a smaller reference, or alternatively, only to those that
have a bigger reference.

Another strategy which reduces the number of messages sent, and therefore
is efficient when computation is much cheaper than sending (as in our setting)
is that clients only send to clients that it is waiting for and only send
the information of the clients that wait for it.

Analogous to this, the client could send the clients that wait for it,
the information of the clients it is waiting for.

Any of the above spreading strategies can even be improved by computing
which information the client one wants to send something to should already
have, such that no superfluous information is sent if avoidable.

The wait-for graph is easily implemented by using standard data structures
and computing cycles in such a graph is a well known operation for which
several algorithms exist in literature.

Specific for the client interface algorithm is that nodes in the graph
contain both client identity, the object that the client is locking,and
whether the client has obtained the lock to this object. An arc is drawn
from one node to another if the client in this triple is waiting for the
client in the other node. Note here that not all clients need be presented
in the graph, but only those that hold a lock. However, the relation that
expresses a client waiting for another client takes all known clients into
account.

Whenever a cycle is detected, from the nodes on this cycle the client
with largest reference surrenders the object it locks.

## Modules ##

<table width="100%" border="0" summary="list of modules">
<tr><td><a href="https://github.com/uwiger/locks/blob/master/doc/locks.md" class="module">locks</a></td></tr>
<tr><td><a href="https://github.com/uwiger/locks/blob/master/doc/locks_agent.md" class="module">locks_agent</a></td></tr>
<tr><td><a href="https://github.com/uwiger/locks/blob/master/doc/locks_leader.md" class="module">locks_leader</a></td></tr>
<tr><td><a href="https://github.com/uwiger/locks/blob/master/doc/locks_server.md" class="module">locks_server</a></td></tr>
<tr><td><a href="https://github.com/uwiger/locks/blob/master/doc/locks_ttb.md" class="module">locks_ttb</a></td></tr></table>