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

branch, master, updated. 52d6ac7ec841361dc5339a06bede9b6cfb24939c
by noreply＠mcs.anl.gov 29 Sep '12

29 Sep '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 52d6ac7ec841361dc5339a06bede9b6cfb24939c (commit) via 3d8b71c2f10af7cbc6921db7eeccd0c0e9ce3f50 (commit) from 3c087bc86514356e196c0c212a1b042e92345b22 (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 52d6ac7ec841361dc5339a06bede9b6cfb24939c Author: Dries Kimpe <dkimpe(a)mcs.anl.gov> Date: Sat Sep 29 20:34:09 2012 -0500 Update TODO commit 3d8b71c2f10af7cbc6921db7eeccd0c0e9ce3f50 Author: Dries Kimpe <dkimpe(a)mcs.anl.gov> Date: Sat Sep 29 20:33:16 2012 -0500 Adjust captions to match modified figures ----------------------------------------------------------------------- Summary of changes: papers/conditional-write/TODO | 10 ++++------ papers/conditional-write/paper.tex | 10 +++++++--- 2 files changed, 11 insertions(+), 9 deletions(-) Diff of changes: diff --git a/papers/conditional-write/TODO b/papers/conditional-write/TODO index 64c28f1..0095cb5 100644 --- a/papers/conditional-write/TODO +++ b/papers/conditional-write/TODO @@ -1,7 +1,8 @@ -- Add governement license argonne +DONE - Add governement license argonne -- Fix figures +DONE - Fix figures + - Send to Ja-Quel for clearance @@ -9,10 +10,7 @@ a) reorganize implementation text and take material from vtag paper b) suggestions on points to make in the conclusion -2) fix the graphs (to draw lines through averages, or go back to just -points if we lack time) - -3) balance columns on last page +DONE - balance columns on last page 4) submit paper and email co-authors with submitted copy diff --git a/papers/conditional-write/paper.tex b/papers/conditional-write/paper.tex index b2914a7..0684561 100644 --- a/papers/conditional-write/paper.tex +++ b/papers/conditional-write/paper.tex @@ -375,7 +375,8 @@ The prototype software was built using MPICH 1.2.1 and GCC 4.1.2. \label{fig:cond-small-conflicts} } \caption{Sixteen concurrent conditional read/modify/write operations with one - client node and one server node} + client node and one server node. Each point represents an experiment, + the solid line shows the average of all experiments.} \label{fig:cond-small} \vspace{-.1in} \end{figure} @@ -452,7 +453,8 @@ write operations and the observed read/modify/write performance. \includegraphics[width=3in]{scale-allbins-rate} \caption{Random read/modify/write rate with 32 server nodes and 16 concurrent operations per client -(random updates to $2^{64}$ possible blocks, no contention)} +(random updates to $2^{64}$ possible blocks, no contention). +Solid line indicates average.} \label{fig:scale-allbins-rate} \vspace{-.1in} \end{figure} @@ -482,7 +484,9 @@ number of data servers and the distribution of data on those servers. \includegraphics[width=3in] {scale-512bins-conflicts} \label{fig:scale-512bins-conflicts} } -\caption{Read/modify/write operations with 32 server nodes, 16 concurrent operations per client node, and random updates to 512 different blocks} +\caption{Read/modify/write operations with 32 server nodes, 16 concurrent + operations per client node, and random updates to 512 different blocks. +Solid line indicates average.} \label{fig:scale-512bins} \vspace{-.1in} \end{figure} hooks/post-receive --

1 0

branch, master, updated. 3c087bc86514356e196c0c212a1b042e92345b22
by noreply＠mcs.anl.gov 29 Sep '12

