Data Synchronization A Complete Theoretical Solution for Filesystems_2

2025-04-27 0 0 367.24KB 22 页 10玖币

侵权投诉

Citation: Csirmaz, E. P; Csirmaz, L

Data Synchronization: A Complete

Theoretical Solution for Filesystems.

2022,1, 0.

Article

Data Synchronization: A Complete Theoretical Solution for

Filesystems

Elod P. Csirmaz1,∗and Laszlo Csirmaz2

1elod@epcsirmaz.com

2Rényi Institute, Budapest, and UTIA, Prague; csirmaz@renyi.hu

*Correspondence: elod@epcsirmaz.com

Abstract:

Data reconciliation in general, and ﬁlesystem synchronization in particular, lacks rigorous

theoretical foundation. This paper presents, for the ﬁrst time, a complete analysis of synchronization for

two replicas of a theoretical ﬁlesystem. Synchronization has two main stages: identifying the conﬂicts, and

resolving them. All existing (both theoretical and practical) synchronizers are operation-based: they deﬁne,

using some rationale or heuristics, how conﬂicts are to be resolved without considering the effect of the

resolution on subsequent conﬂicts. Instead, our approach is declaration-based: we deﬁne what constitutes

the resolution of all conﬂicts, and for each possible scenario we prove the existence of sequences of

operations/commands which convert the replicas into a common synchronized state. These sequences

consist of operations rolling back some local changes, followed by operations performed on the other

replica. The set of rolled-back operations provides the user with clear and intuitive information on the

proposed changes, so she can easily decide whether to accept them or ask for other alternatives. All

possible synchronized states are described by specifying a set of conﬂicts, a partial order on the conﬂicts

describing the order in which they need to be resolved, as well as the effect of each decision on subsequent

conﬂicts. Using this classiﬁcation, the outcomes of different conﬂict resolution policies can be investigated

easily.

Keywords: data synchronization; conﬂict resolution, ﬁlesystem theory

MSC: 08A02, 08A70, 68M07, 68P05

1. Introduction and related work

This work is a comprehensive treatment of ﬁlesystem synchronization and conﬂict res-

olution on a simple but powerful theoretical model of ﬁlesystems. Synchronizing diverged

copies of some data stored on a variety of devices and locations is an important and ubiquitous

task. The last two decades have seen tremendous advancement, both theoretical and practi-

