[Assorted-commits] SF.net SVN: assorted:[1334] ydb/trunk/README

[<yan...@us...>]

Revision: 1334
          http://assorted.svn.sourceforge.net/assorted/?rev=1334&view=rev
Author:   yangzhang
Date:     2009-03-26 07:54:36 +0000 (Thu, 26 Mar 2009)

Log Message:
-----------
more notes

Modified Paths:
--------------
    ydb/trunk/README

Modified: ydb/trunk/README
===================================================================
--- ydb/trunk/README	2009-03-24 09:26:20 UTC (rev 1333)
+++ ydb/trunk/README	2009-03-26 07:54:36 UTC (rev 1334)
@@ -46,9 +46,9 @@
 [Protocol Buffers]: http://code.google.com/p/protobuf/
 [State Threads]: http://state-threads.sourceforge.net/
 
-Requirements for tools:
+Requirements for tools (building, deployment, analysis):
 
-- [Assorted Shell Tools] (bash-commons, mssh)
+- [Assorted Shell Tools] (bash-commons, gcc-config, mssh)
 - [Pylab] 0.98.3
 - [Python] 2.5
 
@@ -763,35 +763,59 @@
     - if not, why did we set down this road a year ago?
     - cut our losses?
 
-- TODO PAPER!!!
+Period 3/24/09-3/26/09
 
-- TODO related work
+recovery schemes
 
-    [HST+91] Svein-Olaf Hvasshovd, Tore Saeter, Oystein Torboørnsen, Petter
-    Moe, and Oddvar Risnes. A continously available and highly scalable
-    transaction server: Design experience from the HypRa project. In
-    Proceedings of the 4th International Workshop on High Performance
-    Transaction Systems, September 1991.
+- all approaches assume network replication
+- on recovery, xfer physical log
+  - snapshots can be piecewise, don't have to be transactional
+- on recovery, xfer transaction log
+  - snapshots must be transactional
+- on recovery, xfer full state
+  - normally, do nothing
+  - mark state COW so that it may be incrementally transferred without pausing
+    the ongoing work
+    - worst case: 2x size; try to discard copied state immediately
+  - distribute the xfer among all the standing replicas [IMPLEMENTED]
+  - catch-up: either:
+    - have leader stream txns to joiner; this is better if the txns touch a
+      lot of data, such that it's cheaper to xfer and execute txns than to
+      xfer state [IMPLEMENTED]
+    - re-xfer state; this is better if the states don't touch much data, such
+      that it's cheaper to xfer state than to xfer and execute txns
 
-    Ricardo Jimenez-Peris , M. Patino-Martinez , Gustavo Alonso , Bettina
-    Kemme, Are quorums an alternative for data replication?, ACM Transactions
-    on Database Systems (TODS), v.28 n.3, p.257-294, September 2003
+another logical view
 
-    ~\cite{peris-srds202}R. Jimenez-Peris , M. Patino-Martinez , G. Alonso,
-    An algorithm for non-intrusive, parallel recovery of replicated data and
-    its correctness, Proceedings of the 21st IEEE Symposium on Reliable
-    Distributed Systems (SRDS'02), p.150, October 13-16, 2002
+- normally:
+  - either:
+    - phys log: probably more expensive [implemented]
+    - txn log: cheaper, already serialized
+    - nothing
+  - either:
+    - incremental snapshots: write pages & seqno to disk
+    - full snapshot: useful for replaying txn log
+    - nothing
+- recovery:
+  - either:
+    - xfer (out-of-date) state: small optimizations like COW [simple version
+      implemented]
+    - xfer (tail of) phys log; requires all replicas to do phys ops in same
+      order
+    - xfer (tail of) txn log; requires full snapshot and no multi-partition
+- catch-up:
+  - either:
+    - stream txns from leader and replay them [implemented]
+    - stream phys log from replica and replay them
+    - iteratively re-xfer out-of-date state
+- multi-partition woes
+  - how to solve multi-partition recovery?
+  - should we not be looking at txn based methods at all?
+  - phys logging requires physical ops to be carried out in the same order at
+    all replicas?
 
-    ~\cite{bartoli-dsn01}B. Kemme, A. Bartoli, and O. Babaoglu. Online
-    Reconfiguration in Replicated Databases Based on Group Communication.  In
-    Proc. of the Int. Conf. on Dependable Systems and Networks (DSN 2001),
-    Goteborg, Sweden, June 2001.
+Period 3/26/09-3/
 
-    ~\cite{amir-thesis} Y. Amir. Replication Using Group Communication Over a
-    Dynamic Network. PhD thesis, Institute of Computer Science, The Hebrew
-    University of Jerusalem, Israel. Also available at
-    http://www.dsn.jhu.edu/~yairamir/Yair_phd.pdf, 1995.
-
 - TODO faster disk logging using separate threads
 
 - TODO show aries-write


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.