29 Sep '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 3c087bc86514356e196c0c212a1b042e92345b22 (commit) from 0d702682088fb96aa01f803571948641123a9678 (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 3c087bc86514356e196c0c212a1b042e92345b22 Author: Dries Kimpe <dkimpe(a)mcs.anl.gov> Date: Sat Sep 29 20:29:24 2012 -0500 Improve figures - Added script and data for average of runs - Adjusted graphs to show solid line average, point for runs ----------------------------------------------------------------------- Summary of changes: papers/conditional-write/figs/Makefile | 12 ++ papers/conditional-write/figs/calc_average.hs | 128 ++++++++++++++++++++ .../figs/cond-small-conflicts.plt | 5 +- papers/conditional-write/figs/cond-small-rate.plt | 5 +- papers/conditional-write/figs/cond-small.avg.dat | 6 + papers/conditional-write/figs/conflicts.plt | 2 +- .../figs/scale-512bins-conflicts.plt | 5 +- .../conditional-write/figs/scale-512bins-rate.plt | 8 +- .../conditional-write/figs/scale-512bins.avg.dat | 5 + .../conditional-write/figs/scale-allbins-rate.plt | 8 +- .../conditional-write/figs/scale-allbins.avg.dat | 5 + 11 files changed, 176 insertions(+), 13 deletions(-) create mode 100644 papers/conditional-write/figs/calc_average.hs create mode 100644 papers/conditional-write/figs/cond-small.avg.dat create mode 100644 papers/conditional-write/figs/scale-512bins.avg.dat create mode 100644 papers/conditional-write/figs/scale-allbins.avg.dat Diff of changes: diff --git a/papers/conditional-write/figs/Makefile b/papers/conditional-write/figs/Makefile index 1c82fc3..f4fb836 100644 --- a/papers/conditional-write/figs/Makefile +++ b/papers/conditional-write/figs/Makefile @@ -7,9 +7,21 @@ %.pdf: %.svg inkscape -A $@ $< +%: %.hs + ghc $< + +%.avg.dat: %.dat calc_average + ./calc_average <$< >$@ + + + all:: +AVGS=cond-small.dat scale-allbins.dat scale-512bins.dat + +all:: $(patsubst %.dat, %.avg.dat, $(AVGS)) + FIGURES=$(patsubst %.plt, %.pdf, $(wildcard *.plt)) FIGURES+=cond-overview.pdf diff --git a/papers/conditional-write/figs/calc_average.hs b/papers/conditional-write/figs/calc_average.hs new file mode 100644 index 0000000..9a4bc4d --- /dev/null +++ b/papers/conditional-write/figs/calc_average.hs @@ -0,0 +1,128 @@ +import System.IO +import Data.List +import Data.Char (isSpace) + + +sumList all@(x:xs) [] = all +sumList [] all@(x:xs) = all +sumList all1@(x:xs) all2@(y:ys) = zipWith (+) all1 all2 + + +sumLists = foldr sumList [] + +-- Take two lists; If the first argument is equal, return a list containing of the +-- first argument followed by the sum of the corresponding arguments from the lists +-- If not equal: return the second list +updateItem :: (Num a, Eq a) => [a] -> (a,[[a]]) -> (Bool, (a,[[a]])) +updateItem (x:xs) y@(y1,ys) | x == y1 = (True, (x,(xs:ys))) + | otherwise = (False, y) + + + +-- Fold function to apply updateItem to each element of a list, keeping track if +-- we found the element. +-- Take: +-- a list of numbers : the line we're trying to update +-- a list of numbers : the current line we're examining in the overall data +-- the current accumulator: what we've processed so far +-- and returns +-- update accumulator +doTransform :: (Num a, Eq a) => [a] -> (a,[[a]]) -> (Bool, [(a,[[a]])]) -> (Bool, [(a, [[a]])]) +doTransform searchitem curel accum@(sel,b) = (newval, updatedline:b) + where (found,updatedline) = updateItem searchitem curel + newval = sel || found + + +-- gets a line and the accumulator, and returns (Bool, Acc) +-- where Bool is true if Acc was updated, False if not +-- updateAcc :: [a] -> [[a]] -> (Bool, [a]) +-- updateAcc a b = (True, b) +updateAcc :: (Eq a, Num a) => [a] -> [(a,[[a]])] -> (Bool,[(a,[[a]])]) +updateAcc a b = foldr applyTransform (False,[]) b + where applyTransform = doTransform a + + +-- Takes the new line and the accumulator, and adds or updates acc +updateList a@(a1:as) b | updated == True = newlist + | otherwise = (a1,[as]) : b + where (updated, newlist) = updateAcc a b + + +--- ==================== +--- Showing stuff +--- ================== + +-- fold which takes last element as seed +myFoldR func list = foldr func lastel remainder + where lastel = last list + remainder = init list + +myConcat:: [String] -> String -> String +--myConcat a token = myFoldR addToken a +-- where addToken a b = a ++ token ++ b + +myConcat lines sep = intercalate sep lines + +prettify :: (Num a, Show a) => [(a,[a])] -> String +prettify input = (myConcat lines "\n") ++ "\n" + where + createLine a = myConcat (map show a) "\t" + flatten = map (\(a,b) -> a:b) + lines = map createLine (flatten input) + + +-- Hack since I don't remember how to force an instance of a polymorphic +-- function +readNum :: String -> Double +readNum = read + + +-- Calculate average of items +calcAverage (a,b) = (a, map (\a -> a/len) (sumLists b)) + where len = fromIntegral ( length b) + +-- reduceRes :: (Eq a, Num a) => [(a,[[a]])] -> [(a,[a])] +reduceRes list = map doReduce list + where doReduce = calcAverage + +-- +-- Cleanup the input a bit +-- +removeComment :: String -> String +removeComment (x:xs) | x == '#' = [] + | otherwise = x:removeComment (xs) +removeComment _ = [] + + +removeWhite :: String -> String +removeWhite = f . f + where f = reverse . dropWhile isSpace + + +filterComments:: [String] -> [String] +filterComments = filter (not . null) . map (removeWhite . removeComment) + + +-- +-- +-- +main :: IO () +main = do + let acc = [] + + input <- getContents + let splitlines = (filterComments . lines) input + let splitwords = map words splitlines + let makenum = map doNum splitwords + where doNum a = map readNum a + + let acc = foldr updateList [] makenum + -- let acc = [0] + + let sortedRes = sortBy compareHead acc + where compareHead (a1,_) (b1,_) = compare a1 b1 + + let reducedres = reduceRes sortedRes + + putStr (prettify reducedres) + return () diff --git a/papers/conditional-write/figs/cond-small-conflicts.plt b/papers/conditional-write/figs/cond-small-conflicts.plt index 26fde5b..83fc794 100644 --- a/papers/conditional-write/figs/cond-small-conflicts.plt +++ b/papers/conditional-write/figs/cond-small-conflicts.plt @@ -1,5 +1,5 @@ #set term po eps color solid "NimbusSanL-Regu" 16 fontfile "/usr/share/texmf-texlive/fonts/type1/urw/helvetic/uhvr8a.pfb" -set term po eps color solid 16 +#set term po eps color solid 16 # color blindness work around set style line 1 lc 1 lw 4 @@ -26,6 +26,7 @@ set rmargin 5 set xtics (1, 8, 16, 24, 32, "2^64" 55) set xrange [0:60] -plot "cond-small.dat" using 1:(100*($2/($2+$3))) notitle with linespoints +plot "cond-small.dat" using 1:(100*($2/($2+$3))) notitle with points, \ + "cond-small.avg.dat" using 1:(100*($2/($2+$3))) notitle with lines lc 1 #plot "< cat rand-un-read-ext4-vosd.dat |grep read" using 2:5 title "VOSD/ext4 (disk)" with points lt 1, \ diff --git a/papers/conditional-write/figs/cond-small-rate.plt b/papers/conditional-write/figs/cond-small-rate.plt index ee9ffa5..40e33dc 100644 --- a/papers/conditional-write/figs/cond-small-rate.plt +++ b/papers/conditional-write/figs/cond-small-rate.plt @@ -1,5 +1,5 @@ #set term po eps color solid "NimbusSanL-Regu" 16 fontfile "/usr/share/texmf-texlive/fonts/type1/urw/helvetic/uhvr8a.pfb" -set term po eps color solid 16 +#set term po eps color solid 16 # color blindness work around set style line 1 lc 1 lw 4 @@ -26,6 +26,7 @@ set rmargin 5 set xtics (1, 8, 16, 24, 32, "2^64" 55) set xrange [0:60] -plot "cond-small.dat" using 1:4 notitle with linespoints +#plot "cond-small.dat" using 1:4 notitle with linespoints +plot "cond-small.dat" using 1:4 notitle with points, "cond-small.avg.dat" using 1:4 notitle with lines lc 1 #plot "< cat rand-un-read-ext4-vosd.dat |grep read" using 2:5 title "VOSD/ext4 (disk)" with points lt 1, \ diff --git a/papers/conditional-write/figs/cond-small.avg.dat b/papers/conditional-write/figs/cond-small.avg.dat new file mode 100644 index 0000000..59d5823 --- /dev/null +++ b/papers/conditional-write/figs/cond-small.avg.dat @@ -0,0 +1,6 @@ +1.0 15000.0 125815.4 327.23269760000005 +8.0 60000.0 61147.6 1263.0694076 +16.0 150000.0 77729.4 1760.690236 +24.0 200000.0 68950.8 1879.2588284 +32.0 200000.0 51608.0 2117.4447472 +55.0 200000.0 0.0 2868.7762291999998 diff --git a/papers/conditional-write/figs/conflicts.plt b/papers/conditional-write/figs/conflicts.plt index e3e4e16..79cbb63 100644 --- a/papers/conditional-write/figs/conflicts.plt +++ b/papers/conditional-write/figs/conflicts.plt @@ -1,4 +1,4 @@ -set term po eps color solid 16 +#set term po eps color solid 16 set output 'conflicts.eps' set style data histogram diff --git a/papers/conditional-write/figs/scale-512bins-conflicts.plt b/papers/conditional-write/figs/scale-512bins-conflicts.plt index b09ea26..5cbf2d8 100644 --- a/papers/conditional-write/figs/scale-512bins-conflicts.plt +++ b/papers/conditional-write/figs/scale-512bins-conflicts.plt @@ -1,5 +1,5 @@ #set term po eps color solid "NimbusSanL-Regu" 16 fontfile "/usr/share/texmf-texlive/fonts/type1/urw/helvetic/uhvr8a.pfb" -set term po eps color solid 16 +#set term po eps color solid 16 # color blindness work around set style line 1 lc 1 lw 4 @@ -27,5 +27,6 @@ set xtics (1, 8, 16, 24, 32) set xrange [0:33] set yrange [0:100] -plot "scale-512bins.dat" using 1:(100*($5/($5+$6))) notitle with linespoints +plot "scale-512bins.dat" using 1:(100*($5/($5+$6))) notitle with points lc 1, \ + "scale-512bins.avg.dat" using 1:(100*($5/($5+$6))) notitle with lines lc 1 diff --git a/papers/conditional-write/figs/scale-512bins-rate.plt b/papers/conditional-write/figs/scale-512bins-rate.plt index 7f1cace..2fca1af 100644 --- a/papers/conditional-write/figs/scale-512bins-rate.plt +++ b/papers/conditional-write/figs/scale-512bins-rate.plt @@ -1,5 +1,5 @@ #set term po eps color solid "NimbusSanL-Regu" 16 fontfile "/usr/share/texmf-texlive/fonts/type1/urw/helvetic/uhvr8a.pfb" -set term po eps color solid 16 +#set term po eps color solid 16 # color blindness work around set style line 1 lc 1 lw 4 @@ -26,7 +26,9 @@ set rmargin 5 set xtics (1, 8, 16, 24, 32) set xrange [0:33] -plot "scale-512bins.dat" using 1:7 title "conditional updates" with linespoints, \ -"scale-512bins.dat" using 1:4 title "locked updates" with linespoints +plot "scale-512bins.dat" using 1:7 notitle with points lc 1, \ + "scale-512bins.avg.dat" using 1:7 title "conditional updates" with lines lc 1, \ + "scale-512bins.dat" using 1:4 notitle with points lc 2, \ + "scale-512bins.avg.dat" using 1:4 title "locked updates" with lines lc 2 #plot "< cat rand-un-read-ext4-vosd.dat |grep read" using 2:5 title "VOSD/ext4 (disk)" with points lt 1, \ diff --git a/papers/conditional-write/figs/scale-512bins.avg.dat b/papers/conditional-write/figs/scale-512bins.avg.dat new file mode 100644 index 0000000..3f4d638 --- /dev/null +++ b/papers/conditional-write/figs/scale-512bins.avg.dat @@ -0,0 +1,5 @@ +1.0 20000.0 0.0 216.648131 70000.0 1072.2 2632.0612195999997 +8.0 56000.0 0.0 494.4213434 560000.0 72756.0 17653.119012599996 +16.0 64000.0 0.0 533.318144 800000.0 213456.0 30577.525495600003 +24.0 48000.0 0.0 519.2737402 960000.0 364413.4 34537.980198599995 +32.0 57600.0 0.0 534.3734866000001 960000.0 433940.2 9323.8588624 diff --git a/papers/conditional-write/figs/scale-allbins-rate.plt b/papers/conditional-write/figs/scale-allbins-rate.plt index cc37057..d971fcf 100644 --- a/papers/conditional-write/figs/scale-allbins-rate.plt +++ b/papers/conditional-write/figs/scale-allbins-rate.plt @@ -1,5 +1,5 @@ #set term po eps color solid "NimbusSanL-Regu" 16 fontfile "/usr/share/texmf-texlive/fonts/type1/urw/helvetic/uhvr8a.pfb" -set term po eps color solid 16 +#set term po eps color solid 16 # color blindness work around set style line 1 lc 1 lw 4 @@ -26,7 +26,9 @@ set rmargin 5 set xtics (1, 8, 16, 24, 32) set xrange [0:33] -plot "scale-allbins.dat" using 1:7 title "conditional updates" with linespoints, \ -"scale-allbins.dat" using 1:4 title "locked updates" with linespoints +plot "scale-allbins.dat" using 1:7 notitle with points lc 1, \ + "scale-allbins.avg.dat" using 1:7 title "conditional updates" with lines lc 1, \ + "scale-allbins.dat" using 1:4 notitle with points lc 2, \ + "scale-allbins.dat" using 1:4 title "locked updates" with lines lc 2 #plot "< cat rand-un-read-ext4-vosd.dat |grep read" using 2:5 title "VOSD/ext4 (disk)" with points lt 1, \ diff --git a/papers/conditional-write/figs/scale-allbins.avg.dat b/papers/conditional-write/figs/scale-allbins.avg.dat new file mode 100644 index 0000000..a6ec72f --- /dev/null +++ b/papers/conditional-write/figs/scale-allbins.avg.dat @@ -0,0 +1,5 @@ +1.0 20000.0 0.0 216.58491200000003 20000.0 0.0 2711.1732736 +8.0 56000.0 0.0 491.6805944000001 3200000.0 0.0 21960.535207400004 +16.0 64000.0 0.0 522.1389048 6400000.0 0.0 41567.6530836 +24.0 48000.0 0.0 543.2123152 6000000.0 0.0 54053.664260599995 +32.0 57600.0 0.0 539.030164 8000000.0 0.0 78492.718312 hooks/post-receive --