cal, in the closely related ﬁelds of distributed data storage [

] and group editors [

This progress has been based on, and has expanded signiﬁcantly, two competing theoretical

frameworks: Operational Transformation (OT) and Conﬂict-free Replicated Data Types (CRDT).

OT appeared in the seminal work [

] and was reﬁned later in [

]. The general idea is that

operations are enriched with the context in which they were generated. Before applying them,

they are transformed depending on the context of their origin and the context where they are

to be applied. Main applications are collaborative editors, the most notable example being

Google Docs [

]. The core concept of CRDT is commutativity, see [

]. Basic data types

with special operators are devised so that executing the operators in different orders yield the

same results. Examples are counters or sets with add and delete operators. The basic types are

used as building blocks in more complex applications such as collaborative editors [

], the

commercial product Riak [8], and others.

Data Synchronization: A Complete Theoretical Solution for Filesystems

arXiv:2210.04565v2 [cs.IT] 12 Nov 2022

Data Synchronization: A Complete Theoretical Solution for Filesystems 2 of 22

Both OT and CRDT have been successfully applied in a variety of synchronization tasks

[

]. Filesystem synchronization, however, ﬁts very poorly into these frameworks, mainly

because it works under a completely different modus operandi: constant, low latency communi-

cation in OT and CRDT versus a single data exchange in ﬁlesystem synchronization; frequent

loose synchronization with eventual convergence requirement versus a single but complete

synchronization; small number of differences versus signiﬁcant structural differences accumu-

lated during an extended time period; and so on. Consequently, for a theoretical investigation

of ﬁlesystem synchronization, we follow a traditional framework instead, described in e.g. [

]

and depicted in Figure 1adapted from [4].

Φ1

Φ2

. . . . . . merged state . . . . . .

. . . . . . replicas . . . . . .

update detector

reconciler

α0

updates

β0

updates

α1

synchronization

β1

synchronization

Figure 1.

Outline of the synchronization process. Identical replicas of the original ﬁlesystem

are

updated (modiﬁed) yielding the divergent replicas

Φ1

and

Φ2

. The reconciler uses the update information

and

extracted by the update detectors, and generates the synchronizing instructions

α1

and

β1

. These

create the identical merged state

when applied to the replicas. The update detectors determine the

update information

and

either by comparing the different states of the replicas (e.g.

Φ1

vs.

), or by

having access to the update instructions α0and β0that were applied to Φ.

Two identical replicas of the original ﬁlesystem

are updated independently, yielding the

divergent replicas

Φ1

and

Φ2

. In the state-based case the update detector receives the original

(

) and the current (

Φ1

Φ2

) states, and generates the update information

(or

) describing

the differences between the original ﬁlesystem and the replica. In the operation-based case the

update decoder has access to the performed operations

α0

(

β0

) only. The reconciler receives the

information provided by the update detectors and generates the synchronizing instructions

α1

and

β1

, respectively. These instructions, applied to the replicas

Φ1

and

Φ2

, create the identical

merged state Ψ.

In order to reach such a common synchronized state, existing theoretical and practical

ﬁlesystem synchronizers, such as [

], apply some conﬂict-resolution strategy.

They identify all (or some) of the conﬂicts, then apply their strategy to the conﬂicts one at

a time. These algorithms are typically ﬁxed and deﬁned by some rationale or heuristics, or

dictated by the underlying technology. In contrast, we deﬁne what comprises a synchronized state.

Intuitively, it is a maximal consistent merger of the replicas, meaning that no further changes

can be applied to the merged state from those that were applied to the replicas during the

update phase. Then we proceed to prove that every such maximal state (and only these states)

can be reached by resolving the conﬂicts in some order.

In the meticulous survey [

] of existing theoretical and practical ﬁlesystem synchronizers

it has been observed that “resolving conﬂicts is an open problem where [. .. ] most academic

works present arbitrary resolution methods that lack a rationale for their decisions” (page i),

and that “a ﬁle system can be affected by more than one conﬂict at once, which has not been

Data Synchronization: A Complete Theoretical Solution for Filesystems 3 of 22

discussed in related academic works” (page 65). By presenting, for the ﬁrst time, a complete

analysis of the synchronization process for two replicas of a theoretical ﬁlesystem model, we

ﬁll these gaps.

1.1. Our contribution

This paper is a complete analysis of the synchronization process of two replicas of a

theoretical ﬁlesystem. Our ﬁlesystem model together with the commands considered – such as

create,rmdir, or edit – are discussed in Secion 3. The changes between the original replica and

the locally updated versions are captured by a special command set as deﬁned in Section 4,

which also deﬁnes algorithms generating this update information.

The important question of which ﬁlesystems can, in general, be considered to be a synchro-

nized state of two divergent replicas is tackled in Section 5. Our deﬁnition captures this notion

in its full generality without prescribing how the synchronized state can be reached. Providing

such a declaration-based deﬁnition of the synchronized state is one of our main contributions.

Section 6presents the generic synchronization algorithm based on conﬂict resolution. By using

different strategies to resolve conﬂicts, any of the synchronized states allowed by our deﬁnition,

and only those, can be the result of the algorithm. Finally, Section 7summarizes the results and

lists open problems and directions for future research.

2. Methodology

Our ﬁlesystem model, deﬁned in Section 3, is arguably simple, but it retains all important

structural properties of real ﬁlesystems. It is this simplicity that allows us to exploit a rich and

intriguing algebraic structure [

] which eventually leads to the claimed theoretical results. In

Section 7we discuss some possible extensions of the ﬁlesystem model.

Depending on the data communicated by the replicas, synchronizers are categorized as

either state-based or operation-based [

]. In state-based synchronization replicas send their

current versions of the ﬁlesystem, or merely the differences (called diff s) between the current

states and the last known synchronized state [

]. Operation-based synchronizers transmit the

complete log (or trace) of all operations performed by the user [

]. The synchronization method

of this paper is reminiscent of operation-based one, but can also be considered, with similar

overhead, to be state-based. A set of virtual ﬁlesystem operations (commands) will be deﬁned

in Section 3. Each of these commands have a clear and intuitive operational meaning, but are

not necessarily available to the end-user. The current state of the ﬁlesystem is described by

a special – called canonical – sequence of virtual commands, which transforms the original

ﬁlesystem to the actual replica. The update detector can generate this canonical sequence from

the operations performed by the user on the replica (operation-based) as well as from the

differences between the original and ﬁnal state (state-based). On Figure 1these sequences

correspond to the information in αand βpassed to the reconciler.

Filesystem synchronization must resolve all conﬂicts between the replicas. Conﬂict resolu-

tion, however, should be “intuitively correct,” i.e. discarding all changes made by both replicas

is not a viable alternative. The majority of commercially or theoretically available synchroniz-

ers do not present a rationale to explain their concrete conﬂict resolution approach [

]. Two

notable exceptions are [

] and [

] which describe high-level consistency philosophies. In

[

] the main principles are 1) no lost update: preserve all updates on all replicas because these

