tag:blogger.com,1999:blog-72297263563501575292024-02-08T12:21:48.550-05:00Que es BhaskarK.S. Bhaskar muses on life, the universe and everything, but especially on technology, software (especially free and open source software - FOSS), Linux, databases and GT.MBhaskarhttp://www.blogger.com/profile/14323369551611484731noreply@blogger.comBlogger13125tag:blogger.com,1999:blog-7229726356350157529.post-10977231002422130142011-04-23T18:55:00.007-04:002011-04-30T23:15:20.010-04:00Maintaining Eventual Path Consistency<div dir="ltr" style="text-align: left;" trbidi="on"><h1 id="internal-source-marker_0.4749040540837971" style="font-family: inherit;"><span style="background-color: transparent; color: black; font-size: 24pt; font-style: normal; font-weight: bold; text-decoration: none; vertical-align: baseline;"></span></h1><div style="font-family: inherit;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">In an earlier post (</span><a href="http://ksbhaskar.blogspot.com/2011/03/eventual-consistency-vs-eventual.html"><span style="background-color: transparent; color: #000099; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: underline; vertical-align: baseline;">Eventual State Consistency vs. Eventual Path Consistency</span></a><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">), I wrote about the difference between two types of Eventual Consistency. While Eventual State Consistency is the more familiar variety, there are applications that require Eventual Path Consistency.</span></div><div style="font-family: inherit;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"></span></div><div style="font-family: inherit;"><br />
<span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">We are of course discussing Eventually Consistent application configurations that relax Consistency in favor of Availability and Partition tolerance per the </span><a href="http://www.julianbrowne.com/article/viewer/brewers-cap-theorem"><span style="background-color: transparent; color: #000099; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: underline; vertical-align: baseline;">CAP theorem</span></a><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">. If either of Availability and Partition tolerance can be relaxed, Consistency is easily provided, for example, by ensuring that a transaction is committed at the remote instance as part of committing it at the local instance. The case where Consistency can be relaxed is not just more desirable in an “always on” business environment where the competition is just mouse clicks away - it is also technically more challenging (and hence more interesting to a geek like me).</span><br />
<br />
</div><div style="font-family: inherit;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"></span></div><div style="font-family: inherit;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">In order to provide Eventual Consistency, an application has to (a) detect when two instances have diverged - i.e., are mutually Inconsistent - and (b) bring them back to a Consistent state.</span></div><div style="font-family: inherit;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"></span></div><a name='more'></a><div style="font-family: inherit;"><br />
</div><div style="font-family: inherit;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">The distinction between Eventual State Consistency and Eventual Path Consistency applies to all types of databases, relational (“SQL”) as well as non-relational (“NoSQL”). Consistency, however, is relevant only to databases that support Atomic, Consistent, Isolated and Durable (</span><a href="http://en.wikipedia.org/wiki/ACID"><span style="background-color: transparent; color: #000099; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: underline; vertical-align: baseline;">ACID</span></a><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">) transactions where a transaction has a well defined beginning (transaction start) and a well defined end (transaction commit). Without transactions, every update is in theory Consistent and relies on all data read from the very first update to a newly created database - in other words, while Consistency may be theoretically meaningful without transactions, it is not a useful concept in practice.</span></div><div style="font-family: inherit;"><br />
</div><div style="font-family: inherit;"><b><span style="font-size: large;">Detecting Inconsistency</span></b></div><h2 style="font-family: inherit;"><span style="font-size: large;"><span style="background-color: transparent; color: black; font-style: normal; font-weight: bold; text-decoration: none; vertical-align: baseline;"></span></span></h2><div style="font-family: inherit;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">The problem to be solved is summarized thus:</span></div><div style="font-family: inherit;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"></span></div><ul style="font-family: inherit;"><li style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; list-style-type: disc; text-decoration: none; vertical-align: baseline;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">Two instances, A and B, independently execute </span><a href=#ApplicationCodeEquivalence><span style="background-color: transparent; color: #000099; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: underline; vertical-align: baseline;">logically equivalent application code</span></a><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"> and commit Durable updates to their local databases without checking for Consistency with respect to the state of the other instance.</span></li>
<li style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; list-style-type: disc; text-decoration: none; vertical-align: baseline;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">In conjunction with committing updates locally, each instance transmits information to the other instance to replicate the transaction. The local commit is required (otherwise Durability is not satisfied), but Eventual Consistency means that remote receipt and commit is not required for a local commit.</span></li>
<li style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; list-style-type: disc; text-decoration: none; vertical-align: baseline;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">The remote instance must determine from the transmitted information whether applying the transaction would make its database Inconsistent.</span></li>
</ul><div style="font-family: inherit;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">The brute force approach is simply to re-execute application code for the transaction on the remote instance. If the results on the remote instance are different from those originally computed, an Inconsistency has occurred. But brute force has its limitations and is overkill for most real world problems that I know of.</span></div><div style="font-family: inherit;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"></span></div><div style="font-family: inherit;"><br />
<span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">To determine Inconsistency in a replicated environment, an application needs to look at relative times. Consider a transaction </span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: bold; text-decoration: none; vertical-align: baseline;">a</span><span style="background-color: transparent; color: black; font-size: 6.6pt; font-style: normal; font-weight: bold; text-decoration: none; vertical-align: sub;">n</span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"> computed and committed by A and replicated to B. In reverse chronological order:</span></div><div style="font-family: inherit;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"></span></div><ol style="font-family: inherit;"><li style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; list-style-type: decimal; text-decoration: none; vertical-align: baseline;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: bold; text-decoration: none; vertical-align: baseline;">T</span><span style="background-color: transparent; color: black; font-size: 6.6pt; font-style: normal; font-weight: bold; text-decoration: none; vertical-align: sub;">0</span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"> is the time at which B performs the check for Consistency to commit a</span><span style="background-color: transparent; color: black; font-size: 6.6pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: sub;">n</span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">.</span></li>
<li style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; list-style-type: decimal; text-decoration: none; vertical-align: baseline;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: bold; text-decoration: none; vertical-align: baseline;">T</span><span style="background-color: transparent; color: black; font-size: 6.6pt; font-style: normal; font-weight: bold; text-decoration: none; vertical-align: sub;">-1</span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"> is the time at which a</span><span style="background-color: transparent; color: black; font-size: 6.6pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: sub;">n</span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"> was committed on A. A provides ACID properties for a</span><span style="background-color: transparent; color: black; font-size: 6.6pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: sub;">n</span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"> at T</span><span style="background-color: transparent; color: black; font-size: 6.6pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: sub;">-1</span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">.</span></li>
<li style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; list-style-type: decimal; text-decoration: none; vertical-align: baseline;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">At time T</span><span style="background-color: transparent; color: black; font-size: 6.6pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: sub;">-1</span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"> the database on A is current and Consistent with transactions committed on B up to time </span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: bold; text-decoration: none; vertical-align: baseline;">T</span><span style="background-color: transparent; color: black; font-size: 6.6pt; font-style: normal; font-weight: bold; text-decoration: none; vertical-align: sub;">-2</span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">.</span></li>
</ol><div style="font-family: inherit;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">In order for B to determine whether a</span><span style="background-color: transparent; color: black; font-size: 6.6pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: sub;">n</span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"> can be safely committed, it must compare a</span><span style="background-color: transparent; color: black; font-size: 6.6pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: sub;">n</span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"> with transactions it computed and committed between T</span><span style="background-color: transparent; color: black; font-size: 6.6pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: sub;">-2</span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"> and T</span><span style="background-color: transparent; color: black; font-size: 6.6pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: sub;">0</span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">. Transactions committed before T</span><span style="background-color: transparent; color: black; font-size: 6.6pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: sub;">-2</span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"> do not need to be examined because they were replicated to A by T</span><span style="background-color: transparent; color: black; font-size: 6.6pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: sub;">-1</span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">, and hence application logic A would have ensured Consistency of a</span><span style="background-color: transparent; color: black; font-size: 6.6pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: sub;">n</span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"> with respect to them. Transactions replicated from A and committed before T</span><span style="background-color: transparent; color: black; font-size: 6.6pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: sub;">0</span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"> also do not need to be examined, because database serialization on A would have ensured their Consistency with respect to all updates computed and committed on A prior to a</span><span style="background-color: transparent; color: black; font-size: 6.6pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: sub;">n</span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">.</span></div><div style="font-family: inherit;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"></span></div><div style="font-family: inherit;"><br />
<span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">In order to determine Consistency, the instances therefore need a common measure of time. This does not need to be time as we intuitively understand it - for example, they could have a common understanding of the number of steps through state space that they have taken. But the understanding must be common (fuzziness should be bounded and its limits known), and the measure must increase monotonically.</span></div><div style="font-family: inherit;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"></span></div><div style="font-family: inherit;"><br />
<span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">Detecting Inconsistency for Eventual State Consistency is a straightforward proposition: check whether any update to the database state in B computed and committed by transactions between T</span><span style="background-color: transparent; color: black; font-size: 6.6pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: sub;">-2</span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"> and T</span><span style="background-color: transparent; color: black; font-size: 6.6pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: sub;">0</span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"> conflicts with any update in a</span><span style="background-color: transparent; color: black; font-size: 6.6pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: sub;">n</span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"> (a “Consistent update check”). Updates in the state of B replicated from A and further modified by a</span><span style="background-color: transparent; color: black; font-size: 6.6pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: sub;">n</span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"> should be ignored because (a) the application logic on A would have ensured Consistency and (b) the fact that the replicated updates were committed means that they did not conflict with any update on B.</span></div><div style="font-family: inherit;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"></span></div><div style="font-family: inherit;"><br />
<span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">Detecting Inconsistency for Eventual Path Consistency is a little harder. Instance B must check:</span></div><div style="font-family: inherit;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"></span></div><ul style="font-family: inherit;"><li style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; list-style-type: disc; text-decoration: none; vertical-align: baseline;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">whether any elements of the database state that A </span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: italic; font-weight: normal; text-decoration: none; vertical-align: baseline;">used or read</span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"> to compute a</span><span style="background-color: transparent; color: black; font-size: 6.6pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: sub;">n</span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"> were changed by B between T</span><span style="background-color: transparent; color: black; font-size: 6.6pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: sub;">-2</span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"> and T</span><span style="background-color: transparent; color: black; font-size: 6.6pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: sub;">-1</span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"> (this “Consistent use check” is not required for Eventual State Consistency), and</span></li>
<li style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; list-style-type: disc; text-decoration: none; vertical-align: baseline;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">whether any update to the database state in B computed and committed by transactions between T</span><span style="background-color: transparent; color: black; font-size: 6.6pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: sub;">-2</span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"> and T</span><span style="background-color: transparent; color: black; font-size: 6.6pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: sub;">0</span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"> conflicts with any update in a</span><span style="background-color: transparent; color: black; font-size: 6.6pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: sub;">n</span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"> (this “Consistent update check” is the same as for Eventual State Consistency).</span></li>
</ul><div style="font-family: inherit;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"></span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">Note that:</span></div><div style="font-family: inherit;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"></span></div><ol style="font-family: inherit;"><li style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; list-style-type: decimal; text-decoration: none; vertical-align: baseline;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">The Consistent use check needs to ensure Consistency not just of data whose values were read, but also </span><a href=#DataAbsence><span style="background-color: transparent; color: #000099; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: underline; vertical-align: baseline;">data whose absence affects results</span></a><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">.</span></li>
<li style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; list-style-type: decimal; text-decoration: none; vertical-align: baseline;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">Any transactions from A following a replicated transaction that cannot be committed on B can also not be committed, because that would </span><a href="#SufficientCondition"><span style="background-color: transparent; color: #000099; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: underline; vertical-align: baseline;">violate the serialization of those transactions</span></a><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">.</span></li>
<li style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; list-style-type: decimal; text-decoration: none; vertical-align: baseline;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">Generalizing from two mutually replicating instances to three is possible in theory but hard in practice. Depending on replication delays, it is possible for an instance C, which has computed and committed no transactions of its own to detect Inconsistency in transactions computed by instances A and B, neither of which detects Inconsistency in the replication stream from the other.</span></li>
</ol><div style="font-family: inherit;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"></span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">When Inconsistency is detected, steps must be taken to restore Consistency.</span></div><div style="font-family: inherit;"><br />
</div><div style="font-family: inherit;"><b><span style="font-size: large;">Restoring Consistency</span></b></div><h2 style="font-family: inherit;"><span style="font-size: large;"><span style="background-color: transparent; color: black; font-style: normal; font-weight: bold; text-decoration: none; vertical-align: baseline;"></span></span></h2><div style="font-family: inherit;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">The problem to be solved is summarized thus:</span></div><div style="font-family: inherit;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"></span></div><ul style="font-family: inherit;"><li style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; list-style-type: disc; text-decoration: none; vertical-align: baseline;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">An instance A computed and committed a transaction a</span><span style="background-color: transparent; color: black; font-size: 6.6pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: sub;">n</span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"> (perhaps with an externally visible action, an ATM withdrawal authorization or a ticket issued to a concert or sporting event).</span></li>
<li style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; list-style-type: disc; text-decoration: none; vertical-align: baseline;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">Transaction a</span><span style="background-color: transparent; color: black; font-size: 6.6pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: sub;">n</span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"> was replicated to instance B.</span></li>
<li style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; list-style-type: disc; text-decoration: none; vertical-align: baseline;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">Instance B has detected that committing the transaction would violate Consistency with respect to at least one transaction in its database, b</span><span style="background-color: transparent; color: black; font-size: 6.6pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: sub;">p</span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"> (if there are multiple such transactions, b</span><span style="background-color: transparent; color: black; font-size: 6.6pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: sub;">p </span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">is the earliest).</span></li>
</ul><div style="font-family: inherit;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: italic; font-weight: normal; text-decoration: none; vertical-align: baseline;">A requirement for any solution is that every transaction must have a correcting (or inverse) transaction</span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: italic; font-weight: normal; text-decoration: none; vertical-align: baseline;">.</span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"> Otherwise, the application is deadlocked because A and B have both committed conflicting updates that may be externally visible. Ensuring an inverse transaction for every transaction may require </span><a href="#ChangeRules"><span style="background-color: transparent; color: #000099; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: underline; vertical-align: baseline;">changes to application Consistency rules</span></a><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">.</span></div><div style="font-family: inherit;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"></span></div><div style="font-family: inherit;"><br />
<span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">The simplest approach to achieving Eventual State Consistency is for B to compute and commit a transaction B</span><span style="background-color: transparent; color: black; font-size: 6.6pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: sub;">nX</span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"> which corrects the committing of a</span><span style="background-color: transparent; color: black; font-size: 6.6pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: sub;">n</span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"> by instance B. In turn, B</span><span style="background-color: transparent; color: black; font-size: 6.6pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: sub;">nX</span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"> will get replicated to instance A. Such an approach should suffice for many Eventual State Consistency needs.</span></div><div style="font-family: inherit;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"></span></div><div style="font-family: inherit;"><br />
<span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">But the simplest approach will not produce Eventual Path Consistency since instances A and B will have different paths through state space. Even for State Consistency, approach may not always work. For example, in some applications, an Inconsistency with a</span><span style="background-color: transparent; color: black; font-size: 6.6pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: sub;">n</span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"> may mean that the probability increases that a</span><span style="background-color: transparent; color: black; font-size: 6.6pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: sub;">n+1</span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">, a</span><span style="background-color: transparent; color: black; font-size: 6.6pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: sub;">n+2</span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">, etc. will also be detected as Inconsistent, causing an </span><a href="#DivergingSpiral"><span style="background-color: transparent; color: #000099; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: underline; vertical-align: baseline;">upward spiral of correcting entries</span></a><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">.</span></div><div style="font-family: inherit;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"></span></div><div style="font-family: inherit;"><br />
<span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">A more useful approach is to designate one instance as the liege and the other as the vassal - the designations can be swapped at any time, of course. To resolve Inconsistencies, the liege is always right. In this example, assume that A is the liege and B the vassal. Corrective action occurs thus:</span></div><div style="font-family: inherit;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"></span></div><ol style="font-family: inherit;"><li style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; list-style-type: decimal; text-decoration: none; vertical-align: baseline;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">Using its journal files, B rolls back its database to the state it was in when transaction b</span><span style="background-color: transparent; color: black; font-size: 6.6pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: sub;">p-1</span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"> was committed. Because of update serialization, transactions rolled off would include transactions computed and committed by B as well as those replicated from A. The rolled off transactions are saved.</span></li>
<li style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; list-style-type: decimal; text-decoration: none; vertical-align: baseline;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">The database state of B is now no longer Inconsistent with the state of A. Replication can now resume, catching up from the rollback point, as can normal transaction processing on B.</span></li>
<li style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; list-style-type: decimal; text-decoration: none; vertical-align: baseline;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">B creates a reconciliation log from the file with the rolled off transactions with transactions originally computed and committed by A and replicated to B filtered out - these are already processed and committed on A and do not need to be reprocessed. It sends this reconciliation log to A.</span></li>
<li style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; list-style-type: decimal; text-decoration: none; vertical-align: baseline;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">A reads and reprocesses the transactions in the reconciliation log. If the result of A reprocessing a transaction generates the same result, it simply commits the transaction to its database. If the result of A reprocessing a transaction results in a different result, A computes and commits the correcting transaction.</span></li>
<li style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; list-style-type: decimal; text-decoration: none; vertical-align: baseline;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">The results of A reprocessing the reconciliation log are replicated to B in the normal course.</span></li>
</ol><div style="font-family: inherit;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">It is of course not always the case that B detects an Inconsistency. It is just as possible for A to detect an Inconsistency when replicating from B. In this case, A as the liege does not rollback its database. Instead, A commands B to rollback its database to the state immediately prior to the transaction that would cause an Inconsistency at A if committed. In either case, B rolls back its database - the only difference is whether it determines the rollback point or whether A sends it the rollback point. Also, A discards the replication stream from B until after B rolls back its database.</span></div><div style="font-family: inherit;"><br />
</div><div style="font-family: inherit;"><b><span style="font-size: large;">Conclusion</span></b></div><h2 style="font-family: inherit;"><span style="font-size: large;"><span style="background-color: transparent; color: black; font-style: normal; font-weight: bold; text-decoration: none; vertical-align: baseline;"></span></span></h2><div style="font-family: inherit;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">For Eventual Path Consistency to be successfully deployed, the application and database engine </span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: underline; vertical-align: baseline;">must</span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"> cooperate. The application must be well behaved: in particular, the probability of Inconsistencies detected on replication must be low. It may be possible to reconfigure some otherwise ill behaved applications to make them behave better, for example, by preferential routing to the liege instance of transactions that are likely to “collide”, since transactions processed and committed by the liege are not rolled back and reprocessed.</span></div><div style="font-family: inherit;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"></span></div><div style="font-family: inherit;"><br />
<span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">In a future blog post, I will describe the pragmatic trade-offs of a real-world application that implements Eventual Consistency.</span></div><div style="font-family: inherit;"><br />
</div><div style="font-family: inherit;"><span style="font-size: large;"><b>Notes</b></span></div><h2 style="font-family: inherit;"><span style="font-size: large;"><span style="background-color: transparent; color: black; font-style: normal; font-weight: bold; text-decoration: none; vertical-align: baseline;"></span></span></h2><ol style="font-family: inherit;"><li style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; list-style-type: decimal; text-decoration: none; vertical-align: baseline;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"><a name="ApplicationCodeEquivalence"></a>The application code at the two instances does not have to be identical. What is required is that given the same set of inputs, they generate database state changes that are logically identical (they must be identical for state elements material to the application, such as the balance in an account; there may be state that is not material, such as the process id on the instance that computed the state change).</span></li>
<li style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; list-style-type: decimal; text-decoration: none; vertical-align: baseline;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"><a name="DataAbsence"></a>The absence of data may be as important as its presence. Consider the case where a database has nodes (or rows) where the first subscript (or primary key component) is the last name of US Presidents. An application may test for the presence of “Obama” (testing for the presence of data) or it may check whether or not the successor to “Nixon” is “Pierce” (testing for the absence of data).</span></li>
<li style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; list-style-type: decimal; text-decoration: none; vertical-align: baseline;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"><a name="SufficientCondition"></a>While this is a sufficient condition, it is not a necessary condition. In theory, only those transactions committed on A that relied on the database updates committed by the conflicting transaction cannot be committed. In practice, tracking the dependencies and would create a forest of dependency trees that could in theory spiral out of control and lead to computational meltdown.</span></li>
<li style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; list-style-type: decimal; text-decoration: none; vertical-align: baseline;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"><a name="ChangeRules"></a>In order to implement Eventual Consistency, changes to application Consistency rules are likely to be mandatory. Consider an example where the application implements a Consistency rule such as “no seat to a concert can have more than one owner”. If instances A and B sell the same seat at the same time, there is no way to restore Consistency. So, application Consistency rule has to be changed to something like “no seat to a concert can have more than one owner unless an action item to correct the situation has been put in the Customer Service work queue.” If two concurrent ATM withdrawals have depleted the balance in an account, the inverse transaction may be to put the account into overdrawn status and perhaps charge the owner(s) a service fee.</span></li>
<li style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; list-style-type: decimal; text-decoration: none; vertical-align: baseline;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"><a name="DivergingSpiral"></a>As an example of an upward spiral of correcting entries, in the hypothetical sports seating application, the probability of “collisions” increases as the venue starts to sell out, and if the correcting action is to generate a ticket for Customer Service, the volume of calls needed could soon get out of hand, let alone the problem of irate customers.</span></li>
</ol></div>Bhaskarhttp://www.blogger.com/profile/14323369551611484731noreply@blogger.com0tag:blogger.com,1999:blog-7229726356350157529.post-4837270976803048922011-03-26T23:49:00.000-04:002011-03-26T23:49:19.901-04:00Eagle Scout Tracking Sheet<div dir="ltr" style="text-align: left;" trbidi="on"><span style="background-color: transparent; color: black; font-family: inherit; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">There is a lot to do for a boy scout to go from the rank of Life to the rank of Eagle. On </span><a href="http://docs.google.com/" style="font-family: inherit;"><span style="background-color: transparent; color: #000099; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: underline; vertical-align: baseline;">Google docs</span></a><span style="background-color: transparent; color: black; font-family: inherit; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"> I have created </span><a href="https://spreadsheets.google.com/ccc?key=0ApN3e-tpxLwOdEhKWkFwZjAtZk13ejFEdnFWb3M4VkE&hl=en" style="font-family: inherit;"><span style="background-color: transparent; color: #000099; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: underline; vertical-align: baseline;">a spreadsheet that a boy scout troop can use to track the progress towards the rank of Eagle of Life scouts</span></a><span style="background-color: transparent; color: black; font-family: inherit; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">. My intention is for this to be a tool for scouts themselves to use, rather than having their parents or troop adult leaders using this. In addition to helping them see where they are in the process, I think seeing where their peers stand helps to motivate scouts!</span><br style="font-family: inherit;" /><span style="background-color: transparent; color: black; font-family: inherit; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"></span><a name='more'></a><br />
<span style="background-color: transparent; color: black; font-family: inherit; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">Make a copy for your troop’s use. While you can download it to your computer, it will be more useful if it remains a shared resource.</span><br style="font-family: inherit;" /><span style="background-color: transparent; color: black; font-family: inherit; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"></span><br style="font-family: inherit;" /><span style="background-color: transparent; color: black; font-family: inherit; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">If you want to experiment, play with Test Scout (modifying only the cells with a </span><span style="background-color: #d5a6bd; color: black; font-family: inherit; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">lilac background</span><span style="background-color: transparent; color: black; font-family: inherit; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"> in the Test Scout sheet). Use New Scout as a template to add an entry for each scout who reaches Life.</span><br style="font-family: inherit;" /><span style="background-color: transparent; color: black; font-family: inherit; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"></span><br style="font-family: inherit;" /><span style="background-color: transparent; color: black; font-family: inherit; font-size: 11pt; font-style: italic; font-weight: normal; text-decoration: none; vertical-align: baseline;">My aim is to make this a useful tracking tool for scouts to use, without spoon-feeding them - I feel strongly that the Eagle rank is meaningful only when earned because actually going through the process gives them a sense of accomplishment and helps them grow.</span><span style="background-color: transparent; color: black; font-family: inherit; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"></span><br />
<br />
<b><span style="font-size: large;">Adding a Scout</span></b><br />
<h2 style="font-family: inherit;"><span style="font-size: large;"><span style="background-color: transparent; color: black; font-style: normal; font-weight: bold; text-decoration: none; vertical-align: baseline;"></span></span></h2><span style="background-color: transparent; color: black; font-family: inherit; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">Adding a new scout to the spreadsheet involves two high level steps: (a) creating a new sheet for the scout, and (b) adding that scout to the Dashboard.</span><br style="font-family: inherit;" /><span style="background-color: transparent; color: black; font-family: inherit; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"></span><ul style="font-family: inherit;"><li style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; list-style-type: disc; text-decoration: none; vertical-align: baseline;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">Duplicate the New Scout sheet, and position it in an appropriate place in the sheets. I suggest ordering the sheets for scouts from youngest to oldest. That way, older scouts scroll off to the right, as they age out of boy scouts, while the sheets for current scouts stay in front of you.</span></li>
<li style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; list-style-type: disc; text-decoration: none; vertical-align: baseline;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">Rename the duplicated sheet with the name of the scout. In the sheet, enter the date that he will turn 18 and the date he advanced to Life. The </span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: underline; vertical-align: baseline;">only</span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"> data to be modified in each sheet are the cells with a </span><span style="background-color: #d5a6bd; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">lilac background</span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">. With a few exceptions - such as the months of each type of leadership experience - most of the data to be entered is dates.</span></li>
<li style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; list-style-type: disc; text-decoration: none; vertical-align: baseline;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">On the Dashboard sheet, create a column for the new scout and copy the data from the New Scout column to the created column. Move the column to keep the scouts ordered from youngest to oldest. Edit each cells in the column you created, changing “New Scout” wherever it occurs to the name of the scout - it must be </span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: underline; vertical-align: baseline;">exactly</span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"> the same name as that of the sheet you created.</span></li>
<li style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; list-style-type: disc; text-decoration: none; vertical-align: baseline;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">In the sharing settings (at the time I write this, Google docs has a “Share” button in the upper right; clicking it offers a “Sharing settings” option), add the e-mail address of each scout - it does not have to be a Google e-mail address - to give the scout access.</span></li>
<li style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; list-style-type: disc; text-decoration: none; vertical-align: baseline;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">Reiterate to the scout that the only cells he should edit are the lilac cells in the sheet with his name.</span></li>
</ul><br style="font-family: inherit;" /><span style="background-color: transparent; color: black; font-family: inherit; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"></span><br style="font-family: inherit;" /><span style="background-color: transparent; color: black; font-family: inherit; font-size: 11pt; font-style: italic; font-weight: normal; text-decoration: none; vertical-align: baseline;">Please post your suggestions for improvement as comments or send them to me. Thank you very much.</span><span style="background-color: transparent; color: black; font-family: inherit; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"></span></div>Bhaskarhttp://www.blogger.com/profile/14323369551611484731noreply@blogger.com0tag:blogger.com,1999:blog-7229726356350157529.post-77170026208387439662011-03-15T07:46:00.002-04:002011-03-18T07:08:09.250-04:00Software Compared to Cities<div dir="ltr" style="text-align: left;" trbidi="on"><div style="background-color: white; font-family: inherit;">(I have previously posted earlier versions of this write up elsewhere.)</div><div style="background-color: white; font-family: inherit;"><br />
</div><div style="background-color: white; font-family: inherit;"></div><div style="background-color: white; font-family: inherit;">Why should a system that is working well need to be replaced?</div><div style="background-color: white; font-family: inherit;"><br />
</div><div style="background-color: white; font-family: inherit;">Successful <span style="color: black;">software</span> systems are like <span style="color: black;">cities</span>. There are <span style="color: black;">cities</span> in Europe that have been continuously inhabited for thousands of years. London or Rome today would be unrecognizable to Julius Caesar, yet the old <span style="color: black;">cities</span> were never abandoned and replaced - they were just continuously re-developed over the centuries. Although we like to discuss replacing major <span style="color: black;">software</span> systems because their quirks annoy us, perhaps we should think of these as limitations that must be lived with, just as in these days of the automobile, we still deal with streets in Boston that were engineered for horses and wagons, and we have no intention of razing and rebuilding downtown. </div><a name='more'></a><br />
<div style="background-color: white; font-family: inherit;">The prospect of "big-bang" conversions of large mission critical <span style="color: black;">software</span> systems gives CIOs ulcers just the way that the prospect of razing and rebuilding entire downtowns gives city fathers ulcers. I suspect that in the not too distant future, a school of thought may evolve to the effect that large <span style="color: black;">software</span> systems will not only not be replaced, but also that we should not plan to replace them. Just as we may tear down buildings and build highways, we should not think in terms of replacing large <span style="color: black;">software</span> systems, but in terms of a process of continuous modernization and renewal (with the <span style="color: black;">software </span>equivalent of urban decay if money is not spent on maintenance when it is needed) </div><div style="background-color: white; font-family: inherit;"><br />
</div><div style="background-color: white; font-family: inherit;">The first lesson is that instead of asking what the life expectancy is of a mission critical <span style="color: black;">software</span> system, it is more meaningful to ask what it takes to keep it healthy and contemporary on an ongoing basis. <span style="color: black;">Cities</span> evolve. With a few notable exceptions of seats of Government, <span style="color: black;">cities</span> are not greenfield creations. They start small, and grow, and what they are good at changes over time.</div><div style="background-color: white; font-family: inherit;"><br />
</div><div style="background-color: white; font-family: inherit;">The second lesson for <span style="color: black;">software</span> is probably that mega projects that try to do everything are almost certainly doomed from the start. The history of attempts to replace <a href="http://worldvista.org/AboutVistA">VistA</a> variants (e.g., CHCS at the Department of Defense) are also not encouraging. Rome was not built in a day.</div><div style="background-color: white; font-family: inherit;"><br />
</div><div style="background-color: white; font-family: inherit;">The third lesson from the analogy is that, since large applications evolve, they will always have aspects that are obsolete and awkward. So, if we love them, we must love them warts and all.</div></div>Bhaskarhttp://www.blogger.com/profile/14323369551611484731noreply@blogger.com0tag:blogger.com,1999:blog-7229726356350157529.post-8375399046469103972011-03-13T14:53:00.005-04:002011-03-27T21:32:29.941-04:00Eventual State Consistency vs. Eventual Path Consistency<div dir="ltr" style="text-align: left;" trbidi="on"><div style="font-family: inherit;"><span class="Apple-style-span" style="border-collapse: separate; color: black; font-size: small; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px;"></span></div><div style="background-color: transparent; font-family: inherit;"><h1 id="internal-source-marker_0.925797660369426"><span style="background-color: transparent; color: black; font-size: 15pt; font-style: normal; font-weight: bold; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">Overview</span></h1><a href="http://www.julianbrowne.com/article/viewer/brewers-cap-theorem"><span style="background-color: transparent; color: #000099; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: underline; vertical-align: baseline; white-space: pre-wrap;">Brewer’s CAP Theorem</span></a><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> </span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">says that a distributed application has to relax at least one of three properties - Consistency, Availability and Partition Tolerance.</span></div><div style="background-color: transparent; font-family: inherit;"><br />
<span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">It is often Consistency that is relaxed in favor of Availability and Partitioning. For example, several popular database engines provide for geographically distributed instances, each of which commits its transactions locally, and then replicates to one or more remote instances. In the event these updates collide with (or conflict with) updates made locally, corrective action can be initiated, either with a blanket rule such as “local always wins”, “remote always wins” or “ignore”; or with something more sophisticated, such as invoking application logic to take corrective action.</span></div><div style="background-color: transparent; font-family: inherit;"><br />
<span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">However, there are applications where detection of colliding updates does not suffice to ensure Consistency (where Consistency is defined as the database always being within the design parameters of the application logic – for example, the “in balance” guarantee that the sums of the assets and liabilities columns of a balance sheet are always equal). There are applications where Consistency may require that the data </span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: underline; vertical-align: baseline; white-space: pre-wrap;">read</span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> by application logic, not just the updates. must also be validated when checking for collisions.</span></div><div style="background-color: transparent; font-family: inherit;"><br />
<span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">I refer to collision detection by validating updates alone as Eventual State Consistency, and collision detection by also validating data read as Eventual Path Consistency.</span><br />
<a name='more'></a><br />
<h1><span style="background-color: transparent; color: black; font-size: 15pt; font-style: normal; font-weight: bold; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">Example</span></h1><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">A and B are two instances. Users initiate financial transactions on two accounts, P and Q, as well as a transaction to change a service charge rate. The service charge rate affects the result of the transactions on P and Q. The business requires that after a service charge rate change, transactions must reflect the new rate or have exceptions logged against them as requiring further action.</span></div><div style="background-color: transparent; font-family: inherit;"><br />
<table style="border-bottom-style: none; border-collapse: collapse; border-color: initial; border-left-style: none; border-right-style: none; border-top-style: none; border-width: initial;"><colgroup></colgroup></table></div><div style="background-color: transparent; font-family: inherit;"><table style="border-collapse: collapse; border-style: none;"><colgroup><col width="120"></col><col width="120"></col><col width="398"></col></colgroup><tbody>
<tr style="height: 0px;"><td style="border-bottom-color: rgb(170, 170, 170); border-bottom-style: dotted; border-bottom-width: 1px; border-left-color: rgb(170, 170, 170); border-left-style: dotted; border-left-width: 1px; border-right-color: rgb(170, 170, 170); border-right-style: dotted; border-right-width: 1px; border-top-color: rgb(170, 170, 170); border-top-style: dotted; border-top-width: 1px; padding-bottom: 0px; padding-left: 7px; padding-right: 7px; padding-top: 0px; vertical-align: top;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: bold; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">Instance A</span></td><td style="border-bottom-color: rgb(170, 170, 170); border-bottom-style: dotted; border-bottom-width: 1px; border-left-color: rgb(170, 170, 170); border-left-style: dotted; border-left-width: 1px; border-right-color: rgb(170, 170, 170); border-right-style: dotted; border-right-width: 1px; border-top-color: rgb(170, 170, 170); border-top-style: dotted; border-top-width: 1px; padding-bottom: 0px; padding-left: 7px; padding-right: 7px; padding-top: 0px; vertical-align: top;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: bold; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">Instance B</span></td><td style="border-bottom-color: rgb(170, 170, 170); border-bottom-style: dotted; border-bottom-width: 1px; border-left-color: rgb(170, 170, 170); border-left-style: dotted; border-left-width: 1px; border-right-color: rgb(170, 170, 170); border-right-style: dotted; border-right-width: 1px; border-top-color: rgb(170, 170, 170); border-top-style: dotted; border-top-width: 1px; padding-bottom: 0px; padding-left: 7px; padding-right: 7px; padding-top: 0px; vertical-align: top;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: bold; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">Comments</span></td></tr>
<tr style="height: 0px;"><td style="border-bottom-color: rgb(170, 170, 170); border-bottom-style: dotted; border-bottom-width: 1px; border-left-color: rgb(170, 170, 170); border-left-style: dotted; border-left-width: 1px; border-right-color: rgb(170, 170, 170); border-right-style: dotted; border-right-width: 1px; border-top-color: rgb(170, 170, 170); border-top-style: dotted; border-top-width: 1px; padding-bottom: 0px; padding-left: 7px; padding-right: 7px; padding-top: 0px; vertical-align: top;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: bold; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"></span></td><td style="border-bottom-color: rgb(170, 170, 170); border-bottom-style: dotted; border-bottom-width: 1px; border-left-color: rgb(170, 170, 170); border-left-style: dotted; border-left-width: 1px; border-right-color: rgb(170, 170, 170); border-right-style: dotted; border-right-width: 1px; border-top-color: rgb(170, 170, 170); border-top-style: dotted; border-top-width: 1px; padding-bottom: 0px; padding-left: 7px; padding-right: 7px; padding-top: 0px; vertical-align: top;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">Change service rate</span></td><td style="border-bottom-color: rgb(170, 170, 170); border-bottom-style: dotted; border-bottom-width: 1px; border-left-color: rgb(170, 170, 170); border-left-style: dotted; border-left-width: 1px; border-right-color: rgb(170, 170, 170); border-right-style: dotted; border-right-width: 1px; border-top-color: rgb(170, 170, 170); border-top-style: dotted; border-top-width: 1px; padding-bottom: 0px; padding-left: 7px; padding-right: 7px; padding-top: 0px; vertical-align: top;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"></span></td></tr>
<tr style="height: 0px;"><td style="border-bottom-color: rgb(170, 170, 170); border-bottom-style: dotted; border-bottom-width: 1px; border-left-color: rgb(170, 170, 170); border-left-style: dotted; border-left-width: 1px; border-right-color: rgb(170, 170, 170); border-right-style: dotted; border-right-width: 1px; border-top-color: rgb(170, 170, 170); border-top-style: dotted; border-top-width: 1px; padding-bottom: 0px; padding-left: 7px; padding-right: 7px; padding-top: 0px; vertical-align: top;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"></span></td><td style="border-bottom-color: rgb(170, 170, 170); border-bottom-style: dotted; border-bottom-width: 1px; border-left-color: rgb(170, 170, 170); border-left-style: dotted; border-left-width: 1px; border-right-color: rgb(170, 170, 170); border-right-style: dotted; border-right-width: 1px; border-top-color: rgb(170, 170, 170); border-top-style: dotted; border-top-width: 1px; padding-bottom: 0px; padding-left: 7px; padding-right: 7px; padding-top: 0px; vertical-align: top;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">Transaction on Q</span></td><td style="border-bottom-color: rgb(170, 170, 170); border-bottom-style: dotted; border-bottom-width: 1px; border-left-color: rgb(170, 170, 170); border-left-style: dotted; border-left-width: 1px; border-right-color: rgb(170, 170, 170); border-right-style: dotted; border-right-width: 1px; border-top-color: rgb(170, 170, 170); border-top-style: dotted; border-top-width: 1px; padding-bottom: 0px; padding-left: 7px; padding-right: 7px; padding-top: 0px; vertical-align: top;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">Transaction on Q uses new service charge rate.</span></td></tr>
<tr style="height: 0px;"><td style="border-bottom-color: rgb(170, 170, 170); border-bottom-style: dotted; border-bottom-width: 1px; border-left-color: rgb(170, 170, 170); border-left-style: dotted; border-left-width: 1px; border-right-color: rgb(170, 170, 170); border-right-style: dotted; border-right-width: 1px; border-top-color: rgb(170, 170, 170); border-top-style: dotted; border-top-width: 1px; padding-bottom: 0px; padding-left: 7px; padding-right: 7px; padding-top: 0px; vertical-align: top;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">Transaction on P</span></td><td style="border-bottom-color: rgb(170, 170, 170); border-bottom-style: dotted; border-bottom-width: 1px; border-left-color: rgb(170, 170, 170); border-left-style: dotted; border-left-width: 1px; border-right-color: rgb(170, 170, 170); border-right-style: dotted; border-right-width: 1px; border-top-color: rgb(170, 170, 170); border-top-style: dotted; border-top-width: 1px; padding-bottom: 0px; padding-left: 7px; padding-right: 7px; padding-top: 0px; vertical-align: top;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"></span></td><td style="border-bottom-color: rgb(170, 170, 170); border-bottom-style: dotted; border-bottom-width: 1px; border-left-color: rgb(170, 170, 170); border-left-style: dotted; border-left-width: 1px; border-right-color: rgb(170, 170, 170); border-right-style: dotted; border-right-width: 1px; border-top-color: rgb(170, 170, 170); border-top-style: dotted; border-top-width: 1px; padding-bottom: 0px; padding-left: 7px; padding-right: 7px; padding-top: 0px; vertical-align: top;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">Transaction on P uses old rate since the rate change has not propagated to A.</span></td></tr>
<tr style="height: 0px;"><td style="border-bottom-color: rgb(170, 170, 170); border-bottom-style: dotted; border-bottom-width: 1px; border-left-color: rgb(170, 170, 170); border-left-style: dotted; border-left-width: 1px; border-right-color: rgb(170, 170, 170); border-right-style: dotted; border-right-width: 1px; border-top-color: rgb(170, 170, 170); border-top-style: dotted; border-top-width: 1px; padding-bottom: 0px; padding-left: 7px; padding-right: 7px; padding-top: 0px; vertical-align: top;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">Apply replicated service rate change</span></td><td style="border-bottom-color: rgb(170, 170, 170); border-bottom-style: dotted; border-bottom-width: 1px; border-left-color: rgb(170, 170, 170); border-left-style: dotted; border-left-width: 1px; border-right-color: rgb(170, 170, 170); border-right-style: dotted; border-right-width: 1px; border-top-color: rgb(170, 170, 170); border-top-style: dotted; border-top-width: 1px; padding-bottom: 0px; padding-left: 7px; padding-right: 7px; padding-top: 0px; vertical-align: top;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"></span></td><td style="border-bottom-color: rgb(170, 170, 170); border-bottom-style: dotted; border-bottom-width: 1px; border-left-color: rgb(170, 170, 170); border-left-style: dotted; border-left-width: 1px; border-right-color: rgb(170, 170, 170); border-right-style: dotted; border-right-width: 1px; border-top-color: rgb(170, 170, 170); border-top-style: dotted; border-top-width: 1px; padding-bottom: 0px; padding-left: 7px; padding-right: 7px; padding-top: 0px; vertical-align: top;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">Change applied. There is no collision in A, and Consistency is maintained since the transaction on P precedes the rate change.</span></td></tr>
<tr style="height: 0px;"><td style="border-bottom-color: rgb(170, 170, 170); border-bottom-style: dotted; border-bottom-width: 1px; border-left-color: rgb(170, 170, 170); border-left-style: dotted; border-left-width: 1px; border-right-color: rgb(170, 170, 170); border-right-style: dotted; border-right-width: 1px; border-top-color: rgb(170, 170, 170); border-top-style: dotted; border-top-width: 1px; padding-bottom: 0px; padding-left: 7px; padding-right: 7px; padding-top: 0px; vertical-align: top;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">Apply replicated transaction on Q</span></td><td style="border-bottom-color: rgb(170, 170, 170); border-bottom-style: dotted; border-bottom-width: 1px; border-left-color: rgb(170, 170, 170); border-left-style: dotted; border-left-width: 1px; border-right-color: rgb(170, 170, 170); border-right-style: dotted; border-right-width: 1px; border-top-color: rgb(170, 170, 170); border-top-style: dotted; border-top-width: 1px; padding-bottom: 0px; padding-left: 7px; padding-right: 7px; padding-top: 0px; vertical-align: top;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"></span></td><td style="border-bottom-color: rgb(170, 170, 170); border-bottom-style: dotted; border-bottom-width: 1px; border-left-color: rgb(170, 170, 170); border-left-style: dotted; border-left-width: 1px; border-right-color: rgb(170, 170, 170); border-right-style: dotted; border-right-width: 1px; border-top-color: rgb(170, 170, 170); border-top-style: dotted; border-top-width: 1px; padding-bottom: 0px; padding-left: 7px; padding-right: 7px; padding-top: 0px; vertical-align: top;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">Change applied. There is no collision detected by A in either the update, or any data read by logic to compute the update.</span></td></tr>
<tr style="height: 0px;"><td style="border-bottom-color: rgb(170, 170, 170); border-bottom-style: dotted; border-bottom-width: 1px; border-left-color: rgb(170, 170, 170); border-left-style: dotted; border-left-width: 1px; border-right-color: rgb(170, 170, 170); border-right-style: dotted; border-right-width: 1px; border-top-color: rgb(170, 170, 170); border-top-style: dotted; border-top-width: 1px; padding-bottom: 0px; padding-left: 7px; padding-right: 7px; padding-top: 0px; vertical-align: top;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"></span></td><td style="border-bottom-color: rgb(170, 170, 170); border-bottom-style: dotted; border-bottom-width: 1px; border-left-color: rgb(170, 170, 170); border-left-style: dotted; border-left-width: 1px; border-right-color: rgb(170, 170, 170); border-right-style: dotted; border-right-width: 1px; border-top-color: rgb(170, 170, 170); border-top-style: dotted; border-top-width: 1px; padding-bottom: 0px; padding-left: 7px; padding-right: 7px; padding-top: 0px; vertical-align: top;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">Attempt to apply replicated transaction on P</span></td><td style="border-bottom-color: rgb(170, 170, 170); border-bottom-style: dotted; border-bottom-width: 1px; border-left-color: rgb(170, 170, 170); border-left-style: dotted; border-left-width: 1px; border-right-color: rgb(170, 170, 170); border-right-style: dotted; border-right-width: 1px; border-top-color: rgb(170, 170, 170); border-top-style: dotted; border-top-width: 1px; padding-bottom: 0px; padding-left: 7px; padding-right: 7px; padding-top: 0px; vertical-align: top;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">Instance B should detect a collision, since it should observe that the data that was read by the application logic on A to compute the result of transaction P has changed on B, and therefore Consistency of B cannot be guaranteed. Corrective action should be required.</span></td></tr>
</tbody></table><br />
<span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">Although applying updates would result in the two instances A and B having the same </span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: underline; vertical-align: baseline; white-space: pre-wrap;">state</span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">, they would not have the same </span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: underline; vertical-align: baseline; white-space: pre-wrap;">path through state space</span><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">. There are situations where having the same end state may be acceptable, but other situations where it is not – consider, for example, the case where the path through state space resembles a short-term interest-free loan! In some applications, an audit (e.g., from an examination of the archived journal files of the database) must show that the path through state space is Consistent at the point when each transaction is committed.</span></div><div style="background-color: transparent; font-family: inherit;"><br />
<span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">The situation when there are three instances, A, B and C is significantly more complicated. There are scenarios when transactions processed on A and B can replicate to each other without colliding, but where C is unable to maintain Consistency with respect to transactions processed and committed on A and B, and replicated successfully to each other, because of timing differences between replication to C from A and B.</span><br />
<span class="Apple-style-span" style="border-collapse: separate; color: black; font-size: small; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px;"></span><br />
<h1><span style="background-color: transparent; color: black; font-size: 15pt; font-style: normal; font-weight: bold; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">Corrective Action</span></h1><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"></span></div><div style="background-color: transparent; font-family: inherit;"><span style="background-color: transparent; color: black; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">In a future post, I will discuss one way to take corrective action to restore Consistency, at least in the case of two instances.</span><br />
<h1><span style="background-color: transparent; color: black; font-size: 15pt; font-style: normal; font-weight: bold; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">Update - March 13, 2011</span></h1><span style="font-size: small;">I originally titled this post Eventual consistency vs. eventual Consistency, with the former referring to state consistency and the latter to path consistency. On the <a href="http://groups.google.com/group/nosql-discussion">NoSQL discussion group</a>, John D. Mitchell suggested the name path consistency. Thanks for the good idea, John.</span><br />
<h1><span style="background-color: transparent; color: black; font-size: 15pt; font-style: normal; font-weight: bold; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">Update - March 16, 2011</span></h1><span style="font-size: small;">Alex Popescu pointed out in a comment that the CAP Conjecture was proved. Somehow, I missed that completely. I have been wrong before, and doubtless will be wrong again, but this was like missing the side of a barn at ten feet. I'll try not to get so caught up in my own thoughts next time. Mea Culpa. I have corrected the post.</span><br />
<h1><span style="background-color: transparent; color: black; font-size: 15pt; font-style: normal; font-weight: bold; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">Update - March 27, 2011</span></h1><span style="font-size: small;">"Instance B detects" corrected to "Instance B should detect" and rest of entry in that cell adjusted accordingly. The earlier language threw Jeff Darcy off (see his blog at <a href="http://pl.atyp.us/wordpress/?p=3215">http://pl.atyp.us/wordpress/?p=3215</a>) as indeed it would have mislead anyone who read what I said rather than what I meant. Thanks, Jeff.</span></div></div>Bhaskarhttp://www.blogger.com/profile/14323369551611484731noreply@blogger.com6tag:blogger.com,1999:blog-7229726356350157529.post-85274094536726860902011-02-12T22:55:00.000-05:002011-02-12T23:20:07.397-05:00From 44 seconds to 27 seconds - Simple Tuning of the 3n+1 Benchmark on GT.M<div dir="ltr" style="text-align: left;" trbidi="on">The bottom line first: with a little simple tuning, I was able to improve the performance on my laptop of my benchmark of the 1 to 1,000,000 3n+1 problem.<br />
<ul style="text-align: left;"><li>For four worker processes:</li>
<ul><li>from 44 to 27 seconds</li>
<li>from to 72,026 to 109,311 reads/second</li>
<li>from to 49,298 to 74,828 updates/second</li>
</ul><li>For eight worker processes:</li>
<ul><li>from 248 to 30 seconds</li>
<li>from 12,782 to 109,285 reads/second</li>
<li>from 8,750 to 74,802 updates/second</li>
</ul></ul><br />
<a name='more'></a>In response to <a href="https://libdb.wordpress.com/2011/01/31/revving-up-a-benchmark-from-626-to-74000-operations-per-second">Don Anderson's report of his results</a> on the <a href="http://ksbhaskar.blogspot.com/2010/06/3n1-nosqlkey-valueschema-freesche.html">3n+1database benchmark version 2</a> this post documents some simple tuning of the implementation <a href="http://ksbhaskar.blogspot.com/2010/06/results-for-3n1-benchmark-version-2-for.html">I previously reported</a>. At that time, I did only minimal tuning (<a href="http://fis-gtm.com/">GT.M</a> has fewer knobs to turn and buttons to push than most database engines because when we add tuning knobs and buttons we endeavor to make them self-tuning).<br />
<br />
<b>Notes</b><br />
<ul style="text-align: left;"><li>I did not attempt to tune:</li>
<ul><li>The number of parallel worker threads - one objective of the benchmark is to test the database with access contention, which is simulated with two and four worker processes per CPU (core). [Studying database operation without access contention is like studying a highway without traffic.]</li>
<li>The database block size - GT.M supports database block sizes in multiples of 512 bytes from 512 to 65,024 bytes. Smaller block sizes are computationally more efficient; larger block sizes (at least those which are multiples of the native page size of the underlying file system - 4KB on my laptop) are more efficient for IO). I just used the popular 4KB database block size from GT.M's gdedefaults file.</li>
<li>The access method - GT.M supports the Buffered Global (BG) access method which uses a pool of buffers in shared memory as a cache for database blocks and the Mapped Memory (MM) access method which simply maps database files to the virtual address space of processes that access them, letting the operating system manage caching (MM also provides recoverability). BG is more commonly used, and that is what I benchmarked.</li>
<li>A few other parameters that are not self-tuning, and for many of which the default is often used. For example, there is an option to write a full block worth of bytes, even if the actual data is less than a full block - on some IO subsystems, this may result in a faster and simpler write operation instead of a read-modify-write operation - I just used the default, to write only the actual data.</li>
</ul><li>I ran the tests on both jfs, which is my preferred file system, and ext4, which is popular these days for Linux.</li>
<li>I ran the test for inputs of 1 through 100,000 as well as 1through 1,000,000. I am reporting only the results for the larger problem - running the smaller problem first only gives me an immediate check in case I don't have something set up correctly.</li>
<li>The test program is available and can be downloaded from <a href="http://sourceforge.net/projects/fis-gtm/files/Benchmarking/threeen1/threeen1f.tgz">http://sourceforge.net/projects/fis-gtm/files/Benchmarking/threeen1/threeen1f.tgz</a></li>
<li>A spreadsheet with all results is available at <a href="http://tinyurl.com/Bhaskar3nplus1Results">http://tinyurl.com/Bhaskar3nplus1Results</a> - the benchmark results reported here are the runs dated February 5, 2011.</li>
</ul><ul style="text-align: left;"></ul><br />
<b>Benchmark System</b><br />
<br />
I ran the benchmark on a System 76 laptop with the following specifications (the system referred to as Ardmore in the spreadsheet):<br />
<ul style="text-align: left;"><li>CPU: Intel Core2 Duo T7500 at 2.20GHz</li>
<li>RAM: 4GB 667MHz DDR2</li>
<li>Disk: Seagate ST9200420AS 200GB 7200rpm with SATA interface</li>
<li>OS: 64-bit Ubuntu 10.10 with Linux kernel 2.6.35-25-generic</li>
<li>File system: jfs & ext4</li>
<li>Database: GT.M V5.4-001 64-bit version</li>
</ul><br />
<b>Baseline</b><br />
<br />
I first ran the test with default settings from the gdedefaults file in the GT.M distribution: a database block size of 4KB with 1,000 global buffers (corresponding to a database cache of 4MB) and 128 journal buffers (each of 512 bytes, corresponding to 64KB of journal file buffers). This yielded the following run times in seconds:<br />
<ul style="text-align: left;"><li> Four worker processes - jfs: 44; ext4: 66</li>
<li>Eight worker processes - jfs: 248; ext4: 104</li>
</ul><br />
I believe that the reason eight workers were so much worse than four resulted from churning the database blocks cached in the global buffer pool. The database grows to 138MB, and the 3n+1 problem results in only very limited locality of references. So more concurrent processes results in a buffer pool that is too small for a large working set.<br />
<br />
<br />
<b>Increase database buffer pool to 5,000 buffers</b><br />
<br />
With 5,000 buffers (20MB buffer pool), performance increases with eight workers, improves slightly with ext4 but decreases with four on jfs. I do not have a good explanation for the anomalous decrease - unless increasing the buffer pool impacts overall memory usage (for example by reducing the file buffer cache - an unlikely scenario when going from 4MB to 20MB on a machine with 4GB RAM), increasing the buffer pool should never reduce throughput.<br />
<br />
With GT.M's daemonless database engine, concurrent processes cooperate to manage the database: just one process accessing the database does not give optimal performance, and adding processes increases performance (only up to a point of course). In this case, eight processes perform better than four.<br />
<ul style="text-align: left;"><li> Four worker processes - jfs: 81; ext4: 61<br />
</li>
<li>Eight worker processes - jfs: 52; ext4: 40<br />
</li>
</ul><br />
<b>Increase journal buffers to 2,000</b><br />
<br />
I increased the number of journal buffers to 2,000 (1MB) expecting performance to be about the same, and if anything slightly better (there should be no penalty to increasing the number of journal buffers). I was a little surprised that two increased and one decreased (as the resolution of reported times is one second, the difference between 39 seconds and 40 seconds is not meaningful). I don't yet have a good explanation for this anomaly.<br />
<ul style="text-align: left;"><li> Four worker processes - jfs: 75; ext4: 66<br />
</li>
<li>Eight worker processes - jfs: 66; ext4: 39<br />
</li>
</ul>In my opinion, this configuration (5,000 global buffers & 2,000 journal buffers) reflects a common scenario for small to medium database applications where the in-memory cache size is perhaps 10-20% of the database size.<br />
<br />
<b>Increase database buffer pool to 35,000 buffers</b><br />
<br />
To replicate Don Anderson's test where he had a RAM cache large enough for the entire database, I increased the number of database buffers to 35,000. The database was still operated so as to be recoverable from the journal files to exactly the same extent as before.<br />
<br />
This gave me the best results. I ran each test three times to verify that the results were similar each time.<br />
<ul style="text-align: left;"><li> Four worker processes - jfs: 27, 27, 29; ext4: 30, 30, 34<br />
</li>
<li>Eight worker processes - jfs: 29, 29, 30; ext4: 30, 31,36<br />
</li>
</ul>The median update and reads rates were:<br />
<ul style="text-align: left;"><li>Four worker processes</li>
<ul><li>jfs: 80,332 updates/second & 117,369 reads/second</li>
<li>ext4: 72,308 updates/second & 105,642 reads/second<br />
</li>
</ul><li>Eight worker processes</li>
<ul><li>jfs: 74,828 updates/second & 109,311 reads/second</li>
<li>ext4: 70,008 updates/second and 102,266 reads/second<br />
</li>
</ul></ul><br />
<b>In conclusion</b><br />
<br />
A little effort in tuning the database provides improved results over the default. It is also worth noting that even with the increased contention of eight parallel worker processes (four processes per core), performance was very good except in the cases where they were churning a too-small buffer pool.</div>Bhaskarhttp://www.blogger.com/profile/14323369551611484731noreply@blogger.com8tag:blogger.com,1999:blog-7229726356350157529.post-47847918737960186212011-02-02T13:52:00.000-05:002011-02-10T22:08:08.721-05:00Responses to Dan Weinreb's comments of February 1, 2011<div dir="ltr" style="text-align: left;" trbidi="on">I am responding to Dan Weinreb's comments to my post <a href="http://ksbhaskar.blogspot.com/2011/01/comments-in-response-to-don-andersons.html">Comments in response to Don Anderson's 3n+1 benchmark</a> with another blog entry because this was too long to post as a reply.<br />
<a name='more'></a><br />
<br />
Thanks for the comments, Dan. Let me start by echoing and responding to your closing comment, because that is a topic near and dear to my heart - it was the paucity of well-specified benchmarks for side by side comparisons that started me off down this path some months ago. I currently seek benchmark problems to meaningfully show how a platform (the combination of database engine and OS) degrade when pushed to the limits by ever increasing workloads.<br />
<br />
By way of background in response to your other comments, let us first look at the benchmark problem. I admit it is slightly contrived to use a database but the 3n+1 problem has the virtue of being easily understood and programmed. Also, using a recoverable database is not unreasonable for long-running computational problems.<br />
<br />
For this problem, the concept of a transaction is not well defined, unlike, say, transfering money from my checking account to my savings account where the application requirements clearly delineate the computational boundaries to which ACID semantics must apply. In the case of the 3n+1 problem, Consistency can mean that for the longest sequence found so far, the lengths for the integers in that sequence should be recorded.<br />
<br />
So, I believe my concept of recoverability is the same as yours. If the system crashes, Durability requires that the database must be restorable to its last Consistent state. For the 3n+1 problem, Atomicity and Isolation are not meaningful.<br />
<br />
A real world implementation of Schrödinger's cat is pipelining and parallel execution in CPUs, where the black box view is well defined but the glass box view (such as the state of the program counter) is fuzzy (i.e., trying to get a clear glass box view forces the system to give you a black box view). But the hardware guarantees a Consistent state when an external event mandates it, such as an interrupt that requires state to be saved for future resumption, or when a debugger attaches to a process.<br />
<br />
GT.M implements pipelining in the database engine (as I am sure other engines do, but GT.M is the only one I am familiar with). Journal buffers are filled and database blocks in the cache are dirtied. Journal buffers are written out and "hardened" with an fsync() before the corresponding database blocks are written out. The glass box view of the database is fuzzy. Discovery of a new longest sequence is like an external event, which requires and results in a Consistent state being made Durable.<br />
<br />
With that background, in response to you question as to whether this is a database benchmark, yes, this is a database benchmark. It measures the performance of a database that is operated in a recoverable mode for the problem solution.<br />
<br />
With respect to your comment on the sizes of keys, this problem as discussed does use keys in the tens of bytes. But note that its easy to make the keys longer, should one wish to benchmark longer keys - since integers are converted to strings by replacing each digit with a string, using longer strings for each digit would use longer keys. Similarly, the values associated with each key are also easily made longer. GT.M also supports longer keys and values than the benchmark uses.<br />
<br />
Indeed, we have used this same program to benchmark file systems by using an upper limit of 40,000,000, during the course of which the largest integer encountered is the fifteen digit integer 474,637,698,851,092 which the unchanged threeen1f program represents as a string of 74 UTF-8 characters / 124 bytes.<br />
<br />
You mention replication. GT.M also allows logical multi site (LMS) application configurations to be deployed. Every database engine makes different engineering trade-offs with respect to CAP limitations. Depending on the engineering trade-offs made between consistency, availability and performance, replication can certainly affect database performance. I would like to come up with a problem that allows apples-to-apples comparisons with respect to replication, but have not yet had that light bulb moment of a problem whose solutions can overcome the different engineering trade-offs. GT.M has at least one LMS configuration operating with instances in England, France and California, and at least for the trade-offs made by GT.M, replication does not materially affect performance.<br />
<br />
Your comment with respect to tuning are spot on. Even in an apples-to-apples comparison, no two apples are ever <i>exactly</i> alike!</div>Bhaskarhttp://www.blogger.com/profile/14323369551611484731noreply@blogger.com2tag:blogger.com,1999:blog-7229726356350157529.post-43537175730011714952011-01-31T15:29:00.000-05:002011-02-10T22:10:11.370-05:00Comments in response to Don Anderson's 3n+1 benchmark<div dir="ltr" style="text-align: left;" trbidi="on"><span style="font-size: small;"><span style="font-family: Verdana,sans-serif;">I am thrilled that </span><a href="https://libdb.wordpress.com/2011/01/31/revving-up-a-benchmark-from-626-to-74000-operations-per-second" style="font-family: Verdana,sans-serif;">Don Anderson has responded</a><span style="font-family: Verdana,sans-serif;"> to a </span><a href="http://ksbhaskar.blogspot.com/2010/06/3n1-nosqlkey-valueschema-freesche.html" style="font-family: Verdana,sans-serif;">benchmarking problem I proposed</a><span style="font-family: Verdana,sans-serif;"> aimed at apples to apples benchmarks of databases and platforms.<a name='more'></a></span><br style="font-family: Verdana,sans-serif;" /><br style="font-family: Verdana,sans-serif;" /><span style="font-family: Verdana,sans-serif;">I did virtually no tuning when I </span><a href="http://ksbhaskar.blogspot.com/2010/06/results-for-3n1-benchmark-version-2-for.html" style="font-family: Verdana,sans-serif;">posted a solution</a><span style="font-family: Verdana,sans-serif;"> using </span><a href="http://fis-gtm.com/" style="font-family: Verdana,sans-serif;">FIS GT.M</a><span style="font-family: Verdana,sans-serif;">. Now that Anderson has posted results with tuning, I am motivated to do some performance tuning to see how much better I can get my program to run. I will post results when I have them.</span><br style="font-family: Verdana,sans-serif;" /><br style="font-family: Verdana,sans-serif;" /><span style="font-family: Verdana,sans-serif;">Incidentally I used the benchmark to to </span><a href="http://tinco.pair.com/bhaskar/gtm/doc/misc/101005-1dthreeen1fFilesystemBenchmark.pdf" style="font-family: Verdana,sans-serif;">compare several Linux file systems </a><span style="font-family: Verdana,sans-serif;">- in a nutshell, from fastest to slowest, the typical ranking was ext2, ext4, xfs, jfs, ext3 and btrfs.</span><br style="font-family: Verdana,sans-serif;" /><br style="font-family: Verdana,sans-serif;" /><b><span style="font-family: Verdana,sans-serif;">Some Comments and Corrections to Anderson's Observations</span></b><br style="font-family: Verdana,sans-serif;" /><br style="font-family: Verdana,sans-serif;" /><span style="font-family: Verdana,sans-serif;">Apropos transaction processing and ACID transactions. Since many NoSQL databases don't support transaction processing and ACID transactions, I did not require the use of transaction processing in the problem statement, but did require the database to be operated for recoverability (understanding that apples to apples comparisons of recoverability algorithms are not straightforward). GT.M supports both fully ACID transactions (TP) as well as non-TP updates with slightly relaxed Durability (which are also fully journaled and recoverable - the run-time system ensures that no database block is written to disk until the journal records for that update are written to the journal file and an fsync() performed). In order to ensure serialization, a TP commit also commits any prior non-TP updates. The JNLFLUSH that Anderson writes about is not needed for normal operation. My benchmark program uses a combination of TP and non-TP - results are updated using TP commits, but intermediate computations use non-TP updates. So, the database is indeed operated in a recoverable mode.</span><br style="font-family: Verdana,sans-serif;" /><br style="font-family: Verdana,sans-serif;" /><span style="font-family: Verdana,sans-serif;">Apropos his comments about "a stopwatch being started after the runners hear the starting gun", what he is evidently referring to are these two lines of code:</span><br style="font-family: Verdana,sans-serif;" /><br style="font-family: Verdana,sans-serif;" /><span style="font-family: "Courier New",Courier,monospace;"> Lock -l1 ; Release lock so processes can run</span></span><br />
<span style="font-size: small;"><span style="font-family: "Courier New",Courier,monospace;"> Set startat=$HOROLOG ; Get starting time</span><br style="font-family: "Courier New",Courier,monospace;" /><br style="font-family: Verdana,sans-serif;" /><span style="font-family: Verdana,sans-serif;">The situation at that point is that several worker processes have been spawned, and are waiting for the parent process to release lock l1. In theory, we want the lock release and the starting of the timer to happen at the same time. The reason I release the lock first is that interprocess communication is involved for the workers to be able to start their work, whereas the timer is started at the very next line of the same process - in other words, doing them in this order gets the start time closer to when the workers actually start. But even if I were to reverse the lines, it would only affect times by milliseconds in the worst case, because the parent process is not getting a lock: it is <i>releasing</i> a lock which it owns, which is a near instantaneous operation.</span><br style="font-family: Verdana,sans-serif;" /><br style="font-family: Verdana,sans-serif;" /><span style="font-family: Verdana,sans-serif;">Extending Anderson's analogy, the starting gun of a race starts the stopwatch. That's what we have here.</span><br style="font-family: Verdana,sans-serif;" /><br style="font-family: Verdana,sans-serif;" /><b><span style="font-family: Verdana,sans-serif;">A Few Minor Nits</span></b><br style="font-family: Verdana,sans-serif;" /><br style="font-family: Verdana,sans-serif;" /><span style="font-family: Verdana,sans-serif;">Anderson writes "GT.M (the language formally known as MUMPS)". Actually, the formal name of the language (commonly used in health care applications, just as SQL is commonly used in business applications) is M (ISO/IEC 11756:1999), but it is informally known as MUMPS (as in Massachusetts General Hospital Utilty Multi-Programming System). GT.M is a FOSS implementation of a transaction processing database engine with an implementation of M. It is easy to use the database from C, as well as Python, Perl and PHP. There are API compatible clients for other databases (go to <a href="http://mgateway.com/">M/Gateway</a> to see some). Indeed, the <a href="http://www.mgateway.com/docs/universalNoSQL.pdf">Universal NoSQL white paper by George James and Rob Tweed</a> discusses how the GT.M engine can store all four common NoSQL use cases.</span><br style="font-family: Verdana,sans-serif;" /><br style="font-family: Verdana,sans-serif;" /><span style="font-family: Verdana,sans-serif;">To access current GT.M documentation, go to the <a href="http://fis-gtm.com/">GT.M home page</a> and click on the User Documentation tab. The link in Anderson's post is to old documentation on Source Forge - which remains there so as to not break old web pages that may point to it.</span><br style="font-family: Verdana,sans-serif;" /><br style="font-family: Verdana,sans-serif;" /><span style="font-family: Verdana,sans-serif;">GT.M has functionality for creating LMS (Logical Multi Site) application configurations as described in the user documentation, with a 20,000 kilometer distance limit between instances.</span><br style="font-family: Verdana,sans-serif;" /><br style="font-family: Verdana,sans-serif;" /><span style="font-family: Verdana,sans-serif;">When Anderson says, "I used 3 threads, as that seemed to be the sweet spot", he misses one aspect of the benchmarking problem. In order to simulate a database under load (dealing with concurrency has costs), it requires at least two processes per core. I suspect that going from 3 threads to 4 threads (since his computer has a dual core CPU) would not affect his results too much. I did not tune my results for the number of cores by the way - my results include runs with 8 worker processes on a dual core CPU. Someday, I'd like to see if I can come up with an apples to apples way to compare database engines under heavy load - how a system performs as it is pushed to the breaking point tells us more about its robustness than how it runs with resources to spare.</span></span></div>Bhaskarhttp://www.blogger.com/profile/14323369551611484731noreply@blogger.com3tag:blogger.com,1999:blog-7229726356350157529.post-71691629707779270092010-06-12T11:18:00.001-04:002011-02-12T23:04:35.612-05:00Results for 3n+1 Benchmark version 2 for GT.M<div dir="ltr" style="text-align: left;" trbidi="on"><h1><a name='more'></a></h1><h1>Results for Enhanced 3n+1 Benchmark for GT.M - Work laptop on 20100612</h1><h2>Computing Platform - System 76 laptop</h2>CPU - Intel Core2 Duo T7500 2.20GHz<br />
RAM - 4GB<br />
Disk - Seagate 200GB 7200rpm with SATA interface<br />
OS - Kubuntu 9.10 64-bit Linux kernel 2.6.31-14-generic<br />
File system - jfs<br />
<br />
Database - GT.M V5.4-000A 64-bit version<br />
<br />
<h2>Program</h2>The source code for the program can be downloaded from <a href="http://sourceforge.net/projects/fis-gtm/files/Benchmarking/threeen1/threeen1f.tgz">http://sourceforge.net/projects/fis-gtm/files/Benchmarking/threeen1/threeen1f.tgz</a> <br />
<br />
Note that the resolution of time measured and reported by this program is one second.<br />
<br />
This program runs in UTF-8 mode. It stores a database that is logically ^cycle(11)=15 as ^cycle("eins eins") with a value "eins <span style="font-family: verdana;">пять". The actual strings used for each digit are specified in the comments of the source program at label digits. Encoded strings in UTF-8 demonstrates that the database is not limited to ASCII or an ISO-8859 variant (in fact, the keys and values can be any arbitrary sequence of bytes).</span><br />
<br />
<h2>Database Configuration</h2>Block size - 4096 bytes<br />
Global buffers - 5000<br />
Journal buffers - 2000<br />
Type of journaling - before image (for backward recovery)<br />
<br />
The journal file and database were on the same disk. This is not how production systems are configured, but my laptop has only one hard drive. If the database and journals were on separate disks, performance may be a little better.<br />
<h2>Licenses</h2>GT.M is licensed under GNU Affero General Public License version 3.<br />
<h2>Results</h2>The benchmark was run three times. The update rates are colored <span style="font-family: trebuchet ms;"><span style="color: red;">red </span></span>and read rates are colored <span style="color: blue;">blue</span>.<br />
<br />
$ cat threeen1.dat <br />
1 100000 4 5000<br />
1 100000 8 5000<br />
1 1000000 4 5000<br />
1 1000000 8 5000<br />
$ gtm_icu_version=4.2 gtm_chset=UTF-8 LC_CTYPE=en_US.utf8 /usr/lib/fis-gtm/V5.4-000A_x86_64/gtm -run threeen1f <threeen1.dat <br />
1 100,000 4 5,000 350 1,570,824,736 5 217,350 317,350 <span style="color: red;">43,470</span> <span style="color: blue;">63,470</span><br />
1 100,000 8 5,000 350 1,570,824,736 7 218,379 318,379 <span style="color: red;">31,197</span> <span style="color: blue;">45,483</span><br />
1 1,000,000 4 5,000 524 56,991,483,520 52 2,169,141 3,169,141 <span style="color: red;">41,714</span> <span style="color: blue;">60,945</span><br />
1 1,000,000 8 5,000 524 56,991,483,520 46 2,169,919 3,169,919 <span style="color: red;">47,172</span> <span style="color: blue;">68,911</span><br />
$ gtm_icu_version=4.2 gtm_chset=UTF-8 LC_CTYPE=en_US.utf8 /usr/lib/fis-gtm/V5.4-000A_x86_64/gtm -run threeen1f <threeen1.dat <br />
1 100,000 4 5,000 350 1,570,824,736 4 217,686 317,686 <span style="color: red;">54,422</span> <span style="color: blue;">79,422</span><br />
1 100,000 8 5,000 350 1,570,824,736 7 218,660 318,660 <span style="color: red;">31,237</span> <span style="color: blue;">45,523</span><br />
1 1,000,000 4 5,000 524 56,991,483,520 52 2,169,118 3,169,118 <span style="color: red;">41,714</span> <span style="color: blue;">60,945</span><br />
1 1,000,000 8 5,000 524 56,991,483,520 48 2,170,464 3,170,464 <span style="color: red;">45,218</span> <span style="color: blue;">66,051</span><br />
$ gtm_icu_version=4.2 gtm_chset=UTF-8 LC_CTYPE=en_US.utf8 /usr/lib/fis-gtm/V5.4-000A_x86_64/gtm -run threeen1f <threeen1.dat <br />
1 100,000 4 5,000 350 1,570,824,736 5 217,823 317,823 <span style="color: red;">43,565</span> <span style="color: blue;">63,565</span><br />
1 100,000 8 5,000 350 1,570,824,736 7 218,384 318,384 <span style="color: red;">31,198</span> <span style="color: blue;">45,483</span><br />
1 1,000,000 4 5,000 524 56,991,483,520 54 2,169,256 3,169,256 <span style="color: red;">40,171</span> <span style="color: blue;">58,690</span><br />
1 1,000,000 8 5,000 524 56,991,483,520 48 2,169,961 3,169,961 <span style="color: red;">45,208</span> <span style="color: blue;">66,041</span><br />
<br />
The database was being operated with journaling for rapid backward recovery (i.e., recovery would not need a backup to be restored).<br />
<br />
<br />
</div>Bhaskarhttp://www.blogger.com/profile/14323369551611484731noreply@blogger.com0tag:blogger.com,1999:blog-7229726356350157529.post-18911937478232045792010-06-12T10:22:00.001-04:002011-02-12T23:12:11.950-05:003n+1 NoSQL/Key-value/Schema-free/Sche... - version 2<div dir="ltr" style="text-align: left;" trbidi="on"><h1 style="text-align: left;"></h1>Problem statement of the second version of the benchmark. An earlier version of this benchmark problem statement can be found at <br />
<a href="http://ksbhaskar.blogspot.com/2010/02/3n1-nosqlkey-valueschema-freesche.html" id="pswj" title="Click here to visit the statement of the first version of the problem">http://ksbhaskar.blogspot.com/2010/02/3n1-nosqlkey-valueschema-freesche.html</a><br />
<h2 style="text-align: left;">Motivation</h2><div style="text-align: left;">This is an attempt to create a benchmark for apples to apples comparisons of databases that are generally described as NoSQL, key-value, schema-free or schema-less databases. The goals are to create a benchmark that:<br />
<br />
</div><ul style="text-align: left;"><li>is simple to understand and code in most programming languages;</li>
<li>performs a non-trivial amount of representative activity - reads and updates, access contention, recovery, etc.; and</li>
<li>generates results that can be easily replicated and verified by others.<a name='more'></a></li>
</ul><br />
Since many popular databases of the genre being discussed do not support <a href="http://en.wikipedia.org/wiki/ACID" id="q8g3" target="_blank" title="Click here to read the Wikipedia article on ACID transactions">ACID (Atomic, Consistent, Isolated, Durable) transactions</a>, the benchmark does not require transaction processing, although there is no prohibition on using such functionality if available.<br />
<br />
<div><i>If your database supports strings with international character sets with a multi-byte encoding such as UTF-8, please do demonstrate their usage, since it will help show your database in a more attractive light.</i><br />
<h2 style="text-align: left;">Background</h2><div style="text-align: left;">Consider a sequence of positive integers <i>n</i><sub>0</sub>, <i>n</i><sub>1</sub>, <i>n</i><sub>2</sub> ... <i>n</i><sub><i>i</i>+1</sub> is generated from <i>n<sub>i</sub></i> as follows:<br />
<br />
</div><ul style="text-align: left;"><li>if <i>n<sub>i</sub></i> is even, <i>n<sub>i+1</sub></i>=<i>n<sub>i</sub></i>/2</li>
<li>if <i>n<sub>i</sub></i> is odd, <i>n<sub>i+1</sub></i>=3*<i>n<sub>i</sub></i>+1</li>
</ul><div style="text-align: left;"><br />
If <i>n</i><sub>0</sub>=1, this leads to the cycle 1, 4, 2, 1 ... The <a href="http://en.wikipedia.org/wiki/Collatz_conjecture" id="s5ud" target="_blank" title="Click here to read the Wikipedia entry on the Collatz conjecture">Collatz conjecture</a> says that for any positive integer starting point <i>n</i><sub>0</sub>, the sequence eventually leads to 1. The sequence starting with 4 and ending at 1 has three steps. The sequence starting with 6 and ending with 1 (6, 3, 10, 5, 16, 8, 4, 2, 1) has 8 steps, and the highest integer encountered in the sequence is 16.</div><h2 style="text-align: left;">Problem</h2><div style="text-align: left;">Write a program that reads from its standard input three positive integers <i>i</i>, <i>j</i> (0<<i>i</i><<i>j</i><10,000,000,001), <i>k</i> (>0), and an optional fourth integer <i>l</i> (>0), each separated by a single space. It should implement a multiple parallel execution stream (multi-process or multi-threaded) solution that uses a database to compute and report the number of steps in the largest Collatz sequence of any integer in the range, as well as the largest integer encountered when computing those sequences. The input range should be divided into blocks of integers, such that each execution stream looks for the next block not already claimed, claims it, computes and stores results for the integers in it, then moves to the next available block until the entire range is computed. The program should also collect and report statistics on database updates and reads, as well as overall update and read rates.<br />
<br />
More specifically, on its standard output, the program should print the following separated by spaces:</div><div style="text-align: left;"><br />
</div><div style="text-align: left;"><ul><li>the inputs, <i>i</i> and <i>j</i>; representing the range of integers over which the Collatz sequence should be computed<br />
</li>
<li>the number of parallel execution streams, which must be at least twice the number of CPUs or cores (which is reported in <span style="font-family: courier new;">/proc/cpuinfo</span> on Linux); if the input number <i>k</i> greater than or equal to this number, simply print it and use it, otherwise print it in the form <i>k<sub>0</sub></i><span style="font-family: courier new;">-></span><i>k<sub>1</sub></i> where <i>k<sub>0</sub></i> is input number, and <i>k<sub>1</sub></i> is the actual number of execution streams used (i.e., twice the numbers of CPUs or cores)</li>
<li>the size of blocks of integers that each execution stream will work on at a time; if this is not specified, or is greater than the range divided by the number of parallel execution streams, it should be forced to the range divided by the number of parallel execution streams (one block may be smaller than the others); if the input number <i>l</i> is greater than zero and not greater than the range divided by the number of streams, simply print it, otherwise print it in the form <i>l<sub>0</sub></i><span style="font-family: courier new;">-></span><i>l<sub>1</sub></i> where <i>l<sub>0</sub></i> is the input number and <i>l<sub>1</sub></i> is the actual block size<br />
</li>
<li>the maximum number of steps in the sequence for any integer <i>i</i> through <i>j</i></li>
<li>the largest integer reached when computing the steps for any integer in the sequence <i>i</i> through <i>j</i> (caveat: as this will significantly overflow a 32-bit integer, you must use something larger)<br />
</li>
<li>the number of elapsed (wall clock) seconds (fractional seconds optional) it took to solve the problem</li>
<li>the number of updates performed on the database (which will be much higher than <i>j</i>-<i>i</i>+1 since two or more execution streams can potentially update the same node at the same time and because the program will work on integers larger than <i>j</i>); the number of updates to the nodes where the Collatz sequences are tracked should be counted; counting database updates for coordination and control is optional<br />
</li>
<li>the number of reads performed on the database (which will be much higher than <i>j</i>-<i>i</i>+1); the number of reads to the nodes where the Collatz sequences are tracked should be counted, those for coordination and control are optional<br />
</li>
<li>the update rate calculated by the number of updates divided by the elapsed time; and</li>
<li>the read rate calculated by the number of reads divided by the elapsed time</li>
</ul><div style="text-align: left;"><br />
</div>The code does not need to validate inputs. Here are required elements of the solution:<br />
<br />
</div><ul style="text-align: left;"><li>Your solution must use a database configured to be recoverable. In other words, if the system were to crash in the middle of solving a problem, rebooting the computer, recovering the database and restarting the program with the same input <i>i</i> and <i>j</i> uses the partial results in the database computed prior to the crash. Note that the 3n+1 problem does not have the concept of atomic transactions to which a database can supply ACID properties. However, the concepts of Consistency and Durability are meaningful - when a new longest 3n+1 sequence is computed, it must be made Durable, and the lengths of the 3n+1 sequences of each integer in its sequence must also be made Durable. A recovery mechanism of replicating to another system is acceptable as long as the replication is synchronous - i.e., an update is not considered committed to the database on the originating instance until it is received and accepted by the replicating instance. When submitting results, please document the recovery technique used (forward recovery, which requires a backup to be restored and updates applied from a journal file; backward recovery which recovers the database in place from a journal file; etc.).</li>
</ul><div style="text-align: left;"><br />
</div><ul style="text-align: left;"><li>For convenience, your program is allowed to accept multiple lines of input, processing each line in turn. However, between lines, you must empty, clear, re-initialize (whatever term your database engine uses) the data in the database, so that the computation for each line starts out with a database with no data. Of course, this means that in the event of a crash, only the data for the specific <i>i</i> and <i>j</i> being worked is recovered, and resuming and completing the problem only refers to the solution for that <i>i</i> and <i>j</i>.</li>
</ul><div style="text-align: left;"><br />
</div><ul style="text-align: left;"><li>In order to factor in the effect of dealing with access contention and concurrency control, your solution must use <u>at least</u> the greater of <i>k</i> or two concurrent execution streams (threads, processes, or both) per CPU core to solve the problem. So, if your CPU has two cores, and <i>k</i> is 3, you must use at least 4 execution streams.</li>
</ul><br />
<ul><li>The problem involves only integer values with integer keys in the database. This is not representative of real world applications, which more commonly need to use string keys and values. The program should convert the integer keys and values for the number of steps to be stored as strings rather than as integers. For example, instead of creating an entry for a node with a subscript of 11 with a value of 15, you would create an entry with a subscript of "one one" with a value of "one five". Except for nodes storing the number of steps in the Collatz seqence for each integer, you are free to use numerics for all other purposes, including program flow control.</li>
</ul><h2 style="text-align: left;">Submission</h2><div style="text-align: left;">Post your results on the web. You should include:<br />
<br />
</div><ul style="text-align: left;"><li>The computing platform on which you ran your benchmark (details of CPU, RAM, disk type, operating system).</li>
<li>Your program. Your program must either be released under a FOSS license (either determined to be <a href="http://www.gnu.org/licenses/license-list.html#GPLCompatibleLicenses" id="l6yd" target="_blank" title="Click here to visit the Free Software Foundation's list of licenses compatible with the GPL">GPL compatible by the FSF</a> or <a href="http://opensource.org/licenses/alphabetical" id="nzls" target="_blank" title="Click here to visit the Open Source Initiative's list of approved licenses">OSI approved</a>) or it must be released with no claim of Copyright (which puts it in the public domain).</li>
<li>A summary of your database configuration (in order to keep it concise and readable, list only information that would be relevant to someone attempting to reproduce your results).<br />
</li>
<li>Except for the operating system, licenses for the software stack you used ("proprietary" suffices as a description of any license that is not one on the FSF or OSI lists). If your database engine has different versions available under different licenses, you must specify the license of the version you used.</li>
<li>Results for as many of the following inputs as you have the patience to run (you may use higher values for <i>k</i> if that gives better results, and you may specify values of <i>l</i> that optimize throughput):</li>
<ul><li>1 100000 4<br />
</li>
<li>1 100000 8</li>
<li>1 1000000 4</li>
<li>1 1000000 8</li>
<li>1 10000000 8</li>
<li>1 10000000 16</li>
<li>1 100000000 8</li>
<li>1 100000000 16</li>
<li>1 1000000000 16</li>
<li>1 1000000000 32</li>
</ul><li>Results for any other sets of inputs that you choose to run that you think presents your database well.</li>
<li>Any other information that you think adds value to the understanding of the above.<br />
</li>
</ul><h2 style="text-align: left;">Revision History</h2><table border="1" bordercolor="#000000" cellpadding="3" cellspacing="0" id="ltze" style="margin-left: 0px; margin-right: auto; text-align: left;"><tbody>
<tr><td align="center" valign="top"><b>Version<br />
</b></td><td align="center" valign="top"><b>Date<br />
</b></td><td><b>Summary<br />
</b></td></tr>
<tr><td align="center" valign="top">0.1</td><td align="center" valign="top">June 12, 2010</td><td>Initial draft, based on previous Collatz benchmark problem.</td></tr>
</tbody></table><br />
K.S. Bhaskar<br />
bhaskar at bhaskars dot com<br />
<br />
</div><br />
</div>Bhaskarhttp://www.blogger.com/profile/14323369551611484731noreply@blogger.com3tag:blogger.com,1999:blog-7229726356350157529.post-70566927280977678672010-05-01T19:48:00.001-04:002011-02-12T15:30:06.074-05:00Encrypting Partitions on GNU/Linux<div dir="ltr" style="text-align: left;" trbidi="on"><h1 class="western"><span class="Apple-style-span" style="font-size: large;">Motivation </span></h1>Encrypting partitions helps protect against unauthorized access to data in the event the computer hardware is physically lost or stolen. The technique described here relies on the ability of the Linux kernel to:<br />
<ol><li>Create an a map of a real device or a logical volume. </li>
<li>Create an encrypted block device <br />
<a name='more'></a></li>
</ol>It is recommended that all partitions with sensitive files be encrypted. Furthermore, to prevent retrieval of information from pages of memory swapped out to disk, it is recommended that the swap partition either be encrypted, or if swapping is to a file, then that file reside on an encrypted partition.<sup><a href="http://www.blogger.com/post-edit.g?blogID=7229726356350157529&postID=7056692728097767867#FOOTNOTE-1">1</a></sup><br />
<br />
Although it is possible to encrypt the root (<span style="font-family: 'Courier New';"><span style="font-size: x-small;">/</span></span>) partition, I don't see the value in it for most situations, since data to be encrypted would usually reside elsewhere (under <span style="font-family: 'Courier New';"><span style="font-size: x-small;">/home</span></span> and <span style="font-family: 'Courier New';"><span style="font-size: x-small;">/var</span></span>, for example) and the root file system would normally contain just a Linux distribution. <br />
<h2 class="western"><span style="font-size: small;"><i>Nota bene</i></span></h2><ol><li>Encrypting partitions does not help protect a PC during normal operation. This is because an encrypted partition must be mounted and accessible during normal operation. Ergo, an intruder who gains access to a system that is in use will find encrypted partitions mounted and accessible.<sup><a href="http://www.blogger.com/post-edit.g?blogID=7229726356350157529&postID=7056692728097767867#FOOTNOTE-2">2</a></sup> </li>
<li>Encryption keys for partitions tend to be long lived (the duration of the partition). They need to be appropriately safeguarded. </li>
<li>With the technique described here, no keys reside on a PC when it is powered down. So, manual input is required. </li>
<li>Pay attention to directories where temporary files reside. If these are not in encrypted partitions, rebooting with a Linux live CD will provide access to the files and their contents. </li>
<li>Except for a brute force attack on the key, I know of no way to recover data from an encrypted partition. </li>
<li>If you lose a computer, <span style="font-family: 'Nimbus Roman No9 L', serif;"><span style="font-size: small;">and</span></span> find it again, you must assume that it has been compromised (e.g., someone may have installed a rootkit and be waiting for you to use it). Either validate all unencrypted partitions, or do a fresh operating system install before mounting any encrypted partitions. </li>
<li>Caveat: I am neither a computer security guru nor a cryptology guru. Use my instructions and follow my advice at your own peril. While devout prayer and crossed fingers may augment my advice, following the advice of someone who knows what he is talking about may be even better. </li>
</ol><h1 class="western"><span class="Apple-style-span" style="font-size: large;">Nuts and Bolts </span></h1>Read the entire document. understand what you need to do and <u>write down a plan of action before taking the first step</u>. Of course <u>you</u> will not make a mistake, but everything else in this universe is imperfect. <br />
<h2 class="western"><span style="font-size: small;"><i>Encrypting a partition</i></span></h2><u>Before you encrypt a partition, take a backup of its contents.<sup><a href="http://www.blogger.com/post-edit.g?blogID=7229726356350157529&postID=7056692728097767867#FOOTNOTE-3">3</a></sup> The process of encryption destroys the data so you will need to restore the files to the encrypted partition when you are done.</u><br />
<ul><li> All commands here are run as root, either with a root shell or via sudo. This write-up assumes that <span style="font-family: 'Courier New';"><span style="font-size: x-small;">/dev/sda2</span></span> is to be encrypted and mounted as <span style="font-family: 'Courier New';"><span style="font-size: x-small;">/home</span></span>. Adapt these instructions to suit your specific needs. </li>
</ul><ul><li> The <span style="font-family: 'Courier New';"><span style="font-size: x-small;">dmsetup</span></span> and <span style="font-family: 'Courier New';"><span style="font-size: x-small;">cryptsetup</span></span> packages are required (this applies to Debian family Linux distributions; there should be equivalent packages for distributions that use other package management systems). </li>
</ul><ul><li> For the initial (one-of) creation of an encrypted file system, the device must first be unmounted, e.g., to unmount <span style="font-family: 'Courier New';"><span style="font-size: x-small;">/dev/sda2</span></span> which is currently mounted unencrypted at <span style="font-family: 'Courier New';"><span style="font-size: x-small;">/home</span></span>:<br />
</li>
</ul><div style="margin-left: 80px;"><span style="font-family: 'Courier New';"><span style="font-size: x-small;">umount /dev/sda2</span></span> or <span style="font-family: 'Courier New';"><span style="font-size: x-small;">umount /home</span></span></div><ul><li> Create a mapped encrypted version of the device (<span style="font-family: 'Courier New';"><span style="font-size: x-small;">-y</span></span> tells <span style="font-family: 'Courier New';"><span style="font-size: x-small;">cryptsetup</span></span> to verify the passphrase):<br />
</li>
</ul><div style="margin-left: 80px;"><span style="font-family: 'Courier New';"><span style="font-size: x-small;"> cryptsetup -c aes -s 256 -y create sda2-aes /dev/sda2</span></span></div><ul><li> I am of course paranoid, but not so paranoid as to perform this optional step: write random data to the physical partition (by writing zeros to the encrypted partition). This ensures that no data from prior to encryption will remain on the disk post encryption:<br />
</li>
</ul><div style="margin-left: 80px;"><span style="font-family: 'Courier New';"><span style="font-size: x-small;">dd if=/dev/zero count=</span></span><span style="font-family: 'Nimbus Sans L', sans-serif;"><span style="font-size: x-small;">xxxx</span></span><span style="font-family: 'Courier New';"><span style="font-size: x-small;"> of=/dev/mapper/sda2-aes</span></span></div><div style="margin-left: 40px;">(You will need to determine the count, in 512 byte blocks, to be passed to <span style="font-family: 'Courier New';"><span style="font-size: x-small;">dd</span></span> to write over the partition.) </div><ul><li> Create a file system in the mapped device (while jfs is my preferred file system, the choice is yours - some Linux distributions require a package such as <span style="font-family: 'Courier New';"><span style="font-size: x-small;">jfsutils</span></span> to be installed to use jfs):<br />
</li>
</ul><div style="margin-left: 80px;"><span style="font-family: 'Courier New';"><span style="font-size: x-small;">mkfs -t jfs /dev/mapper/sda2-aes</span></span></div><div style="margin-left: 40px;">Replace <span style="font-family: 'Courier New';"><span style="font-size: x-small;">jfs</span></span> with your preferred type of file system. <span style="font-family: 'Courier New';"><span style="font-size: x-small;">ext3</span></span> is the most widely used file system on Linux. <span style="font-family: 'Courier New';"><span style="font-size: x-small;">xfs</span></span> and <span style="font-family: 'Courier New';"><span style="font-size: x-small;">reiserfs</span></span> are other not-uncommon alternatives. (I personally use jfs, but have PCs running <span style="font-family: 'Courier New';"><span style="font-size: x-small;">ext3</span></span> and <span style="font-family: 'Courier New';"><span style="font-size: x-small;">reiserfs</span></span>. All four work with GT.M<span style="font-family: 'Nimbus Roman No9 L', serif;">™</span> although <span style="font-family: 'Courier New';"><span style="font-size: x-small;">ext3</span></span> is what is officially supported.) </div><ul><li> Create a script such as the one below. The output of each command is logged to a file in <span style="font-family: 'Courier New';"><span style="font-size: x-small;">/tmp</span></span> whose name is a time stamp (those <span style="font-family: 'Courier New';"><span style="font-size: x-small;">date +%Y%m%d%H%M%S</span></span> commands provide the time stamps). </li>
</ul><div style="font-family: Courier New; margin-left: 80px;"><span style="font-size: x-small;">gtmuser@gglaptop:~$ cat /usr/local/bin/mounthome<br />
#!/bin/bash<br />
#<br />
# Get password and mount /home<br />
#<br />
umount /home >&/tmp/umounthome_$$_`date +%Y%m%d%H%M%S`.log<br />
cryptsetup remove sda2-aes >&/tmp/cryptsetupremove_$$_`date +%Y%m%d%H%M%S`.log<br />
cryptsetup -c aes -s 256 create sda2-aes /dev/sda2 2>/tmp/cryptsetup_$$_`date +%Y%m%d%H%M%S`.log<br />
fsck -a -t jfs /dev/mapper/sda2-aes | tee /tmp/fsck_$$_`date +%Y%m%d%H%M%S`.log<br />
mount -o relatime /dev/mapper/sda2-aes /home >&/tmp/mount_$$_`date +%Y%m%d%H%M%S`.log</span></div><ul><ul><li> The <span style="font-family: 'Courier New';"><span style="font-size: x-small;">umount</span></span> command unmounts the partition if it is already mounted, and the <span style="font-family: 'Courier New';"><span style="font-size: x-small;">cryptsetup remove</span></span> command removes the mapping of the encrypted partition to the device. If the partition is not mounted or encrypted, these commands are no-ops. Doing it this way permits the script to be run repeatedly. </li>
<li> The <span style="font-family: 'Courier New';"><span style="font-size: x-small;">cryptsetup create</span></span> command creates <span style="font-family: 'Courier New';"><span style="font-size: x-small;">/dev/mapper/sda2-aes</span></span> as a 256-bit AES encrypted map of <span style="font-family: 'Courier New';"><span style="font-size: x-small;">/dev/sda2</span></span>, prompting the user for the password. </li>
<li> The <span style="font-family: 'Courier New';"><span style="font-size: x-small;">fsck</span></span> command performs an automatic check and repair of the partition (in case the system is coming up after a hard crash / power-down). If the system was shut down cleanly, it is a no-op. </li>
<li> The <span style="font-family: 'Courier New';"><span style="font-size: x-small;">mount</span></span> command mounts <span style="font-family: 'Courier New';"><span style="font-size: x-small;">/dev/mapper/sda2-aes</span></span> as <span style="font-family: 'Courier New';"><span style="font-size: x-small;">/home</span></span>, making it available to the system. </li>
<li> If you have multiple partitions with the same encryption key, use the shell to prompt the user for the key and provide it to<span style="font-family: 'Courier New';"><span style="font-size: x-small;"> cryptsetup</span></span>.<br />
</li>
</ul></ul><div style="margin-left: 40px;">Don't worry about the partition getting scrambled if someone inadvertently enters the wrong key – if it doesn't look like a properly formatted partition, the <span style="font-family: 'Courier New';"><span style="font-size: x-small;">mount</span></span> command will fail to mount it and you can just run the script again. </div><ul><li> Edit <span style="font-family: 'Courier New';"><span style="font-size: x-small;">/etc/fstab</span></span>, which specifies which partitions the system should mount, and delete or comment out the line that tells Linux to mount <span style="font-family: 'Courier New';"><span style="font-size: x-small;">/dev/sda2</span></span> as <span style="font-family: 'Courier New';"><span style="font-size: x-small;">/home</span></span>. Henceforth, you will need to explicitly mount it when you boot. You will need to login as root to mount the partition - depending on your login manager, you may need to switch to an alternate text console (e.g., using Ctrl-Alt-F2) to login as root and run mounthome, or <br />
</li>
</ul><ul><li> Verify that the encryption is working (go through a few boot up and shut down cycles, verify recovery from a forced power-down and satisfy yourself that entering an incorrect password doesn't damage the file system). Then restore the previously backed up data. </li>
</ul><h2 class="western"><span style="font-size: small;"><i>Encrypting a swap partition</i></span></h2>The simplest way to encrypt a swap partition is to create a swap file on an encrypted partition. For example, after creating and mounting an encrypted /home, you can create a swap file with commands executed as root such as (in this example, the swap file is 4GB; the dd step ensures that lazy allocation is not used to allocate space for the swap file):<br />
<br />
<div style="margin-left: 40px;"><span style="font-family: 'courier new';">dd if=/dev/zero of=/home/swap bs=1048576 count=4096</span><br />
<span style="font-family: 'courier new';">mkswap /home/swap</span></div><br />
Then append a line <span style="font-family: 'courier new';">swapon /home/swap</span> to the <span style="font-family: 'courier new';">/usr/local/bin/mounthome</span> script described above.<br />
<h1 class="western"><span class="Apple-style-span" style="font-size: large;">Parting Thoughts </span></h1><ol><li>For convenience, instead of entering a key, you can store it on a USB flash drive (back it up!). Boot with the drive plugged in and have the system read the password from the flash drive. <u>Then remove the flash drive to ensure that someone who steals the PC doesn't also steal the flash drive.</u></li>
<li>You must ensure that enough functionality is available to a system when it boots so that you are able to run the script(s) to mount. So, if you are encrypting <span style="font-family: 'Courier New';"><span style="font-size: x-small;">/home</span></span>, you would need to login as a user whose home directory is not under <span style="font-family: 'Courier New';"><span style="font-size: x-small;">/home</span></span> (e.g., user root, or a specially created user) to run the script to mount the encrypted partition. Encrypting a <span style="font-family: 'Courier New';"><span style="font-size: x-small;">/var</span></span> partition is probably impractical because of files such as <span style="font-family: 'Courier New';"><span style="font-size: x-small;">/var/log/messages</span></span> (so if you have application directories under <span style="font-family: 'Courier New';"><span style="font-size: x-small;">/var</span></span>, you may need to mount them in a seprate encrypted partition). </li>
<li>Have fun. As long as you take a backup of the partition you plan to encrypt, as well as <span style="font-family: 'Courier New';"><span style="font-size: x-small;">/etc/fstab</span></span> before you start playing, the commands described here are reasonably foolproof and unlikely to destroy your system. </li>
<li>Fools can be very ingenious.</li>
</ol><div class="endnotes"><div style="page-break-before: always; text-align: center;">notes</div><br />
<sup>1 </sup><a href="http://www.blogger.com/post-edit.g?blogID=7229726356350157529&postID=7056692728097767867" name="FOOTNOTE-1"></a>Note that encrypting a swap partition or a swap file effectively disables the Hibernate function. The operation of Suspend is not affected. <br />
<br />
<sup>2 </sup><a href="http://www.blogger.com/post-edit.g?blogID=7229726356350157529&postID=7056692728097767867" name="FOOTNOTE-2"></a>A corollary of this is to require password protected screen savers that come on automatically after a brief period of inactivity. Thus, a thief who appropriates an appropriately protected inactive laptop would not be able to access the files when the laptop is on, and would also not be able to access the files after it is powered down. If you carry a Bluetooth enabled device on your person, you can also use software such as <a href="http://blueproximity.sourceforge.net/" id="qnxc" title="Click here to visit the BlueProximity home page">BlueProximity</a> to automatically lock the screen when you step away.<br />
<br />
<sup>3 </sup><a href="http://www.blogger.com/post-edit.g?blogID=7229726356350157529&postID=7056692728097767867" name="FOOTNOTE-3"></a>If there is existing sensitive data on the partition, and the backup is to the same computer system - e.g., to /var/tmp - you should encrypt the backup.</div></div>Bhaskarhttp://www.blogger.com/profile/14323369551611484731noreply@blogger.com0tag:blogger.com,1999:blog-7229726356350157529.post-36532113084056701492010-02-28T22:52:00.001-05:002011-02-10T22:10:11.371-05:00Enhanced 3n+1 Benchmark for GT.M - 2010-02-28<div dir="ltr" style="text-align: left;" trbidi="on"><h1><a name='more'></a>Results for Enhanced 3n+1 Benchmark for GT.M - 2010-02-28</h1><h2>Computing Platform - System 76 laptop</h2>CPU - Intel Core2 Duo T7500 2.20GHz<br />
RAM - 4GB<br />
Disk - Seagate 200GB 7200rpm with SATA interface<br />
OS - Kubuntu 9.10 64-bit Linux kernel 2.6.31-19-generic<br />
File system - jfs<br />
<br />
Database - GT.M V5.4-000 64-bit version<br />
<br />
<h2>Program</h2>In addition to adapting the program to the changes in the benchmark problem, I have also attempted to improve the readability of the program to those who are not GT.M programmers.<br />
<br />
<br />
<blockquote><span style="font-family: courier new;">threeen1e</span><br />
<span style="font-family: courier new;"> ; Find the maximum number of steps for the 3n+1 problem for all integers through two input integers.</span><br />
<span style="font-family: courier new;"> ; See http://docs.google.com/View?id=dd5f3337_12fzjpqbc2</span><br />
<span style="font-family: courier new;"> ; Assumes input format is 3 integers separated by a space with the first integer smaller than the second.</span><br />
<span style="font-family: courier new;"> ; Third integer is number of threads. No input error checking is done.</span><br />
<span style="font-family: courier new;"> ; This program is modified to show that the GT.M key-value store can use arbitrary strings for</span><br />
<span style="font-family: courier new;"> ; both keys and values - instead of numeric subscripts and values to store the numver of steps, each</span><br />
<span style="font-family: courier new;"> ; subscript and value is spelled out using the strings in the program source line labelled "digits".</span><br />
<span style="font-family: courier new;"> ;</span><br />
<span style="font-family: courier new;"> ; K.S. Bhaskar 20100228</span><br />
<span style="font-family: courier new;"> ;</span><br />
<span style="font-family: courier new;"> ; No claim of copyright is made with respect to this program.</span><br />
<span style="font-family: courier new;"> ;</span><br />
<span style="font-family: courier new;"> ; Variables do not have to be declared before use, but are New'd in subprograms to ensure that they</span><br />
<span style="font-family: courier new;"> ; do not conflict with names in the caller.</span><br />
<span style="font-family: courier new;"> ;</span><br />
<span style="font-family: courier new;"> ; The program uses strings in different languages for each digit in the database. It reads the program</span><br />
<span style="font-family: courier new;"> ; source at the label digits to get strings (separated by ;) for each language used.</span><br />
<span style="font-family: courier new;">digits ;zero;eins;deux;tres;quattro;пять;ستة;सात;捌;ஒன்பது</span><br />
<span style="font-family: courier new;"> Do digitsinit ; Initialize data for conversion between integers and strings</span><br />
<span style="font-family: courier new;"> ;</span><br />
<span style="font-family: courier new;"> ; Read and process each line in turn. Since process may be restarting after a crash, any</span><br />
<span style="font-family: courier new;"> ; data in database is assumed to be as recovered after a crash. After computing and writing</span><br />
<span style="font-family: courier new;"> ; results from this run, database is cleared for next line of input or next run of the program.</span><br />
<span style="font-family: courier new;"> ;</span><br />
<span style="font-family: courier new;"> ; Loop for ever, read a line (quit on end of file), process that line</span><br />
<span style="font-family: courier new;"> For Read input Quit:$ZEOF!'$Length(input) Do ; input has entire input line</span><br />
<span style="font-family: courier new;"> . Set i=$Piece(input," ",1) ; i - starting number is first piece of input</span><br />
<span style="font-family: courier new;"> . Set j=$Piece(input," ",2) ; j - ending number is second piece of input</span><br />
<span style="font-family: courier new;"> . Set k=$Piece(input," ",3) ; k - parallel execution streams requested is third piece</span><br />
<span style="font-family: courier new;"> . ; Reproduce input on output, formatting numbers</span><br />
<span style="font-family: courier new;"> . Write $FNumber(i,",",0)," ",$FNumber(j,",",0)," ",$FNumber(k,",",0)</span><br />
<span style="font-family: courier new;"> . ;</span><br />
<span style="font-family: courier new;"> . ; Get number of CPUs, calculate number of parallel execution streams, calculate block size</span><br />
<span style="font-family: courier new;"> . Open "cpus":(COMMAND="grep processor /proc/cpuinfo|wc -l":READONLY)::"PIPE"</span><br />
<span style="font-family: courier new;"> . Use "cpus" Read cpus Use $PRINCIPAL ; Number of CPUS on system is in /proc/cpuinfo</span><br />
<span style="font-family: courier new;"> . Close "cpus"</span><br />
<span style="font-family: courier new;"> . Set:4*cpus>k k=4*cpus ; At least four execution streams per CPU</span><br />
<span style="font-family: courier new;"> . Write " ",k ; Report actual number of execution streams</span><br />
<span style="font-family: courier new;"> . Set blk=(j-i+k)\k ; Calculate size of blocks (last block may be smaller)</span><br />
<span style="font-family: courier new;"> . ;</span><br />
<span style="font-family: courier new;"> . ; Launch jobs. Grab lock l1, atomically increment counter, compute and launch one job for each block of numbers.</span><br />
<span style="font-family: courier new;"> . ; Each child job locks l2(pid), decrements the counter and tries to grab lock l1(pid).</span><br />
<span style="font-family: courier new;"> . ; When counter is zero, all jobs have started. Parent releases lock l1 and tries to grab lock l2.</span><br />
<span style="font-family: courier new;"> . ; When all children have released their l2(pid) locks, they're done and parent can gather & report results.</span><br />
<span style="font-family: courier new;"> . Set ^count=0 ; Clear count - may have residual value if restarting from crash</span><br />
<span style="font-family: courier new;"> . Lock +l1 ; Set lock for process synchronization</span><br />
<span style="font-family: courier new;"> . For s=i:blk:j Do</span><br />
<span style="font-family: courier new;"> .. Set c=$Increment(^count) ; Atomic increment of counter in database for process synchronization</span><br />
<span style="font-family: courier new;"> .. Set tmp=$Select(s+blk-1>j:j,1:s+blk-1) ; Compute upper limit for numbers for next child Job</span><br />
<span style="font-family: courier new;"> .. Set def=$ZTRNLNM("gtm_tmp") Set:'$Length(def) def=$ZTRNLNM("PWD") ; Working directory for Jobbed process</span><br />
<span style="font-family: courier new;"> .. Set err=$Text(+0)_"_"_$Job_"_"_s_".mje" ; STDERR for Jobbed process</span><br />
<span style="font-family: courier new;"> .. Set out=$Extract(err,1,$Length(err)-1)_"o" ; STDOUT for Jobbed process</span><br />
<span style="font-family: courier new;"> .. Set cmd="doblk(s,tmp,i,j):(ERROR="""_err_""":OUTPUT="""_out_""":DEFAULT="""_def_""")" ; Command to Job</span><br />
<span style="font-family: courier new;"> .. Job @cmd ; Job child process for next block of numbers</span><br />
<span style="font-family: courier new;"> . For Quit:'^count Hang 0.1 ; Wait for processes to start (^count goes to 0 when they do)</span><br />
<span style="font-family: courier new;"> . Lock -l1 ; Release lock so processes can run</span><br />
<span style="font-family: courier new;"> . Set startat=$HOROLOG ; Get starting time</span><br />
<span style="font-family: courier new;"> . Lock +l2 ; Wait for processes to finish</span><br />
<span style="font-family: courier new;"> . ;</span><br />
<span style="font-family: courier new;"> . ; When parent gets lock l2, child processes have completed and parent gathers and reports results.</span><br />
<span style="font-family: courier new;"> . set endat=$HOROLOG ; Get ending time - time between startat and endat is the elapsed time</span><br />
<span style="font-family: courier new;"> . ; Calculate duration</span><br />
<span style="font-family: courier new;"> . Set duration=(86400*($Piece(endat,",",1)-$Piece(startat,",",1)))+$Piece(endat,",",2)-$Piece(startat,",",2)</span><br />
<span style="font-family: courier new;"> . Write " ",$FNumber(^result,",",0) ; Show largest number of steps for the range i through j</span><br />
<span style="font-family: courier new;"> . Write " ",$FNumber(^highest,",",0) ; Show the highest number reached during the computation</span><br />
<span style="font-family: courier new;"> . Write " ",$FNumber(duration,",",0) ; Show the elapsed time </span><br />
<span style="font-family: courier new;"> . Write " ",$FNumber(^updates,",",0) ; Show number of updates</span><br />
<span style="font-family: courier new;"> . Write " ",$FNumber(^reads,",",0) ; Show number of reads</span><br />
<span style="font-family: courier new;"> . ; If duratation is greater than 0 seconds, display update and read rates</span><br />
<span style="font-family: courier new;"> . Write:duration " ",$FNumber(^updates/duration,",",0)," ",$FNumber(^reads/duration,",",0)</span><br />
<span style="font-family: courier new;"> . Write !</span><br />
<span style="font-family: courier new;"> . Lock -l2 ; Release lock for next run</span><br />
<span style="font-family: courier new;"> . Do dbinit ; Initialize database for next run</span><br />
<span style="font-family: courier new;"> Quit</span><br />
<span style="font-family: courier new;"> ;</span><br />
<span style="font-family: courier new;">dbinit ; Entryref dbinit clears database between lines</span><br />
<span style="font-family: courier new;"> Kill ^count,^highest,^reads,^result,^step,^updates</span><br />
<span style="font-family: courier new;"> Quit</span><br />
<span style="font-family: courier new;"> ;</span><br />
<span style="font-family: courier new;">digitsinit ; Initialize arrays to convert between strings and integers</span><br />
<span style="font-family: courier new;"> New m,x</span><br />
<span style="font-family: courier new;"> Set x=$Text(digits)</span><br />
<span style="font-family: courier new;"> For m=0:1:9 Set di($Piece(x,";",m+2))=m,ds(m)=$Piece(x,";",m+2)</span><br />
<span style="font-family: courier new;"> Quit</span><br />
<span style="font-family: courier new;"> ;</span><br />
<span style="font-family: courier new;">inttostr(n) ; Convert an integer to a string</span><br />
<span style="font-family: courier new;"> New m,s</span><br />
<span style="font-family: courier new;"> Set s=ds($Extract(n,1))</span><br />
<span style="font-family: courier new;"> For m=2:1:$Length(n) Set s=s_" "_ds($Extract(n,m))</span><br />
<span style="font-family: courier new;"> Quit s</span><br />
<span style="font-family: courier new;"> ;</span><br />
<span style="font-family: courier new;">strtoint(s) ; Convert a string to an integer</span><br />
<span style="font-family: courier new;"> New m,n</span><br />
<span style="font-family: courier new;"> Set n=di($Piece(s," ",1))</span><br />
<span style="font-family: courier new;"> For m=2:1:$Length(s," ") Set n=10*n+di($Piece(s," ",m))</span><br />
<span style="font-family: courier new;"> Quit n</span><br />
<span style="font-family: courier new;"> ;</span><br />
<span style="font-family: courier new;">; This is where Jobbed processes start</span><br />
<span style="font-family: courier new;">doblk(myfirst,mylast,allfirst,alllast)</span><br />
<span style="font-family: courier new;"> Set reads=0,updates=0,highest=alllast ; Start with zero reads and zero writes, highest number is at least alllast</span><br />
<span style="font-family: courier new;"> Do digitsinit ; Initialize data for conversion between integers and strings</span><br />
<span style="font-family: courier new;"> Lock +l2($JOB) ; Get lock l2 that parent will wait on till this Jobbed processes is done</span><br />
<span style="font-family: courier new;"> If $Increment(^count,-1) ; Decrement ^count to say this process is alive</span><br />
<span style="font-family: courier new;"> Lock +l1($JOB) ; This process will get lock l1($JOB) only parent has released lock on l1</span><br />
<span style="font-family: courier new;"> Do dostep(myfirst,mylast) ; Do the block assigned to this process</span><br />
<span style="font-family: courier new;"> Do:alllast>mylast dostep(mylast+1,alllast) ; Help with the numbers after this process' block, if there are any</span><br />
<span style="font-family: courier new;"> Do:allfirst<myfirst dostep(allfirst,myfirst-1) ; Help with the numbers before this process' block, if there are any</span><br />
<span style="font-family: courier new;"> TStart () ; Update global statistics inside a transaction</span><br />
<span style="font-family: courier new;"> ; The following line unconditionally adds the number of reads & write performed by this process to the</span><br />
<span style="font-family: courier new;"> ; number of reads & writes performed by all processes, and sets the highest for all processes if the</span><br />
<span style="font-family: courier new;"> ; highest calculated by this process is greater than that calculated so far for all processes</span><br />
<span style="font-family: courier new;"> Set:$Increment(^reads,reads)&$Increment(^updates,updates)&(highest>$Get(^highest)) ^highest=highest</span><br />
<span style="font-family: courier new;"> TCommit</span><br />
<span style="font-family: courier new;"> Lock -l1($JOB),-l2($JOB) ; Release locks to tell parent this parent is done</span><br />
<span style="font-family: courier new;"> Quit ; Jobbed processes terminate here</span><br />
<span style="font-family: courier new;"> ;</span><br />
<span style="font-family: courier new;">dostep(first,last) ; Calculate the maximum number of steps from first through last</span><br />
<span style="font-family: courier new;"> New current,currpath,i,n</span><br />
<span style="font-family: courier new;"> For current=first:1:last Do</span><br />
<span style="font-family: courier new;"> . Set n=current ; Start n at current</span><br />
<span style="font-family: courier new;"> . Kill currpath ; Currpath holds path to 1 for current</span><br />
<span style="font-family: courier new;"> . ; Go till we reach 1 or a number with a known number of steps</span><br />
<span style="font-family: courier new;"> . For i=0:1 Quit:$Increment(reads)&($Data(^step($$inttostr(n)))!(1=n)) Do</span><br />
<span style="font-family: courier new;"> .. Set currpath(i)=n ; log n as current number in sequence</span><br />
<span style="font-family: courier new;"> .. Set n=$Select('(n#2):n/2,1:3*n+1) ; compute the next number</span><br />
<span style="font-family: courier new;"> .. Set:n>highest highest=n ; see if we have a new highest number reached </span><br />
<span style="font-family: courier new;"> . Do:0<i ; if 0=i we already have an answer for n, nothing to do here</span><br />
<span style="font-family: courier new;"> .. If 1<n Set i=i+$$strtoint(^step($$inttostr(n)))</span><br />
<span style="font-family: courier new;"> .. TStart () ; Atomically set maximum</span><br />
<span style="font-family: courier new;"> .. Set:i>$Get(^result) ^result=i</span><br />
<span style="font-family: courier new;"> .. TCommit</span><br />
<span style="font-family: courier new;"> .. Set n="" For Set n=$Order(currpath(n)) Quit:""=n Set:$Increment(updates) ^step($$inttostr(currpath(n)))=$$inttostr(i-n)</span><br />
<span style="font-family: courier new;"> Quit</span></blockquote>The resolution of time measured and reported natively by GT.M is one second (higher resolutions are possible by calling a standard external library function).<br />
<br />
<br />
<br />
This program runs the enhanced benchmark, the difference from the pure numeric benchmark being that instead of storing a database node ^cycle(11) with a value 15, it stores a database note ^cycle("eins eins") with a value "eins <span style="font-family: verdana;">пять". The actual strings used for each digit are specified in the comments of the source program at label 15. The strings are actually encoded in UTF-8 to demonstrate that the database is not limited to ASCII or an ISO-8859 variant (in fact, the keys and values can be any arbitrary sequence of bytes).</span><br />
<br />
<h2>Database Configuration</h2>Block size - 4096 bytes<br />
Global buffers - 5000<br />
Journal buffers - 2000<br />
Type of journaling - before image (for backward recovery)<br />
<br />
The journal file and database were on the same disk. This is not how production systems are configured, but my laptop has only one hard drive. If the database and journals were on separate disks, performance may be a little better.<br />
<h2>Licenses</h2>GT.M is licensed under GNU Affero General Public License version 3.<br />
<h2>Results</h2>I ran the benchmark three times. I have manually colored the outputs below to improve readability.<br />
<br />
<div style="font-family: Courier New;">$ mumps -run threeen1e <.fis-gtm/threeen1.dat</div><div style="font-family: Courier New;">1 100,000 4 8 <span style="color: red;">350</span> <span style="color: blue;">1,570,824,736</span> <span style="color: red;">6</span> <span style="color: blue;">221,796</span> <span style="color: red;">1,021,796</span> <span style="color: blue;">36,966</span> <span style="color: red;">170,299</span></div><div style="font-family: Courier New;">1 100,000 8 8 <span style="color: red;">350</span> <span style="color: blue;">1,570,824,736</span> <span style="color: red;">6</span> <span style="color: blue;">221,186</span> <span style="color: red;">1,021,186</span> <span style="color: blue;">36,864</span> <span style="color: red;">170,198</span></div><div style="font-family: Courier New;">1 1,000,000 4 8 <span style="color: red;">524</span> <span style="color: blue;">56,991,483,520</span> <span style="color: red;">62</span> <span style="color: blue;">2,296,210</span> <span style="color: red;">10,296,210</span> <span style="color: blue;">37,036</span> <span style="color: red;">166,068</span></div><div style="font-family: Courier New;">1 1,000,000 8 8 <span style="color: red;">524</span> <span style="color: blue;">56,991,483,520</span> <span style="color: red;">68</span> <span style="color: blue;">2,289,947</span> <span style="color: red;">10,289,947</span> <span style="color: blue;">33,676</span> <span style="color: red;">151,323</span></div><div style="font-family: Courier New;">$ mumps -run threeen1e <.fis-gtm/threeen1.dat</div><div style="font-family: Courier New;">1 100,000 4 8 <span style="color: red;">350</span> <span style="color: blue;">1,570,824,736</span> <span style="color: red;">6</span> <span style="color: blue;">221,674</span> <span style="color: red;">1,021,674 <span style="color: blue;">36,946</span></span> <span style="color: red;">170,279</span></div><div style="font-family: Courier New;">1 100,000 8 8 <span style="color: red;">350</span> <span style="color: blue;">1,570,824,736</span> <span style="color: red;">6</span> <span style="color: blue;">220,975</span> <span style="color: red;">1,020,975</span> <span style="color: blue;">36,829</span> <span style="color: red;">170,163</span></div><div style="font-family: Courier New;">1 1,000,000 4 8 <span style="color: red;">524</span> <span style="color: blue;">56,991,483,520</span> <span style="color: red;">69</span> <span style="color: blue;">2,297,107</span> <span style="color: red;">10,297,107</span> <span style="color: blue;">33,291</span> <span style="color: red;">149,233</span></div><div style="font-family: Courier New;">1 1,000,000 8 8 <span style="color: red;">524</span> <span style="color: blue;">56,991,483,520</span> <span style="color: red;">67</span> <span style="color: blue;">2,299,968</span> <span style="color: red;">10,299,968</span> <span style="color: blue;">34,328</span> <span style="color: red;">153,731</span></div><div style="font-family: Courier New;">$ mumps -run threeen1e <.fis-gtm/threeen1.dat</div><div style="font-family: Courier New;">1 100,000 4 8 <span style="color: red;">350</span> <span style="color: blue;">1,570,824,736</span> <span style="color: red;">7</span> <span style="color: blue;">222,972</span> <span style="color: red;">1,022,972</span> <span style="color: blue;">31,853</span> <span style="color: red;">146,139</span></div><div style="font-family: Courier New;">1 100,000 8 8 <span style="color: red;">350</span> <span style="color: blue;">1,570,824,736</span> <span style="color: red;">6</span> <span style="color: blue;">221,596</span> <span style="color: red;">1,021,596</span> <span style="color: blue;">36,933</span> <span style="color: red;">170,266</span></div><div style="font-family: Courier New;">1 1,000,000 4 8 <span style="color: red;">524</span> <span style="color: blue;">56,991,483,520</span> <span style="color: red;">60</span> <span style="color: blue;">2,308,976</span> <span style="color: red;">10,308,976</span> <span style="color: blue;">38,483</span> <span style="color: red;">171,816</span></div><div style="font-family: Courier New;">1 1,000,000 8 8 <span style="color: red;">524</span> <span style="color: blue;">56,991,483,520</span> <span style="color: red;">61</span> <span style="color: blue;">2,275,655</span> <span style="color: red;">10,275,655</span> <span style="color: blue;">37,306</span> <span style="color: red;">168,453</span></div><div style="font-family: Courier New;">$</div><br />
<br />
I was very surprised at how large the largest numbers encountered were - for example, the 56,991,483,520 encountered for a range with an upper limit of 1,000,000. <br />
Since the results seemed reasonably consistent and predictable, I decided to run them on a much larger range. I knew that although I would have space on my laptop for the database, I would not have space for the journal files. So, set the limit at which GT.M switches journal files to around 500MB, and baby sat the following run, deleting older generation journal files whenever GT.M switched. So, this is not a good measure of database performance because the IO subsystem was deleting large files concurrent with creating large files. But I am astounded at the largest number encountered.<br />
<br />
<br />
<span style="font-family: courier new;">$ echo 1 10000000 4 | mumps -run threeen1e</span><br />
<span style="font-family: courier new;">1 10,000,000 4 8 <span style="color: red;">685</span> <span style="color: blue;">60,342,610,919,632</span> <span style="color: red;">3,120 <span style="color: blue;">23,417,210</span></span> <span style="color: red;">103,417,210</span> <span style="color: blue;">7,506</span> <span style="color: red;">33,147</span></span><br />
<span style="font-family: courier new;">$</span></div>Bhaskarhttp://www.blogger.com/profile/14323369551611484731noreply@blogger.com0tag:blogger.com,1999:blog-7229726356350157529.post-30450229648863854082010-02-14T09:34:00.001-05:002011-02-10T22:10:11.372-05:003n+1 NoSQL/Key-Value/Schema-Free/Schema-Less Database Benchmark<div dir="ltr" style="text-align: left;" trbidi="on"><h1 style="text-align: left;"></h1><h2 style="text-align: left;">Motivation</h2><div style="text-align: left;">This is an attempt to create a benchmark for apples to apples comparisons of databases that are generally described as NoSQL, key-value, schema-free or schema-less databases. The goals are to create a benchmark that:<br />
<br />
</div><ul style="text-align: left;"><li>is simple to understand and code - ideally, a page of code or less in most programming languages;</li>
<li>performs a non-trivial amount of representative activity - reads and updates, access contention, recovery, etc.; and</li>
<li>generates results that can be easily replicated and verified by others.<a name='more'></a></li>
</ul><br />
Since many popular databases of the genre being discussed do not support <a href="http://en.wikipedia.org/wiki/ACID" id="q8g3" target="_blank" title="Click here to read the Wikipedia article on ACID transactions">ACID (Atomic, Consistent, Isolated, Durable) transactions</a>, the benchmark uses simple reads and updates rather than requiring transaction processing.<br />
<br />
<div><i>If your database supports strings, it is strongly recommended that you implement and present the enhanced benchmark with strings described below, even if you also implement and present an integer-only benchmark. Also, if your database supports strings with international character sets with a multi-byte encoding such as UTF-8, please do demonstrate their usage, since it will help show your database in a more attractive light.</i><br />
<h2 style="text-align: left;">Background</h2><div style="text-align: left;">Consider a sequence of positive integers <i>n</i><sub>0</sub>, <i>n</i><sub>1</sub>, <i>n</i><sub>2</sub> ... <i>n</i><sub><i>i</i>+1</sub> is generated from <i>n<sub>i</sub></i> as follows:<br />
<br />
</div><ul style="text-align: left;"><li>if <i>n<sub>i</sub></i> is even, <i>n<sub>i+1</sub></i>=<i>n<sub>i</sub></i>/2</li>
<li>if <i>n<sub>i</sub></i> is odd, <i>n<sub>i+1</sub></i>=3*<i>n<sub>i</sub></i>+1</li>
</ul><div style="text-align: left;"><br />
If <i>n</i><sub>0</sub>=1, this leads to the cycle 1, 4, 2, 1 ... The <a href="http://en.wikipedia.org/wiki/Collatz_conjecture" id="s5ud" target="_blank" title="Click here to read the Wikipedia entry on the Collatz conjecture">Collatz conjecture</a> says that for any positive integer starting point <i>n</i><sub>0</sub>, the sequence eventually leads to 1. The sequence starting with 4 and ending at 1 has three steps. The sequence starting with 6 and ending with 1 (6, 3, 10, 5, 16, 8, 4, 2, 1) has 8 steps.</div><h2 style="text-align: left;">Problem</h2><div style="text-align: left;">Write a program that reads from its standard input three positive integers <i>i</i>, <i>j</i> and <i>k</i> (0<<i>i</i><<i>j</i><10,000,000,001), separated by a single space, and on its standard output, prints the following separated by spaces:</div><div style="text-align: left;"><br />
</div><div style="text-align: left;"><ul><li>the inputs, <i>i</i>, <i>j</i> & <i>k;</i></li>
<li>the actual number of execution streams;</li>
<li>the maximum number of steps for any integer in the sequence <i>i</i> through <i>j</i>;</li>
<li>the largest integer reached when computing the steps for any integer in the sequence <i>i</i> through <i>j</i>;</li>
<li>the number of elapsed (wall clock) seconds it took to solve the problem;</li>
<li>the minimum number of updates performed on the database (the actual number may be higher if two or more execution streams updated the same node);</li>
<li>the minimum number of reads performed on the database (the actual number may be higher);</li>
<li>the update rate calculated by the minimum number of updates divided by the elapsed time; and</li>
<li>the read rate calculated by the minimum number of reads divided by the elapsed time.</li>
</ul><div style="text-align: left;"><br />
</div>The code does not need to validate inputs. Here are required elements of the solution:<br />
<br />
</div><ul style="text-align: left;"><li>Your solution must use a database configured to be recoverable. In other words, if the system were to crash in the middle of solving a problem, rebooting the computer, recovering the database and restarting the program with the same input <i>i</i> and <i>j</i> uses the partial results in the database prior to the crash. A recovery mechanism of replicating to another system is acceptable as long as the replication is synchronous - i.e., an update is not considered committed to the database on the originating instance until it is received and accepted by the replicating instance. When submitting results, please document the recovery technique used (forward recovery, which requires a backup to be restored and updates applied from a journal file; backward recovery which recovers the database in place from a journal file; etc.).</li>
</ul><div style="text-align: left;"><br />
</div><ul style="text-align: left;"><li>For convenience, your program is allowed to accept multiple lines of input, processing each line in turn. However, between lines, you must empty, clear, re-initialize (whatever term your database engine uses) the data in the database, so that the computation for each line starts out with a database with no data. Of course, this means that in the event of a crash, only the data for the specific <i>i</i> and <i>j</i> being worked is recovered, and resuming and completing the problem only refers to the solution for that <i>i</i> and <i>j</i>.</li>
</ul><div style="text-align: left;"><br />
</div><ul style="text-align: left;"><li>In order to factor in the effect of dealing with access contention and concurrency control, your solution must use <u>at least</u> the greater of <i>k</i> or four concurrent execution streams (threads, processes, or both) per CPU core to solve the problem. So, if your CPU has two cores, and <i>k</i> is 6, you must use at least 8 execution streams. When each stream completes its allocated work, it must check to make sure that no other stream has unfinished work, and if it finds unfinished work, it should work on it. Thus, if the problem is 1 through 1,000,000 and there are four streams assigned 1 through 250,000; 250,001 through 500,000; 501,000 through 750,000 and 750,001 through 1,000,000; after completing the work on its 250,000 numbers, each stream must check the other 750,000 numbers and work on any number that it finds still waiting to be worked on. In this example, this means that solving the problem involves <i>at least</i> 1,000,000 database updates and <i>at least</i> 4,000,000 database reads.</li>
</ul><div style="text-align: left;"><br />
</div><h2 style="text-align: left;">Submission</h2><div style="text-align: left;">Post your results either directly to the <a href="http://groups.google.com/group/nosql-discussion" id="oopk" target="_blank" title="Click here to visit the NoSQL lsit">NoSQL list</a>, or on the web with a URL in a post on the NoSQL list. You should include:<br />
<br />
</div><ul style="text-align: left;"><li>The computing platform on which you ran your benchmark (details of CPU, RAM, disk type, operating system).</li>
<li>Your program. Your program must either be released under a FOSS license (either determined to be <a href="http://www.gnu.org/licenses/license-list.html#GPLCompatibleLicenses" id="l6yd" target="_blank" title="Click here to visit the Free Software Foundation's list of licenses compatible with the GPL">GPL compatible by the FSF</a> or <a href="http://opensource.org/licenses/alphabetical" id="nzls" target="_blank" title="Click here to visit the Open Source Initiative's list of approved licenses">OSI approved</a>) or it must be released with no claim of Copyright (which puts it in the public domain).</li>
<li>A summary of your database configuration (in order to keep it concise and readable, list only information that would be relevant to someone attempting to reproduce your results).<br />
</li>
<li>Except for the operating system, licenses for the software stack you used ("proprietary" suffices as a description of any license that is not one on the FSF or OSI lists). If your database engine has different versions available under different licenses, you must specify the license of the version you used.</li>
<li>Results for as many of the following inputs as you have the patience to run:</li>
<ul><li>1 100000 4<br />
</li>
<li>1 100000 8</li>
<li>1 1000000 4</li>
<li>1 1000000 8</li>
<li>1 10000000 8</li>
<li>1 10000000 16</li>
<li>1 100000000 8</li>
<li>1 100000000 16</li>
<li>1 1000000000 16</li>
<li>1 1000000000 32</li>
</ul><li>Results for any other sets of inputs that you choose to run that you think presents your database well.</li>
<li>Any other information that you think adds value to the understanding of the above.<br />
</li>
</ul><h2 style="text-align: left;">Enhancement to Use Strings</h2>The benchmark as formulated above stores integer keys and values in the database, which is not representative of real world applications that more commonly need to use keys and values that are strings. The enhanced benchmark requires that keys and values for the number of steps be stored as strings rather than as integers. For example, instead of creating an entry for step(11) with a value of 15, you would create an entry step("one one") with a value of "one five". You are free to use numerics for all other purposes, including program flow control.<br />
<h2 style="text-align: left;">Revision History</h2><table border="1" bordercolor="#000000" cellpadding="3" cellspacing="0" id="ltze" style="margin-left: 0px; margin-right: auto; text-align: left;"><tbody>
<tr><td align="center" valign="top"><b>Version<br />
</b></td><td align="center" valign="top"><b>Date<br />
</b></td><td><b>Summary<br />
</b></td></tr>
<tr><td align="center" valign="top">0.1</td><td align="center" valign="top">November 21, 2009</td><td>Initial Draft</td></tr>
<tr><td align="center" valign="top">0.2</td><td align="center" valign="top">December 1, 2009</td><td>Added section on Enhancement to Use Strings</td></tr>
<tr><td align="center" valign="top">0.3</td><td align="center" valign="top">February 19, 2010</td><td><ul><li>Add recommendation to provide enhanced benchmark using strings, with international character support, if supported by the database.</li>
<li>Change "cycle length" to "steps" to correspond to Wikipedia page on the Collatz conjecture. The number of steps is one smaller than the cycle length.</li>
<li>Enhance output to print largest integer reached during the computation, estimate number of reads and number of updates, and read and update rates.</li>
<li>Clean up / clarify wording to improve readability.</li>
</ul></td></tr>
</tbody></table><br />
K.S. Bhaskar<br />
bhaskar at bhaskars dot com<br />
<br />
</div><br />
</div>Bhaskarhttp://www.blogger.com/profile/14323369551611484731noreply@blogger.com0tag:blogger.com,1999:blog-7229726356350157529.post-31331597470176869102010-01-30T17:55:00.001-05:002011-02-10T22:10:40.388-05:00Citizenship in the World Merit Badge Workbook<div dir="ltr" style="text-align: left;" trbidi="on"><h1></h1>This document can be viewed at <a href="http://docs.google.com/View?id=dd5f3337_17gsnxnphp" id="io6:" title="http://docs.google.com/View?id=dd5f3337_17gsnxnphp">http://docs.google.com/View?id=dd5f3337_17gsnxnphp</a><br />
If you want to copy it to edit it to work on the merit badge, please get an account at Google docs and send me an e-mail. I will share it with you on <a href="http://docs.google.com/" id="wmhq" title="Click here to go to Google docs">Google docs (http://docs.google.com)</a> giving you view access. From there you can make your own Google docs copy and edit it on online or download it and edit it off-line on your word processor. I personally use and recommend <a href="http://openoffice.org/" id="we04" title="Click here to visit OpenOffice.org">OpenOffice.org (http://openoffice.org)</a> which is <a href="http://en.wikipedia.org/wiki/Free_and_open_source_software" id="sc16" title="Click here to visit the Wikipedia article on Free / Open Source Software">Free / Open Source Software</a> for word processing, spreadsheets, presentations and much more.<br />
<a name='more'></a><br />
<br />
K.S. Bhaskar / bhaskar at bhaskars dot com<br />
Merit Badge Counselor registered with <a href="http://cccbsa.org/" id="bh:5" title="Click here to visit the web site of the BSA Chester County Council, Pennsylvania">BSA Chester County Council, Pennsylvania</a><br />
<br />
<br />
<div align="left"><table border="1" bordercolor="#000000" cellpadding="3" cellspacing="0" class="" id="lwnp"><tbody>
<tr><td><b>Scout's Name<br />
</b></td><td><b>Troop<br />
</b></td><td><b>Counselor's Name<br />
</b></td></tr>
<tr><td><br />
</td><td><br />
</td><td><br />
</td></tr>
</tbody></table></div><br />
<h2>Requirement 1</h2><i>Explain what citizenship in the world means to you and what you think it takes to be a good world citizen.</i><br />
<br />
<br />
<br />
<h2>Requirement 2</h2><i>Explain how one becomes a citizen of the United States</i>,<br />
<br />
<br />
<br />
<br />
<br />
<br />
<i>explain the rights,</i><br />
<br />
<br />
<br />
<br />
<br />
<i>duties,</i><br />
<br />
<br />
<br />
<br />
<br />
<br />
<i>and obligations of US citizenship.</i><br />
<br />
<br />
<br />
<br />
<br />
<i>Discuss the<br />
similarities and differences between the rights, duties, and<br />
obligations of US citizens and the citizens of two other countries.</i><br />
<br />
<br />
<div align="left"><table border="1" bordercolor="#000000" cellpadding="3" cellspacing="0" class="" id="gdxw"><tbody>
<tr><td><br />
</td><td><b>Country #1</b></td><td><b>Country #2</b></td></tr>
<tr><td><b>Country Name<br />
</b></td><td><br />
</td><td><br />
</td></tr>
<tr><td><b>Rights - Similarities with US<br />
</b></td><td><br />
</td><td><br />
</td></tr>
<tr><td><b>Rights - Differences from US</b></td><td><br />
</td><td><br />
</td></tr>
<tr><td><b>Duties - Similarities with US<br />
</b></td><td><br />
</td><td><br />
</td></tr>
<tr><td><b>Duties - Differences from US</b></td><td><br />
</td><td><br />
</td></tr>
<tr><td><b>Obligations - Similarities with US<br />
</b></td><td><br />
</td><td><br />
</td></tr>
<tr><td><b>Obligations - Differences from US</b></td><td><br />
</td><td><br />
</td></tr>
</tbody></table></div><div align="left"><br />
</div><h2>Requirement 3<br />
</h2><i>Do both of the following.</i><br />
<h3>Requirement 3a</h3><i>Pick a current world event.</i><br />
<br />
<br />
<br />
<br />
<br />
<br />
<i>In relation to this current event, discuss<br />
with your counselor how a country's national interest and its<br />
relationship with other countries might affect areas such as its<br />
security,</i><br />
<br />
<br />
<br />
<br />
<br />
<br />
<i>its economy,</i><br />
<br />
<br />
<br />
<br />
<br />
<br />
<i>its values,</i><br />
<br />
<br />
<br />
<br />
<br />
<br />
<i>and the health of its citizens.</i><br />
<br />
<br />
<br />
<br />
<h3>Requirement 3b</h3><i>Select a foreign country</i><br />
<br />
<br />
<br />
<i>and discuss with your counselor how its<br />
geography,</i><br />
<br />
<br />
<br />
<i>natural resources,</i><br />
<br />
<br />
<br />
<i>and climate</i><br />
<br />
<br />
<br />
<i>influence its economy</i><br />
<br />
<br />
<br />
<i>and its<br />
global partnerships with other countries.</i><br />
<br />
<br />
<br />
<br />
<h2>Requirement 4</h2><i>Do two of the following.</i><br />
<h3>Requirement 4a</h3><i>Explain international law</i><br />
<br />
<br />
<br />
<i>and how it differs from national law.</i><br />
<br />
<br />
<br />
<i>Explain<br />
the role of international law</i><br />
<br />
<br />
<br />
<i>and how international law can be used as<br />
a tool for conflict resolution.</i><br />
<br />
<br />
<br />
<h3>Requirement 4b</h3><i>Using resources such as major daily newspapers, the Internet (with your<br />
parent's permission), and news magazines, observe a current issue that<br />
involves international trade, foreign exchange, balance of payments,<br />
tariffs, and free trade.<br />
</i><br />
<br />
<br />
<i>Explain what you have learned. Include in your<br />
discussion an explanation of why countries must cooperate in order for<br />
world trade and global competition to thrive.<br />
</i><br />
<br />
<br />
<h3>Requirement 4c</h3><i>Select TWO of the following organizations and describe their role in the world.<br />
</i><br />
<ol><li><i>The United Nations</i></li>
<li><i>The World Court</i></li>
<li><i>World Organization of the Scout Movement</i></li>
<li><i>The World Health Organization</i></li>
<li><i>Amnesty International</i></li>
<li><i>The International Committee of the Red Cross</i></li>
<li><i>CARE <br />
</i></li>
</ol><br />
<div align="left"><table border="1" bordercolor="#000000" cellpadding="3" cellspacing="0" class="" id="yfce"><tbody>
<tr><td><b>Organization 1<br />
</b></td><td><b>Organization 2<br />
</b></td></tr>
<tr><td><br />
</td><td><br />
</td></tr>
</tbody></table></div><br />
<h2>Requirement 5</h2><i>Do all of the following:</i><br />
<h3>Requirement 5a</h3><i>Discuss the differences between constitutional and nonconstitutional governments.</i><br />
<br />
<div align="left"><table border="1" bordercolor="#000000" cellpadding="3" cellspacing="0" class="" id="be7b"><tbody>
<tr><td><b>Constitutional</b></td><td><b>Nonconstitutional</b></td></tr>
<tr><td><br />
</td><td><br />
</td></tr>
</tbody></table></div><br />
<br />
<h3>Requirement 5b</h3><i>Name at least five different types of governments currently in power in the world.</i><br />
<br />
<div align="left"><table border="1" bordercolor="#000000" cellpadding="3" cellspacing="0" class="" id="h36x"><tbody>
<tr><td><br />
</td><td><b>Country<br />
</b></td><td><b>Type of Government<br />
</b></td></tr>
<tr><td><b>1.</b></td><td><br />
</td><td><br />
</td></tr>
<tr><td><b>2.<br />
</b></td><td><br />
</td><td><br />
</td></tr>
<tr><td><b>3.<br />
</b></td><td><br />
</td><td><br />
</td></tr>
<tr><td><b>4.<br />
</b></td><td><br />
</td><td><br />
</td></tr>
<tr><td><b>5.<br />
</b></td><td><br />
</td><td><br />
</td></tr>
</tbody></table></div><br />
<h3>Requirement 5c</h3><i>Show on a world map countries that use each of these five different forms of government.</i><br />
<br />
[<i>You can download a blank world map at <a href="http://upload.wikimedia.org/wikipedia/commons/archive/b/b4/20070311100827%21A_large_blank_world_map_with_oceans_marked_in_blue.gif" id="w2xa" title="Link to a blank world map">http://upload.wikimedia.org/wikipedia/commons/archive/b/b4/20070311100827!A_large_blank_world_map_with_oceans_marked_in_blue.gif</a> and print it. If a country you want is not outlined, then draw it on the map, or choose another map.</i>]<br />
<br />
<h2>Requirement 6</h2><i>Do all of the following:</i><br />
<h3>Requirement 6a</h3><i>Explain how a government is represented abroad</i><br />
<br />
<br />
<br />
<i>and how the<br />
United States government is accredited to international organizations.</i><br />
<br />
<br />
<br />
<h3>Requirement 6b</h3>Describe the roles of the following in the conduct of foreign relations.<br />
<br />
<div align="left"><table border="1" bordercolor="#000000" cellpadding="3" cellspacing="0" class="" id="jfh3"><tbody>
<tr><td><b>1.<br />
</b></td><td><b>Ambassador</b></td><td><br />
</td></tr>
<tr><td><b>2.<br />
</b></td><td><b>Consul</b></td><td><br />
</td></tr>
<tr><td><b>3.<br />
</b></td><td><b>Bureau of International Information Programs</b></td><td><br />
</td></tr>
<tr><td><b>4.<br />
</b></td><td><b>Agency for International Development</b></td><td><br />
</td></tr>
<tr><td><b>5.<br />
</b></td><td><b>United States and Foreign Commercial Service</b></td><td><br />
</td></tr>
</tbody></table></div><br />
<h3>Requirement 6c</h3><i>Explain the purpose of a passport and visa for international travel.</i><br />
<br />
<br />
<br />
<h2>Requirement 7</h2><i>Do TWO of the following and share with your counselor what you have learned:</i><br />
<br />
<div align="left"><table border="1" bordercolor="#000000" cellpadding="3" cellspacing="0" class="" id="ruey"><tbody>
<tr><td><b>a.<br />
</b></td><td><b>Visit the Web site (With your parent/guardian's permission)<br />
of the U.S. State Department. Learn more about an issue you find<br />
interesting that is discussed on this Web site.</b></td><td><br />
</td></tr>
<tr><td><b>b.<br />
</b></td><td><b>Visit the Web site (With your parent/guardian's<br />
permission) of an international news organization or foreign<br />
government, OR examine a foreign newspaper available at your local<br />
library, bookstore, or newsstand. Find a news story about a human right<br />
realized in the United States that is not recognized in another<br />
country.</b></td><td><br />
</td></tr>
<tr><td><b>c.<br />
</b></td><td><b>Visit with a student or Scout from another country and<br />
discuss the typical values, holidays, ethnic foods, and traditions<br />
practiced or enjoyed there.</b></td><td><br />
</td></tr>
<tr><td><b>d.<br />
</b></td><td><b>Attend a world Scout jamboree.</b></td><td><br />
</td></tr>
<tr><td><b>e.<br />
</b></td><td><b>Participate in or attend an international event in your area, such as an ethnic festival, concert, or play.</b> </td><td><br />
</td></tr>
</tbody></table></div><br />
<br />
<br />
<br />
<br />
<br />
</div>Bhaskarhttp://www.blogger.com/profile/14323369551611484731noreply@blogger.com0