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 f73e7e567b8a1a53c364b9ec4288b50ee17521ab (commit) from 1b9e4aadee5c2adba092fec7bed68c66e24577f3 (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 f73e7e567b8a1a53c364b9ec4288b50ee17521ab Author: Phil Carns <[email protected]> Date: Mon Oct 29 10:02:03 2012 -0400 some background on placement algorithms ----------------------------------------------------------------------- Summary of changes: .../simulation-2012-10/simulation-2012-10.txt | 73 ++++++++++++++++---- 1 files changed, 60 insertions(+), 13 deletions(-) Diff of changes: diff --git a/code/doc/resilience/simulation-2012-10/simulation-2012-10.txt b/code/doc/resilience/simulation-2012-10/simulation-2012-10.txt index 0e33647..efccebe 100644 --- a/code/doc/resilience/simulation-2012-10/simulation-2012-10.txt +++ b/code/doc/resilience/simulation-2012-10/simulation-2012-10.txt @@ -88,25 +88,71 @@ as we add greater fidelity to the Triton model. === Replica placement strategies -We assume that servers will use an epidemic fault detection and status -dissemination protocol to maintain a list of available servers. Clients can +We assume that servers will use an epidemic fault detection and +dissemination protocol to proactively maintain a list of available servers. Clients can retrieve a snapshot of this system state at any time. We therefore assume that any entity in the system (client or server) has a reasonably accurate list of available servers in the system, and can refresh this list if it -detects that it is out of date. Clients and servers can therefore use an -algorithmic mapping of objects to servers that requires no communication. -The mapping algorithm takes three inputs: the object ID (OID), a list of +detects that it is out of date. The mapping algorithm for an object will +therefore take three inputs: the object ID (OID), a list of available servers, and a replication factor. The algorithm produces a result which is an ordered list of servers to place the object on. -There are many options for algorithms that satisfy this model, but the most -appropriate algorithms will exhibit the following properties... - -* why this is the most important design choice, what the tradeoffs are -* what properties we want in a placement algorithm (no communication to -find data, algorithmic/deterministic placement, minimal movement on server -add/remove) -* list of examples that we will evaluate +There are several known algorithms that will satisfy this model, but the most +appropriate algorithms will exhibit several key properties. The first is +that the ordered list of servers produced by the placement algorithm should +not change as servers are added or removed from the system (except for +places where those specific servers impact the placement list). This +minimizes the need to move existing objects in order to +satisfy the placement algorithm following system changes. This is +especially important following a server failure; all surviving replicas +should remain on the server that previously hosted the replicas, and the +first replica should be promoted to be the primary for the object. The only +required data movement will be to generate new replicas, not to move +existing replicas. + +The second desirable property is that the algorithms should not require any +explicit communication steps to locate the appropriate server for an object. +This means that it must produce a deterministic result given a list of +available servers, as opposed to producing a set of candidate servers that must +be queried to locate an object. A deterministic +placement algorithm that leverages a full list of servers and requires no +communication offers notable advantages in that it reduces latency and +simplifies the steps required to rebuild following a failure. It also +simplifies consistency in that there is no ambiguity in where to locate a +given object. Servers are always authoritative for +placement decisions. If a client contacts the wrong server (due to a fault +or innacurate system state information) then the server will send a negative +acknowledgement inform the client that it must refresh its state +information and repeat the placement algorithm. + +A third desirable (but not required) property is for the placement algorithm +to produce predictable results, in that it is possible for the storage +system to select a set of object IDs for a data set that will compliment +each other in terms of avoiding overlapping replicas. This type of +algorithm can be used to optimize application I/O performance and limit the +scope of communication needed to discover affected objects following a +failure. + +Based on our desired placement algorithm properties, we will focus on placement algorithms that use a deterministic +distance metric to place objects on the servers that are "nearest" to a +given object ID. All servers are assigned a numerical ID (server ID). +The distance metric is used to rank servers according to which ones +have the lowest distance from the object ID, and the top N servers are +selected to hold the object and its replicas. This ranking will not change +as servers are added or removed, other than to add or remove those specific +servers from the placement list for a given object. + +In this report we evaluate four examples of deterministic, distance metric +based algorithms for object placement: + +* one-dimensional euclidian distance +* exclusive or (XOR) +* two-dimensional euclidian distance +* Jenkins hash + +These algorithms and their trade offs will be discussed in greater detail in +<<sec-rebuild-sim>>. == Methodology @@ -308,6 +354,7 @@ objects are small). We will revisit this issue in the next section to determine if servers using declustered replication should select a smaller transfer size to improve efficiency. +[[rebuild-sim]] == Large-scale rebuild simulation [[fig-1d]] hooks/post-receive --