updates are equally valid; and 2) no side effects: such as a merge where objects unexpectedly

disappear. While these principles intuitively make sense, it is easy to see that neither could

possibly be upheld for every conﬂict; even the authors provide counterexamples. In [

] the

relevant consistency requirements are worded as follows:

intention-conﬁned effect: operations applied to the replicas by the synchronizer must be

based on operations generated by the end-user; and

Data Synchronization: A Complete Theoretical Solution for Filesystems 4 of 22

aggressive effect preservation: the effect of compatible operations should be preserved fully;

and the effect of conﬂicting operations should be preserved as much as possible.

These requirements are in fact variations of the OT consistency model, see for example the

notion of intention preservation in [

]. (We note that the other two OT principles – convergence

and causality preservation – do not apply to ﬁlesystem synchronizers.)

In agreement with R1 and R2 we declare what a synchronized state is, rather than present

an algorithm which generates it. Our declaration can be outlined as follows. Suppose that the

two replicas

Φ1

and

Φ2

are represented by the canonical sequences

and

, respectively, that is,

Φ1=αΦ

and

Φ2=βΦ

, where

αΦ

is the result of applying the command sequence

. The

synchronized or merged state Ψis determined by the canonical sequence µas Ψ=µΦsuch that

C0 µis applicable to the original ﬁlesystem Φ,

C1 every command in µcan be found either in α, in β, or in both, and

C2 µ

is maximal, i.e. no canonical sequence adding more commands to

can satisfy both C0

and C1.

Condition C0 is the obvious requirement that the synchronizer must not cause errors. Condition

C1 ensures that the synchronization satisﬁes the intention-conﬁned effect (no surprise changes

in the merged ﬁlesystem) requirement R1 as

should consist only of commands which were

supplied by the replicas. The other consistency requirement R2 is guaranteed by C2 as

maximal, therefore it preserves as much of the intention of the users as possible. Note that this

deﬁnition of a synchronized state is never vacuous. There are only ﬁnitely many sequences

which satisfy C0 and C1 as every command in

comes from either

and no repetitions

are allowed, and there are at least two, namely

and

. Because of this, the empty sequence

(undoing all changes) will not satisfy C2 (assuming one of

and

is not empty), in line with

our requirements.

The declaration-based synchronization is intuitively clear, easy to understand, and does

not use any predetermined conﬂict-resolving policy. An operational characterization is proved

in Theorem 2. The essence of this theorem is that any merged ﬁlesystem

can be generated

from the replica, say Φ1, by

1. rolling back some of the commands in α, followed by (1)

2. applying some commands from the other sequence β,

and vice versa for the other replica. The commands rolled back represent a minimal set whose

removal resolves all conﬂicts. These commands also give users a clear understanding of the

changes the synchronizer wants to perform on their ﬁlesystem. They are also helpful when

some of the rolled-back commands should be introduced again after the merging (doing a redo

of the undo).

Turning to traditional conﬂict-based synchronization, Section 6proves that any declaration-

based merged state, and only those states, can be the result of a conﬂict-based synchronization

algorithm. For each pair of canonical sequences describing the replicas to be synchronized

we deﬁne what the conﬂicting command pairs are. Their resolution uses the winner/loser

paradigm: the winner command is accepted while the loser command is discarded. It turns out

that resolving a conﬂict may automatically resolve some of the subsequent conﬂicts, but no new

conﬂicts are created. Using this result the outcomes of different conﬂict resolving policies can

