‫Welcome back.
‫Now that we have a good understanding
‫of what types of databases are available to us
‫and how to pick the right database for our use case,
‫let's continue our discussion about databases
‫in the context of a large scale system.
‫So in this lecture,
‫we're going to learn about three techniques
‫to improve the performance, availability and scalability
‫of our database.
‫The first technique which improves the performance
‫of our database queries is called indexing.
‫The purpose of indexing is to speed up retrieval operations
‫and locate the desired records in a sublinear time.
‫Without indexing,
‫those operations may require a full table scan
‫which can take a very long time when we have large tables.
‫Let's look at a few examples of such operations.
‫Let's assume that we have a very large table with many rows
‫that contain data about our company's users.
‫If we want to perform a query
‫to find all the users that live in a particular city
‫so we can send them relevant notifications for example,
‫our SQL query would look like this.
‫Now, internally to find all the rows in the table
‫that match this condition,
‫our database would have to scan linearly
‫through all the rows.
‫Which for large tables can take a very long time.
‫Other examples of costly operations
‫that involve a full table scan
‫include getting the list of users in our table sorted.
‫For example, by their last name, age, or income.
‫So in addition to the sorting operation,
‫we would still need to go the entire table at least once.
‫Either of those operations if performed very frequently
‫or on very large tables can become a performance bottleneck
‫and impact our users' performance.
‫This is where indexing comes in.
‫A database index is a helper table that we can create
‫from a particular column or a group of columns.
‫When the index is created from a single column,
‫this index table contains a mapping from the column value
‫to the record that contains that value.
‫Once that index table is created,
‫we can put that table inside a data structure.
‫For example,
‫we can use a hashmap which provides us very fast lookups
‫or we can use a type of self-balancing tree
‫like a B-Tree, for example,
‫which keeps all the values sorted
‫so it's easier to both find a particular record in it
‫and return a sorted list of rows
‫that match a certain condition.
‫For example, if we create an index from the city column
‫and place that index in a hash table,
‫then a query that looks for all the users
‫that live in the city of LA can return this list immediately
‫without the need to scan through the entire table.
‫Similarly, if we want to get a sorted view of all the users
‫based on their age within a certain range,
‫then an index that is organized in a balanced tree
‫will provide us with this view
‫in a logarithmic time complexity
‫that avoids both scanning the entire table,
‫and sorting it for every query.
‫Now, as we already mentioned,
‫indexes can be formed not only from one column,
‫but also from a set of columns.
‫An example for that would be if we want to get all the users
‫that live in a particular city
‫and also have a particular last name.
‫If we were to create an index only for the city column,
‫we would get all the users
‫who live in that particular city immediately.
‫However, we would still need to scan linearly
‫through all those users
‫and check if their last name is our query.
‫On the other hand, if we create a composite index
‫from both columns,
‫we can have a direct mapping from a pair of values
‫to the row that contains them.
‫So for the same query that looks for people
‫that live in a particular city
‫and have a particular last name,
‫we can get the result immediately without any linear scan.
‫Of course, as always,
‫if we prioritize one type of operation,
‫we have to make a tradeoff somewhere.
‫In the case of indexing, we make the read queries faster
‫in the expense of additional space
‫for storing the index tables,
‫and also the speed of write operations.
‫The reason the write operations become slower
‫is that whenever we want to update or add a new row,
‫now we also need to update the index table.
‫It's important to note
‫that although we use the relational database
‫for all our examples,
‫indexing is also extensively used
‫in non-relational databases such as document stores
‫to speed up queries.
‫The next technique we're going to talk about
‫is database replication.
‫When we store a mission critical data
‫about our business in a database,
‫our database instance
‫become a potential single point of failure.
‫So just like we avoided a single point of failure
‫for compute instances,
‫we're going to apply the same technique for databases.
‫If we replicate our data
‫and run multiple instances of our database
‫on different computers,
‫we can increase the full tolerance of our system
‫which in turn provides us with higher availability.
‫With multiple replicas of our data,
‫we can make sure that if one of the replicas goes down
‫or becomes unavailable either temporarily or permanently,
‫our business is not affected
‫because queries can continue going to the available replicas
‫while we work to either restore or replace
‫the faulty instance.
‫In addition to higher availability,
‫we can also get better performance
‫in a form of higher throughput.
‫If we have thousands or millions of users
‫making requests to our database through our services,
‫we can handle a much larger volume of queries
‫if we distribute them among a larger number of computers.
‫The trade off that we make
‫when we introduce replication in our database
‫is much higher complexity
‫especially when it comes to write, update,
‫and delete operations.
‫Making sure that concurrent modifications
‫to the same records don't conflict with each other
‫and provide some predictable guarantees
‫in terms of consistency and correctness
‫is not a trivial task.
‫Distributed databases are notorious
‫for being difficult to design, configure, and manage,
‫especially on a high scale.
‫And it requires some competency
‫in the field of distributed systems.
‫Database replication is supported
‫by pretty much all modern databases.
‫In particular, all the non-relational databases
‫incorporate replication out-of-the-box.
‫As those databases were designed in an age
‫where high availability and large scale
‫were already a big concern for most companies.
‫The support for replication in relational databases
‫varies among different relational database implementations.
‫The third technique we're going to talk about
‫is database partitioning,
‫which is also referred to as database sharding.
‫Unlike replication where we run multiple instances
‫of our database with the same copy of the data
‫on each one of them,
‫when we do database partitioning,
‫we split the data among different database instances.
‫And for increased performance,
‫we typically run each instance on a separate computer.
‫When our data is split among a group of computers,
‫we can store way more data than we could originally
‫if we had only one machine for our disposal.
‫Additionally with partitioning,
‫different queries that touch different parts of our data
‫can be performed completely in parallel.
‫So with database partitioning,
‫we get both better performance and higher scalability.
‫Of course, just like in the case of database replication,
‫database sharding essentially turns our database
‫into a distributed a database.
‫This increases the complexity of the database
‫and also adds some overhead,
‫as now we also need to be able to route queries
‫to the right shards
‫and make sure that neither of the shards becomes too large
‫in comparison to the others.
‫Database sharding is the first class feature
‫in pretty much all non-relational databases.
‫The reason for that
‫is that non-relational databases by design
‫decouple different records from each other.
‫So storing the records on different computers
‫is a lot more natural and easier to implement.
‫When it comes to relational databases,
‫just like in the case of replication,
‫the support for partitioning depends on the implementation.
‫The reason it's less supported in relational databases
‫is because relational database queries
‫that involve multiple records are a lot more common.
‫And having those records spread across multiple machines
‫is just a lot more challenging to implement
‫in a performant way
‫while still supporting things like asset transactions
‫or table joints.
‫So when we choose a relational database for a use case
‫that involves a high volume of data,
‫we need to make sure that partitioning is well supported.
‫While we're on the topic of partitioning,
‫it's worth mentioning
‫that partitioning is not only used for databases
‫but can also be used to logically split our infrastructure.
‫For example, we can partition our compute instances
‫using configuration files
‫so that requests from paid customers go to some machines
‫and traffic from free users
‫go to other maybe less powerful machines.
‫Alternatively, we can send traffic
‫from mobile devices to one group of computers
‫and send desktop traffic to another group of computers
‫running the same application.
‫This way, if we have an outage, we can easily know
‫what type of users are affected
‫and decide how to act upon it.
‫As a final note,
‫those three techniques, indexing, replication
‫and partitioning are completely orthogonal to each other.
‫So we don't need to choose one over the other.
‫And in fact, all three of them are commonly used together
‫in most real life, large scale systems.
‫In this lecture, we learned about three techniques
‫that we can apply to our database
‫to make it much more robust in a large scale system.
‫We first learned about indexing,
‫which improves the performance of our database
‫by speeding up search and retrieval operations.
‫Then we learned about database replication
‫which improves our systems availability
‫and performance through increased throughput.
‫And finally, we learned about the third technique
‫which is database partitioning.
‫Database partitioning improves our database scalability
‫by splitting up our data across multiple database instances
‫running on different computers.
‫I'll see you soon in the next lecture.