Changeset 211dc60 in trunk

Timestamp:

2017-06-05T22:26:46Z (8 years ago)

Author:

meejah <meejah@…>

Branches:

master

Children:

adb9a98

Parents:

17cff7a

git-author:

Brian Warner <warner@…> (2016-11-15 00:24:26)

git-committer:

meejah <meejah@…> (2017-06-05 22:26:46)

Message:

updates from summit

File:

• docs/specifications/servers-of-happiness.rst (modified) (1 diff)

docs/specifications/servers-of-happiness.rst ¶

@@ -109 +109 @@
 We calculate share placement like so:
 
-1. Query 2n servers for existing shares.
+0. Start with an ordered list of servers. Maybe *2N* of them.
 
-2. Construct a bipartite graph of readonly servers to shares, where an edge
-exists between an arbitrary readonly server s and an arbitrary share n if and only if s
-holds n.
+1. Query all servers for existing shares.
 
-3. Calculate the maximum matching graph of the bipartite graph. The maxmum matching
-is the matching which contains the largest possible number of edges.
+2. Construct a bipartite graph G1 of *readonly* servers to pre-existing
+   shares, where an edge exists between an arbitrary readonly server S and an
+   arbitrary share T if and only if S currently holds T.
 
-4. Construct a bipartite graph of servers to shares, removing any servers and
-shares used in the maximum matching graph from step 3. Let an edge exist between
-server s and share n if and only if s holds n.
+3. Calculate a maximum matching graph of G1 (a set of S->T edges that has or
+   is-tied-for the highest "happiness score"). There is a clever efficient
+   algorithm for this, named "Ford-Fulkerson". There may be more than one
+   maximum matching for this graph; we choose one of them arbitrarily, but
+   prefer earlier servers. Call this particular placement M1. The placement
+   maps shares to servers, where each share appears at most once, and each
+   server appears at most once.
 
-5. Calculate the maximum matching graph of the new graph.
+4. Construct a bipartite graph G2 of readwrite servers to pre-existing
+   shares. Then remove any edge (from G2) that uses a server or a share found
+   in M1. Let an edge exist between server S and share T if and only if S
+   already holds T.
 
-6. Construct a bipartite graph of servers to share, removing any servers and
-shares used in the maximum matching graphs from steps 3 and 5. Let an edge exist
-between server s and share n if and only if s can hold n.
+5. Calculate a maximum matching graph of G2, call this M2, again preferring
+   earlier servers.
 
-7. Calculate the maximum matching graph of the new graph.
+6. Construct a bipartite graph G3 of (only readwrite) servers to shares. Let
+   an edge exist between server S and share T if and only if S already has T,
+   or *could* hold T (i.e. S has enough available space to hold a share of at
+   least T's size). Then remove (from G3) any servers and shares used in M1
+   or M2 (note that we retain servers/shares that were in G1/G2 but *not* in
+   the M1/M2 subsets)
 
-8. Renew the shares on their respective servers from steps 3
-and 5.
+7. Calculate a maximum matching graph of G3, call this M3, preferring earlier
+   servers. The final placement table is the union of M1+M2+M3.
 
-9. Place share n on server s if an edge exists between s and n in the
-maximum matching graph from step 7.
+8. Renew the shares on their respective servers from M1 and M2.
 
-10. If any placements from step 7 fail, remove the server from the set of possible
-servers and regenerate the matchings.
+9. Upload share T to server S if an edge exists between S and T in M3.
 
+10. If any placements from step 9 fail, mark the server as read-only. Go back
+    to step 2 (since we may discover a server is/has-become read-only, or has
+    failed, during step 9).
+
+Rationale (Step 4): when we see pre-existing shares on read-only servers, we
+prefer to rely upon those (rather than the ones on read-write servers), so we
+can maybe use the read-write servers for new shares. If we picked the
+read-write server's share, then we couldn't re-use that server for new ones
+(we only rely upon each server for one share, more or less).
 
 Properties of Upload Strategy of Happiness