09 How Does MC Use Multi-threading and State Machines to Handle Request Commands #

Hello, I am your caching teacher Chen Bo, welcome to the 9th lesson “Memcached Network Model and State Machine”

Network Model #

After understanding the system architecture of MC, we can now delve into the various modules of MC one by one. First, let’s learn about the network model of MC.

Main Thread #

MC uses Libevent to implement a multithreaded network IO model. The IO handling threads of MC are divided into main thread and worker threads, each with its own event_base to listen for network events. The main thread is responsible for listening and establishing connections. The worker threads are responsible for reading, parsing, processing and responding to the established connections.

When the main thread is listening on a port, if a connection comes in, the main thread accepts the connection and schedules it to a worker thread. The scheduling process starts by encapsulating the file descriptor (fd) into a CQ_ITEM structure and storing it in the new connection queue. The main thread then polls a worker thread and sends a notification through a pipe to the selected worker thread. Upon receiving the notification, the worker thread retrieves a connection from the new connection queue and begins reading network IO from that connection and processing it, as shown in the diagram below. This processing logic of the main thread mainly occurs in the state machine, corresponding to the connection state of ‘conn_listening’.

Worker Thread #

After receiving the pipe notification from the main thread, the worker thread pops a new connection from the connection queue and creates a ‘conn’ structure. It then registers the ‘conn’ for read events and continues to listen for IO events on that connection. When a command arrives on this connection, the worker thread reads the command sent by the client, parses and processes it, and finally returns a response. The main processing logic of the worker thread also occurs in the state machine, in a function called ‘drive_machine’.

State Machine #

This state machine is shared between the main thread and the worker threads, and is implemented using switch-case statements. The state machine function is shown in the diagram below. It switches on the connection state and performs different logical operations and state transitions based on the different states of the connection. Next, we will analyze the state machine of MC.

Main Thread State Machine #

As shown in the diagram below, the main thread only handles the ‘conn_listening’ state in the state machine. It is responsible for accepting new connections and scheduling them to worker threads. The processing of other states in the state machine mainly occurs in the worker threads. Since MC supports both TCP and UDP protocols, and most internet companies use TCP protocol and access MC through a text-based protocol, the subsequent explanation of the state machine will mainly focus on TCP text protocol.

Worker Thread State Machine #

The processing logic of the worker thread’s state machine is shown in the diagram below, which includes some reset operations performed when a ‘conn’ connection structure is newly created, registering read events, reading network data when data comes in, and parsing and processing the data. If it is a read command or stat command, the processing is basically complete at this stage, and the response is written to the connection buffer. If it is an update command, after initial processing, the worker thread will continue to read the value part and then perform storage or modification. After the changes are completed, the response is written to the connection buffer. Finally, the response is sent to the client. After responding to the client, the connection resets its connection state and waits to enter the next command processing loop. This process mainly includes the 8 state events of ‘conn_new_cmd’, ‘conn_waiting’, ‘conn_read’, ‘conn_parse_cmd’, ‘conn_nread’, ‘conn_write’, ‘conn_mwrite’, and ‘conn_closing’.

Worker Thread State Events and Logical Processing #

conn_new_cmd #

After the main thread schedules a new connection to a worker thread through ‘dispatch_conn_new’, the worker thread creates a ‘conn’ object. The initial state of this connection is ‘conn_new_cmd’. In addition to entering the ‘conn_new_cmd’ state through a new connection, the connection state will also be set to ‘conn_new_cmd’ when the command processing of the connection is completed and it is ready to accept a new command.

Upon entering ‘conn_new_cmd’, the worker thread calls the ‘reset_cmd_handler’ function to reset the ‘cmd’ and ‘substate’ fields of the ‘conn’, and if necessary, shrink the connection buffer. When processing commands from the client, the worker thread needs to allocate a larger read buffer to store key value updates for write commands, and a larger write buffer to buffer the value results to be sent to the client for read commands. During continuous operation, these buffers can consume a lot of memory due to operations involving large size values. Therefore, we need to set a threshold. After exceeding the threshold, we need to shrink the memory used by the buffers to avoid excessive memory consumption by connections. This operation is important in backend service and middleware development, because the number of connections in online services can easily reach tens of thousands. If each connection occupies more than tens of KB of memory, the backend system will occupy hundreds of MB or even several GB of memory space.

conn_parse_cmd #

After processing the main logic of the ‘conn_new_cmd’ state, if there is data available to read in the read buffer, the connection enters the ‘conn_parse_cmd’ state. Otherwise, it will enter the ‘conn_waiting’ state and wait for network data to arrive.

conn_waiting #

After entering the ‘conn_waiting’ state, the processing logic is simple, just register the read event through the ‘update_event’ function, and then update the connection state to ‘conn_read’.

conn_read #

