Implementing availability domain aware replication policies

Inventors

MAHMOOD, Mohammad • LIAO, Roger Sean

Assignees

Vista IP Law Group LLP • Nutanix Inc

Abstract

Systems for distributed data storage. A method commences upon accessing a set of data items that describe computing nodes to be organized into a ring topology. The ring topology and distributed data storage policies are characterized by quantitative failure-resilient characteristics such as a replication factor. Various characteristics of the topology serve to bound two or more availability domains of the ring into which the computing nodes can be mapped. A set of quantitative values pertaining to respective quantitative failure-resilient characteristics are used for enumerating candidate ring topologies where the computing nodes are mapped into the availability domains. Using the quantitative failure-resilient characteristics, alternative candidate ring topologies are evaluated so as to determine a configuration score for candidate ring topologies. A candidate ring topology is configured based on a computed configuration score surpassing a threshold score. When a failure event is detected, the ring is reevaluated, remapped, and considered for reconfiguration.

Core Innovation

The invention provides availability-domain aware replication in a distributed storage system using a ring topology mapped across multiple availability domains. Virtual machines operate on computing nodes and manage both addition of computing nodes into a ring and replication of data using the computing nodes in the ring.

In the ring, a first virtual machine in a first availability domain causes storage of a first portion of replicas of data, and a second virtual machine in a second availability domain causes storage of a second portion of replicas of data. The replication configuration is selected by computing quantitative failure-resilient properties for candidate ring topologies and evaluating those candidates.

The approach uses a replication factor RF, a configuration score CS, and a configuration score threshold CST to select a configuration that exceeds the threshold. A replication configurator uses neighboring configurations and configuration metrics to reduce computation and to minimize ring node position changes.

The metrics include a node score based on minimum ring distance within a same availability domain and a maximum consecutive node score, and the patent describes heuristic and informed search techniques, including A* and related approaches, that transition between configurations using a heuristic function and a transition score to identify candidate ring topologies mapped across availability domains.

Claims Coverage

The independent claims (three total) cover virtual machines in a virtualization system that replicate data in a distributed storage system by managing ring membership and replica placement across availability domains, with ring membership managed by addition into the ring and storage of replica portions by virtual machines assigned to different availability domains.

Across the independent claim set, the core claim coverage is the same: virtual machines manage both adding computing nodes into a ring and replicating data using the ring, with replica portions stored by virtual machines located in different availability domains. Dependent claims further refine ring composition, including additional replica portions and ring updates triggered by replacement of failed virtual machines or by topology or configuration changes, and may specify availability domain assignment using an availability domain identifier.

Stated Advantages

Documented Applications

No documented applications found