takeaway

The KeyDB project is a branch of Redis fork. It is well known that Redis is a single-threaded KV memory storage system, and KeyDB converts Redis to multi-threaded with 100% compatibility with the REDis API.


Redis multithreading will be released at the end of this year, we wait and see

Threading model

KeyDB splits the main thread of Redis into the main thread and the worker thread. Each worker thread is an IO thread that listens on ports, accepts requests, reads data, and parses protocols. As shown in the figure:



KeyDB uses the SO_REUSEPORT feature. Multiple threads can be bound to listen on the same port.

Each worker thread does CPU binding, and SO_INCOMING_CPU is used to read data, specifying the CPU to receive data.

After the protocol is parsed, each thread will manipulate the data in memory, and a global lock controls multithreading access to the data in memory.

In fact, the main thread is also a worker thread, including the work content of the worker thread as well as the work content that only the main thread can complete. The subscript 0 in the Worker thread array is the main thread.

The main work of the main thread is to implement serverCron, including:

  • To deal with statistics
  • Client link management
  • Resize and reshard of DB data
  • Processing aof
  • Replication Primary/secondary synchronization
  • Tasks in cluster mode

Link management

In Redis all link management is done in one thread. In the design of KeyDB, each worker thread is responsible for a set of links, and all links are inserted into the link list of this thread for maintenance. Links must be created, worked, and destroyed in the same thread. Add a new field for each link

int iel; /* the event loop index we’re registered with */

Used to indicate which thread takes over the link.

KeyDB maintains three key data structures for link management:

  • Clients_pending_write: Thread-specific linked list that maintains queues that synchronize data sent to client links
  • Clients_pending_asyncwrite: Thread-specific linked list that maintains queues that send data asynchronously to client links
  • Clients_to_close: Global linked list that maintains client links that need to be closed asynchronously

It is divided into synchronous and asynchronous queues because redis has some linkage APIS, such as PUB/SUB. After pub, messages need to be sent to the client of SUB. The thread executed by PUB and the client of SUB are not in the same thread. KeyDB will need to send data to non-thread clients to be maintained in asynchronous queues.

The logic of synchronous sending is relatively simple, which is completed in this thread. The following figure illustrates how to send data synchronously to the client:



As mentioned above, the creation of a link, the receipt of data, the sending of data, and the release of the link must all be performed in the same thread. Asynchronous sending involves the interaction between two threads. KeyDB pipes messages in two threads:

int fdCmdWrite; // write pipe int fdCmdRead; / / read the pipeCopy the code

When a local thread needs to send data asynchronously, it checks whether the client belongs to the local thread first. The non-local thread obtains the thread ID of the client and then sends AE_ASYNC_OP::CreateFileEvent to the dedicated thread, requiring that a write socket event be added. The dedicated thread adds the corresponding request to the write event as it processes the pipe message, as shown below:



Redis maintains a global asynchronous close list because some close client requests are not executed entirely in the thread where the link is located.



Locking mechanism

KeyDB implements a spinlock-like locking mechanism called FastLock.

The main data structures for FastLock are:

struct ticket { uint16_t m_active; // Unlock +1 uint16_t m_avail; // lock +1}; struct fastlock { volatile struct ticket m_ticket; volatile int m_pidOwner; // Current thread id volatile int m_depth; // the number of times the current thread is locked};Copy the code

Use atomic operations __atomic_load_2, __atomic_FETch_add, __atomic_compare_exchange to determine whether the lock can be obtained by comparing M_ACTIVE = m_AVAIL.

Fastlock provides two ways to acquire locks:

  • Try_lock: returns after a failed attempt
  • Lock: busy, with sched_yield being used to actively surrender the CPU every 1024 * 1024 busy times and move to the end of the CPU’s task for execution.

Combine try_lock with events in KeyDB to avoid busy situations. Each client has its own lock, which is attempted before reading the client data, and if it fails, exits because the data has not yet been read, so it can be processed again in the next epoll_wait processing event loop.



Active-Replica



KeyDB implements the multi-active mechanism. Each replica can be set as writable but not read-only, and data is synchronized between replicas. The main features are:

  • Each replica has a UUID mark to remove ring replication
  • Rreplay API is added to package incremental commands as rreplay commands with local UUids
  • Key, value and timestamp version are used for conflict check. If the local key is the same and the timestamp version is larger than that of the synchronized data, the new write fails. The timestamp version of the key is obtained by moving the current timestamp 20 bits to the left and incrementing the last 44 bits.

The last

Welcome everyone interested can pay attention to my public number [Java small melon brother sharing platform], the article will be updated inside, there are all kinds of Java information is free to share.