This is an automated email from the git hooks/post-receive script. It was
generated because a ref change was pushed to the repository containing
the project "".
The branch, master has been updated
via f94ef3623502f4cf3ca7d2dcb08ef870c2b47895 (commit)
from 2849491c1852b1f8ccaaabb2edfb11fa6a0032f8 (commit)
Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.
- Log -----------------------------------------------------------------
commit f94ef3623502f4cf3ca7d2dcb08ef870c2b47895
Author: Phil Carns <carns(a)mcs.anl.gov>
Date: Mon Jul 30 14:12:52 2012 -0400
move status details to appendix
-----------------------------------------------------------------------
Summary of changes:
.../prototype-2012-07/prototype-2012-07.txt | 351 ++++++++++----------
1 files changed, 176 insertions(+), 175 deletions(-)
Diff of changes:
diff --git a/code/doc/resilience/prototype-2012-07/prototype-2012-07.txt b/code/doc/resilience/prototype-2012-07/prototype-2012-07.txt
index 5f26298..ea37e58 100644
--- a/code/doc/resilience/prototype-2012-07/prototype-2012-07.txt
+++ b/code/doc/resilience/prototype-2012-07/prototype-2012-07.txt
@@ -49,179 +49,6 @@ I/O-intensive application workloads while simulated failures are injected into
the storage system. The range of failures that can be handled properly at
this time include transient network failures, network link failures, storage
device faults, and server failures.
-
-The following subsections describe the current status of each major
-component related to fault tolerance in the Triton prototype.
-
-=== Object placement algorithm (COMPLETE)
-
-The object placement algorithm is the algorithm used by both clients and
-servers in Triton to locate specific objects in the system (both to access
-existing objects and to create new objects).
-
-[[fig-placement]]
-.Object placement example
-image::figs/triton-layout.png[]
-
-<<fig-placement>> shows an example of how objects are mapped to servers
-in Triton. In this context, the address space for all objects can be
-thought of as a ring, with the value of the OID indicating a position
-on the ring. The set of available servers can be placed on this ring
-in the same manner. In order to map an object with N-way replication
-to N servers, you simply choose the N servers that are closest to the
-object ID on this virtual ring of IDs.
-
-Servers are always considered to be authoritative when making placement
-decisions because they actively maintain an up-to-date view of the overall
-storage system status (see <<sec-fault-detect>>). Clients retrieve a
-snapshot of the system state when they first contact the storage system, and
-will continue to use this snapshot until they receive an indication of a
-server fault or receive a response from a server indicating that the client
-made a faulty placement calculation. Clients automatically respond to these
-conditions by contacting previously known servers in turn until receiving a
-new snapshot of the system state. The client then re-calculates the
-placement for the storage operation in question and retries the operation.
-Using this mechanism, clients are able to transparently adapt their
-placement decisions in response to server failures.
-
-=== Replication protocol (COMPLETE)
-
-Triton uses a primary-copy replication protocol, in which clients write all
-data to the authoritative master server for a given object, and that server
-forwards data to appropriate replicas. The long term goal is to make the
-replication semantics tunable to reflect the needs of the application. In
-the current prototype, however, all data is forwarded immediately, and a
-write operation is not considered to be complete from the client's point of
-view until it has been made durable on all servers.
-
-[[fig-rep2]]
-.Triton replication with update numbers
-image::figs/replication2.png[]
-
-<<fig-rep2>> outlines the default replication protocol used in Triton. All writes are performed at the primary server for a given
-object. As each write request for an object arrives, the master server
-assigns a unique, increasing "update number" to each write operation.
-It then stores the data locally while simultaneously forwarding the data
-and the update number to a replica. An arbitrary number of replicas
-may be chained together in sequence, with each applying the data locally
-while simultaneously forwarding to the next replica. This strategy allows
-any number of concurrent writes to be applied concurrently to the same
-object while still achieving consistent results on all replicas. This
-mechanism can be used to achieve POSIX read/write consistency for replicated
-storage operations.
-
-=== Transient network failure handling (COMPLETE)
-
-All network storage operations are automatically retried in Triton. The
-decision of when to retry and how often to retry is governed by a
-centralized policy component on each client or server (see
-<<sec-traffic-cop>>). In addition, the network protocol assigns a unique
-identifier (known as the Non-Idempotent Identifier, or NIID) to each
-non-idempotent storage operation. A non-idempotent storage operation is any
-operation that only produces a valid result exactly once. For example, if
-you attempt to create the same object twice, then the second attempt should
-produce an error indicating that the object already exists. These
-non-idempotent (NI) operations are problematic for generic network retry policies,
-because they may produce erroneous error conditions if the client is unable
-to detect if the initial attempt succeeded or not. The NIID mechanism
-combats this problem by storing the unique identifier for the operation
-persistently on the server side, so that identical retries can be
-distinguished from unique operations and handled properly by the server.
-This is a similar technique to RPC response caching in NFS, except that the
-request identifiers are stored persistently and replicated in order to
-continue safe operation in failover scenarios and highly concurrent
-workloads.
-
-=== Server fault detection and state propagation (PLACEHOLDER)
-[[sec-fault-detect]]
-
-The System State component of Triton is a server-side construct that serves
-two roles: detecting peer server faults and maintaining a list of available
-servers in the system. We intende to simulate and prototype the use of
-epidemic protocols in this role, but this work is not complete at this time.
-Instead we are using a placeholder component in order to test the remainder
-of the system in the absense of an epidemic protocol implementation.
-The placeholder does not actively detect failures, but
-it does propagate explicit state changes to all servers in the system.
-This allows for fault conditions to be injected on one server and
-automatically propagated for fault handling purposes to all other servers in
-the system. The API is complete and uses the same semantics that we would
-expect from an epidemic-based fault detection system.
-
-=== Policy engine (PROTOTYPE)
-[[sec-traffic-cop]]
-
-Triton uses a centralized component on each client and each server, known as
-the Traffic Cop, to unified all failure policy decisions. It tracks all in
-progress operations and makes decisions including:
-
-* how long to wait before timing out operations
-* when to retry operations
-* when to re-calculate placement decisions
-* when to refresh client state information
-* whether incoming server request should be processed or stalled
-
-The API for this functionality is complete and has been thoroughly tested.
-However, the Traffic Cop prototype only makes simple, static policy
-decisions at this time.
-
-=== Server object recovery (COMPLETE)
-[[sec-recovery]]
-
-Once a server has been made aware of a fault (see sections
-<<sec-fault-detect>> and <<sec-traffic-cop>>), it completes the current
-operations that are in flight, stalls incoming operations, and initiates a
-Recovery procedure. The purpose of recovery is to identify objects that
-have been affected by a fault and create "stub" objects to mark the location
-of new replicas for those objects. No object data is transferred. The
-purpose of the recovery is simply to assess the system and insure that all
-metadata is consistent with the placement algorithm. The recovery algorithm
-consists of contacting peer servers, and requesting a list of new objects
-that a given server should create stubs for. In order to service this
-request, peer servers enumerate all potentially affected objects and consult
-the placement algorithm to determine if a new replica is required for the
-object in question. This mechanism is complete and has been tested for a
-variety of failure conditions. We intend to improve its performance in the
-future, however, through a series of local storage and metadata storage
-optimizations.
-
-=== Server object rebuild (INCOMPLETE)
-
-The rebuild procedure occurs after recovery and after servers have resumed
-full operation. Rebuild is the mechanism by which object data is
-transferred to the stub objects created in the recovery phase (see
-<<sec-recovery>>), therefore
-regaining full redundancy for the replicated object. Until the rebuild is
-complete, the objects affected by a failure are in a degraded mode.
-
-The rebuild functionality has not been implemented at this time.
-This means that the Triton storage system can only continue operating
-correctly until N-1 storage faults, where N is the replication factor
-of the objects stored on the system. Once N faults have been reached,
-there is a risk that objects may have been lost in their entirety due
-to the fact that data has not been re-replicated since the first fault.
-
-=== Fault injection (COMPLETE)
-
-In order to test the validity of the various Triton fault tolerance
-mechanisms, it is important to be able to introduce failure conditions in a
-controlled manner. Triton provides a number fault injection primitives:
-
-* Network fault injection: Triton can inject individual faults or an
- ongoing percentage of network faults by using a stackable fault-injection
- module atop the Triton network transport. This fault-injection module can
- silently discard message, producing either an immediate error code or a
- timeout, without perturbing the underlying transport.
-* Disk fault injection: The local storage abstraction in Triton has similar
- functionality to the network layer, in that it can introduce arbitrary
- failures without perturbing the underlying storage devices. The error
- conditions in this case produce immediate errors from local storage
- operation.
-* System state injection: The status of a server can be modified at any
- point to indicate a failure condition, independent of the network or
- storage device status. This status change will be automatically
- propagated to othe servers in the system.
-
== Benchmark
=== Introduction
@@ -410,7 +237,181 @@ image::figs/2x.pdf[]
image::figs/3x.pdf[]
-== Analysis
+== Conclusions
+
+[appendix]
+== Appendix: status of select components
+
+This appendix describes the current status of each major
+component related to fault tolerance in the Triton prototype.
+
+=== Object placement algorithm (COMPLETE)
+
+The object placement algorithm is the algorithm used by both clients and
+servers in Triton to locate specific objects in the system (both to access
+existing objects and to create new objects).
+
+[[fig-placement]]
+.Object placement example
+image::figs/triton-layout.png[]
+
+<<fig-placement>> shows an example of how objects are mapped to servers
+in Triton. In this context, the address space for all objects can be
+thought of as a ring, with the value of the OID indicating a position
+on the ring. The set of available servers can be placed on this ring
+in the same manner. In order to map an object with N-way replication
+to N servers, you simply choose the N servers that are closest to the
+object ID on this virtual ring of IDs.
+
+Servers are always considered to be authoritative when making placement
+decisions because they actively maintain an up-to-date view of the overall
+storage system status (see <<sec-fault-detect>>). Clients retrieve a
+snapshot of the system state when they first contact the storage system, and
+will continue to use this snapshot until they receive an indication of a
+server fault or receive a response from a server indicating that the client
+made a faulty placement calculation. Clients automatically respond to these
+conditions by contacting previously known servers in turn until receiving a
+new snapshot of the system state. The client then re-calculates the
+placement for the storage operation in question and retries the operation.
+Using this mechanism, clients are able to transparently adapt their
+placement decisions in response to server failures.
+
+=== Replication protocol (COMPLETE)
+
+Triton uses a primary-copy replication protocol, in which clients write all
+data to the authoritative master server for a given object, and that server
+forwards data to appropriate replicas. The long term goal is to make the
+replication semantics tunable to reflect the needs of the application. In
+the current prototype, however, all data is forwarded immediately, and a
+write operation is not considered to be complete from the client's point of
+view until it has been made durable on all servers.
+
+[[fig-rep2]]
+.Triton replication with update numbers
+image::figs/replication2.png[]
+
+<<fig-rep2>> outlines the default replication protocol used in Triton. All writes are performed at the primary server for a given
+object. As each write request for an object arrives, the master server
+assigns a unique, increasing "update number" to each write operation.
+It then stores the data locally while simultaneously forwarding the data
+and the update number to a replica. An arbitrary number of replicas
+may be chained together in sequence, with each applying the data locally
+while simultaneously forwarding to the next replica. This strategy allows
+any number of concurrent writes to be applied concurrently to the same
+object while still achieving consistent results on all replicas. This
+mechanism can be used to achieve POSIX read/write consistency for replicated
+storage operations.
+
+=== Transient network failure handling (COMPLETE)
+
+All network storage operations are automatically retried in Triton. The
+decision of when to retry and how often to retry is governed by a
+centralized policy component on each client or server (see
+<<sec-traffic-cop>>). In addition, the network protocol assigns a unique
+identifier (known as the Non-Idempotent Identifier, or NIID) to each
+non-idempotent storage operation. A non-idempotent storage operation is any
+operation that only produces a valid result exactly once. For example, if
+you attempt to create the same object twice, then the second attempt should
+produce an error indicating that the object already exists. These
+non-idempotent (NI) operations are problematic for generic network retry policies,
+because they may produce erroneous error conditions if the client is unable
+to detect if the initial attempt succeeded or not. The NIID mechanism
+combats this problem by storing the unique identifier for the operation
+persistently on the server side, so that identical retries can be
+distinguished from unique operations and handled properly by the server.
+This is a similar technique to RPC response caching in NFS, except that the
+request identifiers are stored persistently and replicated in order to
+continue safe operation in failover scenarios and highly concurrent
+workloads.
+
+=== Server fault detection and state propagation (PLACEHOLDER)
+[[sec-fault-detect]]
+
+The System State component of Triton is a server-side construct that serves
+two roles: detecting peer server faults and maintaining a list of available
+servers in the system. We intende to simulate and prototype the use of
+epidemic protocols in this role, but this work is not complete at this time.
+Instead we are using a placeholder component in order to test the remainder
+of the system in the absense of an epidemic protocol implementation.
+The placeholder does not actively detect failures, but
+it does propagate explicit state changes to all servers in the system.
+This allows for fault conditions to be injected on one server and
+automatically propagated for fault handling purposes to all other servers in
+the system. The API is complete and uses the same semantics that we would
+expect from an epidemic-based fault detection system.
+
+=== Policy engine (PROTOTYPE)
+[[sec-traffic-cop]]
+
+Triton uses a centralized component on each client and each server, known as
+the Traffic Cop, to unified all failure policy decisions. It tracks all in
+progress operations and makes decisions including:
+
+* how long to wait before timing out operations
+* when to retry operations
+* when to re-calculate placement decisions
+* when to refresh client state information
+* whether incoming server request should be processed or stalled
+
+The API for this functionality is complete and has been thoroughly tested.
+However, the Traffic Cop prototype only makes simple, static policy
+decisions at this time.
+
+=== Server object recovery (COMPLETE)
+[[sec-recovery]]
+
+Once a server has been made aware of a fault (see sections
+<<sec-fault-detect>> and <<sec-traffic-cop>>), it completes the current
+operations that are in flight, stalls incoming operations, and initiates a
+Recovery procedure. The purpose of recovery is to identify objects that
+have been affected by a fault and create "stub" objects to mark the location
+of new replicas for those objects. No object data is transferred. The
+purpose of the recovery is simply to assess the system and insure that all
+metadata is consistent with the placement algorithm. The recovery algorithm
+consists of contacting peer servers, and requesting a list of new objects
+that a given server should create stubs for. In order to service this
+request, peer servers enumerate all potentially affected objects and consult
+the placement algorithm to determine if a new replica is required for the
+object in question. This mechanism is complete and has been tested for a
+variety of failure conditions. We intend to improve its performance in the
+future, however, through a series of local storage and metadata storage
+optimizations.
+
+=== Server object rebuild (INCOMPLETE)
+
+The rebuild procedure occurs after recovery and after servers have resumed
+full operation. Rebuild is the mechanism by which object data is
+transferred to the stub objects created in the recovery phase (see
+<<sec-recovery>>), therefore
+regaining full redundancy for the replicated object. Until the rebuild is
+complete, the objects affected by a failure are in a degraded mode.
+
+The rebuild functionality has not been implemented at this time.
+This means that the Triton storage system can only continue operating
+correctly until N-1 storage faults, where N is the replication factor
+of the objects stored on the system. Once N faults have been reached,
+there is a risk that objects may have been lost in their entirety due
+to the fact that data has not been re-replicated since the first fault.
+
+=== Fault injection (COMPLETE)
+
+In order to test the validity of the various Triton fault tolerance
+mechanisms, it is important to be able to introduce failure conditions in a
+controlled manner. Triton provides a number fault injection primitives:
+
+* Network fault injection: Triton can inject individual faults or an
+ ongoing percentage of network faults by using a stackable fault-injection
+ module atop the Triton network transport. This fault-injection module can
+ silently discard message, producing either an immediate error code or a
+ timeout, without perturbing the underlying transport.
+* Disk fault injection: The local storage abstraction in Triton has similar
+ functionality to the network layer, in that it can introduce arbitrary
+ failures without perturbing the underlying storage devices. The error
+ conditions in this case produce immediate errors from local storage
+ operation.
+* System state injection: The status of a server can be modified at any
+ point to indicate a failure condition, independent of the network or
+ storage device status. This status change will be automatically
+ propagated to othe servers in the system.
-=== Introduction
hooks/post-receive
--
