Browse Prior Art Database

Method for Minimizing Liveness Message Flooding in Replicated and Distributed Data Stores

IP.com Disclosure Number: IPCOM000243002D
Publication Date: 2015-Sep-08
Document File: 4 page(s) / 52K

Publishing Venue

The IP.com Prior Art Database

Abstract

Data store systems are often composed of a cluster of machines employing replication to provide high availability and durability of the data. Although cluster members are connected and can directly communicate with each other, it is common practice to shield the client from knowing cluster membership using a front-end server. A common recurring pattern in distributed data storage systems is storing client data whose lifetime is governed by the presence and reachability of the client (e.g., client session state shared by multiple back-end servers, access leases delegated by a server to a client, etc.). In such systems, clients periodically and frequently report their liveness back to a server in order to maintain and renew the data asoociated with them. We present a design that minimizes such renewal message traversal between cluster members, in an environment where clients are unable to connect directly to cluster members, and an arbitrary target selection policy is made by the front end server relaying the clients? requests to the cluster.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 24% of the total text.

Page 01 of 4

Method for Minimizing Liveness Message Flooding in Replicated and Distributed Data Stores

Method for Minimizing Liveness Message Flooding in Replicated and Distributed Data Stores


1. Background and Prior Art

Data store systems are often composed of a cluster of machines employing replication to provide high availability and durability of the data. Although cluster members are connected and can directly communicate with each other, it is common practice to shield the client from knowing cluster membership using a front-end server. Specifically, in cloud and Web based systems, clients communicate with the front end service over HTTP, a request-response based protocol (i.e., each request-response pair is independent, and no notion of state or session is presumed). The front-end server is free to select any cluster member (also known as a back-end server) as the target for the request and any back-end server can provide a response.

The design of such systems makes different tradeoffs in the context of the CAP theorem (Consistency: all members see the same data at the same time; Availability: guaranteeing that requests can complete despite various failure conditions; and Partition tolerance: system continues to operate despite arbitrary message loss or failure of part of the system). The subject of this invention disclosure is Eventually Consistent Systems, a weaker consistency model where updates can be unsynchronized and, if no update happens for some time, all replicas converge to a correct common state. This is unlike strongly consistent systems, where all updates are synchronized by a consensus protocol, such as Paxos.

A common recurring pattern in distributed data storage systems is storing client data whose lifetime is governed by the presence and reachability of the client (e.g., client session state shared by multiple back-end servers, access leases delegated by a server to a client, etc.). The pattern is exemplified by the following steps:

§ Establishing state: a client requests the data store to save some state on its behalf. The state has an associated expiration time, after which it is automatically removed from the data storage system

§ Renewing state: the client periodically informs the data storage system of its liveness (i.e., a heartbeat), thereby extending the expiration time associated with its previously saved state.

§ Cancelling state: eventually the client explicitly informs the data storage system that its saved state is no longer needed and can be safely deleted.

State establishment and cancellation occur only once, whereas renewal messages are numerous and sent by the client as long as it requires the saved state to remain valid. Selecting the expiration duration (or TTL - Time To Live) is a tradeoff between message frequency and freshness. Shorter TTL require more frequent renewals but allow stale data to be removed more quickly. Since data validity is important, it is vital to minimize the overhead of ke...