1 0

branch, master, updated. 0d702682088fb96aa01f803571948641123a9678
by noreply＠mcs.anl.gov 29 Sep '12

29 Sep '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 0d702682088fb96aa01f803571948641123a9678 (commit) from 3dafc76b6e1a63504dee3856499528deb439386c (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 0d702682088fb96aa01f803571948641123a9678 Author: Dries Kimpe <dkimpe(a)mcs.anl.gov> Date: Sat Sep 29 19:21:57 2012 -0500 Add Argonne LLC license ----------------------------------------------------------------------- Summary of changes: papers/conditional-write/TODO | 14 ++++++++++++++ papers/conditional-write/paper.tex | 20 +++++++++++++------- 2 files changed, 27 insertions(+), 7 deletions(-) Diff of changes: diff --git a/papers/conditional-write/TODO b/papers/conditional-write/TODO index c17b83d..64c28f1 100644 --- a/papers/conditional-write/TODO +++ b/papers/conditional-write/TODO @@ -1,5 +1,19 @@ - Add governement license argonne + + - Fix figures - Send to Ja-Quel for clearance +1) some of the broader suggestions from rob: + a) reorganize implementation text and take material from vtag paper + b) suggestions on points to make in the conclusion + +2) fix the graphs (to draw lines through averages, or go back to just +points if we lack time) + +3) balance columns on last page + +4) submit paper and email co-authors with submitted copy + + diff --git a/papers/conditional-write/paper.tex b/papers/conditional-write/paper.tex index 2f162b3..b2914a7 100644 --- a/papers/conditional-write/paper.tex +++ b/papers/conditional-write/paper.tex @@ -566,13 +566,19 @@ general user-defined data procedures as well. \section*{Acknowledgments} -This material is based upon work supported by, or in part by -U.S. Department of Energy's Oak Ridge National Laboratory and -included the Extreme Scale Systems Center, located at ORNL and -funded by the DoD in part by the -``Novel Software Storage Architectures'' contract. - - +This material is based upon work supported by, or in part by U.S. Department +of Energy's Oak Ridge National Laboratory and included the Extreme Scale +Systems Center, located at ORNL and funded by the DoD in part by the ``Novel +Software Storage Architectures'' contract. + +The submitted manuscript has been created in part by UChicago Argonne, LLC, +Operator of Argonne National Laboratory (“Argonne”). Argonne, a U.S. +Department of Energy Ofﬁce of Science laboratory, is operated under Contract +No. DE-AC02-06CH11357. The U.S. Government retains for itself, and others +acting on its behalf, a paid-up nonexclusive, irrevocable worldwide license in +said article to reproduce, prepare derivative works, distribute copies to the +public, and perform publicly and display publicly, by or on behalf of the +Government. We gratefully acknowledge the computing resources provided on ``Fusion,'' a 320-node computing cluster hooks/post-receive --

