NON-BLOCKING AND EVENTUALLY CONSISTENT HASHING

Smart overview of the Invention

The patent application describes a method to maintain uninterrupted services in distributed systems using a technique called non-blocking and eventually consistent hashing. This approach addresses the challenges of consistent hashing, particularly when adding or removing nodes in a consistent hash ring (CHR). The technique involves creating a duplicate of the existing CHR to form a new version, allowing both versions to coexist during the transition. This ensures that computing resources on the nodes can continue to service client requests without interruption, even as data migration and version upgrades occur.

Background

Consistent hashing is crucial for stability and scalability in distributed systems, but it has limitations, especially during node changes. Traditional methods require pausing request processing to update hash tables, which can disrupt service. The proposed technique overcomes this by enabling seamless transitions between CHR versions, thus eliminating the need for service interruptions during updates. This innovation is particularly beneficial in environments with a large number of servers where downtime can significantly impact operations.

Implementation

The method involves creating two versions of CHRs, an old and a new version, during node changes. Data and compute resources are migrated from the old version (v1-ring) to the new version (v2-ring) while maintaining service continuity. Various protocols facilitate this process, including a CR-CR message-passing protocol for data migration and a client-server ring-version update protocol for version synchronization. These protocols ensure that client requests are handled efficiently, regardless of the version they interact with.

Protocols and Communication

The disclosed techniques include several protocols to manage the transition between CHR versions. The CR-CR message-passing protocol allows communication between servers associated with different CHR versions to facilitate data migration. The client-server ring-version update protocol enables clients and servers with different versions to upgrade to a higher version seamlessly. A data-checking protocol ensures that client requests are fulfilled accurately during the migration process. These protocols collectively support the system's ability to handle complex scenarios gracefully, ensuring eventual consistency.

Benefits and Applications

The described techniques offer significant advantages, such as improved system performance and enhanced customer service by preventing service disruptions. Each server performs version upgrades and data migrations independently, allowing for flexible and efficient transitions. This approach allows the entire servicing system to manage different transition states effectively, ensuring that client requests are consistently met. The application of these techniques can be beneficial in cloud computing environments, where maintaining high availability and performance is critical.