Key-Value Store key-value data storage explanation – system design 11

system-design-system design 11-key-value data storage-key-value-store-introductoin-to-database-fundamentals-hogantech

Preface

Remember we were here Introduction to database basics – system design 08 After explaining the relational database, this article will explain the principle of Key-Value Store in more depth. Of course, I will also provide an introduction to NoSQL and Key-value database below.

What is NoSQL?

NoSQL means Not Only SQL and is a non-relational database, which means it does not use the traditional relational database model to store data. NoSQL databases typically use more flexible and extensible data models such as key-value pairs, files, graphs, or wide tables. This article will explain the key-value database.

What is a key-value database?

Key-value databases use key-value methods such as hash tables to store data in the form of key-value pairs. The key acts as the primary key and the value can be anything from a simple scalar value to a complex object. Common key-value databases include: Amazon DynamoDB, Redis.

Key-Value Store

Key-Value Store is a Distributed Hash Table, in which DHT is a decentralized storage method that provides hash table-like search and storage. Hash Table is also an Abstract Data Type (ADT). Its advantage is that it can usually complete the Search operation in a relatively fast time. Let's first talk about the principle of hash. A set of keys is generated by a hash function, and it is a unique key. Key-Value Store binds the key to a specific value, and the value can be a storage type such as Map or Image.

Typically we will limit the value to a relatively small file size, approximately MB to KB of content size. Key-value data storage can be used in many different scenarios, such as creating a Messenger and storing user conversations. Such scenarios are very suitable for using this NoSQL approach.

How to design a key-value data store?

If you want to design a system component, you first need to return to the original question. What are the requirements for this system component? For readers who have forgotten their needs, it is recommended that you watch it Non-functional features of software design – System Design 03 .

Functional Requirement

Generally, key-value storage is the same as a general database and has some common functions, such as get and put functions. However, there are still some differences in functional requirements between key-value storage systems and general storage systems.

  1. Configurable services: Some systems may sacrifice strong consistency (Consistency) for higher availability (Availability). The key-value store will need to provide configurable services so that the consistency model can be used in different systems.
  2. Ability to always write: The system needs to have the ability to write to the key-value store. If the user wants strong consistency (Consistency), due to the influence of the CAP theorem, availability (Availability) will inevitably be abandoned. In other words, in CAP, C is preferred.

Non-Functional Requirement

Scalability: The key-value store must be able to run on tens of thousands of servers around the world. And add or delete servers according to needs, while reducing the impact on service availability, or even causing no impact. Additionally, the system should be able to handle a large number of users of the key-value store.

Fault Tolerance: If a system server or system component fails, the key-value store should continue to operate without interruption.

Design key-value data storage

Before starting to design the system, first design simple (Design Simple) principle, you need to assume the following:

  1. The data center is trusted.
  2. Authentication in the data store has been completed.
  3. User requests and responses are via HTTPS.

API design

The first is the design of the API. We need to think about what APIs are needed from a functional perspective. Key-value storage, like the Hash Table, provides two main functions: get and put.

Get function

				
					get(key)
				
			

We return the corresponding value according to the key of the parameter. Let me also mention something else here How does Data Replication optimize the database? - System Design 09 There is the data copying issue mentioned. When the key-value database is copying data, it will find a copy of the object associated with the key. This is done by the system if the storage is configured with a weaker data consistency model.

Put function

				
					put(key, value)
				
			

This function is used to store the value associated with the key. The key-value data store automatically determines where the data should be placed. In addition, the system usually retains metadata about stored objects. In the future, we will also give a good introduction to what metadata is.

Increase scalability

For system design, scalability (Scalability) is very important, so when designing the key-value store (Key-Value Store), we will store the key-value data in the storage node. As needs change, we may need to add or delete storage nodes. This means that we need to partition the data on the nodes in the system to distribute the load to all nodes. Readers who are not yet familiar with partitioning can refer to Data Partitioning What is data partitioning? – System Design 10.

Returning to the partitioning in the key-value data store, here is an example: Suppose we have four nodes, and we want 40% requests to be sent to each node to balance the load. The traditional way to solve this problem is through the modulo operator ( Modulus Operator) to do the calculations. Every request that arrives has a key associated with it. When a request comes in, we calculate the hash value of the key. Then, we find the remainder by combining the hash value with the number of nodes m.