1 0

branch, master, updated. 3dafc76b6e1a63504dee3856499528deb439386c
by noreply＠mcs.anl.gov 29 Sep '12

29 Sep '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 3dafc76b6e1a63504dee3856499528deb439386c (commit) from e46e54b62cc17bb63a1ae73be3b8a189d791a6e3 (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 3dafc76b6e1a63504dee3856499528deb439386c Author: Dries Kimpe <dkimpe(a)mcs.anl.gov> Date: Sat Sep 29 19:10:20 2012 -0500 Gail's comments - finished + TODO ----------------------------------------------------------------------- Summary of changes: papers/conditional-write/TODO | 5 +++++ papers/conditional-write/paper.tex | 25 +++++++++++++++---------- 2 files changed, 20 insertions(+), 10 deletions(-) create mode 100644 papers/conditional-write/TODO Diff of changes: diff --git a/papers/conditional-write/TODO b/papers/conditional-write/TODO new file mode 100644 index 0000000..c17b83d --- /dev/null +++ b/papers/conditional-write/TODO @@ -0,0 +1,5 @@ +- Add governement license argonne +- Fix figures +- Send to Ja-Quel for clearance + + diff --git a/papers/conditional-write/paper.tex b/papers/conditional-write/paper.tex index 2c6452f..2f162b3 100644 --- a/papers/conditional-write/paper.tex +++ b/papers/conditional-write/paper.tex @@ -440,11 +440,11 @@ read/modify/write operations per second as the range of target blocks is varied. Figure~\ref{fig:cond-small-conflicts} shows the percentage of conditional write operations that were successful for each data point. If all 16 concurrent operations attempt to read/modify/write the same -block, then less than 10\% of the updates are successful and we see a +block, then less than 10\% of the updates are successful, and we see a corresponding average aggregate rate of 327 ops/s. If all 16 concurrent -modify different blocks at all times, then 100\% of the updates are +operations modify different blocks at all times, then 100\% of the updates are successful and we see a corresponding average aggregate rate of 2,869 -ops/s. There is a strong correlation between the percentage of successful +ops/s. A correlation exists between the percentage of successful write operations and the observed read/modify/write performance. \begin{figure}[!t] @@ -459,15 +459,18 @@ write operations and the observed read/modify/write performance. \subsubsection{Scalability} -We next evaluate the scalability of the optimistic conditional -write primitives in comparison to traditional pessimistic locking. +We evaluated the scalability of the optimistic conditional +write primitives in comparison with traditional pessimistic locking. Figure~\ref{fig:scale-allbins-rate} shows the ideal scenario, in which the range of blocks being modified is so large that there is never any contention among concurrent updates. In this example we hold the number of servers (and number of objects) constant at 32 and vary the number of client nodes from 1 to 32. Each client node submits 16 concurrent operations so that the aggregate concurrency varies from 16 to 512. The conditional read/modify/write approach attains an average rate of 78,492 -operations per second with 512 concurrent operations. The lock-based read/modify/write -operation, in contrast, only achieves an average rate of 539 operations per +operations per second with 512 concurrent operations. The lock-based +read/modify/write +operation in contrast achieves an average rate of only 539 operations per second. The lock-based approach does not gain any additional performance -beyond 256 concurrent operations due to the fact that the lock server becomes a central bottleneck for all operations. The optimistic approach is limited only by the number of data servers and the distribution of data on those servers. +beyond 256 concurrent operations because the lock server becomes a central +bottleneck for all operations. The optimistic approach is limited only by the +number of data servers and the distribution of data on those servers. \begin{figure}[t] \centering @@ -498,8 +501,8 @@ The performance scales well up through 256 concurrent client operations. At significantly despite a modest decrease in the percentage of successful write operations. This indicates that the level of contention has a stronger impact on performance as the overall concurrency is increased. -However, even in this case, the conditional write approach still -outperforms the lock-based approach by a factor of 17x. +Even in this case, however, the conditional write approach still +outperforms the lock-based approach by a factor of 17. \begin{figure}[!t] \centering @@ -569,6 +572,8 @@ included the Extreme Scale Systems Center, located at ORNL and funded by the DoD in part by the ``Novel Software Storage Architectures'' contract. + + We gratefully acknowledge the computing resources provided on ``Fusion,'' a 320-node computing cluster operated by the Laboratory Computing Resource Center at Argonne National hooks/post-receive --

1 0

branch, master, updated. e46e54b62cc17bb63a1ae73be3b8a189d791a6e3
by noreply＠mcs.anl.gov 29 Sep '12

29 Sep '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 e46e54b62cc17bb63a1ae73be3b8a189d791a6e3 (commit) from 80238201363aceadef5af047c8016c49a5f489ed (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 e46e54b62cc17bb63a1ae73be3b8a189d791a6e3 Author: Dries Kimpe <dkimpe(a)mcs.anl.gov> Date: Sat Sep 29 18:57:24 2012 -0500 Gail's comments - continued ----------------------------------------------------------------------- Summary of changes: papers/conditional-write/paper.tex | 34 +++++++++++++++++++--------------- 1 files changed, 19 insertions(+), 15 deletions(-) Diff of changes: diff --git a/papers/conditional-write/paper.tex b/papers/conditional-write/paper.tex index 9e58e4f..2c6452f 100644 --- a/papers/conditional-write/paper.tex +++ b/papers/conditional-write/paper.tex @@ -349,22 +349,20 @@ distributed across servers algorithmically; clients can access those objects using conventional create, read, write, and delete primitives. The prototype also supports data ``forks'' which allow multiple independent byte streams to be associated with the same object. -TOSD forks are similar those offered by the Galley Parallel file +TOSD forks are similar to those offered by the Galley Parallel file system~\cite{nieuwejaar:galley}. \section{Evaluation} \label{sec:evaluation} -\subsection{Environment} - -The experiments presented here were executed on the Fusion cluster which +The experiments presented here were executed on the Fusion cluster, which is part of the Argonne Laboratory Computing Resource Center. Fusion is an IBM iDataPlex dx260 M2 system with a QDR Infiniband interconnect. Fusion has 320 compute nodes consisting of two Intel Nehalem 2.6 GHz Xeon processors with 36 GB of RAM. The Fusion nodes each contain a local disk drive, but we elected to use a ramdisk on each server for -experimental evaluation due to poor performance of the disk subsystem. The -prototype software was built using MPICH 1.2.1 and GCC 4.1.2. +experimental evaluation because of poor performance of the disk subsystem. +The prototype software was built using MPICH 1.2.1 and GCC 4.1.2. \begin{figure}[t] \centering @@ -376,7 +374,8 @@ prototype software was built using MPICH 1.2.1 and GCC 4.1.2. \includegraphics[width=3in] {cond-small-conflicts} \label{fig:cond-small-conflicts} } -\caption{16 concurrent conditional read/modify/write operations with one client node and one server node} +\caption{Sixteen concurrent conditional read/modify/write operations with one + client node and one server node} \label{fig:cond-small} \vspace{-.1in} \end{figure} @@ -395,21 +394,26 @@ updates enforced by a version number. When executed in locking mode, each concurrent operation first acquires a lock for the object, reads a value, modifies the value, writes the value, and releases the lock. The locking method utilizes -ZooKeeper~\cite{hunt2010zookeeper}. ZooKeeper is a highly reliable +ZooKeeper~\cite{hunt2010zookeeper}, a highly reliable distributed coordination service. Zookeeper runs as a standalone process -and has a C client library to link against for applications. ZooKeeper supports reliability though redundant servers -and stores data to disk. ZooKeeper is used by major organizations such as -Yahoo!, Rackspace and Zynga~\cite{zookeeper-users}. +and has a C client library to link against for applications. ZooKeeper +supports reliability through redundant servers +and stores data to disk. It is used by major organizations such as +Yahoo!, Rackspace, and Zynga~\cite{zookeeper-users}. ZooKeeper itself does have not provide a native lock mechanism, but it does offer a set of primitives which can be used to construct a lock. The Apache ZooKeeper suite publishes a recipe/protocol for how to perform -locks in ZooKeeper~\cite{zookeeper-lock}. We implemented this locking recipe in a thread-safe manner with one deviation from the published recipe: we used a 'get' operation to set a watcher instead of the -'exists' operation. This is because using 'exists' can leak resource if a -watch is set on a non-existent node~\cite{zookeeper-watch-jira}. ZooKeeper was configured with default settings except for specifying the maxClientCnxns=0 option to prevent it from limiting the number of concurrent connections. In all cases we used a single lock server but assigned a +locks in ZooKeeper~\cite{zookeeper-lock}. We implemented this locking recipe +in a thread-safe manner with one deviation from the published recipe: we used +a ``get'' operation to set a watcher instead of the +``exists'' operation. The reason is that using ``exists'' can leak a resource if a +watch is set on a nonexistent node~\cite{zookeeper-watch-jira}. ZooKeeper was configured with default settings except for specifying the maxClientCnxns=0 option to prevent it from limiting the number of concurrent connections. In all cases we used a single lock server but assigned a unique lock to each object in the storage system. The conditional update method was described in -Section~\ref{sec:implementation}. The benchmark loops over each read/modify/write sequence until the corresponding write is successfully applied. If there is no contention then this loop produces one iteration per update operation. +Section~\ref{sec:implementation}. The benchmark loops over each +read/modify/write sequence until the corresponding write is successfully +applied. If there is no contention, then this loop produces one iteration per update operation. We did not hold the total number of operations in each experiment at a fixed value. Instead, we varied the number of operations performed hooks/post-receive --

