![](https://csdnimg.cn/release/download_crawler_static/15422745/bg4.jpg)
4
Fig. 1. Data logging method of TRAP design.
The above process represents a typical re-do
recovery process upon an outage that results in data loss
or data damage while earlier data is available in a full
backup or a mirror storage. An undo process is also
possible with the parity log if the newest data is
available by doing the following computation instead of
Equation (2):
A
i
(r)= A
i
(k)
P’
T(k)
P’
T(k-1)
…
P’
T(r+1)
where A
i
(k) represents the latest or newest data of block
A
i
.
Fig. 2. The overall data structure of ST-CDP backup data.
3.2 INSERTING SNAPSHOTS IN PARITY LOGS
The TRAP architecture discussed above provides a
CDP function by means of parity logs resulting from
block write operations. Since every change is kept in the
log, one can go back to any point-in-time. The traditional
snapshot/backup, on the other hand, provides periodic
data images of block level storage. When data recovery
is necessary, these two data protection techniques work
quite differently. TRAP needs to retrieve the parity log
for each data block and perform the parity computation
to recover the data block corresponding to the recovery
time point. As the parity log gets longer, so does the
recovery time because of longer parity computations.
Snapshot, on the other hand, just needs to restore the
corresponding data blocks corresponding to the recovery
time point, though the number of possible recovery
points is limited by the frequency of snapshots
performed.
ST-CDP takes a hybrid approach by inserting
snapshots periodically into the parity logs. Snapshot is a
common technique used in data storages for data
protection and recovery. There are two types of
snapshots: clone/full copy snapshot and copy-on-write
differential snapshot. A clone is a full copy of the
original data on a volume at a point-in-time that can be
created through either software or hardware mirroring.
Copy-On-Write (COW) differential snapshot makes a
copy of the original data before it is overwritten when a
change to the original volume occurs. The block about to
be modified is read and then written to a “differences
area”, which preserves a copy of the data block before it
is overwritten with the change. Using the blocks in the
differences area and unchanged blocks in the original
volume, a volume can be logically constructed that
represents the snapshot copy at the point-in-time in
which it was created. Figure 2 shows the new parity
logging structure. As we insert snapshots in the parity
logs, sub-logs are formed that are separated by periodic
snapshots. At recovery time, only one sub-log that
contains the recovery time point is needed. The recovery
time for each data block is limited by the half of the sub-
log length because parity computation can be done both
ways, redo and undo, as shown in [41]. To minimize log
retrieval time, one can also organize all sub-logs in an
efficient data structure as will be discussed shortly.
There are two important design issues that need to
be considered carefully to implement the ST-CDP
architecture. These issues have to do with whether we
keep CDP data and insert snapshots in parity logs based
on LBA address of data blocks (Space) or based on time
of updates (Time). Each has its pros and cons.
Let us first consider that we keep our CDP data and
insert snapshots based on space. That is, we keep a
parity log for each distinct LBA and insert a snapshot
data block after a certain number of write operations has
been done on the block. In this way, we can ensure that
all parity sub-logs are limited to a predetermined length
and hence control the recovery time. In addition, the
recovery algorithm is relatively simple since each block
has its corresponding CDP data. There are several
disadvantages of space-based design. The first is its
performance impact on applications. We need to keep
track of CDP data corresponding to each data block,
which takes not only more I/O operations on each write
but also more meta data to keep track of CDP data of
each block. For example, to determine when to insert
snapshots, a counter is needed to keep track of the
number of writes for each block. Furthermore, if write
operations are not uniformly distributed across data
blocks, we may end up with long parity logs and more
snapshots for some blocks and short parity logs and
fewer snapshots for others.
Now consider the time option, which keeps CDP
data purely based on time of updates. That is, we do not
distinguish different blocks but insert snapshots based
IEEE TRANSACTIONS ON COMPUTERS
This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication.