0:08

So big data is when you need to store trillions or more objects.

Â For example, trillions of file addresses in Dropbox, or user profiles,

Â or emails and user accounts, for example, in Gmail or services like that.

Â And you need fast search and fast access to that data.

Â So hash tables, in general, is a good solution for

Â that problem because they give a constant time search access on average.

Â But for number of keys in the order of ten to the power of 12,

Â the amount of memory that a single hash table will store becomes too

Â big to store it in one computer and so we need to do something else,

Â we need to use more computers probably.

Â And the solution to this is distributed hash tables.

Â So the first idea for distributed hash table is the following,

Â just get more computers.

Â Get 1,000 computers.

Â If you are Google or Dropbox you can do that.

Â And then you will store your data on many computers.

Â And you will do the following.

Â You create a hash table on each of those computers.

Â And then you will separate the data between those computers.

Â So each computer will store its own part of the data.

Â And you need to determine quickly, and automatically, and

Â deterministically which computer should store some object O.

Â 1:30

And there is a simple way, just compute some hash function of this object,

Â modular 1000, so we get basically a value from 0 to 999 for each object and

Â that will be the number of the computer which should store this object.

Â And then you send a request to that computer and search or modify

Â what you need to do with that object in the local hash table of that computer.

Â And that seems to already solve our problem because if a new

Â request comes you quickly compute the hash function on the object and

Â you know where to send your request.

Â And then that computer just looks up in its local hash table.

Â Each of the local hash tables can be 1,000 times less

Â than the total amount of data stored, and so it is scalable.

Â If you need more data, you just get more computers and everything works.

Â Still there are problems with this approach.

Â and the main problem is that computers sometimes break.

Â And especially if you have a lot of computers, then they break pretty often.

Â For example if a computer breaks once in two years on average, then if you have

Â 1,000 computers, on average, more than one computer breaks every day.

Â Because there are less than 1,000 days in two years, and you have 1,000 computers.

Â So what do you do in that case?

Â You don't want to lose your user's data.

Â So you need to store several copies of the data.

Â So basically you can do it in a way that every computer stores each part of data.

Â Each part of data should be stored on several computers.

Â And what happens then when some computer breaks?

Â Well, luckily the data which is stored on this computer

Â is also stored somewhere else.

Â But if that's the only copy left after this computer broke, you also need to also

Â copy that data to some other computer, so that it is again stored in several places.

Â And you need to relocate the data from the broken computer and

Â also sometimes your service grows and you want to buy more computers.

Â You want to reply faster to your clients and

Â new computers are added to the cluster.

Â And then this formula take hash value of the object modular 1000.

Â And this is the number of computer on which your object is stored.

Â It no longer works.

Â Because the numbers of the computers always change.

Â New computers come in.

Â Broken computers come out.

Â And so you need something else.

Â 3:51

And one way to solve this is called consistent hashing.

Â So first, we choose some hash function with sum cardinality m.

Â And we choose a circle, a regular circle, and

Â you put numbers from zero to m minus one on the circle in a clockwise order.

Â And then each object, O, is mapped

Â to some point on the circle corresponding to the number hash value of this object.

Â 4:18

Which is from 0 to m- 1, so it always maps to some of the numbers on the circle.

Â And also, each computer ID is mapped to the same circle.

Â We hash the ID of the computer and

Â we get the number of the points to which this computer is mapped.

Â So let's look at the picture.

Â Here's our circle.

Â And, for example m is 12.

Â Then we put 12 points around the circle.

Â And we put numbers from 0 to 11 around the circle.

Â And then, objects, such as for example,

Â name Steve, can be mapped to some of those 12 points.

Â And if hash value of Steve is 9,

Â then Steve is mapped to the point with number 9.

Â And also computers can be mapped to points, and for example,

Â this computer with ID 253.

Â If the hash value of 253 is 5, then this computer is mapped to the point 5.

Â So what do we do then?

Â 5:17

We make a rule that each object is stored on the so-called closest computer,