1 0

branch, master, updated. 80238201363aceadef5af047c8016c49a5f489ed
by noreply＠mcs.anl.gov 29 Sep '12

29 Sep '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 80238201363aceadef5af047c8016c49a5f489ed (commit) from e5539a92a31c0c5c8ac373b11c574e6c0721ed5e (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 80238201363aceadef5af047c8016c49a5f489ed Author: Dries Kimpe <dkimpe(a)mcs.anl.gov> Date: Sat Sep 29 18:14:10 2012 -0500 Gail's comments - continued ----------------------------------------------------------------------- Summary of changes: papers/conditional-write/paper.tex | 63 +++++++++++++++++++---------------- 1 files changed, 34 insertions(+), 29 deletions(-) Diff of changes: diff --git a/papers/conditional-write/paper.tex b/papers/conditional-write/paper.tex index 3de2964..9e58e4f 100644 --- a/papers/conditional-write/paper.tex +++ b/papers/conditional-write/paper.tex @@ -249,35 +249,39 @@ attributes~\cite{10.1109/SNAPI.2008.14}. Implementing the conditional operations on object attributes rather than on object data minimizes changes to the existing T10 standard. CAS and FA primitives can be used to implement some common data structures in storage systems, such as -linked lists, work queues and delivery counters. Later +linked lists, work queues and, delivery counters. Later work~\cite{OSDCluster08} also demonstrated that directory operations can be -supported on OSDs by using the CAS primitive to guarantee correctness. -Lang et. al. explored the possibility of adding similar atomic operations +supported on Object Storage Devices (OSD) by using the CAS primitive to guarantee correctness. +Lang et al. explored the possibility of adding similar atomic operations (FA, enqueue, and dequeue) to storage systems by way of file system extended attributes rather than objects~\cite{lang:aattrs}. A number of distributed key-value storage systems have identified -a similar need for conditional operators; such as conditional -put and delete operations in Amazon SimpleDB~\cite{simpledb}, -the watch statement in Redis~\cite{redis}, the condput operation in -Hyperdex~\cite{hyperdex_atomic}, and the conditional put, update, and +a similar need for conditional operators. These include conditional +put and delete operations in Amazon SimpleDB~\cite{simpledb}; +the watch statement in Redis~\cite{redis}; the condput operation in +Hyperdex~\cite{hyperdex_atomic}; and the conditional put, update, and delete operations in Amazon DynamoDB~\cite{dynamodb}. \section{Implementation strategies} \label{sec:implementation} -There are multiple variations to choose from when implementing a +One can choose from multiple techniques when implementing a conditional write operation in a storage system. One approach is -to implement a compare-and-swap primitive. In order to use a compare-and-swap primitive, the caller would provide the original data along with the new data for a write operation. The server would then compare the original data to the current data on disk. If the buffers match, then the server will atomically ``swap'' the data on disk with the new data buffer. -The principle advantage of +to implement a compare-and-swap primitive. In order to use a compare-and-swap +primitive, the caller would provide the original data along with the new data +for a write operation. The server would then compare the original data to the +current data on disk. If the buffers match, then the server will atomically +``swap'' the data on disk with the new data buffer. +The principal advantage of this approach is that it requires no modification to the \texttt{read()} -function and requires no additional metadata infrastructure. There are +function and requires no additional metadata infrastructure. This has two drawbacks, however. The first is that each update must first read -existing data off of disk in order to perform the comparison, which -limits performance for large updates. The second is that compare-and-swap -primitives are susceptible to the ``ABA problem''~\cite{michael2004aba} +existing data off of disk in order to perform the comparison, thereby +limiting performance for large updates. The second is that compare-and-swap +primitives are susceptible to the ``ABA problem''~\cite{michael2004aba}, which may be a concern in some use cases if the application needs to -detect whether a modification has been performed or not. +detect whether a modification has been performed. We therefore elected to use a version-based conditional update strategy. At read time, @@ -290,8 +294,8 @@ The granularity of the version number is a critical design consideration for version-based conditional primitives. A version number could apply to an entire object, a block, or an arbitrary extent. Extent-based versioning allows for smaller granularity and greater concurrency. We elected to use extent-based versioning for this -reason. Our prototype builds upon previous work in the Transactional Object -Storage Device work (TOSD, formerly known as the VOSD) which provides +reason. Our prototype builds on previous work on the Transactional Object +Storage Device (TOSD, formerly known as the VOSD), which provides efficient, byte-granular atomicity and versioning in order to support the construction of lightweight replication protocols~\cite{carns2010object}. The TOSD uses log-structured storage for all data. It maintains an index that maps @@ -305,8 +309,9 @@ storage system must either provide a compound version number (by appending multiple version numbers or hashing multiple version numbers) or promote the region to use a single consistent version number that is greater than or equal to all version numbers contained in that region. -We did not implement either approach in our prototype, and instead only -allow conditional updates to byte regions that share a single version +We did not implement either approach in our prototype; instead, we allow + +conditional updates only to byte regions that share a single version number. \begin{figure}[!t] @@ -319,30 +324,30 @@ number. The final design consideration when adding conditional operators in an HPC storage system is the question of which level of abstraction should -perform the actual conditional comparison to determine if a write will -succeed or not. For example, this comparison could be performed by the +perform the actual conditional comparison to determine whether a write will +succeed. For example, this comparison could be performed by the storage server or provided natively by the local storage abstraction. The local storage abstraction layer is likely to be the most efficient location for the comparison, and this approach requires minimal -modification the the server or the storage system protocol. The drawback +modification of the server or the storage system protocol. The drawback is that it complicates consistency if data is replicated across -servers. In particular, it may produce non-deterministic results +servers. In particular, it may produce nondeterministic results if concurrent conditional updates are applied in different orders on different replicas. To avoid this problem, we instead used the -approach shown in Figure~\ref{fig:arch-overview}. A master server is -chosen to perform the comparison atomically on behalf of all replicas. +approach shown in Figure~\ref{fig:arch-overview}. A master server +performs the comparison atomically on behalf of all replicas. If the conditional comparison succeeds, then the update is forwarded as a normal write operation to local storage and to replica servers. -This allows the master server to serialize conflicting conditional -operations and prevent non-deterministic ordering across replicas. +This approach allows the master server to serialize conflicting conditional +operations and prevent nondeterministic ordering across replicas. In this work we demonstrate our conditional write implementation using a prototype distributed object storage system that uses MPI for communication, Aesop~\cite{kimpe2012aesop} as the programming model, and the TOSD~\cite{carns2010object} for local storage. Objects are -distributed across servers algorithmically, and clients can access those +distributed across servers algorithmically; clients can access those objects using conventional create, read, write, and delete primitives. -The prototype also supports data ``forks'', which allow multiple +The prototype also supports data ``forks'' which allow multiple independent byte streams to be associated with the same object. TOSD forks are similar those offered by the Galley Parallel file system~\cite{nieuwejaar:galley}. hooks/post-receive --

1 0

branch, master, updated. e5539a92a31c0c5c8ac373b11c574e6c0721ed5e
by noreply＠mcs.anl.gov 29 Sep '12

29 Sep '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 e5539a92a31c0c5c8ac373b11c574e6c0721ed5e (commit) from 81670cf92937ab117fcedfe07349f6183805ea98 (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 e5539a92a31c0c5c8ac373b11c574e6c0721ed5e Author: Dries Kimpe <dkimpe(a)mcs.anl.gov> Date: Sat Sep 29 17:54:14 2012 -0500 First page of Gail's edits ----------------------------------------------------------------------- Summary of changes: papers/conditional-write/paper.tex | 61 +++++++++++++++++++++--------------- 1 files changed, 36 insertions(+), 25 deletions(-) Diff of changes: diff --git a/papers/conditional-write/paper.tex b/papers/conditional-write/paper.tex index e9542af..3de2964 100644 --- a/papers/conditional-write/paper.tex +++ b/papers/conditional-write/paper.tex @@ -74,7 +74,7 @@ William Gropp\IEEEauthorrefmark{5}} \\ \IEEEauthorblockA{\IEEEauthorrefmark{2}Sandia National Laboratories, Livermore, CA, USA} \IEEEauthorblockA{\IEEEauthorrefmark{3}University of Connecticut, Storrs, CT, USA} \IEEEauthorblockA{\IEEEauthorrefmark{4}Oak Ridge National Laboratory, Oak Ridge, TN, USA} -\IEEEauthorblockA{\IEEEauthorrefmark{5}University of Illinois Urbana-Champaign, +\IEEEauthorblockA{\IEEEauthorrefmark{5}University of Illinois at Urbana-Champaign, Urbana, IL, USA} } @@ -110,7 +110,8 @@ Urbana, IL, USA} %\renewcommand{\footrulewidth}{0pt} \begin{abstract} -HPC storage systems rely on access coordination to insure that concurrent +High-Performance Computing (HPC) storage systems rely on access coordination +to ensure that concurrent updates do not produce incoherent results. HPC storage systems typically employ pessimistic distributed locking to provide this functionality in cases where applications cannot perform their own coordination. This approach, @@ -140,46 +141,51 @@ of read/modify/write workloads. \IEEEpeerreviewmaketitle \section{Introduction} -Parallel applications rely on HPC storage systems to present a shared +Parallel applications rely on High-Performance Computing (HPC) storage systems to present a shared storage name space and service concurrent I/O requests from a large number of processes. Because an HPC storage system is a shared resource, some level -of access coordination is required to insure that concurrent updates do not +of access coordination is required to ensure that concurrent updates do not produce incoherent results. In some -cases this coordination is handled by the application itself (e.g. via -MPI synchronization or explicit data partitioning), while in other cases +cases this coordination is handled by the application itself (e.g., by +MPI synchronization or explicit data partitioning); in other cases coordination is provided by the storage system (e.g. POSIX file semantics). Storage system synchronization primitives are especially critical in cases where it is difficult for applications to protect -consistency on their own. Examples include: +consistency on their own. Examples include \begin{itemize} -\item concurrent name space (file or directory) updates -\item unaligned access in block-based storage systems -\item applications in which application-level coordination is not feasible (examples include loosely coupled calculations like reverse index computation, the GUPS workload, and parallel histogram creation) +\item concurrent name space (file or directory) updates, +\item unaligned access in block-based storage systems, and +\item applications in which application-level coordination is not feasible + (examples include loosely coupled calculations like reverse index + computation, the GUPS workload, and parallel histogram creation). \end{itemize} -The traditional approach to providing access coordination in these cases is via -distributed file locking in a parallel file system. There are drawbacks -to this approach, however. Distributed locking is pessimistic; it +The traditional approach to providing access coordination in these cases is +through +distributed file locking in a parallel file system. This approach has +several drawbacks. + Distributed locking is pessimistic; it introduces significant overhead even in cases where conflicts are rare. In addition, it introduces shared state on client processes. This shared state complicates fault tolerance and compromises scalability by forcing the storage system to be cognizant of client and application fault conditions. -This problem has been studied extensively in database and shared memory -literature, and a well-known alternative to locking in those arenas is +This problem has been studied extensively in the database and shared-memory +literature. A well-known alternative to locking in those arenas is to leverage conditional storage operations, such as compare-and-swap or load-link/store-conditional. These primitives can be used as building -blocks to construct a number of higher-level atomic operations. Conditional +blocks to construct a number of higher-level atomic operations. +To data, however, conditional storage operations have not been adopted -in HPC storage systems to date, however, for a number of reasons. Notably, +in HPC storage systems for a number of reasons. Notably, the traditional POSIX API does not support conditional storage primitives, and -present-day HPC storage systems do not expose any other API to client +current HPC storage systems do not expose any other API to client nodes. -In addition, there is also a lack of support for efficient +In addition, there is a lack of support for efficient comparison or conditional checks in the local storage abstractions that form -the foundation of most HPC storage systems -(e.g. Trove (PVFS), Objectstore (Ceph), and ldiskfs or ZFS +the foundation of most HPC storage systems, for example, +Trove (PVFS), Objectstore (Ceph), and ldiskfs or ZFS (Lustre). Fortunately, two storage trends are now converging in a way that makes @@ -191,9 +197,12 @@ model~\cite{Devulapalli:2007:IPF:1362622.1362659}~\cite{weil:pdsw07}~\cite{Nicol not tied to legacy POSIX semantics and can more easily be modified to expose additional synchronization primitives to applications, while still providing a solid foundation for a variety of higher level -interfaces (including POSIX). The second trend is towards increased +interfaces (including POSIX). The second trend is toward increased functionality in local storage abstractions in order to support features -such as checksumming~\cite{narayan2009uncovering}, log-structured storage~\cite{Rosenblum:1992:DIL:146941.146943}, or provenance~\cite{Muniswamy-Reddy:2006:PSS:1267359.1267363}. These features inherently require additional metadata +such as checksumming~\cite{narayan2009uncovering}, log-structured +storage~\cite{Rosenblum:1992:DIL:146941.146943}, and +provenance~\cite{Muniswamy-Reddy:2006:PSS:1267359.1267363}. These features +inherently require additional metadata support in the local storage component of a distributed storage system, and this same metadata infrastructure can often be reused to support conditional storage primitives with modest incremental complexity. @@ -218,7 +227,7 @@ database systems. Kung and Robinson~\cite{Kung:1981:OMC:319566.319567} established both the initial terminology and methodology for optimistic updates in distributed databases. They also identified the conditions in which those techniques would be more efficient than traditional locking -algorithms. Later work by Agrawal et. al. developed sophisticated +algorithms. Later work by Agrawal et al. developed sophisticated models for comparing optimistic and pessimistic algorithms in database systems~\cite{Agrawal:1987:CCP:32204.32220}. @@ -233,7 +242,9 @@ systems~\cite{Agrawal:1987:CCP:32204.32220}. %to guarantee the correct execution order of transactions. %Similar to using transaction attributes to maintain concurrency in a database system, -Devulapalli et. al. explored optimistic techniques in object storage systems by expanding the T10 API to include Compare-and-Swap (CAS) and Fetch-and-Add (FA) operations for object +Devulapalli et al. explored optimistic techniques in object storage systems by +expanding the T10 API to include compare-and-swap (CAS) and fetch-and-add (FA) +operations for object attributes~\cite{10.1109/SNAPI.2008.14}. Implementing the conditional operations on object attributes rather than on object data minimizes changes to the existing T10 standard. CAS and FA primitives can be used hooks/post-receive --

1 0

branch, master, updated. 81670cf92937ab117fcedfe07349f6183805ea98
by noreply＠mcs.anl.gov 29 Sep '12

29 Sep '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 81670cf92937ab117fcedfe07349f6183805ea98 (commit) from 3fa602620d2f63e5f9f859b11e47b1b9b312d422 (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 81670cf92937ab117fcedfe07349f6183805ea98 Author: Rob R <rross(a)mcs.anl.gov> Date: Sat Sep 29 14:58:22 2012 -0500 toning down abstract claims. ----------------------------------------------------------------------- Summary of changes: papers/conditional-write/paper.tex | 13 +++++++------ 1 files changed, 7 insertions(+), 6 deletions(-) Diff of changes: diff --git a/papers/conditional-write/paper.tex b/papers/conditional-write/paper.tex index 5624014..e9542af 100644 --- a/papers/conditional-write/paper.tex +++ b/papers/conditional-write/paper.tex @@ -113,17 +113,18 @@ Urbana, IL, USA} HPC storage systems rely on access coordination to insure that concurrent updates do not produce incoherent results. HPC storage systems typically employ pessimistic distributed locking to provide this functionality in cases -where applications cannot perform their own coordination. This approach -introduces significant performance overhead and complicates fault handling, however. +where applications cannot perform their own coordination. This approach, +however, +introduces significant performance overhead and complicates fault handling. -In this work we evaluate the viability of optimistic, conditional storage -operations as an alternative to distributed locking in HPC storage +In this work we evaluate the viability of conditional storage +operations as an optimistic alternative to distributed locking in HPC storage systems. We investigate design strategies and compare the two approaches in a prototype object storage system using a parallel read/modify/write benchmark. Our prototype illustrates that conditional operations can be easily integrated into distributed object storage systems and can also outperform standard -coordination primitives in a wide variety of workload scenarios. In fact, -our experiments show that conditional updates can achieve over two orders +coordination primitives for a simple update workload. +Our experiments show that conditional updates can achieve over two orders of magnitude higher performance than pessimistic locking for some types of read/modify/write workloads. \end{abstract} hooks/post-receive --

1 0

branch, master, updated. 3fa602620d2f63e5f9f859b11e47b1b9b312d422
by noreply＠mcs.anl.gov 29 Sep '12

29 Sep '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 3fa602620d2f63e5f9f859b11e47b1b9b312d422 (commit) via f3650ef7495ab7a1b5a2fefcbc20b976101c1f6a (commit) from 176784cd14421202ef46f4586257b46dfd7c2478 (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 3fa602620d2f63e5f9f859b11e47b1b9b312d422 Author: Phil Carns <carns(a)mcs.anl.gov> Date: Sun Sep 30 02:42:14 2012 +0800 note what versions of mpich/gcc we used commit f3650ef7495ab7a1b5a2fefcbc20b976101c1f6a Author: Phil Carns <carns(a)mcs.anl.gov> Date: Sun Sep 30 02:36:12 2012 +0800 spell check ----------------------------------------------------------------------- Summary of changes: papers/conditional-write/paper.tex | 21 +++++++++++---------- 1 files changed, 11 insertions(+), 10 deletions(-) Diff of changes: diff --git a/papers/conditional-write/paper.tex b/papers/conditional-write/paper.tex index 34a1db9..5624014 100644 --- a/papers/conditional-write/paper.tex +++ b/papers/conditional-write/paper.tex @@ -162,7 +162,7 @@ distributed file locking in a parallel file system. There are drawbacks to this approach, however. Distributed locking is pessimistic; it introduces significant overhead even in cases where conflicts are rare. In addition, it introduces shared state on client processes. This shared -state complicates fault tolerance and compromizes scalability by forcing the +state complicates fault tolerance and compromises scalability by forcing the storage system to be cognizant of client and application fault conditions. This problem has been studied extensively in database and shared memory @@ -263,7 +263,7 @@ function and requires no additional metadata infrastructure. There are two drawbacks, however. The first is that each update must first read existing data off of disk in order to perform the comparison, which limits performance for large updates. The second is that compare-and-swap -primitives are succeptable to the ``ABA problem''~\cite{michael2004aba} +primitives are susceptible to the ``ABA problem''~\cite{michael2004aba} which may be a concern in some use cases if the application needs to detect whether a modification has been performed or not. @@ -346,7 +346,8 @@ IBM iDataPlex dx260 M2 system with a QDR Infiniband interconnect. Fusion has 320 compute nodes consisting of two Intel Nehalem 2.6 GHz Xeon processors with 36 GB of RAM. The Fusion nodes each contain a local disk drive, but we elected to use a ramdisk on each server for -experimental evaluation due to poor performance of the disk subsystem. +experimental evaluation due to poor performance of the disk subsystem. The +prototype software was built using MPICH 1.2.1 and GCC 4.1.2. \begin{figure}[t] \centering @@ -379,15 +380,15 @@ for the object, reads a value, modifies the value, writes the value, and releases the lock. The locking method utilizes ZooKeeper~\cite{hunt2010zookeeper}. ZooKeeper is a highly reliable distributed coordination service. Zookeeper runs as a standalone process -and has a C client library to link against for applications. ZooKeeper supports reliabilty though redundant servers +and has a C client library to link against for applications. ZooKeeper supports reliability though redundant servers and stores data to disk. ZooKeeper is used by major organizations such as Yahoo!, Rackspace and Zynga~\cite{zookeeper-users}. ZooKeeper itself does have not provide a native lock mechanism, but it does offer a set of primitives which can be used to construct a lock. The Apache ZooKeeper suite publishes a recipe/protocol for how to perform -locks in ZooKeeper~\cite{zookeeper-lock}. We implemented this locking recipe in a thread-safe manner with one deviation from the published reciped: we used a 'get' operation to set a watcher instead of the +locks in ZooKeeper~\cite{zookeeper-lock}. We implemented this locking recipe in a thread-safe manner with one deviation from the published recipe: we used a 'get' operation to set a watcher instead of the 'exists' operation. This is because using 'exists' can leak resource if a -watch is set on a non-existant node~\cite{zookeeper-watch-jira}. ZooKeeper was configured with default settings except for specifying the maxClientCnxns=0 option to prevent it from limiting the number of concurrent connections. In all cases we used a single lock server but assigned a +watch is set on a non-existent node~\cite{zookeeper-watch-jira}. ZooKeeper was configured with default settings except for specifying the maxClientCnxns=0 option to prevent it from limiting the number of concurrent connections. In all cases we used a single lock server but assigned a unique lock to each object in the storage system. The conditional update method was described in @@ -504,7 +505,7 @@ degrade server performance. Contention on other blocks therefore becomes increasingly likely as the server takes longer to process all read/modify/write operations. This indicates that conditional operation primitives may benefit from a back off algorithm to alleviate server pressure -once high contention is observed. A server could control the back off strategy itself by delaying acknowledgements for failed conditional update requests. This would allow the back off algorithm to take advantage of statistics gathered by +once high contention is observed. A server could control the back off strategy itself by delaying acknowledgments for failed conditional update requests. This would allow the back off algorithm to take advantage of statistics gathered by servers to make intelligent back off policy decisions. \section{Conclusions} @@ -523,17 +524,17 @@ cases with little contention. We also discovered that conditional update performance may degrade significantly if steps are not taken to throttle the retry rate in high-contention scenarios. Despite this behavior, conditional updates were found to outperform a standard pessimistic -locking implementation by a wide margin in all cases. We therfore believe +locking implementation by a wide margin in all cases. We therefore believe that optimistic coordination primitives are an excellent alternative to pessimistic locking for a wide range of potential HPC storage use cases. In future work we intend to explore back off algorithms that automatically account for server processing rate and contention levels to prevent server -performance degredation in high-contention scenarios. We also hope to +performance degradation in high-contention scenarios. We also hope to explore the use of conditional updates in common file system use cases, such as maintaining a consistent file and directory name space. We will also evaluate the use of conditional updates in managing the consistency -of distributed data structures in scientific data analyis. Finally, +of distributed data structures in scientific data analysis. Finally, we would also like to evaluate the use of additional server-side atomic update operations for use in HPC environments. The techniques used to implement conditional versioned updates may also be applicable to more hooks/post-receive --

1 0

branch, master, updated. 176784cd14421202ef46f4586257b46dfd7c2478
by noreply＠mcs.anl.gov 29 Sep '12

29 Sep '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 176784cd14421202ef46f4586257b46dfd7c2478 (commit) from 64dac5fb17f8a063f35b840a03bccb46c249e578 (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 176784cd14421202ef46f4586257b46dfd7c2478 Author: Phil Carns <carns(a)mcs.anl.gov> Date: Sun Sep 30 02:32:19 2012 +0800 some of the smaller edits from rob ----------------------------------------------------------------------- Summary of changes: papers/conditional-write/paper.tex | 15 +++++++++------ 1 files changed, 9 insertions(+), 6 deletions(-) Diff of changes: diff --git a/papers/conditional-write/paper.tex b/papers/conditional-write/paper.tex index d7051a5..34a1db9 100644 --- a/papers/conditional-write/paper.tex +++ b/papers/conditional-write/paper.tex @@ -254,9 +254,10 @@ delete operations in Amazon DynamoDB~\cite{dynamodb}. \section{Implementation strategies} \label{sec:implementation} -There are multiple techniques to choose from when implementing a +There are multiple variations to choose from when implementing a conditional write operation in a storage system. One approach is -to provide a compare-and-swap primitive. The principle advantage of +to implement a compare-and-swap primitive. In order to use a compare-and-swap primitive, the caller would provide the original data along with the new data for a write operation. The server would then compare the original data to the current data on disk. If the buffers match, then the server will atomically ``swap'' the data on disk with the new data buffer. +The principle advantage of this approach is that it requires no modification to the \texttt{read()} function and requires no additional metadata infrastructure. There are two drawbacks, however. The first is that each update must first read @@ -264,7 +265,9 @@ existing data off of disk in order to perform the comparison, which limits performance for large updates. The second is that compare-and-swap primitives are succeptable to the ``ABA problem''~\cite{michael2004aba} which may be a concern in some use cases if the application needs to -detect whether a modification has been performed or not. We therefore +detect whether a modification has been performed or not. + +We therefore elected to use a version-based conditional update strategy. At read time, the storage system produces a version number for the region being read. The client can then write the same region with an incremented version @@ -272,7 +275,7 @@ number. The server will reject the write operation if the incremented version number is not strictly higher than what is already on disk. The granularity of the -version number is another critical design consideration. A version number could apply to an entire object, a block, or +version number is a critical design consideration for version-based conditional primitives. A version number could apply to an entire object, a block, or an arbitrary extent. Extent-based versioning allows for smaller granularity and greater concurrency. We elected to use extent-based versioning for this reason. Our prototype builds upon previous work in the Transactional Object @@ -363,7 +366,7 @@ experimental evaluation due to poor performance of the disk subsystem. \subsection{Benchmark} -We constructed a parallel read/modify/write benchmark for use in evaluating our prototype. The read/modify/write access pattern has applications in a variety of name space and coordination use cases, but our benchmark focuses on the most basic block (4 KiB) read/modify/write example. MPI is used to start a benchmark process on each compute node, synchronize timing, and aggregate results. Aesop +We constructed a parallel read/modify/write benchmark for use in evaluating our prototype. The read/modify/write access pattern has applications in a variety of name space and coordination use cases, but our benchmark focuses on a simple 4 KiB block read/modify/write example. MPI is used to start a benchmark process on each compute node, synchronize timing, and aggregate results. Aesop is used within each client process to generate additional concurrency. Each read/modify/write operation selects a random object and a random fork within that object to read a value in, update it, and write the change back to the same block. Forks are used for convenience as opposed to modifying different offsets in a single fork. The benchmark @@ -464,7 +467,7 @@ limits the total range of blocks being updated to 512 (16 blocks per server). In this configuration, the number of blocks to be updated is constant, but the probability of contention increases as more concurrent operations are generated. The performance of the -The lock-based approach is not significantly effected by the level of +The lock-based approach is not significantly affected by the level of contention produced by the benchmark. It therefore achieves a maximum average rate of 534 ops/s, which is within 1\% of the performance attained using pessimistic locking with no contention. The conditional results show an interesting trend, however. hooks/post-receive --

1 0