October 2012 - Triton-commits - mailman3.cels.anl.gov

branch, master, updated. 99f063b444f5db8b9e630d3a43488817d654f1d6
by noreply＠mcs.anl.gov 29 Oct '12

29 Oct '12

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 99f063b444f5db8b9e630d3a43488817d654f1d6 (commit) from 40e9abc1303d7cbb7313eac1b0a80d7529b91e92 (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 99f063b444f5db8b9e630d3a43488817d654f1d6 Author: Phil Carns <carns(a)mcs.anl.gov> Date: Mon Oct 29 17:48:35 2012 -0400 fill in some text about CRUSH ----------------------------------------------------------------------- Summary of changes: .../simulation-2012-10/simulation-2012-10.txt | 16 ++++++++++++++-- 1 files changed, 14 insertions(+), 2 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 0801988..0489bb7 100644 --- a/code/doc/resilience/simulation-2012-10/simulation-2012-10.txt +++ b/code/doc/resilience/simulation-2012-10/simulation-2012-10.txt @@ -157,8 +157,16 @@ based algorithms for object placement: These algorithms and their trade offs will be discussed in greater detail in <<sec-rebuild-sim>>. -TODO: somewhere (here or in future work) talk about and reference the Ceph/CRUSH work as -well. +Weil et. al. <<Weil>> developed a related object placement algorithm, +known as CRUSH, that distributes replicated objects over a large +collection of servers. CRUSH is notable for allowing administratorss to +partition devices into hierarchies to reflect expected failure domains +and for allowing administrators to weights to different devices. +Previous studies of the CRUSH algorithms have not focused on the time +required to complete a rebuild, however, but instead focused on the cost of +the placement algorithm itself and the degree to which it minimizes +superfluous data movement following server failure or addition. We will +consider CRUSH algorithms in future work. == Methodology @@ -553,3 +561,7 @@ erasure coding algorithms for quiescent data. - [[[Maymounkov]]] Petar Maymounkov and David Mazieres, “Kademlia: A peer-to-peer information system based on the XOR metric,” in Proc. Workshop on Peer-to-peer Systems, 2002. +- [[[Weil]]] S. A. Weil, S. A. Brandt, E. L. Miller, and C. Maltzahn. + CRUSH: Controlled, scalable, decentralized placement + of replicated data. In Proceedings of the 2006 ACM/IEEE + Conference on Supercomputing (SC ’06), Tampa, FL, Nov. 2006. ACM. hooks/post-receive --

1 0

branch, master, updated. 40e9abc1303d7cbb7313eac1b0a80d7529b91e92
by noreply＠mcs.anl.gov 29 Oct '12

29 Oct '12

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 40e9abc1303d7cbb7313eac1b0a80d7529b91e92 (commit) via b91f2e33a88d6d169d26d8699c60e47b2d7b431a (commit) from 11b06189faee07b72966e81134a19beecde985a7 (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 40e9abc1303d7cbb7313eac1b0a80d7529b91e92 Author: Phil Carns <carns(a)mcs.anl.gov> Date: Mon Oct 29 16:53:34 2012 -0400 mark TODO note in data distribution commit b91f2e33a88d6d169d26d8699c60e47b2d7b431a Author: Phil Carns <carns(a)mcs.anl.gov> Date: Mon Oct 29 16:52:41 2012 -0400 edit final results and conclusions ----------------------------------------------------------------------- Summary of changes: .../simulation-2012-10/simulation-2012-10.txt | 95 ++++++++++--------- 1 files changed, 50 insertions(+), 45 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 38a28ef..0801988 100644 --- a/code/doc/resilience/simulation-2012-10/simulation-2012-10.txt +++ b/code/doc/resilience/simulation-2012-10/simulation-2012-10.txt @@ -263,6 +263,8 @@ storage systems. We therefore based the distribution of objects on the characteristics of the GPFS file system on Intrepid, a 557 teraflop IBM Blue Gene/P system operated by the Argonne Leadership Computing Facility... +TODO: fill in the following material: + * Information about Intrepid and its file system * How data was captured from Intrepid, what date it was captured * Summarize data (histogram? total files? total size?) @@ -394,7 +396,7 @@ were configured such that a rebuilding server pulled data from the lowest ranking surviving replica for an object. [[fig-1d]] -.Rebuild data distribution and rate for 1-dimensional nearest neighbor placement following a single server failure on a storage system with 2 million objects and 570 TiB of data +.Rebuild data distribution and rate for one-dimensional euclidean nearest neighbor placement following the failure of server 200. image::figs/1d.pdf[] TODO: do we want to show the ring figure from previous deliverables @@ -403,15 +405,16 @@ somewhere to help illustrate how this works? <<fig-1d>> shows the rebuild performance and distribution of data when the placement algorithm utilizes a simple, one-dimensional euclidean distance metric to identify the closest servers for each object. The distance between an object and a given -server is simply the absolute value of the difference in the two IDs in this -case. This placement algorithm has a number of practical advantages. It +server is calculated absolute value of the arithmetic difference in the +object ID and server ID. This placement algorithm has a number of practical advantages. It can be calculated efficiently from a sorted list of servers without iterating through the entire list, meaning that the calculation scales well with the number of servers. The placement is also highly predictable, in -that an object allocation component could easily select object IDs (or -ranges of object IDs) that result in objects and replicas landing on -specific servers, which is a powerful feature for application I/O -optimization. +that an object allocation component could explicitly select object IDs (or +ranges of object IDs) in order to meet specific placement constraints. For +example, the object allocator could optimize application I/O performance by +selecting object IDs that are guaranteed not to overlap replicas on any +server. The one-dimensional euclidean distance metric results in a straightforward (but limited) distribution of data during the rebuild procedure. @@ -426,14 +429,15 @@ distributed evenly across the object ID space, while object IDs were chosen at random. [[fig-xor]] -.Rebuild data distribution and rate for XOR nearest neighbor placement following a single server failure on a storage system with 2 million objects and 570 TiB of data +.Rebuild data distribution and rate for XOR nearest neighbor placement following the failure of server 200. image::figs/xor.pdf[] The XOR distance metric is an alternative metric advocated as part of the -Kademlia distributed storage system. TODO: cite. It is similar to the -one-dimensional euclidean metric, except that rather than basing the metric -on the simple arithmetic difference of the object ID and server ID, it uses -the XOR value of the two IDs. The result of simulating this strategy is +Kademlia distributed storage system <<Maymounkov>>. It is similar to the +one-dimensional euclidean metric, but the distance is calculated as a +bitwise exclusive or of the object ID and server ID rather than the +arithmetic difference. The resulting data distribution and performance of +rebuild when using this distrance metric is shown in <<fig-xor>>. Unlike the one-dimensional euclidean metric, it does not overlap sending and receiving servers during the rebuild procedure. However, it only utilizes a total of five servers when objects have @@ -441,12 +445,12 @@ three-way replication, and as a result it achieves an aggregate rebuild rate of only 15.49 GiB/s. [[fig-2d]] -.Rebuild data distribution and rate for 2-dimensional nearest neighbor placement following a single server failure on a storage system with 2 million objects and 570 TiB of data +.Rebuild data distribution and rate for 2-dimensional nearest neighbor placement following the failure of server 200. image::figs/2d.pdf[] -The basic one-dimesional metric shown in <<fig-1d>> can be expanded to a +The basic one-dimesional metric previously shown in <<fig-1d>> can be expanded to a larger number of dimensions by dividing up the integer ID space so that -subsets of the space indicate positions in different dimensions. For +subsets of the ID space represent coordinates in each dimension. For example, a two-dimensional distance metric for a 64-bit object ID would use the first 32 bits as an X value and the second 32 bits as a Y value. The distance between two points (i.e., an object ID and a server ID) can then be @@ -458,53 +462,54 @@ randomly. We see from these results that increasing the dimensionality of the euclidean distance metric increases the number of servers involved in the rebuild. In the two-dimensional case there are 10 servers that must rebuild objects and 8 servers that must respond to rebuild requests. This -is because with additional dimensions there are additional possibilities for -"nearest" servers when calculating the distance, and data is more widely -distributed. The aggregate rate achieved in the two-dimensional case is -32.42 GiB/s. A number of algorithms exist for identifying nearest neighbors -in a 2D or 3D space (TODO: cite), meaning that this algorithm is still +is because there are additional possibilities for +"nearest" servers when calculating distance in a multi-dimensional space. The aggregate rate achieved in the two-dimensional case is +32.42 GiB/s. There are a variety of nearest neighbor search algorithms +available in the literature that can be used to compute placement when using +multi-dimensional dimension metrics, meaning that this algorithm is still relatively simple to compute for a large number of servers. It is also still predictable in terms of the possibility of choosing object IDs to meet certain placement constraints. [[fig-hash]] -.Rebuild data distribution and rate for hashed nearest neighbor placement following a single server failure on a storage system with 2 million objects and 570 TiB of data +.Rebuild data distribution and rate for hashed nearest neighbor placement following the failure of server 200. image::figs/hash.pdf[] -The final algorithm uses the Jenkins hash algorithm to compute the +The distance metric that we evaluated uses the Jenkins hash algorithm to compute the distance between two IDs. It simply hashes the value of the object ID with the value of the server ID and treats the result as a numerical distance metric. This approach eschews predictable placement in favor of wider distribution of rebuild data following a failure. The result of simulating a rebuild in this scenario is shown in <<fig-hash>>. The aggregate rate achieved is 658.96 GiB/s, far higher than the previous three -algorithms, because it involves so many servers in the rebuild procedure. +algorithms, because it involves a much larger number of servers in the rebuild procedure. Given a large enough set of randomly chosen object IDs it would involve all -servers in a rebuild operation. There are three notable disadvantages to +servers in the rebuild. There are three notable disadvantages to this approach, however, despite its high rebuild rate: the placement is not predictable (making it difficult to optimize placement based on application -requirements), the computation is expensive (the distance to every server +requirements), the computation is expensive (the distance between the object +and every server must be calculated before choosing the N closest), and servers would have to communicate extensively prior to rebuild in order to establish lists of -object IDs that must be rebuilt. +object IDs that must be rebuilt on each server. == Conclusions -In this report we have demonstrated an ability to simulate complex storage -algorithms at larger scales than can be effectively tested on existing -systems. We focused on the rebuild algorithm used by servers to reconstruct -object replicas following a failure, and in particular on the placement -algorithm used to dictate the location of each replica. Our preliminary -results show that the choice of placement algorithm can have a profound -impact on rebuild performance. +In this report we have demonstrated the ability to simulate complex +storage algorithms at larger scales than can be effectively tested on +existing systems. We focused our initial simulation efforts on evaluation of +rebuild algorithms, and in particular on how rebuild algorithms are +affected by the placement algorithm used to determine the location of +objects and replicas. Our preliminary results show that the choice of placement +algorithm can have a profound impact on rebuild performance. === Future work Moving forward, we intend to analyze the projected failure rate of exascale -systems to determine how quickly a rebuild algorithm must make progress in -order to avoid data loss. Using this metric as a goal we will expand our -simulation to include additional details including the cost of locating data -on the system the cost of assembling a list of affected objects to be +systems to determine how quickly a rebuild algorithm must complete in +order to avoid data loss. Using this metric as a goal, we will expand our +simulation to include additional details such as the cost of locating data +on the system the cost of assembling lists of objects to be rebuilt. If necessary, we will seek to identify algorithms that bridge the gap between algorithms that distribute data widely across all servers and algorithms that provide ease of calculation and predictable placement. @@ -514,11 +519,9 @@ network or disk models. Our goal is to use these simulations to guide the choice of algorithm (or family of algorithms) used in Triton and to validate their -behavior at scale. - -Similar simulations could also be used to evaluate epidemic protocols for -fault detection and state dissemination. We also intend to explore the use -of erasure coding for quiescent data. +behavior at scale. If this approach proves successful we will use similar +simulation techniques to evaluate epidemic protocols for fault detection and +erasure coding algorithms for quiescent data. == Bibliography @@ -545,6 +548,8 @@ of erasure coding for quiescent data. http://www.mellanox.com. 2012. - [[[Seagate]]] Seagate Savvio 10K hard drive. http://www.seagate.com. 2012. -- [[[SuperMicro]]] SuperMicro SC417E16 series chasis. - http://www.supermicro.com. - +- [[[SuperMicro]]] SuperMicro SC417E16 series chassis. + http://www.supermicro.com. 2012. +- [[[Maymounkov]]] Petar Maymounkov and David Mazieres, “Kademlia: A peer-to-peer + information system based on the XOR metric,” in Proc. Workshop on + Peer-to-peer Systems, 2002. hooks/post-receive --

1 0

branch, master, updated. 11b06189faee07b72966e81134a19beecde985a7
by noreply＠mcs.anl.gov 29 Oct '12

29 Oct '12

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 11b06189faee07b72966e81134a19beecde985a7 (commit) from 68cc09019600dddf69b62324c7c7727d3ff3ca35 (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 11b06189faee07b72966e81134a19beecde985a7 Author: Phil Carns <carns(a)mcs.anl.gov> Date: Mon Oct 29 15:47:11 2012 -0400 some editing of intro to rebuild results section ----------------------------------------------------------------------- Summary of changes: .../simulation-2012-10/simulation-2012-10.txt | 13 +++++++------ 1 files changed, 7 insertions(+), 6 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 1975cc4..38a28ef 100644 --- a/code/doc/resilience/simulation-2012-10/simulation-2012-10.txt +++ b/code/doc/resilience/simulation-2012-10/simulation-2012-10.txt @@ -374,20 +374,21 @@ in <<sec-placement>> to determine their impact on the overall rebuild performance of a large scale storage system. We simulate the behavior of a storage system consisting of 768 servers, each with a theoretical peak throughput of 12 GiB/s, as described in <<sec-params>>. The initial -conditions of the system were specified such that the system contained -approximately two million objects. The size of each object was chosen +conditions specified that the system contained +approximately two million unique objects, not counting replication. The size of each object was chosen pseudo-randomly according to the distribution of representative object sizes as described in <<sec-data>>. Each object was set to use 3-way replication, and the total data volume of all objects (including replicas) was approximately 570 TiB. Although we anticipate that a production deployment would eventually contain a much larger number of objects, this volume is sufficient to achieve a steady-state aggregate rebuild -rate that could be extrapolated to any data volume. +rate that can be extrapolated to calculate the rebuild time for larger +volumes. In each case the simulation modeled the failure of a single storage node -(the 200th server out of 768) and measure the time needed to redistribute -data such that each affected object regains full three-way replication. -This requires rebuilding approximately 8000 replicas containing +(the 200th server out of 768) and measured the time needed to redistribute +data such that each affected object regained full three-way replication. +This required rebuilding approximately 8000 replicas containing approximately 2.24 TiB of data. Unless otherwise noted, all simulations were configured such that a rebuilding server pulled data from the lowest ranking surviving replica for an object. hooks/post-receive --

1 0

branch, master, updated. 68cc09019600dddf69b62324c7c7727d3ff3ca35
by noreply＠mcs.anl.gov 29 Oct '12

29 Oct '12

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 68cc09019600dddf69b62324c7c7727d3ff3ca35 (commit) from 9520c8c3f9ce6a1b0b16143885c900e7cc26fba8 (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 68cc09019600dddf69b62324c7c7727d3ff3ca35 Author: Phil Carns <carns(a)mcs.anl.gov> Date: Mon Oct 29 15:44:26 2012 -0400 edit pipeline results ----------------------------------------------------------------------- Summary of changes: .../simulation-2012-10/simulation-2012-10.txt | 47 +++++++++---------- 1 files changed, 22 insertions(+), 25 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 71558f3..1975cc4 100644 --- a/code/doc/resilience/simulation-2012-10/simulation-2012-10.txt +++ b/code/doc/resilience/simulation-2012-10/simulation-2012-10.txt @@ -162,6 +162,7 @@ well. == Methodology +[[sec-sim-method]] === Simulation We have constructed a discrete event simulator for the Triton storage system in @@ -314,34 +315,33 @@ five years. The Triton rebuild model uses not only configurable hardware parameters, but also a number of configurable rebuild algorithm parameters as well. The most prominent of these is the pipeline buffer size to use for data -transfers between servers. Each server is configured with a limit on the -amount of memory to set aside for buffering data that will be sent or -received during such transfers. This total memory buffer pool can be broken -up into an arbitrary number of individual buffers in order to pipeline -transfers to a single server or maintain multiple independent transfers to -different servers. The size of these individual memory buffers is the -pipeline buffer size. +transfers between servers. The model is configured to limit the amount of +memory that each server can use for buffering data to be sent or received. +These pools of memory are in turn broken up into smaller individual buffers +in order to pipeline transfers or maintain multiple independent transfers to +different servers. The size of these individual buffers is referred to as +the pipeline buffer size in this report. [[fig-pipeline-perf]] .Rate of data transfer between two servers with a total receive memory pool size of 1 GiB and a total send memory pool size of 1 GiB image::figs/pipeline-perf.pdf[] - -In order to gauge the sensitivity of the model to the pipeline buffer size, -we executed a sequence of simulations that rebuild a single 200 GiB object using -two servers while varying the pipeline buffer size. <<fig-pipeline-perf>> +We executed a sequence of simulations that rebuild a single 200 GiB object using +two servers while varying the pipeline buffer size in order to select an +optimal value for subsequent experiments. <<fig-pipeline-perf>> shows the aggregate performance achieved by the system assuming that each server is allowed to commit no more than 2 GiB of total memory to the -rebuild transfers. There is a separate request and acknowledgment for each -pipeline buffer in addition to the bulk data transfer. The sending server -sources its data from disk while the receiving server sinks its data to -disk. We see that, up until a certain point (256 MiB buffers), increasing -the pipeline buffer size improves performance dramatically. This is due to +rebuild transfers. The simulation includes all rebuild steps outlined earlier +in <<sec-sim-method>>, including request and response messages, RDMA +transfer, reading data from the source server, and writing data to the +destination server. Increasing +the pipeline buffer size improves performance dramatically up to a certain +point. This trend can be attributed to the relatively high cost of the average seek time of the system (2.5 milliseconds) relative to the transfer rate of the hard drives (1.2 GiB/s). The model assumes that each write operation incurs a single seek cost -followed by a transfer cost calculated as the transfer size divided by the -transfer rate. This means, for example, that a pipeline buffer size of 4 +followed by a transfer cost calculated as the buffer size divided by the +transfer rate. For example, a pipeline buffer size of 4 MiB will incur an extra 2.5 millisecond delay for every 4 MiB of data transfer, leading to poor disk utilization. @@ -350,10 +350,9 @@ transfer, leading to poor disk utilization. image::figs/pipeline-idle.pdf[] We also see in <<fig-pipeline-perf>> that the performance eventually drops -off if the pipeline buffer size is too large, however. This is due to the -fact that if the pipeline buffer is too large, then the disks will be idle -while waiting for large network transfers to complete before performing any -I/O operations (or vice versa). <<fig-pipeline-idle>> shows the cumulative +off if the pipeline buffer size is too large, however. This is because of +poor utilization of the hard drives if the pipeline has to stall too long +between transfers. <<fig-pipeline-idle>> shows the cumulative percentage of time that the disk subsystem on the rebuilding server is idle during the simulated data transfer shown in <<fig-pipeline-perf>>. As we can see in this figure, allocating the entire 1 GiB memory buffer pool for @@ -365,9 +364,7 @@ optimal for the system parameters used in this study. Note, however, that this pipeline buffer size also means that no more than 4 objects can be rebuilt concurrently given the chosen memory pool constraints if the server elects to rebuild multiple objects simultaneously (for example, if the -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. TODO: actually do this... +objects are small). [[sec-rebuild-sim]] === Large-scale rebuild simulation hooks/post-receive --

1 0

branch, master, updated. 9520c8c3f9ce6a1b0b16143885c900e7cc26fba8
by noreply＠mcs.anl.gov 29 Oct '12

29 Oct '12

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 9520c8c3f9ce6a1b0b16143885c900e7cc26fba8 (commit) from d53faf48f19b37896d0c5743d4b60586e528dd12 (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 9520c8c3f9ce6a1b0b16143885c900e7cc26fba8 Author: Phil Carns <carns(a)mcs.anl.gov> Date: Mon Oct 29 15:37:06 2012 -0400 edit system parameters and add citations ----------------------------------------------------------------------- Summary of changes: .../simulation-2012-10/simulation-2012-10.txt | 24 ++++++++++++------- 1 files changed, 15 insertions(+), 9 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 e45d1be..71558f3 100644 --- a/code/doc/resilience/simulation-2012-10/simulation-2012-10.txt +++ b/code/doc/resilience/simulation-2012-10/simulation-2012-10.txt @@ -279,21 +279,22 @@ system in the Triton ROSS simulation: * disk latency: 2.5 millisecond * number of servers: 768 -In this study we set the network bandwidth and latency of each server +We set the network bandwidth and latency of each server to 100 Gib/s and 1 microsecond, respectively, to reflect the advertised -bandwidth of the most recent generation of FDR InfiniBand adapters. -TODO: cite Mellanox. We also set the disk bandwidth to 100 Gib/s in +bandwidth of the most recent generation of FDR InfiniBand adapters +<<Mellanox>>. We also set the disk bandwidth to 100 Gib/s in order to model storage nodes with balanced network and storage performance. This node configuration would likely include a large array of high density -2.5" drives and rack-mount enclosures. TODO: cite Seagate and SuperMicro. +2.5" drives <<Seagate>> and rack-mount enclosures <<SuperMicro>>. The corresponding average seek time for enterprise-class 2.5" hard drives is approximately 2.5 milliseconds. Our model does not simulate storage with -individual hard disk granularity. We instead use a single disk bandwidth -parameter to represent the aggregate rate of an entire hard drive array. +individual hard disk granularity; we instead use a single disk bandwidth +parameter to represent the aggregate rate of an entire locally attached +hard drive array. Finally, we set the total number of servers to 768. This allows for files -to be striped across 128 objects using 3-way replication with no overlap of -objects on a server. Unless otherwise noted, all experiments in this report +to be striped across 256 objects using 3-way replication with no overlap of +objects on any server. Unless otherwise noted, all experiments in this report were performed with a replication factor of 3 for all objects. This example configuration would have a total raw capacity of @@ -301,7 +302,6 @@ approximately 40 PiB and a total theoretical throughput of 9 TiB/s using currently available technology. The peak achievable throughput of such a system is likely to be much lower in practice, but these figures give us a starting point for large our large-scale simulation experiments. - In future work we will model not only present day configurations, but also projected systems using technology that will be available within the next five years. @@ -543,4 +543,10 @@ of erasure coding for quiescent data. (1999). "Efficient optimistic parallel simulations using reverse computation". ACM Transactions on Modeling and Computer Simulation (Association for Computing Machinery) 9 (3): 224–253. +- [[[Mellanox]]] Mellanox Connect-IB InfiniBand host channel adapter cards. + http://www.mellanox.com. 2012. +- [[[Seagate]]] Seagate Savvio 10K hard drive. http://www.seagate.com. + 2012. +- [[[SuperMicro]]] SuperMicro SC417E16 series chasis. + http://www.supermicro.com. hooks/post-receive --

1 0

branch, master, updated. d53faf48f19b37896d0c5743d4b60586e528dd12
by noreply＠mcs.anl.gov 29 Oct '12

29 Oct '12

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 d53faf48f19b37896d0c5743d4b60586e528dd12 (commit) from c8ed620bc499563fa0a5dbd472a7ba0da9eda304 (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 d53faf48f19b37896d0c5743d4b60586e528dd12 Author: Phil Carns <carns(a)mcs.anl.gov> Date: Mon Oct 29 15:11:29 2012 -0400 edit description of triton model ----------------------------------------------------------------------- Summary of changes: .../simulation-2012-10/simulation-2012-10.txt | 40 ++++++++++--------- 1 files changed, 21 insertions(+), 19 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 4d0b52c..e45d1be 100644 --- a/code/doc/resilience/simulation-2012-10/simulation-2012-10.txt +++ b/code/doc/resilience/simulation-2012-10/simulation-2012-10.txt @@ -164,20 +164,21 @@ well. === Simulation -n this report we focus on the activities -that servers perform following a failure and therefore do not model client -processes or applications. The key components of the Triton ROSS model are -therefore the the network devices, disk devices, and storage protocols used -by the servers. +We have constructed a discrete event simulator for the Triton storage system in +order to evaluate its rebuild performance at scale. The model does not yet +include client processes or application workloads. It instead focuses on +the behavior of servers as they recovery from fault conditions. The key +components of the model are the network devices, disk devices, and storage +protocols used by the servers. The network model is a simple cost model based on the startup cost (latency) of the network and the bandwidth (cost per byte transferred) of the network. Each server is assumed to have full-duplex transmit -and receive capability. Messages begin transmission when the sender -has output queue availability and appear to complete from the sender's -perspective as soon as the startup and bandwidth costs have been computed. -However, the message is not delivered for processing on the receiving -side until the receiver's input queue is available.The network fabric +and receive capability. Messages begin transmission when the sender's +output queue is available. From the sender's perspective, the transmission +is complete as soon as enough virtual time has elapsed to account for the +startup and bandwidth costs of the message. +However, the message is not delivered for processing on the receiver until the receiver's input queue is also available. The network fabric itself is not modeled and is instead treated as if it has infinite buffering ability and no internal routing overhead. @@ -189,8 +190,8 @@ The storage protocol used by Triton uses a "pull" model in which rebuilding servers request data from surviving replicas until they have reconstructed all necessary replicas. Each data transfer includes both a request and acknowledgment in addition to the actual data payload itself. Requests and -acknowledgments will be transmitted using traditional two-sided messages, -while the data payload will be transmitted using one-sided RDMA put +acknowledgments are transmitted using traditional two-sided messages, +while the data payload is transmitted using one-sided RDMA put operations. @@ -229,19 +230,20 @@ digraph triton_sim { <<fig-triton-sim>> illustrates the steps involved in transferring a single data buffer between two servers during the rebuild process. -We assume that the rebuilding server (shown in red nodes) begins with -complete knowledge of which objects must be transferred. The nodes shown -in blue represent steps carried out on the server that is responding -to a rebuild request. The buffer in question is read from disk on +We assume that the rebuilding server begins with +complete knowledge of which objects must be transferred. The steps carried +out by the rebuilding +server are shown in red and the steps carried out by the responding server +are shown in blue. +The data buffer is read from disk on the responding server and written to disk on the rebuilding server. -As described earlier, each transfer requires three messages: a request, +As described earlier, each transfer requires three network messages: a request, a buffer (payload) transfer, and a response. The rebuilding server cannot -write to disk until it has received both the data buffer and the response. +write the buffer to disk until it has received both the data buffer and the response. Each server limits the total amount of memory used for sending and receiving data payloads in order to insure that servers are not overwhelmed by incoming data messages. - For clarity, the <<fig-triton-sim>> does not show pipelining. In practice, however, servers will issue multiple overlapping requests as long as memory buffers are available and the disk and network bandwidth are hooks/post-receive --

1 0

branch, master, updated. c8ed620bc499563fa0a5dbd472a7ba0da9eda304
by noreply＠mcs.anl.gov 29 Oct '12

29 Oct '12

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 c8ed620bc499563fa0a5dbd472a7ba0da9eda304 (commit) from 8eb5e2963d6fc08990bb3193995ac3047f8142c6 (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 c8ed620bc499563fa0a5dbd472a7ba0da9eda304 Author: Phil Carns <carns(a)mcs.anl.gov> Date: Mon Oct 29 14:30:37 2012 -0400 edits to intro text on placement ----------------------------------------------------------------------- Summary of changes: .../simulation-2012-10/simulation-2012-10.txt | 26 +++++++++---------- 1 files changed, 12 insertions(+), 14 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 0c808d2..4d0b52c 100644 --- a/code/doc/resilience/simulation-2012-10/simulation-2012-10.txt +++ b/code/doc/resilience/simulation-2012-10/simulation-2012-10.txt @@ -97,11 +97,11 @@ 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 +list of available servers and can refresh that list if it 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. +available servers, and a replication factor. The result of the algorithm is +an ordered list of servers to place the object on. There are several known algorithms that will satisfy this model, but the most appropriate algorithms will exhibit several key properties. The first is @@ -109,20 +109,18 @@ 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 +satisfy the placement algorithm following system changes. This property is +especially important following a server failure. All surviving replicas +should remain on the server that previously hosted the replicas. 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 +The second key 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 +be queried to locate an object. This type of algorithm +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 @@ -134,8 +132,8 @@ 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 +each other in terms of avoiding overlapping replicas. This property can be +leveraged to optimize application I/O performance and limit the scope of communication needed to discover affected objects following a failure. @@ -369,7 +367,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. TODO: actually do this... -[[rebuild-sim]] +[[sec-rebuild-sim]] === Large-scale rebuild simulation In this section we evaluate the example placement strategies described hooks/post-receive --

1 0

branch, master, updated. 8eb5e2963d6fc08990bb3193995ac3047f8142c6
by noreply＠mcs.anl.gov 29 Oct '12

29 Oct '12

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 8eb5e2963d6fc08990bb3193995ac3047f8142c6 (commit) from b91b304184b50906c467c1f215e6f25f428c6427 (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 8eb5e2963d6fc08990bb3193995ac3047f8142c6 Author: Phil Carns <carns(a)mcs.anl.gov> Date: Mon Oct 29 14:05:59 2012 -0400 clean up ross background, add citations ----------------------------------------------------------------------- Summary of changes: .../simulation-2012-10/simulation-2012-10.txt | 31 ++++++++++++++++---- 1 files changed, 25 insertions(+), 6 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 ffddd02..0c808d2 100644 --- a/code/doc/resilience/simulation-2012-10/simulation-2012-10.txt +++ b/code/doc/resilience/simulation-2012-10/simulation-2012-10.txt @@ -66,13 +66,13 @@ deliverable <<ASG>>. === Discrete event simulation with ROSS We constructed a simulation of the Triton rebuild protocol using -Rensselaer’s Optimistic Simulation System (ROSS), developed by Christopher -Carothers and others at the Renselaer Polytechnic Institute. TODO: cite. +Rensselaer’s Optimistic Simulation System (ROSS), a simulation framework developed by Christopher +Carothers et al. at the Renselaer Polytechnic Institute. ROSS is a state-of-the art parallel discrete event simulator that enables complex simulations to be executed efficiently as MPI programs on large -scale parallel computers such as the IBM Blue Gene/P. TODO: list some -examples of things that have been done with ROSS and cite. Be sure to at -least include burst buffer and torus papers. +scale parallel computers such as the IBM Blue Gene/P <<Bauer>>,<<Liu1>>. +ROSS has recently been used to study the potential role of burst buffers in +leadership-class storage systems <<Liu2>>. ROSS models consist of a collection of logical processes (LPs) that each represent a distinct component of the system. Time-stamped messages are @@ -84,7 +84,7 @@ simulation is critical to simulation performance. ROSS utilizes optimistic event processing to minimize synchronization. If ROSS detects that an event was processed in the wrong order, it uses a technique known as reverse computation to roll back the event and any other events that were affected -by it. TODO: cite. ROSS also supports the use of more conservative +by it <<Carothers>>. ROSS also supports the use of more conservative simulation modes for models that do not support this functionality. The simulations presented in this report were executed in conservative mode, but we intend to pursue optimistic execution to improve simulation performance @@ -159,6 +159,9 @@ based algorithms for object placement: These algorithms and their trade offs will be discussed in greater detail in <<sec-rebuild-sim>>. +TODO: somewhere (here or in future work) talk about and reference the Ceph/CRUSH work as +well. + == Methodology === Simulation @@ -524,4 +527,20 @@ of erasure coding for quiescent data. [bibliography] - [[[ASG]]] ASG server-organized resilient storage deliverable 2.1.1, "Triton: Data Organization, Replication, and Resilience". April 31, 2012. +- [[[Bauer]]] D. W. Bauer Jr., C. D. Carothers, and A. Holder. Scalable + time warp on Blue Gene supercomputers. In Proceedings of the 2009 + ACM/IEEE/SCS 23rd Workshop on Principles of Advanced and Distributed + Simulation, pages 35–44, Washington, DC, USA, 2009. IEEE Computer Society. +- [[[Liu1]]] N. Liu and C. D. Carothers. Modeling billion-node torus networks using + massively parallel discrete-event simulation. In Proceedings of the 2011 + IEEE Workshop on Principles of Advanced and Distributed Simulation, + PADS ’11, pages 1–8, Washington, DC, USA, 2011. IEEE Computer + Society. +- [[[Liu2]]] N Liu, J Cope, P Carns, C Carothers, R Ross, G Grider, A Crume, C Maltzahn. + On the Role of Burst Buffers in Leadership-Class Storage Systems. + Proceedings of 28th IEEE MSST conference, 2012. +- [[[Carothers]]] Carothers, Christopher D.; Perumalla, Kalyan S. ; Fujimoto, Richard M. + (1999). "Efficient optimistic parallel simulations using reverse + computation". ACM Transactions on Modeling and Computer Simulation + (Association for Computing Machinery) 9 (3): 224–253. hooks/post-receive --

1 0

branch, master, updated. b91b304184b50906c467c1f215e6f25f428c6427
by noreply＠mcs.anl.gov 29 Oct '12

29 Oct '12

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 b91b304184b50906c467c1f215e6f25f428c6427 (commit) from c0d5ed5d81bf93805a3e9341b922dad2806df65f (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 b91b304184b50906c467c1f215e6f25f428c6427 Author: Phil Carns <carns(a)mcs.anl.gov> Date: Mon Oct 29 13:56:03 2012 -0400 edit triton background, ref previous deliverable ----------------------------------------------------------------------- Summary of changes: .../simulation-2012-10/simulation-2012-10.txt | 22 +++++++++++-------- 1 files changed, 13 insertions(+), 9 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 76abc51..ffddd02 100644 --- a/code/doc/resilience/simulation-2012-10/simulation-2012-10.txt +++ b/code/doc/resilience/simulation-2012-10/simulation-2012-10.txt @@ -35,17 +35,19 @@ choices in the Triton prototype implementation. === Triton resilience strategy Triton is a prototype resilient object storage system. Data is organized -into objects, and each object is replicated across servers in its entirety -using primary-copy replication. When a server fault occurs, the remaining -servers detect the fault and determine which objects have been affected. +into containers known as objects, and each object is replicated in its entirety +using primary-copy, inter-server replication. When a server fault occurs, the remaining +servers proactively detect the fault and determine which objects have been affected. A subset of servers will create new replicas for affected objects in order to regain the desired replication level for each object. -In this report we focus on simulating the I/O activity involved in +In this report we focus on simulating the bulk I/O activity involved in rebuilding objects following a failure. We assume that each server has -already detected the failure and assembled a list of objects to be rebuilt. -The affected servers utilize a "pull" model to request data from surviving -replicas. In this model, each server is independently responsible for +already detected the failure and has already assembled a list of objects to +be rebuilt. The simulation begins with each each rebuilding server +requesting data from surviving replicas and ends once all replicas have been +reconstructed. The rebuilding servers utilize a "pull" model to request data from surviving +replicas. Each server is independently responsible for reaching a consistent state. The storage system will still be active and responsive while objects are @@ -58,8 +60,8 @@ relative to the expected failure rate of the system to prevent subsequent failures from causing data loss due to the loss of all replicas for an object. -More details about the resilience strategy can be found in TODO: cite -previous 2.1.1 deliverable. +More details about the resilience strategy can be found in a previous ASG +deliverable <<ASG>>. === Discrete event simulation with ROSS @@ -520,4 +522,6 @@ of erasure coding for quiescent data. == Bibliography [bibliography] +- [[[ASG]]] ASG server-organized resilient storage deliverable 2.1.1, + "Triton: Data Organization, Replication, and Resilience". April 31, 2012. hooks/post-receive --

1 0

branch, master, updated. c0d5ed5d81bf93805a3e9341b922dad2806df65f
by noreply＠mcs.anl.gov 29 Oct '12

29 Oct '12

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 c0d5ed5d81bf93805a3e9341b922dad2806df65f (commit) from bbd5d84250663d4a8ffb2db641519014f59be834 (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 c0d5ed5d81bf93805a3e9341b922dad2806df65f Author: Phil Carns <carns(a)mcs.anl.gov> Date: Mon Oct 29 13:38:03 2012 -0400 edit abstract ----------------------------------------------------------------------- Summary of changes: .../simulation-2012-10/simulation-2012-10.txt | 28 +++++++++++-------- 1 files changed, 16 insertions(+), 12 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 dfdfa92..76abc51 100644 --- a/code/doc/resilience/simulation-2012-10/simulation-2012-10.txt +++ b/code/doc/resilience/simulation-2012-10/simulation-2012-10.txt @@ -4,21 +4,25 @@ Triton: Resilient Storage Simulation [abstract] == Abstract -Simulation is a critical component of long-range exascale architecture -evaluation. It offers the ability to explore design space trade offs -well in advance of hardware availability and evaluate -complex algorithms that may be difficult to capture adequately with analytical -models. One example of a design space domain that is well-suited to -simulation is the mechanism used by the storage system to reconstruct data -following a server failure. The goal of a reconstruction +Simulation is a critical tool for evaluation of exascale architectures. +It offers the ability to explore design space trade offs before hardware +availability and evaluate complex algorithms that are difficult to +capture with analytical models. The reconstruction algorithm used by the +storage system to recover from faults is an example of an exascale design +space that is well-suited to simulation techniques. +The goal of a reconstruction algorithm should be to recover data quickly enough to avoid data loss from subsequent failures while minimizing the impact on application I/O -performance. Unfortunately, reconstruction time is impacted by a variety -of factors ranging from architecture parameters (disk speed, network +performance. This type of algorithm is difficult to evaluate through +prototyping because it would require exclusive access to a large, fully populated +storage system. It is also difficult to evaluate through analytical models +due to the range of parameters that may affect performance. +Reconstruction time is impacted by a variety +of factors ranging from architecture parameters (e.g., disk speed, network speed, number of servers, expected failure rate), system characteristics -(number of objects, distribution of object sizes, replication factors), -and software algorithms (replica placement strategies, pipelining). -In this report we show preliminary results from a parallel discrete event +(e.g., number of objects, distribution of object sizes, replication levels), +and software algorithms (e.g., replica placement strategies, pipelining). +In this report we present preliminary results from a parallel discrete event simulation of object reconstruction time in the Triton storage system. These results demonstrate our ability to simulate system performance at scales larger than can be effectively tested on existing systems. hooks/post-receive --

1 0