When the worker thread detects incoming network data, the connection enters the ‘conn_read’ state. The processing of ‘conn_read’ is done by ’try_read_network’ function, which reads network data from the socket. If reading fails, the connection enters the ‘conn_closing’ state and closes the connection. If no data is read, it returns to the ‘conn_waiting’ state to continue waiting for data from the client. If data is successfully read, it is stored in the ‘rbuf’ buffer of the ‘conn’, and the connection enters the ‘conn_parse_cmd’ state to prepare for command parsing.

conn_parse_cmd #

conn_parse_cmd is responsible for parsing commands in the state machine. The worker thread first uses try_read_command to read the read buffer of the connection, and separates the command of the data packet using “\n” as the delimiter. If the length of the first line of the command is greater than 1024, the connection is closed. This means that the total length of the key length plus other command fields must be less than 1024 bytes. Of course, for the key, Mc has a default maximum length, key_max_length, which is set to 250 bytes by default. After validating the length of the first line of the command, the command is processed in the process_command function.

process_command is used to handle all protocol commands of Mc, so this function is very important. process_command first splits the command using spaces and determines the command protocol type, and dispatches it to the process_XX_command function for processing.

Mc’s command protocol can be intuitively divided into get types, update types, and other types. However, from the perspective of actual processing, they can be further divided into get types, update types, delete types, arithmetic types, touch types, stats types, and other types. The corresponding processing functions are process_get_command, process_update_command, process_arithmetic_command, process_touch_command, etc. Each processing function can handle different protocols, as shown in the mind map below.

conn_parse_cmd #

Note that the conn_parse_cmd state processing will only enter the process_command when “\n” is read and the complete command header protocol is obtained. Otherwise, it will jump to conn_waiting and continue to wait for the client’s command data packet. In the process_command processing, if it is a get command, after obtaining the value corresponding to the key, it will jump to conn_mwrite, preparing to write the response to the connection buffer. For update type commands, it needs to continue to read the value data, and the connection will jump to the conn_nread state at this time. In the conn_parse_cmd process, if any failure is encountered, it will jump to conn_closing to close the connection.

complete_nread #

For update type protocol commands, continue reading the value data from the conn. After reading the value data, call complete_nread to process and store the data; after the data processing is completed, write the response result to the conn’s wbuf. Then the connection in the update type processing enters the conn_write state.

conn_write #

The conn_write state processing logic is simple, it directly enters the conn_mwrite state. Or when the iovused of the conn is 0, or for UDP protocol, after the response is written to the conn message buffer, it enters the conn_mwrite state.

conn_mwrite #

After entering the conn_mwrite state, the worker thread writes data to the client using transmit. If the write fails, it jumps to conn_closing, closes the connection, and exits the state machine. If the write is successful, it jumps to conn_new_cmd and prepares to retrieve the next new command.

conn_closing #

The last conn_closing state has been mentioned many times before. In the processing of any state, if an exception occurs, it will enter this state, close the connection, and the connection will be game over.

Mc command processing flow #

At this point, the system architecture and state machine of Mc have been fully explained. Now let’s summarize the entire process of Mc’s command processing again, as shown in the figure below, to deepen our understanding of Mc’s state machine and command processing flow.

• After Mc is started, the main thread listens and prepares to accept new connections. When a new connection is accepted, the main thread enters the conn_listening state, accepts the new connection, and schedules it to the worker thread.

• The worker thread listens to the pipe. When it receives a message sent by the main thread through the pipe, the connection in the worker thread enters the conn_new_cmd state, creates the conn structure, performs some initialization and reset operations, then enters the conn_waiting state, registers a read event, and waits for network IO.

• When data arrives, the connection enters the conn_read state and reads network data.

• After successful reading, it enters the conn_parse_cmd state and parses the command according to the Mc protocol.

• For read commands, after obtaining the value result corresponding to the key, it enters the conn_mwrite state.

• For update commands, it enters the conn_nread state and reads the value data. After reading the value, it updates the key. After the update is completed, it enters the conn_write state and writes the result to the buffer. Then, just like read commands, it enters the conn_mwrite state.

• After entering the conn_mwrite state, the result response is sent to the client. After sending the response, it enters the conn_new_cmd state again, resets the connection, and prepares for the next command processing loop.

• In the read, parse, process, and respond process, if any exception occurs, it enters the conn_closing state and closes the connection.

To summarize the content of the last 3 lessons. First, the principles and features of Memcached were explained. Then, based on the system architecture of Memcached, the multi-threaded network model of Mc based on Libevent was learned, and it was understood that the IO main thread is responsible for accepting connections and scheduling, while the worker thread is responsible for reading, processing, and responding to commands. The focus of this lesson is also the Memcached state machine, understanding that the main thread handles conn_listening, and the worker thread handles the other 8 important states. Each state has different processing logic, thereby dividing the entire complex processing process of Mc into stages, with each stage focusing only on a limited logic, ensuring the clarity and simplicity of the entire processing process.

Finally, by summarizing the complete process of Mc command processing, it was learned how Mc establishes a connection, reads, processes, and responds to commands, thereby connecting the system architecture, multi-threaded network model, and state machine processing of Mc.

To facilitate understanding, the mind map of all the knowledge points in this lesson is provided in the figure below.