Instead, in C-Store, we isolate read-only transactions
using snapshot isolation. Snapshot isolation works by
allowing read-only transactions to access the database as
of some time in the recent past, before which we can
guarantee that there are no uncommitted transactions. For
this reason, when using snapshot isolation, we do not need
to set any locks. We call the most recent time in the past
at which snapshot isolation can run the high water mark
(HWM) and introduce a low-overhead mechanism for
keeping track of its value in our multi-site environment. If
we let read-only transactions set their effective time
arbitrarily, then we would have to support general time
travel, an onerously expensive task. Hence, there is also a
low water mark (LWM) which is the earliest effective
time at which a read-only transaction can run. Update
transactions continue to set read and write locks and obey
strict two-phase locking, as described in Section 6.2.
6.1 Providing Snapshot Isolation
The key problem in snapshot isolation is determining
which of the records in WS and RS should be visible to a
read-only transaction running at effective time ET. To
provide snapshot isolation, we cannot perform updates in
place. Instead, an update is turned into an insert and a
delete. Hence, a record is visible if it was inserted before
ET and deleted after ET. To make this determination
without requiring a large space budget, we use coarse
granularity “epochs,” to be described in Section 6.1.1, as
the unit for timestamps. Hence, we maintain an insertion
vector (IV) for each projection segment in WS, which
contains for each record the epoch in which the record was