Consistent Hashing

We were once What is DNS? Introduction to Domain Name System – System Design 06 Various types of algorithms have been introduced to deal with traffic problems, so if we discuss hashing, we have to discuss the Consistent Hashing algorithm. This algorithm is a very suitable method for balancing node load.

In the consistent hash algorithm, we need to first assume that there is a hash ring (Hash Ring) from 0 to n-1, where n is the number of available hash values. We use the ID of each node to calculate its hash value and map its hash value to the Hash Ring. Each request is fulfilled by the next node it finds by moving clockwise in the ring.

Whenever a new node joins the ring, the immediately next node is affected. It must share its profile with the newly added node, while other nodes are not affected. Such algorithms are easily extensible and can keep changes to nodes to a minimum. The hash values are randomly distributed, so we expect the load of requests to be random and evenly distributed around the ring.

The main benefit of consistent hashing is that when nodes join or leave, we need to ensure that the minimum number of keys is moved. However, in practice, the request load is not evenly distributed. Any server that handles large amounts of data can become a bottleneck in a distributed system. The node receives a disproportionately high number of data storage and search requests, reducing overall system performance. Here I provide an article that I think is very detailed, for readers to use as a reference, and with consistent and mixed illustrations.

system-design-system design 11-key-value data storage-key-value-store-introductoin-to-database-fundamentals-hogantech01
system-design-system design 11-key-value data storage-key-value-store-introductoin-to-database-fundamentals-hogantech02
system-design-system design 11-key-value data storage-key-value-store-introductoin-to-database-fundamentals-hogantech03
system-design-system design 11-key-value data storage-key-value-store-introductoin-to-database-fundamentals-hogantech04
system-design-system design 11-key-value data storage-key-value-store-introductoin-to-database-fundamentals-hogantech05
system-design-system design 11-key-value data storage-key-value-store-introductoin-to-database-fundamentals-hogantech06
system-design-system design 11-key-value data storage-key-value-store-introductoin-to-database-fundamentals-hogantech07

Using Virtual Nodes

In addition to using consistent hashing algorithms, we can also use virtual nodes to ensure a more even load distribution among nodes. This method uses multiple hash functions on the same key instead of applying a single hash function.

Here's a quick example, let's say we have four hash functions. For each node, we compute four hash values and put them into the ring. For this request, we only use a hash function. No matter where the request arrives on the ring, it is handled by the next node found while moving in a clockwise direction. There are four locations per server, so the load of requests is more even. Additionally, if a node has more hardware capacity than other nodes, we can add more virtual nodes by using additional hash functions. This way, it will occupy more positions in the ring and serve more requests.

Data Replication

This article How does Data Replication optimize the database? - System Design 09 I have written about database replication. When it comes to key-value databases, we will also have many different methods to handle data replication. Common data replication includes: master-slave relationship and point-to-point relationship.

Primary-secondary replication

In the master-slave method, one of the storage areas is the primary storage area and the other storage areas are auxiliary storage areas. The secondary replica copies its data from the primary replica. The primary storage area is used to handle write requests, while the secondary service serves read requests. Also if the main repository fails we won't be able to write to the storage and it will become a single point of failure.

Peer-to-peer replication

In a peer-to-peer approach, all storage areas are primary storage areas and data is replicated to keep them updated. Reads and writes are also allowed on all nodes. Typically, replicating across all n nodes is inefficient and expensive. Instead, three or five are common choices for the number of storage nodes to replicate.

Conclusion

I will be traveling abroad for nearly two weeks, but I will continue to update technical articles on system design, and will continue to write system design content in the future. If you like this type of article, you might as well leave a message to encourage me!

related articles

Data Partitioning What is data partitioning? – System Design 10

How does Data Replication optimize the database? - System Design 09

Introduction to database basics – system design 08

Load Balancer Explained – System Design 07

What is DNS? Introduction to Domain Name System – System Design 06

Introduction to System Design Components Building Block – System Design 05

Back-of-the-envelope Back-of-the-envelope Calculation – System Design 04

Non-functional features of software design – System Design 03

Application of abstraction in system design – System Design 02

Introduction to Modern System Design – System Design 01

Quote

A Guide to Consistent Hashing

What Is a Key-Value Database?

Leave a Comment

Your email address will not be published. Required fields are marked *

en_USEnglish