be investigated easily. In particular, the iterative approach [

] always works, which applies all

non-conﬂicting commands, resolves, in any way, the ﬁrst conﬂict (which might automatically

resolve other existing conﬂicts), and iterates.

Data Synchronization: A Complete Theoretical Solution for Filesystems 5 of 22

3. Deﬁnitions

This section deﬁnes the basic notation which will be used throughout the rest of the paper.

The exposition follows [

] and [

] with some substantial modiﬁcations. Some results from these

papers are included without proof.

3.1. Namespace and ﬁlesystems

Our ﬁlesystem model is arguably simplistic, nevertheless it captures all important aspects

of real-word implementations. In spirit, it is a mixture of identity- and path-based models

[

]. Objects are stored in nodes, which are uniquely identiﬁed by ﬁxed and predetermined

paths. The set of available nodes is ﬁxed in advance, and no path operations are considered.

Filesystems are required to have the tree-property at all times: in a given ﬁlesystem along any

branch starting from any of the root nodes, there must be zero or more directories, zero or one

ﬁle, followed by empty nodes. Our model does not support links (but see Section 7.4), thus the

namespace – the set of available nodes or paths – forms a collection of rooted trees. Filesystems

are deﬁned over and populate this ﬁxed namespace.

Formally, the namespace is a set

endowed with the partial function

↑:N→N

returning

the parent of every non-root node (it is not deﬁned on roots). If

n=↑m

then

is the parent of

, and

is a child of

. For two nodes

m∈N

we say that

is above

, or

is an ancestor of

, and write

n≺m

n=↑i(m)

for some

i≥

1. As usual,

n4m

means

n≺m

n=m

. As

the parent function induces a tree-like structure,

is a partial order. Two nodes

m∈N

are

comparable if either n4mor m4n, and they are uncomparable or independent otherwise.

Aﬁlesystem

populates the nodes of the namespace with values. The value stored at

node

n∈N

is denoted by

Φ(n)

. This value can be

indicating that the node is empty (no

content, not to be confused with the empty ﬁle); can be

indicating that the node is a directory;

otherwise it is a ﬁle storing the complete content (which could happen to be “no content”). We

use

and

to denote the type of the content corresponding to these possibilities. While

there is only one value of type

and one value of type

(see Section 7.3 for a discussion on

lifting this limitation), there are many different ﬁle values of type

representing different ﬁle

contents.

3.2. Internal ﬁlesystem commands

The synchronizer operates using a specially designed and highly symmetrical set of

internal ﬁlesystem commands. They each modify the ﬁlesystem at a single node only, and contain

additional information usually not thought of as part of a command which allows them to be

inverted, and makes them amenable to algebraic manipulation. Inventing such a command set

was one of the main contributions of [3].

The commands basically implement creating and deleting ﬁles and directories. Modifying

a part of a ﬁle only is not available as a command; whenever a ﬁle is modiﬁed, the new content

must be supplied in its entirety. Still, commands issued by a real-life user or system can be

easily transformed into the internal commands; for example, the move or rename operation can

be modeled as a sequence of a delete and a create.

The set of the internal commands is denoted by

Ω

, and each command

σ∈Ω

has three

components, written as σ=hn,x,yi, as follows:

•n∈Nis the node on which the command acts,

•xis the content at node nbefore the command is executed (precondition), and

•yis the content at node nafter the command was executed.

Thus rmdir

(n)

corresponds to the internal command

, which replaces the directory

value at

by the empty value. The command

creates a directory at

, but only if the

node

has no content, i.e., there is no directory or ﬁle at

(a usual requirement for mkdir

(n)

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

Citation:Csirmaz,E.P;Csirmaz,LDataSynchronization:ACompleteTheoreticalSolutionforFilesystems.2022,1,0.ArticleDataSynchronization:ACompleteTheoreticalSolutionforFilesystemsElodP.Csirmaz1,andLaszloCsirmaz21elod@epcsirmaz.com2RényiInstitute,Budapest,andUTIA,Prague;csirmaz@renyi.hu*Correspondence:elod@...

收起<<

Data Synchronization A Complete Theoretical Solution for Filesystems_2.pdf

共22页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Data Synchronization A Complete Theoretical Solution for Filesystems_2

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: