A good algorithm usually comes together with a set of good data structures that allow the algorithm to manipulate the data efficiently. In this course, we consider the common data structures that are used in various computational problems. You will learn how these data structures are implemented in different programming languages and will practice implementing them in our programming assignments. This will help you to understand what is going on inside a particular built-in implementation of a data structure and what to expect from it. You will also learn typical use cases for these data structures. A few examples of questions that we are going to cover in this class are the following: 1. What is a good strategy of resizing a dynamic array? 2. How priority queues are implemented in C++, Java, and Python? 3. How to implement a hash table so that the amortized running time of all operations is O(1) on average? 4. What are good strategies to keep a binary tree balanced? You will also learn how services like Dropbox manage to upload some large files instantly and to save a lot of storage space!
Distributed Hash Tables
Loading...
From the course by University of California San Diego
Data Structures
1371 оценки
University of California San Diego
1371 оценки
Course 2 of 6 in the Specialization Data Structures and Algorithms
From the lesson
Hash Tables
In this module you will learn about very powerful and widely used technique called hashing. Its applications include implementation of programming languages, file systems, pattern search, distributed key-value storage and many more. You will learn how to implement data structures to store and modify sets of objects and mappings from one type of objects to another one. You will see that naive implementations either consume huge amount of memory or are slow, and then you will learn to implement hash tables that use linear memory and work in O(1) on average! In the end, you will learn how hash functions are used in modern disrtibuted systems and how they are used to optimize storage of services like Dropbox, Google Drive and Yandex Disk!
Meet the Instructors
Alexander S. KulikovVisiting Professor
Department of Computer Science and Engineering
Michael LevinLecturer
Computer Science
Daniel M KaneAssistant Professor
Department of Computer Science and Engineering / Department of Mathematics
Neil RhodesAdjunct Faculty
Computer Science and Engineering
Hi.
In this video we will learn how to store a whole lot of objects,
how to store big data, using distributed hash tables.
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.
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.
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.
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?
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.
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?
Well, we need another rule for that.
We cannot store the addresses of all the other computers
on each of the computers because that is inconvenient.
We will have to constantly update that information.
But, each node, each computer will be so called acquainted with a few neighbors.
So it will store the metric addresses of some of its neighbors.
The rule is that for any key,
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.
And this network of nodes which know some neighbors and
they know some of their neighbors is called, Overlay Network.
So in conclusion, Distributed Hash Tables is a way to store
Big Data on many many computers and access it fast, as if it was on one computer.
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,
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.
And I hope that after this lecture,
you understand how important are data structures we study in this course,
to the modern technological industry, distributed systems, and big data.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
