Information Technology Reference
In-Depth Information
3.3
The Real Deal with Join
The use of
BasicSyncJoin
is insucient for file replication. There are two funda-
mental flaws and limitations: First, it allows installing updates that conflict with
file system semantics: it may introduce orphaned files without parent directories,
mark non-empty directories as tombstones, create multiple files in the same di-
rectory with the same name, and introduce cyclic directory structures. Second,
BasicSyncJoin
processes all updates in one atomic step. This is unrealistic in the
presence of network outages and continuous file system activity. DFS-R realizes
non-atomic joins by committing only versions from the processed records on
disconnects (instead of all of
vv
2
). It also pipe-lines multiple joins should the
sending machine create new updates while (large) files from previous updates
are still being downloaded. A consequence of this relaxation is that condition
(5) is only a necessary, but not sucient condition for conflict detection. Invari-
ant (4) does not hold either, but this is insignificant, as we introduced sets in
the range of version vectors to deal with partial synchronization. Fig.4. illus-
trates the additional refinements one needs to add to
BasicSyncJoin
in order to
address file system semantics. We have limited the iteration of database records
to
vv
2
\
vv
1
to reflect invariant (2), which still holds. We abstain from illustrating
the non-atomic, pipe-lined version.
The refined
SyncJoin
mentions auxiliary functions
conflict-winner
,
purge-losers
,
and
revert-update
. The definition and analysis of these is the subject of Section 5,
but here, we will summarize some of their requirements.
SyncJoin
(
nw, m
1
,m
2
)
let
(
vv
1
,rs
1
,in
1
)=
nw
[
m
1
]
let
(
vv
2
,rs
2
,in
2
)=
nw
[
m
2
]
assume
m
2
∈ in
1
for each
[
uid → r
]
∈ rs
2
where
r.gvsn ∈ vv
2
\ vv
1
:
if
uid ∈ rs
1
∨ rs
1
[
uid
]
<r
then
if
conflict-winner
(
m
1
,r
)
then
purge-losers
(
m
1
,r
)
rs
1
[
uid
]:=
r
else
revert-update
(
m
1
,r
)
vv
1
:=
vv
1
∪ vv
2
Fig. 4.
Synchronized join
Non-interference.
It is trivial to realize a convergent, consistent file replication
system that just deletes all files. So, obviously, we would like to ensure that
DFS-R does not touch the file system on its own. Requiring that DFS-R not
delete or move around any files is too restrictive, because a system that must
automatically resolve conflicts will have to handle creation of name conflicting
files and directories.
Search WWH ::
Custom Search