diff options
| author |   Tschaen, Brendan <ctschaen@att.com> | 2018-10-16 15:13:32 -0400 |
|---|---|---|
| committer | Tschaen, Brendan <ctschaen@att.com> | 2018-10-16 15:15:16 -0400 |
| commit | 73f8de325b31d350883f6752fb04d63c41112e8f (patch) | |
| tree | a786305e313d8cdc040b50f995ed9342173ee571 /docs | |
| parent | 389265e6342302ce5a8db5d4a3cc215e2c24c97a (diff) | |
Initial commit
Change-Id: I510baf73e4d35b651fb04e5b8e038dacb6a5a130
Issue-ID: MUSIC-149
Signed-off-by: Tschaen, Brendan <ctschaen@att.com>
Diffstat (limited to 'docs')
| -rw-r--r-- | docs/histo_graph.svg | 2 | ||||
| -rw-r--r-- | docs/redo_arch.svg | 2 | ||||
| -rw-r--r-- | docs/specs.md | 676 | ||||
| -rw-r--r-- | docs/uml.svg | 2 |
4 files changed, 682 insertions, 0 deletions
diff --git a/docs/histo_graph.svg b/docs/histo_graph.svg new file mode 100644 index 0000000..e664aaf --- /dev/null +++ b/docs/histo_graph.svg @@ -0,0 +1,2 @@ +<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"> +<svg xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" width="542px" height="271px" version="1.1"><defs/><g transform="translate(0.5,0.5)"><ellipse cx="22" cy="131" rx="20" ry="20" fill="#496e7a" stroke="#ffffff" stroke-width="4" pointer-events="none"/><ellipse cx="280" cy="131" rx="20" ry="20" fill="#496e7a" stroke="#ffffff" stroke-width="4" pointer-events="none"/><path d="M 42 131 L 42 131" fill="none" stroke="#00a8e0" stroke-width="3" stroke-miterlimit="10" pointer-events="none"/><path d="M 42 131 L 42 131 L 42 131 L 42 131 Z" fill="#00a8e0" stroke="#00a8e0" stroke-width="3" stroke-miterlimit="10" pointer-events="none"/><ellipse cx="110" cy="72" rx="20" ry="20" fill="#496e7a" stroke="#ffffff" stroke-width="4" pointer-events="none"/><ellipse cx="110" cy="187" rx="20" ry="20" fill="#496e7a" stroke="#ffffff" stroke-width="4" pointer-events="none"/><path d="M 42 131 L 56 131 Q 66 131 66 121 L 66 82 Q 66 72 72.95 72 L 79.9 72" fill="none" stroke="#00a8e0" stroke-width="3" stroke-miterlimit="10" pointer-events="none"/><path d="M 86.65 72 L 77.65 75 L 79.9 72 L 77.65 69 Z" fill="#00a8e0" stroke="#00a8e0" stroke-width="3" stroke-miterlimit="10" pointer-events="none"/><path d="M 42 131 L 56 131 Q 66 131 66 141 L 66 177 Q 66 187 72.95 187 L 79.9 187" fill="none" stroke="#00a8e0" stroke-width="3" stroke-miterlimit="10" pointer-events="none"/><path d="M 86.65 187 L 77.65 190 L 79.9 187 L 77.65 184 Z" fill="#00a8e0" stroke="#00a8e0" stroke-width="3" stroke-miterlimit="10" pointer-events="none"/><ellipse cx="280" cy="22" rx="20" ry="20" fill="#496e7a" stroke="#ffffff" stroke-width="4" pointer-events="none"/><ellipse cx="280" cy="67" rx="20" ry="20" fill="#496e7a" stroke="#ffffff" stroke-width="4" pointer-events="none"/><ellipse cx="360" cy="101" rx="20" ry="20" fill="#496e7a" stroke="#ffffff" stroke-width="4" pointer-events="none"/><path d="M 300 131 L 310 131 Q 320 131 320 121 L 320 111 Q 320 101 324.95 101 L 329.9 101" fill="none" stroke="#00a8e0" stroke-width="3" stroke-miterlimit="10" pointer-events="none"/><path d="M 336.65 101 L 327.65 104 L 329.9 101 L 327.65 98 Z" fill="#00a8e0" stroke="#00a8e0" stroke-width="3" stroke-miterlimit="10" pointer-events="none"/><path d="M 300 67 L 310 67 Q 320 67 320 77 L 320 91 Q 320 101 324.95 101 L 329.9 101" fill="none" stroke="#00a8e0" stroke-width="3" stroke-miterlimit="10" pointer-events="none"/><path d="M 336.65 101 L 327.65 104 L 329.9 101 L 327.65 98 Z" fill="#00a8e0" stroke="#00a8e0" stroke-width="3" stroke-miterlimit="10" pointer-events="none"/><ellipse cx="440" cy="159" rx="20" ry="20" fill="#496e7a" stroke="#ffffff" stroke-width="4" pointer-events="none"/><path d="M 380 101 L 390 101 Q 400 101 400 111 L 400 149 Q 400 159 404.95 159 L 409.9 159" fill="none" stroke="#00a8e0" stroke-width="3" stroke-miterlimit="10" pointer-events="none"/><path d="M 416.65 159 L 407.65 162 L 409.9 159 L 407.65 156 Z" fill="#00a8e0" stroke="#00a8e0" stroke-width="3" stroke-miterlimit="10" pointer-events="none"/><path d="M 220 217 L 310 217 Q 320 217 320 207 L 320 169 Q 320 159 330 159 L 409.9 159" fill="none" stroke="#00a8e0" stroke-width="3" stroke-miterlimit="10" pointer-events="none"/><path d="M 416.65 159 L 407.65 162 L 409.9 159 L 407.65 156 Z" fill="#00a8e0" stroke="#00a8e0" stroke-width="3" stroke-miterlimit="10" pointer-events="none"/><ellipse cx="200" cy="44" rx="20" ry="20" fill="#496e7a" stroke="#ffffff" stroke-width="4" pointer-events="none"/><ellipse cx="200" cy="102" rx="20" ry="20" fill="#496e7a" stroke="#ffffff" stroke-width="4" pointer-events="none"/><ellipse cx="200" cy="159" rx="20" ry="20" fill="#496e7a" stroke="#ffffff" stroke-width="4" pointer-events="none"/><ellipse cx="200" cy="217" rx="20" ry="20" fill="#496e7a" stroke="#ffffff" stroke-width="4" pointer-events="none"/><path d="M 130 72 L 145 72 Q 155 72 155 62 L 155 53 Q 155 44 162.45 44 L 169.9 44" fill="none" stroke="#00a8e0" stroke-width="3" stroke-miterlimit="10" pointer-events="none"/><path d="M 176.65 44 L 167.65 47 L 169.9 44 L 167.65 41 Z" fill="#00a8e0" stroke="#00a8e0" stroke-width="3" stroke-miterlimit="10" pointer-events="none"/><path d="M 220 44 L 230 44 Q 240 44 240 34 L 240 28 Q 240 22 244.95 22 L 249.9 22" fill="none" stroke="#00a8e0" stroke-width="3" stroke-miterlimit="10" pointer-events="none"/><path d="M 256.65 22 L 247.65 25 L 249.9 22 L 247.65 19 Z" fill="#00a8e0" stroke="#00a8e0" stroke-width="3" stroke-miterlimit="10" pointer-events="none"/><path d="M 220 44 L 230 44 Q 240 44 240 54 L 240 60.5 Q 240 67 244.95 67 L 249.9 67" fill="none" stroke="#00a8e0" stroke-width="3" stroke-miterlimit="10" pointer-events="none"/><path d="M 256.65 67 L 247.65 70 L 249.9 67 L 247.65 64 Z" fill="#00a8e0" stroke="#00a8e0" stroke-width="3" stroke-miterlimit="10" pointer-events="none"/><path d="M 220 102 L 230 102 Q 240 102 240 112 L 240 121.5 Q 240 131 244.95 131 L 249.9 131" fill="none" stroke="#00a8e0" stroke-width="3" stroke-miterlimit="10" pointer-events="none"/><path d="M 256.65 131 L 247.65 134 L 249.9 131 L 247.65 128 Z" fill="#00a8e0" stroke="#00a8e0" stroke-width="3" stroke-miterlimit="10" pointer-events="none"/><path d="M 130 72 L 145 72 Q 155 72 155 82 L 155 92 Q 155 102 162.45 102 L 169.9 102" fill="none" stroke="#00a8e0" stroke-width="3" stroke-miterlimit="10" pointer-events="none"/><path d="M 176.65 102 L 167.65 105 L 169.9 102 L 167.65 99 Z" fill="#00a8e0" stroke="#00a8e0" stroke-width="3" stroke-miterlimit="10" pointer-events="none"/><path d="M 220 159 L 230 159 Q 240 159 240 149 L 240 140 Q 240 131 244.95 131 L 249.9 131" fill="none" stroke="#00a8e0" stroke-width="3" stroke-miterlimit="10" pointer-events="none"/><path d="M 256.65 131 L 247.65 134 L 249.9 131 L 247.65 128 Z" fill="#00a8e0" stroke="#00a8e0" stroke-width="3" stroke-miterlimit="10" pointer-events="none"/><path d="M 130 187 L 145 187 Q 155 187 155 177 L 155 168 Q 155 159 162.45 159 L 169.9 159" fill="none" stroke="#00a8e0" stroke-width="3" stroke-miterlimit="10" pointer-events="none"/><path d="M 176.65 159 L 167.65 162 L 169.9 159 L 167.65 156 Z" fill="#00a8e0" stroke="#00a8e0" stroke-width="3" stroke-miterlimit="10" pointer-events="none"/><ellipse cx="520" cy="131" rx="20" ry="20" fill="#496e7a" stroke="#ffffff" stroke-width="4" pointer-events="none"/><path d="M 300 22 L 430 22 Q 440 22 440 32 L 440 121 Q 440 131 450 131 L 489.9 131" fill="none" stroke="#00a8e0" stroke-width="3" stroke-miterlimit="10" pointer-events="none"/><path d="M 496.65 131 L 487.65 134 L 489.9 131 L 487.65 128 Z" fill="#00a8e0" stroke="#00a8e0" stroke-width="3" stroke-miterlimit="10" pointer-events="none"/><g transform="translate(34.5,233.5)"><switch><foreignObject style="overflow:visible;" pointer-events="all" width="63" height="36" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility"><div xmlns="http://www.w3.org/1999/xhtml" style="display: inline-block; font-size: 32px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; vertical-align: top; width: 63px; white-space: nowrap; word-wrap: normal; text-align: center;"><div xmlns="http://www.w3.org/1999/xhtml" style="display:inline-block;text-align:inherit;text-decoration:inherit;">Split</div></div></foreignObject><text x="32" y="34" fill="#000000" text-anchor="middle" font-size="32px" font-family="Helvetica">Split</text></switch></g><g transform="translate(354.5,233.5)"><switch><foreignObject style="overflow:visible;" pointer-events="all" width="90" height="36" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility"><div xmlns="http://www.w3.org/1999/xhtml" style="display: inline-block; font-size: 32px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; vertical-align: top; width: 92px; white-space: nowrap; word-wrap: normal; text-align: center;"><div xmlns="http://www.w3.org/1999/xhtml" style="display:inline-block;text-align:inherit;text-decoration:inherit;">Merge</div></div></foreignObject><text x="45" y="34" fill="#000000" text-anchor="middle" font-size="32px" font-family="Helvetica">Merge</text></switch></g><path d="M 130 187 L 145 187 Q 155 187 155 197 L 155 207 Q 155 217 162.45 217 L 169.9 217" fill="none" stroke="#00a8e0" stroke-width="3" stroke-miterlimit="10" pointer-events="none"/><path d="M 176.65 217 L 167.65 220 L 169.9 217 L 167.65 214 Z" fill="#00a8e0" stroke="#00a8e0" stroke-width="3" stroke-miterlimit="10" pointer-events="none"/><path d="M 460 159 L 470 159 Q 480 159 480 149 L 480 140 Q 480 131 484.95 131 L 489.9 131" fill="none" stroke="#00a8e0" stroke-width="3" stroke-miterlimit="10" pointer-events="none"/><path d="M 496.65 131 L 487.65 134 L 489.9 131 L 487.65 128 Z" fill="#00a8e0" stroke="#00a8e0" stroke-width="3" stroke-miterlimit="10" pointer-events="none"/></g></svg>
\ No newline at end of file diff --git a/docs/redo_arch.svg b/docs/redo_arch.svg new file mode 100644 index 0000000..680c5ba --- /dev/null +++ b/docs/redo_arch.svg @@ -0,0 +1,2 @@ +<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"> +<svg xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" width="511px" height="333px" version="1.1"><defs/><g transform="translate(0.5,0.5)"><rect x="36" y="1" width="110" height="50" fill="none" stroke="#468e9f" stroke-width="3" pointer-events="none"/><g transform="translate(59.5,19.5)"><switch><foreignObject style="overflow:visible;" pointer-events="all" width="62" height="12" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility"><div xmlns="http://www.w3.org/1999/xhtml" style="display: inline-block; font-size: 12px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; vertical-align: top; white-space: nowrap; text-align: center;"><div xmlns="http://www.w3.org/1999/xhtml" style="display:inline-block;text-align:inherit;text-decoration:inherit;">ThreadPool</div></div></foreignObject><text x="31" y="12" fill="#000000" text-anchor="middle" font-size="12px" font-family="Helvetica">ThreadPool</text></switch></g><rect x="191" y="11" width="110" height="30" fill="none" stroke="#468e9f" stroke-width="3" pointer-events="none"/><g transform="translate(204.5,19.5)"><switch><foreignObject style="overflow:visible;" pointer-events="all" width="83" height="12" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility"><div xmlns="http://www.w3.org/1999/xhtml" style="display: inline-block; font-size: 12px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; vertical-align: top; white-space: nowrap; text-align: center;"><div xmlns="http://www.w3.org/1999/xhtml" style="display:inline-block;text-align:inherit;text-decoration:inherit;">Task: Runnable</div></div></foreignObject><text x="42" y="12" fill="#000000" text-anchor="middle" font-size="12px" font-family="Helvetica">Task: Runnable</text></switch></g><rect x="36" y="201" width="110" height="30" fill="none" stroke="#468e9f" stroke-width="3" pointer-events="none"/><g transform="translate(52.5,209.5)"><switch><foreignObject style="overflow:visible;" pointer-events="all" width="76" height="12" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility"><div xmlns="http://www.w3.org/1999/xhtml" style="display: inline-block; font-size: 12px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; vertical-align: top; white-space: nowrap; text-align: center;"><div xmlns="http://www.w3.org/1999/xhtml" style="display:inline-block;text-align:inherit;text-decoration:inherit;">RedoManager<br /></div></div></foreignObject><text x="38" y="12" fill="#000000" text-anchor="middle" font-size="12px" font-family="Helvetica">RedoManager<br></text></switch></g><rect x="1" y="101" width="180" height="50" fill="none" stroke="#468e9f" stroke-width="3" pointer-events="none"/><g transform="translate(17.5,112.5)"><switch><foreignObject style="overflow:visible;" pointer-events="all" width="147" height="26" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility"><div xmlns="http://www.w3.org/1999/xhtml" style="display: inline-block; font-size: 12px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; vertical-align: top; white-space: nowrap; text-align: center;"><div xmlns="http://www.w3.org/1999/xhtml" style="display:inline-block;text-align:inherit;text-decoration:inherit;">TaskPriorityQueue: <br />BlockingQueue<Runnable><br /></div></div></foreignObject><text x="74" y="19" fill="#000000" text-anchor="middle" font-size="12px" font-family="Helvetica">TaskPriorityQueue: <br>BlockingQueue<Runnable><br></text></switch></g><rect x="267" y="110" width="158" height="30" fill="none" stroke="#468e9f" stroke-width="3" pointer-events="none"/><g transform="translate(281.5,118.5)"><switch><foreignObject style="overflow:visible;" pointer-events="all" width="128" height="12" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility"><div xmlns="http://www.w3.org/1999/xhtml" style="display: inline-block; font-size: 12px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; vertical-align: top; white-space: nowrap; text-align: center;"><div xmlns="http://www.w3.org/1999/xhtml" style="display:inline-block;text-align:inherit;text-decoration:inherit;">PrefetchedData: Cache<br /></div></div></foreignObject><text x="64" y="12" fill="#000000" text-anchor="middle" font-size="12px" font-family="Helvetica">PrefetchedData: Cache<br></text></switch></g><rect x="371" y="204" width="138" height="40" fill="none" stroke="#468e9f" stroke-width="3" pointer-events="none"/><g transform="translate(384.5,210.5)"><switch><foreignObject style="overflow:visible;" pointer-events="all" width="111" height="26" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility"><div xmlns="http://www.w3.org/1999/xhtml" style="display: inline-block; font-size: 12px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; vertical-align: top; white-space: nowrap; text-align: center;"><div xmlns="http://www.w3.org/1999/xhtml" style="display:inline-block;text-align:inherit;text-decoration:inherit;">«interface»<br /><b>RedoManagerLogic</b></div></div></foreignObject><text x="56" y="19" fill="#000000" text-anchor="middle" font-size="12px" font-family="Helvetica">«interface»<br><b>RedoManagerLogic</b></text></switch></g><path d="M 163.97 26 L 186.53 26" fill="none" stroke="#000000" stroke-width="2" stroke-miterlimit="10" pointer-events="none"/><path d="M 147.97 26 L 155.97 21.29 L 163.97 26 L 155.97 30.71 Z" fill="none" stroke="#000000" stroke-width="2" stroke-miterlimit="10" pointer-events="none"/><path d="M 174.76 33 L 188.76 26 L 174.76 19" fill="none" stroke="#000000" stroke-width="2" stroke-miterlimit="10" pointer-events="none"/><g transform="translate(147.5,8.5)"><switch><foreignObject style="overflow:visible;" pointer-events="all" width="6" height="11" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility"><div xmlns="http://www.w3.org/1999/xhtml" style="display: inline-block; font-size: 11px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; vertical-align: top; white-space: nowrap;"><div xmlns="http://www.w3.org/1999/xhtml" style="display:inline-block;text-align:inherit;text-decoration:inherit;background-color:#ffffff;">1</div></div></foreignObject><text x="3" y="11" fill="#000000" text-anchor="middle" font-size="11px" font-family="Helvetica">1</text></switch></g><rect x="23.5" y="281" width="135" height="50" fill="none" stroke="#468e9f" stroke-width="3" pointer-events="none"/><g transform="translate(39.5,299.5)"><switch><foreignObject style="overflow:visible;" pointer-events="all" width="103" height="12" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility"><div xmlns="http://www.w3.org/1999/xhtml" style="display: inline-block; font-size: 12px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; vertical-align: top; white-space: nowrap; text-align: center;"><div xmlns="http://www.w3.org/1999/xhtml" style="display:inline-block;text-align:inherit;text-decoration:inherit;">HistoryGraph: DFG<br /></div></div></foreignObject><text x="52" y="12" fill="#000000" text-anchor="middle" font-size="12px" font-family="Helvetica">HistoryGraph: DFG<br></text></switch></g><path d="M 91 201 L 91 155.47" fill="none" stroke="#000000" stroke-width="2" stroke-miterlimit="10" stroke-dasharray="6 6" pointer-events="none"/><path d="M 98 167.24 L 91 153.24 L 84 167.24" fill="none" stroke="#000000" stroke-width="2" stroke-miterlimit="10" pointer-events="none"/><g transform="translate(80.5,170.5)"><switch><foreignObject style="overflow:visible;" pointer-events="all" width="20" height="11" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility"><div xmlns="http://www.w3.org/1999/xhtml" style="display: inline-block; font-size: 11px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; vertical-align: top; white-space: nowrap; text-align: center;"><div xmlns="http://www.w3.org/1999/xhtml" style="display:inline-block;text-align:inherit;text-decoration:inherit;">Use</div></div></foreignObject><text x="10" y="11" fill="#000000" text-anchor="middle" font-size="11px" font-family="Helvetica">Use</text></switch></g><path d="M 91 51 L 91 96.53" fill="none" stroke="#000000" stroke-width="2" stroke-miterlimit="10" stroke-dasharray="6 6" pointer-events="none"/><path d="M 84 84.76 L 91 98.76 L 98 84.76" fill="none" stroke="#000000" stroke-width="2" stroke-miterlimit="10" pointer-events="none"/><g transform="translate(80.5,70.5)"><switch><foreignObject style="overflow:visible;" pointer-events="all" width="20" height="11" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility"><div xmlns="http://www.w3.org/1999/xhtml" style="display: inline-block; font-size: 11px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; vertical-align: top; white-space: nowrap; text-align: center;"><div xmlns="http://www.w3.org/1999/xhtml" style="display:inline-block;text-align:inherit;text-decoration:inherit;">Use</div></div></foreignObject><text x="10" y="11" fill="#000000" text-anchor="middle" font-size="11px" font-family="Helvetica">Use</text></switch></g><path d="M 301 26 L 336 26 Q 346 26 346 36 L 346 105.53" fill="none" stroke="#000000" stroke-width="2" stroke-miterlimit="10" stroke-dasharray="6 6" pointer-events="none"/><path d="M 339 93.76 L 346 107.76 L 353 93.76" fill="none" stroke="#000000" stroke-width="2" stroke-miterlimit="10" pointer-events="none"/><g transform="translate(335.5,40.5)"><switch><foreignObject style="overflow:visible;" pointer-events="all" width="20" height="11" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility"><div xmlns="http://www.w3.org/1999/xhtml" style="display: inline-block; font-size: 11px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; vertical-align: top; white-space: nowrap; text-align: center;"><div xmlns="http://www.w3.org/1999/xhtml" style="display:inline-block;text-align:inherit;text-decoration:inherit;">Use</div></div></foreignObject><text x="10" y="11" fill="#000000" text-anchor="middle" font-size="11px" font-family="Helvetica">Use</text></switch></g><path d="M 146 209 L 336 209 Q 346 209 346 199 L 346 144.47" fill="none" stroke="#000000" stroke-width="2" stroke-miterlimit="10" stroke-dasharray="6 6" pointer-events="none"/><path d="M 353 156.24 L 346 142.24 L 339 156.24" fill="none" stroke="#000000" stroke-width="2" stroke-miterlimit="10" pointer-events="none"/><g transform="translate(270.5,203.5)"><switch><foreignObject style="overflow:visible;" pointer-events="all" width="20" height="11" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility"><div xmlns="http://www.w3.org/1999/xhtml" style="display: inline-block; font-size: 11px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; vertical-align: top; white-space: nowrap; text-align: center;"><div xmlns="http://www.w3.org/1999/xhtml" style="display:inline-block;text-align:inherit;text-decoration:inherit;">Use</div></div></foreignObject><text x="10" y="11" fill="#000000" text-anchor="middle" font-size="11px" font-family="Helvetica">Use</text></switch></g><path d="M 163.97 224 L 366.53 224" fill="none" stroke="#000000" stroke-width="2" stroke-miterlimit="10" pointer-events="none"/><path d="M 147.97 224 L 155.97 219.29 L 163.97 224 L 155.97 228.71 Z" fill="#000000" stroke="#000000" stroke-width="2" stroke-miterlimit="10" pointer-events="none"/><path d="M 354.76 231 L 368.76 224 L 354.76 217" fill="none" stroke="#000000" stroke-width="2" stroke-miterlimit="10" pointer-events="none"/><g transform="translate(175.5,209.5)"><switch><foreignObject style="overflow:visible;" pointer-events="all" width="6" height="11" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility"><div xmlns="http://www.w3.org/1999/xhtml" style="display: inline-block; font-size: 11px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; vertical-align: top; white-space: nowrap;"><div xmlns="http://www.w3.org/1999/xhtml" style="display:inline-block;text-align:inherit;text-decoration:inherit;">1</div></div></foreignObject><text x="3" y="11" fill="#000000" text-anchor="middle" font-size="11px" font-family="Helvetica">1</text></switch></g><path d="M 91 248.97 L 91 276.53" fill="none" stroke="#000000" stroke-width="2" stroke-miterlimit="10" pointer-events="none"/><path d="M 91 232.97 L 95.71 240.97 L 91 248.97 L 86.29 240.97 Z" fill="#000000" stroke="#000000" stroke-width="2" stroke-miterlimit="10" pointer-events="none"/><path d="M 84 264.76 L 91 278.76 L 98 264.76" fill="none" stroke="#000000" stroke-width="2" stroke-miterlimit="10" pointer-events="none"/><g transform="translate(92.5,240.5)"><switch><foreignObject style="overflow:visible;" pointer-events="all" width="6" height="11" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility"><div xmlns="http://www.w3.org/1999/xhtml" style="display: inline-block; font-size: 11px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; vertical-align: top; white-space: nowrap;"><div xmlns="http://www.w3.org/1999/xhtml" style="display:inline-block;text-align:inherit;text-decoration:inherit;">1</div></div></foreignObject><text x="3" y="11" fill="#000000" text-anchor="middle" font-size="11px" font-family="Helvetica">1</text></switch></g><path d="M 219 41 L 228.5 41 Q 238 41 238 51 L 238 161 Q 238 171 228 171 L 129 171 Q 119 171 119 181 L 119 194.29" fill="none" stroke="#00a8e0" stroke-width="3" stroke-miterlimit="10" stroke-dasharray="9 9" pointer-events="none"/><path d="M 113.5 186.65 L 119 197.65 L 124.5 186.65" fill="none" stroke="#00a8e0" stroke-width="3" stroke-miterlimit="10" pointer-events="none"/><g transform="translate(222.5,131.5)"><switch><foreignObject style="overflow:visible;" pointer-events="all" width="31" height="36" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility"><div xmlns="http://www.w3.org/1999/xhtml" style="display: inline-block; font-size: 32px; font-family: Helvetica; color: black; line-height: 1.2; vertical-align: top; white-space: nowrap; text-align: center;"><div xmlns="http://www.w3.org/1999/xhtml" style="display:inline-block;text-align:inherit;text-decoration:inherit;"><font style="font-size: 12px">return</font></div></div></foreignObject><text x="16" y="34" fill="black" text-anchor="middle" font-size="32px" font-family="Helvetica">[Not supported by viewer]</text></switch></g></g></svg>
\ No newline at end of file diff --git a/docs/specs.md b/docs/specs.md new file mode 100644 index 0000000..656f045 --- /dev/null +++ b/docs/specs.md @@ -0,0 +1,676 @@ +# Architecture + +## Music/Cassandra Tables + +### Transaction Information Table (TIT) + +This table contains the entities that are locked to perform a transaction on a partition, it contains an ordered array that contains information of the transactions. + +A row is associated with a specific partition. + +There can be more than one row associated with a partition. But only one is active at any given time. There are two main reasons associated with creating a new TIT row: +* Partition merge/split +* The REDO array is too big, and it's better to start a new row + +This is a type of table, and there can be many instances of this table in Music. Reasons to have more than one table: +* One table per replication policy, for example, there could be one TIT table with a replication factor of 3 and one TIT table with a replication factor of 5. +* Other policy requirements + +#### Columns + +* **id**: UUID + - The id of this row + - **Note**: Later we could force the index to follow a certain pattern, such that the rows of a given MDBC Server are located as close as possible to that server, without violating any other policy associated with the data. +* **redo**: Array<Tuple<Text,Tuple<Text,varint>> + - Array (order-matters) of <TableName,Index> associated with the Redo Records that were applied to this partition +* **partition**: UUID + - The id of the partition associated with this transaction +* **latestapplied**: Int + - Integer associated with the latest RedoRecord applied from the Redo column into the data tables in Music. +* **applied**: boolean + - Flag that indicates that this row Tx's were already committed to the data tables + +#### Primary + +(Partition) + +#### Clustering + +(Index) + +### Redo Records Table (RRT) + +This table is the one that contains the TransactionsDigests. + +There is one row per transaction. + +There is no need to lock on this table. + +This is an append/remove only table, no updates are going to be performed. +* Removes are an optimization, not a correctness requirement +* Removes are only executed when the transaction was completely applied to the data tables and all tables that are pointing to this row are already removed. + +#### Columns + +* **leaseid**: text + * Id of the lease that was used to process the transaction associated with the row in TIT +* **leasecounter**: varint + * Transaction number (counter of the transactions performed so far using the lock in leaseid) +* **transactiondigest**: text + * Serialized transaction digest, can be considered a blob + +#### Primary + +(leaseid,leasecounter) + +#### Clustering + +None + +### TableToPartition Table (TTP) + +This table maps each table to the current (and previous) partitions. + +#### Columns + +* **TableName**: Text + - Name of the table to which partitions are being associated +* **Partition**: UUID + - Current partition that holds this table +* **PreviousPartitions**: Set<UUID> + - Name of all the previous partitions (inclusive of the current partition) + +#### Primary + +(Table) + +#### Clustering + +None + +### PartitionInfo Table (PI) + +This table contains information about a partition. Contains information about the latest Tit row to be locked if this partition wants to be held. The tables associated with this partition and other information of the partition. + +#### Columns + +* **Partition**: UUID + - Name of the partition that this row describe +* **LatestTitTable**: Text + - Name of the table that contains the latest TransactionInformation row associated with this partition +* **LatestTitIndex**: UUID + - Latest index (row) in the previous table, that is currently is being updated with transactions in this partition +* **Tables**: Set<Text> + - All tables that are contained within this partition +* **ReplicationFactor**: Int +* **CurrentOwner**: Text + - URL address associated with the current owner + +#### Primary + +(Partition) + +#### Clustering + +None + +### RedoHistory Table (RH) + +This table represents the Directed Graph that forms the history of REDO logs. Given that we create new REDO logs on each new repartition (or due to other reasons), we need to keep track of the changes and the order of the REDO logs. An example of the repartitions can be seen in [figure 3](#figure-3). + +#### Columns +* **Partition**: uuid + - Partition +* **RedoTable**:Text + - TIT table at this point in time for the Partition +* **RedoIndex**:UUID + - TIT Index for the previous Table +* **PreviousRedo**: Set<Tuple<Text,UUID>> + - Contain + +#### Primary +(Partition) + +#### Clustering +(RedoTable,RedoIndex) + +## Server Architecture + +As shown in [figure 1](#figure-1). The MDBC server is composed of the following components: + +* **RunningQueries** +* **LocalStagingTable** +* **MusicInterface** +* **MusicSQLManager** +* **SQL** + +### Figure 1 + + +**Server Architecture** + +### RunningQueries +This is an in-memory data structure that contains the progress of each transaction being executed. Each transaction holds information about: + +* **LTxId:** local transaction id, unsigned integer +* **CommitRequested** bool indicating if the user tries to commit the request already. +* **SQLDone:** bool indicating if SQL was already committed, atomic bool +* **MusicDone:** bool indicating if music commit was already performed, atomic bool +* **Connection:** reference to a connection object. This is used to complete a commit if it failed in the original thread. +* **Timestamp:** last time this data structure was updated +* **RedoRecordId:** id of the redo record when it was already added to the RRT (it contains the info to the table and index) + +### LocalStagingTable + +This is a serializable in-memory data-structure that contains the information about the changes that were updated by the SQL database for a given transaction. When the transaction is committed, this staging table is freeze and serialized to a string, and committed to Music. See the [algorithms section](#transaction-commit). + +There is one table per client connection. + +It has one main operation: + +```Java +void addOperation(String key, OperationType op, JSONObject oldValue, JSONObject newValue); +``` + +### MusicInterface + +This is the layer that interacts with Music. There is only one instance per MDBC server. It is in charge of holding locks and executing get/puts to Music, following the corresponding locking mechanisms. This object is also used in the MusicSQLManager, so a reference to it is passed when a MusicSQLManager is created. + +### MusicSQLManager + +When a connection is created from a new MDBC client, a Connection object is created. MusicSQLManager is the object that handles the main operations of a connection that translates operation between SQL and Music. + +There is one object of this type for each client connection. + +### SQL or DBInterface + +This interface the main operations that the MusicSQLMAnager performs with the SQL layer. + +## REDO Recovery Architecture + +[Figure 2](#figure-2) shows the main components used to recover using the REDO log. First, we are going to analyze what is the REDO history associated with a given node, and then describe each of the components in figure 2 + +### Figure 2 + + +**Redo Spec Architecture** + +### REDO History + +Given that new Redo log rows are created in TIT each time, the system is repartitioned, then a history is created as shown in [figure 3](#figure-3). Each node represents a give TIT row, and the graph is a directed acyclic graph. + +#### Figure 3 + + +**Redo History Directed Graph** + +#### Properties + +* The are only two types of repartition: split in two or merge two. +* Each partition can only be split into two partitions +* Only two partitions can be merged into a new partition +* Sometimes one node is transformed into a new node, without split or merge. This can happen due to the reasons explained in previous sections, such as a TIT row being too big. +* Each partition is going to have a new different name (e.g. use UUID to name them) +* On partition, a new TIT row is created +* The replication policy used is the max of all the tables that are contained within the partition. + +#### Node + +Each node in the graph contains the following information + +* **RedoTable**: info from RH table +* **RedoIndex**: info from RH table +* **Tables**: tables that are going to be recovered in that node, obtained from the partition in RH table. +* **TIT Metadata Read**: it is a boolean flag that indicates that the associated metadata was already downloaded. +* **ParentsDoneCounter**: it is a counter that is increased each time one of the parents of the node was successfully applied. +* **LastAppliedChange**: last change applied from this Redo Index to this local MDBC server. +* **TxDigestDownloaded**: a boolean flag that indicates that the TxDigest download task was already downloaded + +All this information is used to implement the algorithms to parallelize the REDO operations. + +### Redo Recovery Execution + +We decomposed the recovery algorithm into multiple independent tasks that are going to be executed by a pool of threads. There are three main types of tasks: + +1. Download Metadata (embarrassingly parallel) +2. Download Transaction Digests (embarrassingly parallel) +3. Apply Digests (Sequential with concurrency) + +To save memory usage, and avoid pulling too much data before it is actually consumed, we cannot perform this tasks in this same order. Additionally, prefetched data can be erased, if there is too much data downloaded that was not committed in time. + +### RedoManager + +This is the entity in charge of defining the next tasks to execute and to initialize the REDO recovery and all the required data structures, including the thread pool. + +### RedoManagerLogic + +This is the logic within the redo manager. It is created to allow extension of the algorithms for selecting the tasks. + +#### Interface +```java +void init(HistoryGraph history); +List<Task> getInitialTasks(); +List<Task> setCompleted(Task completedTask); +boolean isDone(); +``` + +### PrefetchedData + +This is going to contain the results of tasks of type 1. and 2. If the recovery algorithm overprovisioned memory, the RedoManager can request to delete the least important data (further to the right in [figure 3](#figure-3)), and it would return the task that was used to generate it. Such that it can be read to the TaskPriorityQueue + + +#### Interface +```java +Metadata getMetadata(int NoodeIdx); +Digest getTransaction(int NodeIdx, String table, UUID row); +Task deleteLessImportant(); +void addMetadata(int NodeIdx, Metadata meta, Task task); +void addDigest(int NodeIdx, String table, UUID row, TxDigest tx, Task task); +long getSize(); +``` + +### HistoryGraph + +This is the object that is going to model the REDO history and will be used to create the plan for recovery. Additionally, it would hold the required data to select the next tasks to perform by the RedoManager. It contains basic graph operations used by the RedoManager. + +#### Interface +```java +long getSize(); +void addNode(String redoTable, String redoIndex); +void addFutureLink(String redoTable, String redoIndex, String previousRedoTable, String previousRedoIndex); +List<Nodes> getRoots(); +List<Nodes> getParents(Node node); +List<Nodes> getChildren(Node node); +List<Nodes> getChildren(List<Node> node); +Iterator<Nodes> getAll(); +Node getNode(String id); +void deleteTableFromPredecessor(String id, String table); +void increaseParentCompleted(String id); +void readyToRun(String id, PrefetchedData data); +void setMetadataDownloaded(String id); +void setDigestDownloaded(String id); +void setRestored(String id); +``` + +### TaskPriorityQueue +This is a special type of priority queue, used to hold the following tasks to be executed by the thread pool. The priority is defined by a combination of operation and the node that is associated. + +The tasks have the following priorities: +1. DownloadMetadata: 3 +2. DownloadDigests: 2 +3. ApplyDigest: 4 (highest) +4. DownloadHistory: 1 (lowest) + +These priorities mean, that we focus on applying the digest more than downloading, tasks of type 3 are only created when all the related data was already downloaded, and the predecessors were already applied. + +The nodes have the following priorities. We enumerate the nodes in the HistoryGraph using Breath-first search, the lower the number, the higher the priority. Intuitively, what this means is that nodes closer to the root, e.g. that are going to be executed first in the recovery, are downloaded first. + +#### Interface +```java +void AddOp(Task task, PriorityLevel prio, String nodeId); +void AddOps(List<Task> tasks) { + +}); +Task GetNextTask(); +boolean freezeBelowLevel(PriorityLevel prio);// This function is only used when the memory is overprovisioned, and we don't want to allow more tasks of type 1 and 2 but is left generic, for future use +boolean restart();// To be used after a freeze was applied +``` + +### ThreadPool + +Normal Java ThreadPool. It's composed of a set of available threads that will run the threads that are stored in the TaskPriorityQueue. + +### Task + +This inherits from Runnable. And it executes one of three types of tasks that was presented in the section [Redo Recovery Execution](#redo-recovery-execution). When this operation is over, it indicates the RedoManager, that the task was successfully completed. Additionally, it calls the corresponding functions in the HistoryGraph + +## Algorithms + +This section describes the main operations that are performed in an ETDB system. + +### Bootup +```python +def boot(tables): + # This function get the set of partitions that are currently associated with the tables + # and also the set of all the partitons that have been associated with those tables + P,oldP = getAllPartitionsFromTTP(tables) + # Lock all partitions, this is done using the Music Interface + for p in P: + locked = lockPartition(p) + # If lock was not succesful + if not locked: + # Explained in another section + result = requestLockRelease(p,"FullOwnership",Max) + if not result: + raise exception + else: + locked = lockPartition(p) + if not locked: + raise exception + # Merge all partitions, explained in another section, using MusicInterface + mergePartitions(tables,P,this.address) + # Pull data from Music data tables, using the MusicSQLManager + pullDataFromMusic(tables,P) + # Apply Redo, using the Redo Recovery + RedoRecovery(tables,P,oldP) +``` + +#### Request Lock Release +```python +def requestLockRelease(p,ownershipType,priority): + # Obtain the url of the owner from the PI table + owner = getCurrentOwnerFromPI(p) + # Request ownership using GRPC + # Current owner receives the query and using the ownership type and prioriy, it decides is if release it + # Releases the lock if required + # Replies with decision + result = remoteOwnershipRequest(owner,p,ownershiptType,priority) + return result +``` + +#### Partitions Merge +```python +def mergePartitions(tables,partitions,newOwner): + # Create a new name using cassandra UUID + newPartitionName = createNewPartitionName() + # Assumption: locks are already held by the local ET node + replicationPolicy = getMaxReplicationFactor(tables) + # Reuse Tit Table if possible, if not create a new one with the corresponding policy + # Why this? The TIT table should be close to this ETDB node + titTableName = getTitTableWithReplicationFactor(replicationPolicy) + # This function creates new row in the table titTableName + # The row has the following values: an empty redo list, lastApplied = -1 + # and applied = false + titIndex = musicInterface.lockAndCreateNewRow(titTableName,newPartitionName) + # this function should change the RedoRecordsTable used for transactions in partition newPartitionName, this is changed to the local state, not in Music + # this is going to create a new records table if required + # Again the redo records table should be close to this ETDB node + changeRedoRecordsTable(newPartitionName,replicationPolicy) + for table in tables: + # This function changes the TTP table + # It appends newPartitionName to PreviousPartitions and change Partition to newPartitionName + # into the row with table "table" + # This needs to be performed with an atomicPut + musicInterface.appendNewPartitionToTTP(table,newPartitionName) + # Create a new row in PI with the corresponding information + musicInterface.addPartitionToPI(newPartitionName,titTableName,titIndex,tables,replicationPolicy.factor,newOwner) + previousRedo = [] + # Get the previous redo locations to create the redohistory node + for partition in partitions: + # This is an atomic get to the table Partition Info + partitionInfo = musicInterface.getPartitionInfo(partitionk) + previousRedo.append([partitionInfo.LatestTitTable,partitionInfo.LatestTitIndex]) + # Add row to RH table + musicInterface.addRedoHistoryRow(newPartitionName,titTableName,titIndex,previousRedo) +``` + +### Transaction Commit + +#### Steps for a query in which ETDB node already owns the tables +1. The query is submitted to the local MDBC client +2. Local transaction Id is generated for the query submitted (LTxId) +3. An element is appended to local data structure [RunningQueries](#runningqueries) using LTxId as the index. +4. If required data is fetched from MUSIC + * Pull the set of keys + * Do an atomic get on each of the keys, currently it pulls the whole table + * **Why atomic gets and not locking the key** + * If the MDC node can hold all the required data for a node, then it would need to pull the data only once from MUSIC, given that not outside entity could have a lock for the range + * Redo Recovery, see [Redo](#redo-recovery-to-mdbc-server) for the corresponding variables +5. The query is executed in the local MDBC SQL Tx Database + * Each new database change (insert,write,delete) is saved into the staging table (LST), see [Staging Table](#localstagingtable) +6. The client sends a commit request to the MDBC driver, RunningQueries (RQ) data structure is updated. +7. Generate a local Commit Id (CommitId), an unsigned integer that is monotonically increasing. +8. Commit transaction to Music + * Push new row to RRT (Quorum Write), no lock required + * The submission contains the following components: + * **LeaseId**: id associated with the lease related to the transaction table; + * **Counter**: is the CommitId generated + * **Operations**: a serialized digest of staging table + * Save RRT index to RQ + * Append (LeaseId, Counter) to Redo Array in the corresponding TIT table and row (Lock has to be already be locked) + * Update RQ progress +9. Mdbc commits to local SQL database + * Update RQ when local SQL is completed +10. SQL DB returns commit the result + +#### Assumptions in this transaction commit +* Locks are already held for the partition +* All tables are within that partition +* Each owner only owns one partition at any time (**This is a really important assumption**) + * If a transaction is executed over more than one partition at any time. There is a requirement to do an additional operation, that indicates if the whole transaction was completed. If we are not smart, then a transaction would take at least 4 quorum operations. + +### Redo Recovery to MDBC Server + +```python + def RedoRecovery(tables,cachedTables,numOfThreads=numCores): + # Initialize Redo data structures + logic = initRedoManagerLogic(historyGraph) + restoreTasks = initTaskPriorityQueue() + pool = initThreadPool(numOfThreads,restoreTasks) + prefetchData = initPrefetchData() + # Obtain all the partitions from TTP table + P,oldP = getAllPartitionsFromTTP(tables) + # Data structure that contains the partitions to which the history was already downloaded + historyDownloadedSet=initEmptySet() + # Get the set of all partitions + allP = union(P,oldP) + # Fetch the history associated with each partition + # This can be done in parallel for each partition + # This is a blocking call + # Implementation: it adds all the fetch operations to the task + H = parallelFetchHistory(allP) + # Generate the history graph based on this information. As explained in previous sections + historyGraph = createHistoryGraph(tables,allP,H) + # Number the nodes in the graph using BFS, this returns a map of nodeNumber to nodeId + numberToIdMap = numberNodes(historyGraph) + # If the local node already hold information about this partition, due to pre warmup (e.g. secondary backup) + if cachedTables: + cleanHistoryGraph(cachedTables) + # This is a blocking call that downloads all metadata + parallelFetchMetadata(historyGraph.getAll()) + + # There are multiple of ways to order the following operations + # We choose this order to reduce to possibility of overcommiting memory + tasks = logic.getInitialTasks() + restoreTasks.addOps(tasks) + +``` + +#### Implementation notes +* Before doing a Redo Recovery, we assumed that we already pull all the data from the data tables, either directly or using the dirty tables. +* When using CacheWarming (e.g. secondary backup), we keep a per table Latest Redo Applied. This means that for all parents of this history node was already applied to this table. And they can be erased from historyGraph. +* Each time a task completes, it calls the function setCompleted(TaskInfo) in the RedoManager +* The Archive Process should be stop completely when a Redo recovery is being performed. + +#### parallelFetchMetadata +```python + def parallelFetchMetadata(historyNodes): + this.metadataReadyCounter = 0 + # initialize the tasks + tasks=[] + # Create the tasks to download all the metadata for nodes that + # still have tables to be recovered completely + for node in historyNodes: + restoreTasks.addOp(createMetadataDownloadTask(node),MetadataPriority,node.id) + metadataReady.wait() +``` + +#### getInitialTasks + +```python + def getInitialTasks(): + # We start downloading the digests for the first two levels + rootNodes = historyGraph.getRoots() + rootChildren = historyGraph.getChildren(rootNodes) + firstTwoLevelNodes = union(rootNodes,rootChildren) + firstTwoLevelNodes = deleteAlreadyApplied(firstTwoLevelNodes) + tasks.append(createTxDigestDownloadForNodes(firstTwoLevelNodes)) + return tasks +``` + +#### setCompleted: RedoManager + +```python + def setCompleted(taskInfo): + # Complete the tasks associated, and return the new tasks to execute + newTasks = logic.setCompleted(taskInfo) + # If new tasks added + if len(newTasks) != 0: + # Add them to run in the thread pool + restoreTasks.addOps(newTasks) + else: + # If not more tasks, check if Redo recovery is over + if(logic.isDone()) + # If over, signal that was completed + complete.signal() +``` + +#### setCompleted: RedoManagerLogic + +This is one of the possible implementations of this function for the redo manager logic. + +```python + def setCompleted(taskInfo): + tasks=[] + # If task completed is of Apply digest + if taskInfo.type == HistoryDownload: + historyDownloadedSet.add(taskInfo.partition) + if len(allP) == len(historyDownloadedSet): + # Signal that the history is complete + historyReady.signal() + elif taskInfo.type == ApplyDigest: + # Set node as completed + historyGraph.setRestored(taskInfo.node) + # Start downloading the tx digest for the grandchildren of this node + nodeChildren = historyGraph.getChildren(taskInfo.node) + nodeGrandchildren = historyGraph.getChildren(nodeChildren) + # This function uses the metadata and information about the tables that were already applied locally, to only fetch data for useful transactions + nodeGrandchildren = deleteAlreadyApplied(firstTwoLevelNodes) + tasks.append(createTxDigestDownloadForNodes(nodeGrandchildren)) + # For each children, increase the parent completed and + # check if they are now able to run + for node in nodeChildren: + historyGraph.increaseParentCompleted(node) + if historyGraph.readyToRun(node,prefetchData): + tasks.append(newApplyDigestTask(node)) + else: + # If task completed is metadata download + if taskInfo.type == MetadataDownload: + ## Atomic increase on counter + metadataReadyCounter+=1 + # Record this in the historygraph + historyGraph.setMetadataDownloaded(taskInfo.node) + if metadataReadyCounter == historyGraph.getSize(): + metadataReady.signal() + # If task completed is digest download + elif taskInfo.type == DigestDownload: + # Record this in the historygraph + historyGraph.setDigestDownloaded(taskInfo.node,taskInfo.table,taskInfo.tableId) + # Check if node is now able to apply the digest + if historyGraph.readyToRun(taskInfo.node,prefetchData): + # Add task if ready + tasks.append(newApplyDigestTask(taskInfo.node)) + return tasks +``` + +In the previous pseudocode: +* **createTxDigestDownloadForNodes**: iterates over the nodes, and for each node, it reads the corresponding metadata in prefetchData, and create a download transaction for each of the elements in the Redo Array + +#### Metadata Download Task + +This is the runanble that downloads the metadata associated to a specific node in the history graph. + +Each runnable is assigned an specific node in the history graph, which in the pseudocode is call "node". Additionally it hold information about the task, and pointers to the + +```python + def run(): + # This is an atomic get to the corresponding row in the TIT + # At this point nobody else should hold a lock to this row + # Optmization: perform this async and return the thread to the thread pool + # -> Problem: completed logic to know when to finish this thread + txInformation = musicInterface.downloadTITInformation(node.partition,node.index) + # Add the metadata to the prefetch data object + prefetchData.addMetadata(node.id,txInformation,this.task) + # Let the resource manager know that the task was completed succesfully + resourceManager.setCompleted(this.task) +``` + +#### Transaction Digest Download Task + +```python + def run(): + # For each of the transactions executed in this TIT row + for redoRecordTable,redoRecordIndex in this.task.transactions: + # This is a quorum read that download the digest and associated data from RRT + txDigest = musicInterface.downloadTxDigestFromRRT(redoRecordTable,redoRecordIndex) + # Add digest to the prefetch data + prefetchData.addDigest(node.id,redoRecordTable,redoRecordIndex,this.task) + # Let the resource manager know that the task was completed succesfully + resourceManager.setCompleted(this.task) +``` + +**Assumption**: +* Metadata was already downloaded in the first stage + +#### Apply Transaction Task + +```python + def run(): + node = historyGraph.getNode(task.id) + metadata = prefetchData.getMetadata(node) + for index in range(max(0,metadata.latestApplied),len(metadata.redo)): + redoRecordTable,redoRecordIndex = metadata.redo[index] + # Get the tx digest from the prefetched data + txDigest = prefetchData.getTransaction(this.task.id,redoRecordTable,redoRecordIndex) + # Deserialize the tx digest + stagingTable = deserializeDigest(txDigest) + # For each table in the staging table + for table in stagingTable: + # For each row in the staging table + for row in stagingTable[table]: + # For each operatino that was applied to that row during the transaction + for op in row: + # Applied the operation in order + MusicSQLManager.applyOperation(op.type,op.old,op.new) + resourceManager.setCompleted(this.task) + + +``` + +**Assumptions** +* All data is already prefetched to be applied by the apply digest task + +#### Download History Task + +```python + def run(): + # Download all the rows that are associated with this partition + history = musicInterface.downloadPartitionRedoHistory(task.partition); + # For each row + for row in history: + # Create a node and corresponding link in the historyGraph + historyGraph.addNode(row.redoTable,row.redoIndex) + # It is a future link because the next node was probably not downloaded yet + historyGraph.addFutureLink(row.redoTable,row.redoIndex,row.previousRedoTable,row.previousRedoIndex) + # Let the resource manager know that the task was completed succesfully + resourceManager.setCompleted(this.task) +``` + +### Redo Commit to Data Table + +We do the same as the Redo Recovery to MDBC server, but instead of pushing to the local SQL database, we push towards the Music data tables. Additionally, we need to update all the corresponding tables. + +The specific differences are: +* For each redo record applied, we need to increase the counter in LatestApplied for the corresponding row in TIT. +* Once all the Redo Records in a TIT row are applied, then we need to change the applied flag in the corresponding TIT row. + + +## TODO +* Analyze the possible states during a failure in partition merging. Some ideas: + - We probably need to create a new table that keeps the id of the partition that was created + and then we need to clean up all the changes that were performed due to this new partition operation (split/merge) + - If the partition id is still in this table and there is no lock on the corresponding TIT table (if it was even created), then we need to clean all the changes, and restart the partion operation (if required) +* Analyze the garbage collection of table information after commiting to the data tables. Some ideas: + - The rows in RRT can be erased after being applied completely into Music data tables + - A TIT row can be erased when all the elements in the Redo Array where already applied to the data tables. When a TIT row is erased, all the children of that node need to be change to point to null + - A PI row table can be erased when there are no more TIT rows or RH rows that point to it. When a PI row is deleted, then the corresponding value need to be erased from the TTP Previous partitions for all the table that are part of that PI row. diff --git a/docs/uml.svg b/docs/uml.svg new file mode 100644 index 0000000..8d6dd52 --- /dev/null +++ b/docs/uml.svg @@ -0,0 +1,2 @@ +<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"> +<svg xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" width="598px" height="263px" version="1.1"><defs/><g transform="translate(0.5,0.5)"><rect x="1" y="106" width="110" height="50" fill="none" stroke="#468e9f" stroke-width="3" pointer-events="none"/><g transform="translate(18.5,124.5)"><switch><foreignObject style="overflow:visible;" pointer-events="all" width="74" height="12" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility"><div xmlns="http://www.w3.org/1999/xhtml" style="display: inline-block; font-size: 12px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; vertical-align: top; white-space: nowrap; text-align: center;"><div xmlns="http://www.w3.org/1999/xhtml" style="display:inline-block;text-align:inherit;text-decoration:inherit;">MDBC Server</div></div></foreignObject><text x="37" y="12" fill="#000000" text-anchor="middle" font-size="12px" font-family="Helvetica">MDBC Server</text></switch></g><rect x="206" y="106" width="120" height="50" fill="none" stroke="#468e9f" stroke-width="3" transform="translate(266,0)scale(-1,1)translate(-266,0)" pointer-events="none"/><g transform="translate(214.5,124.5)"><switch><foreignObject style="overflow:visible;" pointer-events="all" width="103" height="12" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility"><div xmlns="http://www.w3.org/1999/xhtml" style="display: inline-block; font-size: 12px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; vertical-align: top; white-space: nowrap; text-align: center;"><div xmlns="http://www.w3.org/1999/xhtml" style="display:inline-block;text-align:inherit;text-decoration:inherit;">MusicSQLManager</div></div></foreignObject><text x="52" y="12" fill="#000000" text-anchor="middle" font-size="12px" font-family="Helvetica">MusicSQLManager</text></switch></g><g transform="translate(178.5,116.5)"><switch><foreignObject style="overflow:visible;" pointer-events="all" width="18" height="12" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility"><div xmlns="http://www.w3.org/1999/xhtml" style="display: inline-block; font-size: 12px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; vertical-align: top; width: 20px; white-space: nowrap; word-wrap: normal; text-align: center;"><div xmlns="http://www.w3.org/1999/xhtml" style="display:inline-block;text-align:inherit;text-decoration:inherit;">0..*</div></div></foreignObject><text x="9" y="12" fill="#000000" text-anchor="middle" font-size="12px" font-family="Helvetica">0..*</text></switch></g><rect x="206" y="211" width="120" height="50" fill="none" stroke="#468e9f" stroke-width="3" pointer-events="none"/><g transform="translate(236.5,222.5)"><switch><foreignObject style="overflow:visible;" pointer-events="all" width="59" height="26" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility"><div xmlns="http://www.w3.org/1999/xhtml" style="display: inline-block; font-size: 12px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; vertical-align: top; white-space: nowrap; text-align: center;"><div xmlns="http://www.w3.org/1999/xhtml" style="display:inline-block;text-align:inherit;text-decoration:inherit;">«interface»<br /><b>Music</b></div></div></foreignObject><text x="30" y="19" fill="#000000" text-anchor="middle" font-size="12px" font-family="Helvetica">[Not supported by viewer]</text></switch></g><rect x="466" y="76" width="130" height="50" fill="none" stroke="#468e9f" stroke-width="3" transform="translate(531,0)scale(-1,1)translate(-531,0)" pointer-events="none"/><g transform="translate(501.5,87.5)"><switch><foreignObject style="overflow:visible;" pointer-events="all" width="59" height="26" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility"><div xmlns="http://www.w3.org/1999/xhtml" style="display: inline-block; font-size: 12px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; vertical-align: top; white-space: nowrap; text-align: center;"><div xmlns="http://www.w3.org/1999/xhtml" style="display:inline-block;text-align:inherit;text-decoration:inherit;">«interface»<br /><b>SQL</b></div></div></foreignObject><text x="30" y="19" fill="#000000" text-anchor="middle" font-size="12px" font-family="Helvetica">[Not supported by viewer]</text></switch></g><path d="M 343.97 119 L 386 119 Q 396 119 396 110 L 396 105.5 Q 396 101 406 101 L 461.53 101" fill="none" stroke="#000000" stroke-width="2" stroke-miterlimit="10" pointer-events="none"/><path d="M 327.97 119 L 335.97 114.29 L 343.97 119 L 335.97 123.71 Z" fill="#000000" stroke="#000000" stroke-width="2" stroke-miterlimit="10" pointer-events="none"/><path d="M 449.76 108 L 463.76 101 L 449.76 94" fill="none" stroke="#000000" stroke-width="2" stroke-miterlimit="10" pointer-events="none"/><g transform="translate(327.5,101.5)"><switch><foreignObject style="overflow:visible;" pointer-events="all" width="6" height="11" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility"><div xmlns="http://www.w3.org/1999/xhtml" style="display: inline-block; font-size: 11px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; vertical-align: top; white-space: nowrap;"><div xmlns="http://www.w3.org/1999/xhtml" style="display:inline-block;text-align:inherit;text-decoration:inherit;">1</div></div></foreignObject><text x="3" y="11" fill="#000000" text-anchor="middle" font-size="11px" font-family="Helvetica">1</text></switch></g><g transform="translate(439.5,101.5)"><switch><foreignObject style="overflow:visible;" pointer-events="all" width="6" height="12" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility"><div xmlns="http://www.w3.org/1999/xhtml" style="display: inline-block; font-size: 12px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; vertical-align: top; width: 8px; white-space: nowrap; word-wrap: normal; text-align: center;"><div xmlns="http://www.w3.org/1999/xhtml" style="display:inline-block;text-align:inherit;text-decoration:inherit;">1</div></div></foreignObject><text x="3" y="12" fill="#000000" text-anchor="middle" font-size="12px" font-family="Helvetica">1</text></switch></g><rect x="206" y="1" width="120" height="50" fill="none" stroke="#468e9f" stroke-width="3" pointer-events="none"/><g transform="translate(222.5,19.5)"><switch><foreignObject style="overflow:visible;" pointer-events="all" width="87" height="12" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility"><div xmlns="http://www.w3.org/1999/xhtml" style="display: inline-block; font-size: 12px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; vertical-align: top; white-space: nowrap; text-align: center;"><div xmlns="http://www.w3.org/1999/xhtml" style="display:inline-block;text-align:inherit;text-decoration:inherit;">RunningQueries</div></div></foreignObject><text x="44" y="12" fill="#000000" text-anchor="middle" font-size="12px" font-family="Helvetica">RunningQueries</text></switch></g><rect x="466" y="135" width="130" height="50" fill="none" stroke="#468e9f" stroke-width="3" transform="translate(531,0)scale(-1,1)translate(-531,0)" pointer-events="none"/><g transform="translate(478.5,153.5)"><switch><foreignObject style="overflow:visible;" pointer-events="all" width="105" height="12" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility"><div xmlns="http://www.w3.org/1999/xhtml" style="display: inline-block; font-size: 12px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; vertical-align: top; white-space: nowrap; text-align: center;"><div xmlns="http://www.w3.org/1999/xhtml" style="display:inline-block;text-align:inherit;text-decoration:inherit;">Local Staging Table</div></div></foreignObject><text x="53" y="12" fill="#000000" text-anchor="middle" font-size="12px" font-family="Helvetica">Local Staging Table</text></switch></g><path d="M 343.97 144 L 386 144 Q 396 144 396 152 L 396 156 Q 396 160 406 160 L 461.53 160" fill="none" stroke="#000000" stroke-width="2" stroke-miterlimit="10" pointer-events="none"/><path d="M 327.97 144 L 335.97 139.29 L 343.97 144 L 335.97 148.71 Z" fill="#000000" stroke="#000000" stroke-width="2" stroke-miterlimit="10" pointer-events="none"/><path d="M 449.76 167 L 463.76 160 L 449.76 153" fill="none" stroke="#000000" stroke-width="2" stroke-miterlimit="10" pointer-events="none"/><g transform="translate(327.5,126.5)"><switch><foreignObject style="overflow:visible;" pointer-events="all" width="6" height="11" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility"><div xmlns="http://www.w3.org/1999/xhtml" style="display: inline-block; font-size: 11px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; vertical-align: top; white-space: nowrap;"><div xmlns="http://www.w3.org/1999/xhtml" style="display:inline-block;text-align:inherit;text-decoration:inherit;">1</div></div></foreignObject><text x="3" y="11" fill="#000000" text-anchor="middle" font-size="11px" font-family="Helvetica">1</text></switch></g><g transform="translate(439.5,146.5)"><switch><foreignObject style="overflow:visible;" pointer-events="all" width="6" height="12" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility"><div xmlns="http://www.w3.org/1999/xhtml" style="display: inline-block; font-size: 12px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; vertical-align: top; width: 8px; white-space: nowrap; word-wrap: normal; text-align: center;"><div xmlns="http://www.w3.org/1999/xhtml" style="display:inline-block;text-align:inherit;text-decoration:inherit;">1</div></div></foreignObject><text x="3" y="12" fill="#000000" text-anchor="middle" font-size="12px" font-family="Helvetica">1</text></switch></g><path d="M 56 88.03 L 56 36 Q 56 26 66 26 L 201.53 26" fill="none" stroke="#000000" stroke-width="2" stroke-miterlimit="10" pointer-events="none"/><path d="M 56 104.03 L 51.29 96.03 L 56 88.03 L 60.71 96.03 Z" fill="#000000" stroke="#000000" stroke-width="2" stroke-miterlimit="10" pointer-events="none"/><path d="M 189.76 33 L 203.76 26 L 189.76 19" fill="none" stroke="#000000" stroke-width="2" stroke-miterlimit="10" pointer-events="none"/><g transform="translate(57.5,72.5)"><switch><foreignObject style="overflow:visible;" pointer-events="all" width="6" height="11" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility"><div xmlns="http://www.w3.org/1999/xhtml" style="display: inline-block; font-size: 11px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; vertical-align: top; white-space: nowrap;"><div xmlns="http://www.w3.org/1999/xhtml" style="display:inline-block;text-align:inherit;text-decoration:inherit;">1</div></div></foreignObject><text x="3" y="11" fill="#000000" text-anchor="middle" font-size="11px" font-family="Helvetica">1</text></switch></g><path d="M 56 173.97 L 56 226 Q 56 236 66 236 L 201.53 236" fill="none" stroke="#000000" stroke-width="2" stroke-miterlimit="10" pointer-events="none"/><path d="M 56 157.97 L 60.71 165.97 L 56 173.97 L 51.29 165.97 Z" fill="#000000" stroke="#000000" stroke-width="2" stroke-miterlimit="10" pointer-events="none"/><path d="M 189.76 243 L 203.76 236 L 189.76 229" fill="none" stroke="#000000" stroke-width="2" stroke-miterlimit="10" pointer-events="none"/><g transform="translate(57.5,170.5)"><switch><foreignObject style="overflow:visible;" pointer-events="all" width="6" height="11" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility"><div xmlns="http://www.w3.org/1999/xhtml" style="display: inline-block; font-size: 11px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; vertical-align: top; white-space: nowrap;"><div xmlns="http://www.w3.org/1999/xhtml" style="display:inline-block;text-align:inherit;text-decoration:inherit;">1</div></div></foreignObject><text x="3" y="11" fill="#000000" text-anchor="middle" font-size="11px" font-family="Helvetica">1</text></switch></g><path d="M 266 156 L 266 206.53" fill="none" stroke="#000000" stroke-width="2" stroke-miterlimit="10" stroke-dasharray="6 6" pointer-events="none"/><path d="M 259 194.76 L 266 208.76 L 273 194.76" fill="none" stroke="#000000" stroke-width="2" stroke-miterlimit="10" pointer-events="none"/><g transform="translate(255.5,178.5)"><switch><foreignObject style="overflow:visible;" pointer-events="all" width="20" height="11" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility"><div xmlns="http://www.w3.org/1999/xhtml" style="display: inline-block; font-size: 11px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; vertical-align: top; white-space: nowrap; text-align: center;"><div xmlns="http://www.w3.org/1999/xhtml" style="display:inline-block;text-align:inherit;text-decoration:inherit;">Use</div></div></foreignObject><text x="10" y="11" fill="#000000" text-anchor="middle" font-size="11px" font-family="Helvetica">Use</text></switch></g><path d="M 266 106 L 266 55.47" fill="none" stroke="#000000" stroke-width="2" stroke-miterlimit="10" stroke-dasharray="6 6" pointer-events="none"/><path d="M 273 67.24 L 266 53.24 L 259 67.24" fill="none" stroke="#000000" stroke-width="2" stroke-miterlimit="10" pointer-events="none"/><g transform="translate(255.5,72.5)"><switch><foreignObject style="overflow:visible;" pointer-events="all" width="20" height="11" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility"><div xmlns="http://www.w3.org/1999/xhtml" style="display: inline-block; font-size: 11px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; vertical-align: top; white-space: nowrap; text-align: center;"><div xmlns="http://www.w3.org/1999/xhtml" style="display:inline-block;text-align:inherit;text-decoration:inherit;">Use</div></div></foreignObject><text x="10" y="11" fill="#000000" text-anchor="middle" font-size="11px" font-family="Helvetica">Use</text></switch></g><path d="M 128.97 131 L 201.53 131" fill="none" stroke="#000000" stroke-width="2" stroke-miterlimit="10" pointer-events="none"/><path d="M 112.97 131 L 120.97 126.29 L 128.97 131 L 120.97 135.71 Z" fill="none" stroke="#000000" stroke-width="2" stroke-miterlimit="10" pointer-events="none"/><path d="M 189.76 138 L 203.76 131 L 189.76 124" fill="none" stroke="#000000" stroke-width="2" stroke-miterlimit="10" pointer-events="none"/><g transform="translate(112.5,113.5)"><switch><foreignObject style="overflow:visible;" pointer-events="all" width="6" height="11" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility"><div xmlns="http://www.w3.org/1999/xhtml" style="display: inline-block; font-size: 11px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; vertical-align: top; white-space: nowrap;"><div xmlns="http://www.w3.org/1999/xhtml" style="display:inline-block;text-align:inherit;text-decoration:inherit;">1</div></div></foreignObject><text x="3" y="11" fill="#000000" text-anchor="middle" font-size="11px" font-family="Helvetica">1</text></switch></g></g></svg>
\ No newline at end of file |
