Understanding Consensus and Paxos in Distributed Systems – Chord Simple

Understanding Consensus and Paxos in Distributed Systems – Chord Simple: "Now we know that the Paxos algorithm was designed to try to solve the problem of distributed consensus between a network of computers in an asynchronous system. What does the actual algorithm say? How does it get this group of machines to achieve consensus in the face of unpredictable failures?

We’ve already answered these questions (sorta) but we’ll do so here more formally by taking a sneak peek at the actual specification. Fortunately, we’ve pretty much covered the entire algorithm while constructing our auction protocol so there are very few surprises here.



Paxos uses the concepts of Proposers, Acceptors and Learners as roles in which a machine can act.

Proposers are machines with opinions. They try to impose their opinion (value) to a set of acceptors. Analogous to our auction process, these proposers are simply bidders.
Acceptors accept values proposed by proposers à la auctioneers.
Learners decide on the agreed upon value based on the acceptors acceptances. We had our bidders decide the agreed upon value (the chosen bid) in our auction. The learners simply act as external agents that declare a value to be chosen."



'via Blog this'

How B-tree indexing works in MySQL

http://stackoverflow.com/questions/2362667/how-b-tree-indexing-works-in-mysql

Q.  When I create an index for a table in mysql, I see that the index_type is type BTREE. Now although I understand about btree(s), I do not quiet understand how it stores the index and how the database searches the records based on this.

I mean, btree is excellent for databases to perform read and writes large blocks of data, when we create an index for column type of Primary key, what I understand is, it creates a tree and splitting the values for the root based on the value type of the root.

Now, does it store only the the primary key ID under the trees or the whole data associated with that primary key?

After finding the wanted primary ID, how does the database extract the record?

A. The database stores the value indexed as a B-Tree key, and the record pointer as a B-Tree value.

Whenever you search for a record holding a certain value of an indexed column, the engine locates the key holding this value in the B-Tree, retrieves the pointer to the record and fetches the record.

What exactly is a "record pointer", depends on the storage engine.

• In MyISAM, the record pointer is an offset to the record in the MYI file.
• In InnoDB, the record pointer is the value of the PRIMARY KEY.

In InnoDB, the table itself is a B-Tree with a PRIMARY KEY as a B-Tree key. This is what called a "clustered index" or "index-organized table". In this case, all other fields are stored as a B-Treevalue.

In MyISAM, the records are stored without any special order. This is called "heap storage".

Basic Search Algorithms

TopCoder: Data Science Tutorials - Algorithms



Binary Search Tree

In computer science, binary search trees (BST), sometimes called ordered or sorted binary trees, are a class of data structures used to implement lookup tables and dynamic sets. They store data items, known as keys, and allow fast insertion and deletion of such keys, as well as checking whether a key is present in a tree.
Binary search trees keep their keys in sorted order, so that lookup and other operations can use the principle of binary search: when looking for a key in a tree (or a place to insert a new key), they traverse the tree from root to leaf, making comparisons to keys stored in the nodes of the tree and deciding, based on the comparison, to continue searching in the left or right subtrees. On average, this means that each comparison allows the operations to skip over half of the tree, so that each lookup/insertion/deletion takes time proportional to the logarithm of the number of items stored in the tree. This is much better than the linear time required to find items by key in an unsorted array, but slower than the corresponding operations on hash tables.

Analysis of Algorithms

The Sedgewick/Wayne book covers very well (part of Coursera course):
Analysis of Algorithms

As people gain experience using computers, they use them to solve difficult problems or to process large amounts of data and are invariably led to questions like these:

• How long will my program take?

• Why does my program run out of memory?

Basic Sorting Algorithms (plus Python examples)

This site has animated visualizations of the main algorithms (h/t David R. Martin):
Sorting Algorithm Animations

The Sedgewick/Wayne book covers well (part of Coursera course):
Princeton: Sorting Applications

Quicksort is the fastest general-purpose sort.

In most practical situations, quicksort is the method of choice. If stability is important and space is available, mergesort might be best. In some performance-critical applications, the focus may be on just sorting numbers, so it is reasonable to avoid the costs of using references and sort primitive types instead.