Â closest in terms of the distance along the circle.

Â And in this case,

Â each computer stores all objects falling on some arc, which consists

Â of all objects which are closer to this computer than to any other computer.

Â Let's again look at the picture.

Â This is the circle and there are six computers and

Â these computers mapped to some points on this circle.

Â And then the arcs of the same color as the computers near them,

Â are the sets of points,

Â which are closer to the corresponding computer than to any other computer.

Â And so each computer is responsible for some arc of this circle.

Â For all the keys that are mapped to this arc.

Â 6:07

And so what happens when computers come in because new computers are bought or

Â when computers are broken.

Â When a computer goes off when it is broken, it's neighbors take its data.

Â So it has two neighbors, and it's arc is divided into parts, and one part

Â goes to the right neighbor and the, another part goes to the left neighbor.

Â And when a new computer is added it takes data from its neighbors.

Â So it comes between some two already existing computers, and

Â it takes a part of the arc of one of them,

Â and a part of the arc of another one, and he gets its arc.

Â So let's look at an example.

Â For example, the yellow computer breaks and it goes away.

Â And then the green and the blue computer will take its arc and

Â divide it between themselves.

Â So that's what happens.

Â Another problem which still needs to be solved is that when some computer breaks,

Â we need to copy or relocate the data.

Â And how will a node, a computer, know where to send the data that is stored?

Â 7:52

each node will either store this key itself, or it will be acquainted.

Â It will know some other computer which is closer to this

Â key in terms of the distance on the circle.

Â And, that way, if a request comes to some node, any node in the network,

Â about some key, it either can find this key inside it's own storage, or,

Â it will redirect the request to another node which is closer to this key.

Â And that that node will either store the key, or

Â direct the code to the next node, which is even closer to that key.

Â And in finite number of iterations the request will come to the node that will

Â actually stores the key.

Â So that's the idea.

Â And in practice, what we can do is we can put the computers,

Â the nodes on the circle.

Â And then each node will know its immediate neighbors, its neighbors of neighbors.

Â And then its neighbors in distance of 4 and distance of 8, and distance of 16.

Â And for all powers of 2 it will know neighbors to the right and

Â to the left at distance of this part 2.

Â Of course less than n over half.

Â And it's easier to see on the picture again.

Â So suppose we have many, many nodes.

Â And then the upper node will have links to its right and left neighbor.

Â To its right and left neighbor on distance of two, and

Â to its right and left neighbor, the distance of four, and so on.

Â So each node will contain algorithmic number of links to other nodes,

Â which is much better than storing all the other nodes.

Â And, if we need to come to some key from some node that doesn't contain it

Â we'll first jump in the direction where the distance to the key decreases.

Â And we will jump as much as we can.

Â If the computer at distance eight is closer than our computer to the key,

Â we will jump at least by eight.

Â If computer with distance 16 is closer, we'll jump at least 16.

Â If computer with distance 32 is farther, then we'll jump just by 16.

Â In this way, we will always jump by at least a half

Â of the distance which divides us from computer that stores the key itself.

Â And so in algorithmic number of steps, we will actually come from

Â the current computer, to the computer that actually stores our key.

Â 10:48

Consistent Hashing is one way to determine which computer actually owns the data,

Â which computer stores this particular object.

Â And to do that, consistent hashing uses mapping of keys and

Â computer IDs on a circle.

Â And each computer stores a range of keys on an arc,

Â which is closest to this computer in terms of distance along the circle.

Â And also overlay network is used to route the data to and from the right computer.

Â So when a computer is broken,

Â 11:19

first, its data needs to be copied to some other computer.

Â And its neighbors take its data.

Â So computer disappears, and its arc disappears, but

Â this is actually divided between two neighbor computers.

Â And each of those arcs increases a bit, and

Â they cover the whole data and then we proceed.

Â If a new computer appears, it takes some data from its right neighbor,

Â some data from its left neighbor, and assembles an arc for itself.

Â