Patent Description:
Particular embodiments are defined by the subject-matter of the dependent claims. Embodiments which do not fall within the scope of the claims are to be interpreted merely as examples useful for understanding the invention. Object placement strategies in storage systems, e.g. systems implementing content delivery networks (CDNs), can affect performance in storage systems, e.g. for serving objects to clients. Specifically, an object placement strategy should efficiently use storage resources, compute resources, and network resources, while also scaling with varying demand for objects and corresponding varying object diversity within storage systems. In particular, when many clients ask for the same object, load balancing is performed to control access to the object. This load balancing can introduce latency in serving the object to clients. One way to decrease latency introduced by load balancing client access to an object is to replicate the object across storage nodes. Specifically, object replication can facilitate access to the object while decreasing the need to perform load balancing and the corresponding latency associated with performing the load balancing. However, object replication across storage nodes utilizes increased amounts of storage and computational resources within storage systems, thereby limiting storage of other objects across the storage nodes. Accordingly, trade-offs exist between object locality, leading to load balancing for object access and increased latency, and object replication, leading to increased storage and compute resource usage. There therefore exist needs for systems and methods for controlling object replication, and subsequently object access load balancing, through an object placement strategy that balances the trade-offs between object locality and object replication.

Most existing storage systems, e.g. tiered CDNs, use simplified heuristics to control object replication across storage nodes, which can lead to inefficiencies in providing object access. For example, a typically tiered CDN implements an object placement strategy including a first tier of storage nodes that reach CPU and network limits, e.g. network latency limits, and a second tier of storage nodes that reach storage limitations. Controlling object replication through popularity can provide a solution to this problem observed in typical tiered CDN implementations. Specifically, an object placement strategy that relies on object popularity can be used to control object replication in storage systems while balancing the trade-offs between object locality and object replication.

However, using popularity to control object replication is difficult to implement for a number of reasons. In particular, it is hard to accurately measure object popularity to control object replications for a number of reasons. Specifically, popularity of an object can change over time. In turn, this can skew popularity measurements over time and at specific time instances, when the popularity measurement is made based on past popularity measurements. Additionally, object state, e.g. object name, statistics and lookup data-structures, can be used to accurately measure object popularity, e.g. for identifying instances of the object for measuring popularity. Given the extremely large number of objects in storage systems, and corresponding hashing-table space consumption, this state can reach tens of GBs of data that has to be stored, potentially at a significant cost and detriment to performance. Further, popularity distribution is long-tail, which means nodes don't really care about the popularity of most objects, as most objects are not popular and therefore not often requested. However, in order to know if an object is actually popular, e.g. with respect to other objects, the popularity and object states should be measured and maintained for all objects, including unpopular objects, thereby necessitating further resource usage. Additionally, accurately measuring popularity in a centralized server has many disadvantages. Specifically, redundancy is needed in order to provide high availability. Further, communications with a central server adds latency and computational overhead. Additionally, popularity can depend on object locality making it difficult to accurately measure popularity in a centralized server. There therefore exist needs for systems and methods for accurately measuring popularity of objects to control replication of the objects at storage nodes. In particular, there exist needs for systems and methods for controlling object replication and corresponding access load balancing in storage nodes in a distributed manner and on a per-node basis according to popularity of objects at the nodes.

<CIT> is directed to systems, methods, and computer-readable media for load balancing using segment routing and application monitoring. A method can involve receiving a packet including a request from a source device to an application associated with a virtual address in a network, mapping the request to a set of candidate servers hosting the application associated with the virtual address, and encoding the set of candidate servers as a list of segments in a segment routing header associated with the packet. The method can further involve determining that a first candidate server from the set of candidate servers is a next segment in the list of segments, encoding the first candidate server in a destination address field on a header of the packet, and forwarding the packet to the first candidate server.

Various embodiments of the disclosure are discussed in detail below. While specific implementations are discussed, it should be understood that this is done for illustration purposes only. A person skilled in the relevant art will recognize that other components and configurations may be used without parting from the scope of the disclosure. Thus, the following description and drawings are illustrative and are not to be construed as limiting. Numerous specific details are described to provide a thorough understanding of the disclosure. However, in certain instances, well-known or conventional details are not described in order to avoid obscuring the description. References to one or an embodiment in the present disclosure can be references to the same embodiment or any embodiment; and, such references mean at least one of the embodiments.

A method includes receiving, at a dispatcher of a storage system, a request for an object from a client. The method also includes identifying, by the dispatcher of the storage system, candidate storage nodes of the storage system for serving the object to the client by generating an ordered list of the candidate storage nodes using a two-dimensional consistent hashing function. Distribution of the request for the object through one or more candidate storage nodes of the candidate storage nodes for filling the request for the object is facilitated according to the ordered list of candidate storage nodes. Specifically, the one or more candidate storage nodes are configured to facilitate distribution of the request by selectively filling the request for the object to the client using cache admission policies formed based on popularity characteristics of requested objects at the one or more candidate storage nodes.

A system can include one or more processors and at least one computer-readable storage medium storing instructions which, when executed by the one or more processors, cause the one or more processors to receive, at a dispatcher of a storage system, a request for an object from a client. The instructions also cause the one or more processors to identify, by the dispatcher, candidate storage nodes of the storage system for serving the object to the client by generating an ordered list of the candidate storage nodes. Specifically, the instructions cause the one or more processors to generate the ordered list of the candidate storage nodes using a two-dimensional consistent hashing function that depends on both a flow associated with the request for the object and the object itself. Further, the instructions cause the one or more processors to facilitate distribution of the request for the object through one or more candidate storage nodes of the candidate storage nodes according to the ordered list of the candidate storage nodes for filling the request for the object. Specifically, the one or more candidate storage nodes are configured to facilitate the distribution of the request for the object by selectively filling the request for the object to the client using cache admission policies formed based on popularity characteristics of requested objects at the one or more candidate storage nodes.

A non-transitory computer-readable storage medium having stored therein instructions which, when executed by a processor, cause the processor to receive, at a dispatcher of a storage system, a request for an object from a client. The instructions cause the processor to identify, by the dispatcher, candidate storage nodes of the storage system for serving the object to the client by generating an ordered list of the candidate storage nodes. Specifically, the instructions cause the processor to generate the ordered list of the candidate storage nodes using a two-dimensional consistent hashing function. Further, the instructions cause the processor to facilitate distribution of the request for the object through one or more candidate storage nodes of the candidate storage nodes according to the ordered list of the candidate storage nodes for filling the request for the object. Specifically, the dispatcher can facilitate the distribution of the request for the object by transmitting the request for the object to a first candidate storage in the ordered list of the candidate storage nodes. Further, the one or more candidate storage nodes can facilitate the distribution of the request for the object by selectively filling the request for the object to the client using cache admission policies formed based on popularity characteristics of requested objects at the one or more candidate storage nodes.

The disclosed technology addresses the need in the art for controlling object access load-balancing, and corresponding object replication, through a request-driven object placement strategy that balances the trade-offs between object locality and object replication. The present technology involves system, methods, and computer-readable media for controlling object replication at storage nodes based on object popularity. Additionally, the present technology involves systems, methods, and computer-readable media for controlling object replication at storage nodes in a distributed manner and on a per-node basis according to popularity of objects at the nodes.

A description of network environments and architectures for network data access and services, as illustrated in <FIG>, <FIG>, <FIG>, <FIG> is first disclosed herein. A discussion of systems, methods, and computer-readable media for controlling object replication at storage nodes in a distributed manner and on a per-node basis according to popularity of objects at the nodes, as shown in <FIG>, will then follow. The discussion then concludes with a brief description of example devices, as illustrated in <FIG> and <FIG>. These variations shall be described herein as the various embodiments are set forth. The disclosure now turns to <FIG>.

<FIG> illustrates a diagram of an example cloud computing architecture <NUM>. The architecture can include a cloud <NUM>. The cloud <NUM> can include one or more private clouds, public clouds, and/or hybrid clouds. Moreover, the cloud <NUM> can include cloud elements <NUM>-<NUM>. The cloud elements <NUM>-<NUM> can include, for example, servers <NUM>, virtual machines (VMs) <NUM>, one or more software platforms <NUM>, applications or services <NUM>, software containers <NUM>, and infrastructure nodes <NUM>. The infrastructure nodes <NUM> can include various types of nodes, such as compute nodes, storage nodes, network nodes, management systems, etc..

The cloud <NUM> can provide various cloud computing services via the cloud elements <NUM>-<NUM>, such as software as a service (SaaS) (e.g., collaboration services, email services, enterprise resource planning services, content services, communication services, etc.), infrastructure as a service (IaaS) (e.g., security services, networking services, systems management services, etc.), platform as a service (PaaS) (e.g., web services, streaming services, application development services, etc.), and other types of services such as desktop as a service (DaaS), information technology management as a service (ITaaS), managed software as a service (MSaaS), mobile backend as a service (MBaaS), etc..

The client endpoints <NUM> can connect with the cloud <NUM> to obtain one or more specific services from the cloud <NUM>. The client endpoints <NUM> can communicate with elements <NUM>-<NUM> via one or more public networks (e.g., Internet), private networks, and/or hybrid networks (e.g., virtual private network). The client endpoints <NUM> can include any device with networking capabilities, such as a laptop computer, a tablet computer, a server, a desktop computer, a smartphone, a network device (e.g., an access point, a router, a switch, etc.), a smart television, a smart car, a sensor, a GPS device, a game system, a smart wearable object (e.g., smartwatch, etc.), a consumer object (e.g., Internet refrigerator, smart lighting system, etc.), a city or transportation system (e.g., traffic control, toll collection system, etc.), an internet of things (IoT) device, a camera, a network printer, a transportation system (e.g., airplane, train, motorcycle, boat, etc.), or any smart or connected object (e.g., smart home, smart building, smart retail, smart glasses, etc.), and so forth.

<FIG> illustrates a diagram of an example fog computing architecture <NUM>. The fog computing architecture <NUM> can include the cloud layer <NUM>, which includes the cloud <NUM> and any other cloud system or environment, and the fog layer <NUM>, which includes fog nodes <NUM>. The client endpoints <NUM> can communicate with the cloud layer <NUM> and/or the fog layer <NUM>. The architecture <NUM> can include one or more communication links <NUM> between the cloud layer <NUM>, the fog layer <NUM>, and the client endpoints <NUM>. Communications can flow up to the cloud layer <NUM> and/or down to the client endpoints <NUM>.

The fog layer <NUM> or "the fog" provides the computation, storage and networking capabilities of traditional cloud networks, but closer to the endpoints. The fog can thus extend the cloud <NUM> to be closer to the client endpoints <NUM>. The fog nodes <NUM> can be the physical implementation of fog networks. Moreover, the fog nodes <NUM> can provide local or regional services and/or connectivity to the client endpoints <NUM>. As a result, traffic and/or data can be offloaded from the cloud <NUM> to the fog layer <NUM> (e.g., via fog nodes <NUM>). The fog layer <NUM> can thus provide faster services and/or connectivity to the client endpoints <NUM>, with lower latency, as well as other advantages such as security benefits from keeping the data inside the local or regional network(s).

The fog nodes <NUM> can include any networked computing devices, such as servers, switches, routers, controllers, cameras, access points, gateways, etc. Moreover, the fog nodes <NUM> can be deployed anywhere with a network connection, such as a factory floor, a power pole, alongside a railway track, in a vehicle, on an oil rig, in an airport, on an aircraft, in a shopping center, in a hospital, in a park, in a parking garage, in a library, etc..

In some configurations, one or more fog nodes <NUM> can be deployed within fog instances <NUM>, <NUM>. The fog instances <NUM>, <NUM> can be local or regional clouds or networks. For example, the fog instances <NUM>, <NUM> can be a regional cloud or data center, a local area network, a network of fog nodes <NUM>, etc. In some configurations, one or more fog nodes <NUM> can be deployed within a network, or as standalone or individual nodes, for example. Moreover, one or more of the fog nodes <NUM> can be interconnected with each other via links <NUM> in various topologies, including star, ring, mesh or hierarchical arrangements, for example.

In some cases, one or more fog nodes <NUM> can be mobile fog nodes. The mobile fog nodes can move to different geographical locations, logical locations or networks, and/or fog instances while maintaining connectivity with the cloud layer <NUM> and/or the endpoints <NUM>. For example, a particular fog node can be placed in a vehicle, such as an aircraft or train, which can travel from one geographical location and/or logical location to a different geographical location and/or logical location. In this example, the particular fog node may connect to a particular physical and/or logical connection point with the cloud <NUM> while located at the starting location and switch to a different physical and/or logical connection point with the cloud <NUM> while located at the destination location. The particular fog node can thus move within particular clouds and/or fog instances and, therefore, serve endpoints from different locations at different times.

<FIG> illustrates a diagram of an example Network Environment <NUM>, such as a data center. In some cases, the Network Environment <NUM> can include a data center, which can support and/or host the cloud <NUM>. The Network Environment <NUM> can include a Fabric <NUM> which can represent the physical layer or infrastructure (e.g., underlay) of the Network Environment <NUM>. Fabric <NUM> can include Spines <NUM> (e.g., spine routers or switches) and Leafs <NUM> (e.g., leaf routers or switches) which can be interconnected for routing or switching traffic in the Fabric <NUM>. Spines <NUM> can interconnect Leafs <NUM> in the Fabric <NUM>, and Leafs <NUM> can connect the Fabric <NUM> to an overlay or logical portion of the Network Environment <NUM>, which can include application services, servers, virtual machines, containers, endpoints, etc. Thus, network connectivity in the Fabric <NUM> can flow from Spines <NUM> to Leafs <NUM>, and vice versa. The interconnections between Leafs <NUM> and Spines <NUM> can be redundant (e.g., multiple interconnections) to avoid a failure in routing. In some embodiments, Leafs <NUM> and Spines <NUM> can be fully connected, such that any given Leaf is connected to each of the Spines <NUM>, and any given Spine is connected to each of the Leafs <NUM>. Leafs <NUM> can be, for example, top-of-rack ("ToR") switches, aggregation switches, gateways, ingress and/or egress switches, provider edge devices, and/or any other type of routing or switching device.

Leafs <NUM> can be responsible for routing and/or bridging tenant or customer packets and applying network policies or rules. Network policies and rules can be driven by one or more Controllers <NUM>, and/or implemented or enforced by one or more devices, such as Leafs <NUM>. Leafs <NUM> can connect other elements to the Fabric <NUM>. For example, Leafs <NUM> can connect Servers <NUM>, Hypervisors <NUM>, Virtual Machines (VMs) <NUM>, Applications <NUM>, Network Device <NUM>, etc., with Fabric <NUM>. Such elements can reside in one or more logical or virtual layers or networks, such as an overlay network. In some cases, Leafs <NUM> can encapsulate and decapsulate packets to and from such elements (e.g., Servers <NUM>) in order to enable communications throughout Network Environment <NUM> and Fabric <NUM>. Leafs <NUM> can also provide any other devices, services, tenants, or workloads with access to Fabric <NUM>. In some cases, Servers <NUM> connected to Leafs <NUM> can similarly encapsulate and decapsulate packets to and from Leafs <NUM>. For example, Servers <NUM> can include one or more virtual switches or routers or tunnel endpoints for tunneling packets between an overlay or logical layer hosted by, or connected to, Servers <NUM> and an underlay layer represented by Fabric <NUM> and accessed via Leafs <NUM>.

Applications <NUM> can include software applications, services, containers, appliances, functions, service chains, etc. For example, Applications <NUM> can include a firewall, a database, a CDN server, an IDS/IPS, a deep packet inspection service, a message router, a virtual switch, etc. An application from Applications <NUM> can be distributed, chained, or hosted by multiple endpoints (e.g., Servers <NUM>, VMs <NUM>, etc.), or may run or execute entirely from a single endpoint.

VMs <NUM> can be virtual machines hosted by Hypervisors <NUM> or virtual machine managers running on Servers <NUM>. VMs <NUM> can include workloads running on a guest operating system on a respective server. Hypervisors <NUM> can provide a layer of software, firmware, and/or hardware that creates, manages, and/or runs the VMs <NUM>. Hypervisors <NUM> can allow VMs <NUM> to share hardware resources on Servers <NUM>, and the hardware resources on Servers <NUM> to appear as multiple, separate hardware platforms. Moreover, Hypervisors <NUM> on Servers <NUM> can host one or more VMs <NUM>.

In some cases, VMs <NUM> and/or Hypervisors <NUM> can be migrated to other Servers <NUM>. Servers <NUM> can similarly be migrated to other locations in Network Environment <NUM>. For example, a server connected to a specific leaf can be changed to connect to a different or additional leaf. Such configuration or deployment changes can involve modifications to settings, configurations and policies that are applied to the resources being migrated as well as other network components.

In some cases, one or more Servers <NUM>, Hypervisors <NUM>, and/or VMs <NUM> can represent or reside in a tenant or customer space. Tenant space can include workloads, services, applications, devices, networks, and/or resources that are associated with one or more clients or subscribers. Accordingly, traffic in Network Environment <NUM> can be routed based on specific tenant policies, spaces, agreements, configurations, etc. Moreover, addressing can vary between one or more tenants. In some configurations, tenant spaces can be divided into logical segments and/or networks and separated from logical segments and/or networks associated with other tenants. Addressing, policy, security and configuration information between tenants can be managed by Controllers <NUM>, Servers <NUM>, Leafs <NUM>, etc..

Configurations in Network Environment <NUM> can be implemented at a logical level, a hardware level (e.g., physical), and/or both. For example, configurations can be implemented at a logical and/or hardware level based on endpoint or resource attributes, such as endpoint types and/or application groups or profiles, through a software-defined network (SDN) framework (e.g., Application-Centric Infrastructure (ACI) or VMWARE NSX). To illustrate, one or more administrators can define configurations at a logical level (e.g., application or software level) through Controllers <NUM>, which can implement or propagate such configurations through Network Environment <NUM>. In some examples, Controllers <NUM> can be Application Policy Infrastructure Controllers (APICs) in an ACI framework. In other examples, Controllers <NUM> can be one or more management components for associated with other SDN solutions, such as NSX Managers.

Such configurations can define rules, policies, priorities, protocols, attributes, objects, etc., for routing and/or classifying traffic in Network Environment <NUM>. For example, such configurations can define attributes and objects for classifying and processing traffic based on Endpoint Groups (EPGs), Security Groups (SGs), VM types, bridge domains (BDs), virtual routing and forwarding instances (VRFs), tenants, priorities, firewall rules, etc. Other example network objects and configurations are further described below. Traffic policies and rules can be enforced based on tags, attributes, or other characteristics of the traffic, such as protocols associated with the traffic, EPGs associated with the traffic, SGs associated with the traffic, network address information associated with the traffic, etc. Such policies and rules can be enforced by one or more elements in Network Environment <NUM>, such as Leafs <NUM>, Servers <NUM>, Hypervisors <NUM>, Controllers <NUM>, etc. As previously explained, Network Environment <NUM> can be configured according to one or more particular software-defined network (SDN) solutions, such as CISCO ACI or VMWARE NSX. These example SDN solutions are briefly described below.

ACI can provide an application-centric or policy-based solution through scalable distributed enforcement. ACI supports integration of physical and virtual environments under a declarative configuration model for networks, servers, services, security, requirements, etc. For example, the ACI framework implements EPGs, which can include a collection of endpoints or applications that share common configuration requirements, such as security, QoS, services, etc. Endpoints can be virtual/logical or physical devices, such as VMs, containers, hosts, or physical servers that are connected to Network Environment <NUM>. Endpoints can have one or more attributes such as a VM name, guest OS name, a security tag, application profile, etc. Application configurations can be applied between EPGs, instead of endpoints directly, in the form of contracts. Leafs <NUM> can classify incoming traffic into different EPGs. The classification can be based on, for example, a network segment identifier such as a VLAN ID, VXLAN Network Identifier (VNID), NVGRE Virtual Subnet Identifier (VSID), MAC address, IP address, etc..

In some cases, classification in the ACI infrastructure can be implemented by Application Virtual Switches (AVS), which can run on a host, such as a server or switch. For example, an AVS can classify traffic based on specified attributes, and tag packets of different attribute EPGs with different identifiers, such as network segment identifiers (e.g., VLAN ID). Finally, Leafs <NUM> can tie packets with their attribute EPGs based on their identifiers and enforce policies, which can be implemented and/or managed by one or more Controllers <NUM>. Leaf <NUM> can classify to which EPG the traffic from a host belongs and enforce policies accordingly.

Another example SDN solution is based on VMWARE NSX. With VMWARE NSX, hosts can run a distributed firewall (DFW) which can classify and process traffic. Consider a case where three types of VMs, namely, application, database and web VMs, are put into a single layer-<NUM> network segment. Traffic protection can be provided within the network segment based on the VM type. For example, HTTP traffic can be allowed among web VMs, and disallowed between a web VM and an application or database VM. To classify traffic and implement policies, VMWARE NSX can implement security groups, which can be used to group the specific VMs (e.g., web VMs, application VMs, database VMs). DFW rules can be configured to implement policies for the specific security groups. To illustrate, in the context of the previous example, DFW rules can be configured to block HTTP traffic between web, application, and database security groups.

Returning now to <FIG>, Network Environment <NUM> can deploy different hosts via Leafs <NUM>, Servers <NUM>, Hypervisors <NUM>, VMs <NUM>, Applications <NUM>, and Controllers <NUM>, such as VMWARE ESXi hosts, WINDOWS HYPER-V hosts, bare metal physical hosts, etc. Network Environment <NUM> may interoperate with a variety of Hypervisors <NUM>, Servers <NUM> (e.g., physical and/or virtual servers), SDN orchestration platforms, etc. Network Environment <NUM> may implement a declarative model to allow its integration with application design and holistic network policy.

Controllers <NUM> can provide centralized access to fabric information, application configuration, resource configuration, application-level configuration modeling for a software-defined network (SDN) infrastructure, integration with management systems or servers, etc. Controllers <NUM> can form a control plane that interfaces with an application plane via northbound APIs and a data plane via southbound APIs.

As previously noted, Controllers <NUM> can define and manage application-level model(s) for configurations in Network Environment <NUM>. In some cases, application or device configurations can also be managed and/or defined by other components in the network. For example, a hypervisor or virtual appliance, such as a VM or container, can run a server or management tool to manage software and services in Network Environment <NUM>, including configurations and settings for virtual appliances.

As illustrated above, Network Environment <NUM> can include one or more different types of SDN solutions, hosts, etc. For the sake of clarity and explanation purposes, various examples in the disclosure will be described with reference to an ACI framework, and Controllers <NUM> may be interchangeably referenced as controllers, APICs, or APIC controllers. However, it should be noted that the technologies and concepts herein are not limited to ACI solutions and may be implemented in other architectures and scenarios, including other SDN solutions as well as other types of networks which may not deploy an SDN solution.

Further, as referenced herein, the term "hosts" can refer to Servers <NUM> (e.g., physical or logical), Hypervisors <NUM>, VMs <NUM>, containers (e.g., Applications <NUM>), etc., and can run or include any type of server or application solution. Non-limiting examples of "hosts" can include virtual switches or routers, such as distributed virtual switches (DVS), application virtual switches (AVS), vector packet processing (VPP) switches; VCENTER and NSX MANAGERS; bare metal physical hosts; HYPER-V hosts; VMs; DOCKER Containers; etc..

<FIG> illustrates another example of Network Environment <NUM>. In this example, Network Environment <NUM> includes Endpoints <NUM> connected to Leafs <NUM> in Fabric <NUM>. Endpoints <NUM> can be physical and/or logical or virtual entities, such as servers, clients, VMs, hypervisors, software containers, applications, resources, network devices, workloads, etc. For example, an Endpoint <NUM> can be an object that represents a physical device (e.g., server, client, switch, etc.), an application (e.g., web application, database application, etc.), a logical or virtual resource (e.g., a virtual switch, a virtual service appliance, a virtualized network function (VNF), a VM, a service chain, etc.), a container running a software resource (e.g., an application, an appliance, a VNF, a service chain, etc.), storage, a workload or workload engine, etc. Endpoints <NUM> can have an address (e.g., an identity), a location (e.g., host, network segment, virtual routing and forwarding (VRF) instance, domain, etc.), one or more attributes (e.g., name, type, version, patch level, OS name, OS type, etc.), a tag (e.g., security tag), a profile, etc..

Endpoints <NUM> can be associated with respective Logical Groups <NUM>. Logical Groups <NUM> can be logical entities containing endpoints (physical and/or logical or virtual) grouped together according to one or more attributes, such as endpoint type (e.g., VM type, workload type, application type, etc.), one or more requirements (e.g., policy requirements, security requirements, QoS requirements, customer requirements, resource requirements, etc.), a resource name (e.g., VM name, application name, etc.), a profile, platform or operating system (OS) characteristics (e.g., OS type or name including guest and/or host OS, etc.), an associated network or tenant, one or more policies, a tag, etc. For example, a logical group can be an object representing a collection of endpoints grouped together. To illustrate, Logical Group <NUM> can contain client endpoints, Logical Group <NUM> can contain web server endpoints, Logical Group <NUM> can contain application server endpoints, Logical Group N can contain database server endpoints, etc. In some examples, Logical Groups <NUM> are EPGs in an ACI environment and/or other logical groups (e.g., SGs) in another SDN environment.

Traffic to and/or from Endpoints <NUM> can be classified, processed, managed, etc., based Logical Groups <NUM>. For example, Logical Groups <NUM> can be used to classify traffic to or from Endpoints <NUM>, apply policies to traffic to or from Endpoints <NUM>, define relationships between Endpoints <NUM>, define roles of Endpoints <NUM> (e.g., whether an endpoint consumes or provides a service, etc.), apply rules to traffic to or from Endpoints <NUM>, apply filters or access control lists (ACLs) to traffic to or from Endpoints <NUM>, define communication paths for traffic to or from Endpoints <NUM>, enforce requirements associated with Endpoints <NUM>, implement security and other configurations associated with Endpoints <NUM>, etc..

In an ACI environment, Logical Groups <NUM> can be EPGs used to define contracts in the ACI. Contracts can include rules specifying what and how communications between EPGs take place. For example, a contract can define what provides a service, what consumes a service, and what policy objects are related to that consumption relationship. A contract can include a policy that defines the communication path and all related elements of a communication or relationship between endpoints or EPGs. For example, a Web EPG can provide a service that a Client EPG consumes, and that consumption can be subject to a filter (ACL) and a service graph that includes one or more services, such as firewall inspection services and server load balancing.

As discussed previously, object placement strategies in storage systems, e.g. systems implementing CDNs, can affect performance in storage systems, e.g. for serving objects to clients. Specifically, an object placement strategy should efficiently use storage resources, compute resources, and network resources, while also scaling with varying demand for objects and corresponding varying object diversity within storage systems. In particular, when many clients ask for the same object, load balancing is performed to control access to the object. This load balancing can introduce latency in serving the object to clients. One way to decrease latency introduced by load balancing client access to an object is to replicate the object across storage nodes. Specifically, object replication can facilitate access to the object while decreasing the corresponding latency associated with performing the load balancing, e.g. created as a result of load-balancing. However, object replication across storage nodes utilizes increased amounts of storage and computational resources within storage systems, thereby limiting storage of other objects across the storage nodes. Accordingly, trade-offs exist between object locality, leading to load balancing for object access and increased latency, and object replication, leading to increased storage and compute resource usage.

However, using popularity to control object replication is difficult to implement for a number of reasons. In particular, it is hard to accurately measure object popularity to control object replications for a number of reasons. Specifically, popularity of an object can change over time. In turn, this can skew popularity measurements over time and at specific time instances, when the popularity measurement is made based on past popularity measurements. Additionally, object state, e.g. object name, statistics and lookup data-structures, can be used to accurately measure object popularity, e.g. for identifying instances of the object for measuring popularity. Given the extremely large number of objects in storage systems, and corresponding hashing-table space consumption, this state can reach tens of GBs of data that has to be stored, potentially at a significant cost and detriment to performance. Further, popularity distribution is long-tail, which means nodes don't really care about the popularity of most objects, as most objects are not popular and therefore not often requested. However, in order to know if an object is actually popular, e.g. with respect to other objects, the popularity and object states should be measured and maintained for all objects, including unpopular objects, thereby necessitating further resource usage. Additionally, accurately measuring popularity in a centralized server has many disadvantages. Specifically, redundancy is needed in order to provide high availability. Further, communications with a central server adds latency and computational overhead. Additionally, popularity can depend on object locality making it difficult to accurately measure popularity in a centralized server.

The present includes systems, methods, and computer-readable media for controlling object replication based on object popularity. Specifically, a dispatcher of a storage system receives a request for an object from a client. The dispatcher identifies candidate storage nodes of the storage system for serving the object to the client by generating an ordered list of the candidate storage nodes using a two-dimensional consistent hashing function. The two-dimensional consistent hashing function depends on both a flow associated with the request for the object and the object itself. As follows, distribution of the request for the object through one or more candidate storage nodes of the candidate storage nodes is facilitated according to the ordered list of the candidate storage nodes for filing the request for the object. Specifically, the dispatcher can transmit the request for the object to a first candidate storage node in the ordered list of the candidate storage nodes to facilitate the distribution of the request for the object. Further, the one or more candidate storage nodes facilitate the distribution of the request for the object by selectively filling the request for the object to the client using cache admission policies formed based on popularity characteristics of requested objects at the one or more candidate storage nodes.

<FIG> shows an example environment <NUM> for controlling object replication in a storage system based on popularity of requested objects. Specifically, the example environment <NUM> shown in <FIG> can be used to control object replication at storage nodes in a storage system in a distributed manner across the storage nodes. More specifically, the example environment <NUM> shown in <FIG> can be used to control object replication at storage nodes in a storage system on a per-node basis according to object popularity at each of the storage nodes. In controlling object replication based on popularity, the environment <NUM> can effectively control load balancing of access to the object across storage nodes of a storage system. For example, by replicating the object based on popularity across storage nodes, the environment <NUM> can be used to control how many times the object appears in a storage system, and thereby regulate an amount of load balancing used in providing access to the object in the storage system.

The example environment <NUM> shown in <FIG> can be formed, at least in part, through an applicable cloud or fog environment, such as the cloud computing architecture <NUM> shown in <FIG> and the fog computing architecture <NUM> shown in <FIG>. For example, the environment <NUM> can be implemented as part of a CDN implemented in the cloud computing architecture <NUM>. Further in the example, the environment <NUM> can be used to control object replication at storage nodes in the CDN implemented in the cloud computing architecture <NUM>. Further, the environment <NUM> can be formed, at least in part, through an applicable network environment, such as the network environment <NUM> shown in <FIG> and <FIG>. For example, the environment <NUM> can be implemented, at least in part, in a data center formed by the network environment <NUM> shown in <FIG>. Further in the example, the environment <NUM> can be used to control object replication at storage nodes in the data center formed by the network environment <NUM>.

The example environment <NUM> shown in <FIG> includes a client <NUM>, a dispatcher <NUM>, and a server pool <NUM>. The client <NUM> functions to request access for an object and subsequently gain access to the object through the environment <NUM>. A client, as used herein, can include an applicable entity capable of requesting and gaining access to an object. Specifically, a client can include a user, a network service, and an application. For example, a client can include a microservice of a structured application that is configured to request and gain access to an object in executing the structured application.

The dispatcher <NUM> functions to receive a request for an object from the client <NUM>. The dispatcher <NUM> can be implemented as part of the client <NUM>. For example, the dispatcher <NUM> can be implemented through an application executing at the client <NUM>. Alternatively the dispatcher <NUM> can be implemented remote from the client <NUM> and receive the request for the object through a network. For example, the dispatcher <NUM> can be implemented in the cloud computing architecture <NUM> remote from the client <NUM>. Accordingly, the dispatcher <NUM> can receive the request for the object in the cloud computing architecture <NUM> through a network.

The request for the object received from the client <NUM> includes an identifier of the requested object. As will be discussed in greater detail later, the object identifier can be used to select candidate servers for providing the object to the client <NUM>. Further, the request for the object can be included as part of, or otherwise associated, with a data flow for sending data to and receiving data from the client <NUM>. A flow including the request for the object can be associated with a network service that is provisioned to the client <NUM>. For example, a flow can be associated with streaming television content to the client <NUM>, and the request for the object can include a request for a portion of the television content. As will be discussed in greater detail later, a flow of the requested object can be used to select candidate servers for providing the object to the client <NUM>.

The dispatcher <NUM> is included as part of, or otherwise associated with, a storage system. The storage system can be an applicable storage system for storing and serving objects. For example, the storage system can be a CDN. The storage system of the dispatcher <NUM> includes the server pool <NUM>. The server pool <NUM> includes servers S1. While reference is made to servers throughout this description, a server is meant to represent an applicable storage node for storing objects and providing access to the object. Specifically, the servers can represent storage nodes in a datacenter. Additionally, while only nine servers are shown in the server pool <NUM>, in various embodiments, the server pool <NUM> can include more servers or fewer servers.

Using the received request for the object, the dispatcher <NUM> can identify candidate servers of the server pool <NUM> for providing the object to the client <NUM>. A candidate server can include a server that has the requested object stored locally. In turn, the candidate server can provide the object to the client <NUM> from its local storage, e.g. cache. Alternatively, a candidate server can include a server that does not have the requested object stored locally. Subsequently and as will be discussed in greater detail later, the candidate server can determine whether to retrieve the requested object from another location or forward the request to another candidate server. As will be discussed in greater detail later, the candidate server can retrieve the requested object and store the object in local storage at the candidate server. In particular and as will be discussed in greater detail later, the candidate server can use popularity metrics, e.g. popularity characteristics of requested objects at the candidate server, to determine whether to retrieve the requested object from another location. Subsequently, the candidate server can store the requested object locally and provide the object to the client <NUM> from its local storage.

The dispatcher <NUM> can identify the candidate servers of the server pool <NUM> by generating an ordered list of the candidate servers. An ordered list of the candidate servers includes a sequential list of candidate servers through which the object request can be distributed in order to provide the object to the client <NUM>. Specifically, the request for the object can be distributed through the server pool <NUM> according to the ordered list of candidate servers for purposes of ultimately providing the requested object to the client <NUM>. As will be discussed in greater detail later, the dispatcher <NUM> can transmit the object request to a first candidate server in the ordered list of candidate servers. Subsequently and as will be discussed in greater detail later the candidate servers can then sequentially distribute the object request through the candidate servers in the pool of candidate servers based on the ordered list of candidate servers. Specifically, the candidate servers can distribute the object request based on whether the candidate servers agree to provide the object to the client <NUM>. Alternatively, the dispatcher <NUM> can query each of the candidate severs in a distributed fashion to fill the object request. In turn, the object can be replicated based, at least in part, on whether the candidate servers agree to provide the object to the client <NUM>, effectively controlling replication of the object in the server pool <NUM>.

The dispatcher <NUM> generates the ordered list of candidate servers using a two-dimensional consistent hashing function. Example, hashing functions that can be used by the dispatcher <NUM> to generate the ordered list of candidate servers will be discussed in greater detail later. Consistent hashing, as used herein, refers to a technique for distributing flows, e.g. requests for objects corresponding to flows, according to their hashes. In particular, consistent hashing can be used to distribute request for objects/flows, such that the distribution is robust to server-set changes.

As will be discussed in greater detail later with respect to example hashing functions, the dispatcher <NUM> uses a two-dimensional consistent hashing function that is dependent on both the flow associated with the requested object and the object identifier of the requested object to generate the ordered list of candidate servers. Specifically, the dispatcher <NUM> can use flow information of the flow associated with the requested object to apply the two-dimensional consistent hashing function to generate the ordered list of candidate servers. Flow information can include applicable data related to a flow of a requested object. For example, flow information of the requested object can include a <NUM>-tuple of the flow and a client identifier of the client <NUM>.

The dispatcher <NUM> can apply the two-dimensional consistent hashing function based on varying server diversity to generate the ordered list of candidate servers. Server diversity can be defined as a number of candidate servers for serving the object. Server diversity can depend on both an amount of load-balancing within the storage system and an amount of object locality, e.g. the probability of a storage node having a given object in the storage system. For example, the dispatcher <NUM> can select one or more candidate servers using a larger server diversity that weighs load-balancing more than object locality within the storage system, e.g., privileging load balancing over reducing object replication. In another example, the dispatcher <NUM> can select one or more candidate servers using a smaller server diversity that weighs object locality more than load-balancing within the storage system, e.g., achieving lower object replication at the cost of decreased repartition of the ingress load. Accordingly, applying the two-dimensional consistent hashing function with increasing server diversity can increase the number of identified candidate servers as increasing server diversity favors more load-balancing. This concept will be described in further detail later with respect to <FIG>.

Further, as object locality corresponds to the object itself, and load-balancing corresponds to the flow of the object, varying server diversity can cause the hashing function to vary weighing of the object and the flow of the object in application. For example, the dispatcher <NUM> can apply the hashing function with a larger server diversity that favors load-balancing. Subsequently, the hashing function can depend more on the flow of the object rather than the object itself in selecting one or more candidate servers. In another example, the dispatcher <NUM> can apply the hashing function with a smaller sever diversity that favors object locality. Subsequently, the hashing function can depend more on the object itself rather than the flow of the object in selecting one or more candidate server.

<FIG> shows a scenario <NUM> of the dispatcher <NUM> for generating the ordered list of candidate servers using varying server diversity. In the example scenario <NUM> shown in <FIG>, the dispatcher <NUM> can use an applicable hashing function, such as the hashing functions described herein, to generate the ordered list of candidate servers. Specifically, the dispatcher <NUM> uses a two-dimensional consistent hashing function with the request object identification and the flow information of the object flow to identify the ordered list of candidate servers.

Further, the dispatcher <NUM> can apply varying server diversity amounts in the two-dimensional consistent hashing function to different subsets of candidate servers. Specifically, the dispatcher <NUM> can apply ever decreasing server diversity amounts in the two-dimensional consistent hashing function to generate smaller and smaller subsets of candidate servers. Subsequently, the dispatcher <NUM> can randomly or pseudo-randomly select a candidate server in each subset of candidate servers to create the ordered list of candidate servers. In applying ever decreasing server diversity amounts in the two-dimensional consistent hashing function, object locality, e.g., the probability of a candidate server having the request in its storage, is favored more heavily as the size of the subsets of candidate servers decreases. In turn, the final server subset can include one more candidate servers that heavily favor locality of the object, e.g. be identified based on the identification of the object. As locality is heavily favored, the one or more candidate servers in the final subset include a local copy of the requested object. Accordingly, the identified candidate server list will include at least one candidate server, the final candidate server in the list, which has a local copy of the object. This ensures that a copy of the object is available for access by the client <NUM> amongst the candidate servers in the ordered list of candidate servers.

With respect to the example scenario <NUM> shown in <FIG>, the dispatcher <NUM> can apply the hashing function with a large server diversity amount, e.g. a server diversity amount of <NUM>, to generate a first subset of candidate servers <NUM>. The first subset of candidate servers <NUM> includes the first server S1, the second server S2, the third server S3, the fifth server S5, the sixth server S6, the seventh server S7 and the ninth server S9. The fourth server S4 and the eighth server S8 are excluded from the first subset of candidate servers <NUM> through application of the hashing function. As load balancing is favored greater than locality in the larger server diversity amount used to create the first subset of candidate servers <NUM>, some of the candidate servers in the first subset of candidate servers <NUM> might not include a locally stored copy of the object.

The dispatcher <NUM> can then randomly or pseudo-randomly select a server from the first subset of candidate servers <NUM> to function as the first candidate server in the ordered list of candidate servers. Specifically, in the example scenario <NUM> shown in <FIG>, the dispatcher <NUM> selects the third server S3 from the first subset of candidate servers <NUM>. As follows, the dispatcher <NUM> can add an identification of the third server S3 as the first candidate server in the ordered list of candidate servers.

Next, the dispatcher <NUM> decreases the server diversity amount and applies the hashing function to generate a second subset of candidate servers <NUM>. Specifically, the dispatcher <NUM> can apply the hashing function with a decreased server diversity amount, e.g. <NUM>, when compared to the server diversity amount of <NUM> used to generate the first subset of candidate servers <NUM>. The second subset of candidate servers <NUM> includes the second server S2, the fifth server S5, and the seventh server S7. The dispatcher <NUM> can then randomly or pseudo-randomly select a server from the second subset of candidate servers <NUM> to function as the next candidate server in the ordered list of candidate servers. Specifically, in the example scenario <NUM> shown in <FIG>, the dispatcher <NUM> selects the seventh server S7 from the second subset of candidate servers <NUM>. As follows, the dispatcher <NUM> can add an identification of the seventh server S7 as the next candidate server in the ordered list of candidate servers.

This process of decreasing the server diversity amount used in applying the hashing function to ultimately identify a candidate server can be repeated an applicable number of times. Specifically, in the example scenario <NUM>, the dispatcher decreases the server diversity amount and applies the hashing function generate a third subset of candidate servers <NUM>. Specifically, the dispatcher <NUM> can apply the hashing function with a decreased server amount, e.g. <NUM>, when compared to the server diversity amount of <NUM> used to generate the second subset of candidate servers <NUM>. The third subset of candidate servers <NUM> only includes the second server S2. Accordingly, the dispatcher <NUM> can select the second server S2 to function as the next candidate server in the ordered list of candidate servers. As follows, the dispatcher <NUM> can add an identification of the second server S2 as the next candidate server in the ordered list of candidate servers. As discussed previously, since locality is favored as the server diversity is decreased, and as the second server S2 is identified from the hashing function when using the lower server diversity amount, then the second server S2 includes a local copy of the object. Specifically, the second server S2 functions as the last candidate server in the ordered list of candidate servers and also includes a local copy of the object.

The disclosure now turns to a discussion of different hashing functions that can be used by the dispatcher <NUM> to identify the ordered list of candidate servers.

In various embodiments, the dispatcher <NUM> can use a Torus <NUM>-step hashing technique with weights to generate the ordered list of candidate servers. This hashing technique is based on <NUM>-D circular hashing techniques. In a <NUM>-D circular hashing, objects are associated with servers with their closest hash. In the <NUM>-D Torus hashing technique, objects and servers are hashed into points using two different hashing functions for each coordinate. Object and servers can be hashed for each coordinate according to the <NUM>-D Torus hashing technique using a single hashing function and salt. In turn, the dispatcher can select a candidate server that has a hash point closest to an object's hash point. Instead of using a simple distance like Euclidian sqrt( Δ(flow)**<NUM> + Δ (object-id)**<NUM> ) to determine distance between hash points, a weight parameter to Δ (flow): sqrt( α * Δ (flow)**<NUM> + Δ (object-id)**<NUM> ) can be used. Alpha, in this case, is the server diversity. As follows, for α=<NUM>, all requests for a given object go to the same server. When α=infinity, objects are load-balanced between all servers. All other alpha values provide different levels of trade-offs between load-balancing and object locality corresponding to different server diversities. This technique can be generalized to N-Dimensions (with N parameters and N-<NUM> affinity weights). Further, this technique can be generalized to other distances between servers and objects and not be implemented using the closest server and object based on hash points.

In certain embodiments, the dispatcher <NUM> can use a ring hashing technique to generate the ordered list of candidate servers. Specifically, the dispatcher <NUM> can use a ring hashing technique with consistent server subsets to generate the ordered list of candidate servers. In implementing the ring hashing technique, the dispatcher <NUM> can place all or a portion of servers around a circle. For example, servers can be placed pseudo-randomly around a circle, e.g. by assigning a pseudo-random angle to each server. Subsequently, the dispatcher <NUM> can select subsets of servers of diversity d_i by selecting the d_i closest servers to a content identifier hash, e.g. of the request object, on the circle/ring. As follows, the dispatcher <NUM> can use the flow information of the requested object, e.g. <NUM> tuple and a client_id, to select the candidate server with flow-based consistent hashing. The following describes a specific implementation of the ring hashing technique. Specifically, if there are N servers, a list size of L is built, and if α_k is the server diversity parameter for the k_th server in the list, with α _1 = N > α _2 >. > α _L = <NUM>, then the last server is found by: s_L = hash_L mod <NUM>*π. The k-th (k < L) server is found by: s_k = s_L + (hash_k mod <NUM>* π *α_k/N). hash_L is a hash of the object-id, and hash_k (k<L) are different hash functions of the flow-id, and the mod x operator is a shift modulus which returns value between -x/<NUM> and +x/<NUM>.

In another implementation of the ring hashing technique, the α_i servers that are closest to the s_L servers on the ring can be identified, e.g. manually identified. The identified α_i servers that are closest to the s_L servers can then be placed on a newly generated ring. Subsequently, s_k can be directly used to select candidate servers from the α_i servers placed on the newly generated ring.

The ring hashing technique is advantageous when a server is removed from a subset of servers. Specifically, when a server is removed, the content/object stored at that server has to be redistributed. Further, it is desirable to redistribute the content to a server that is closest through the ring hash technique, e.g. closest on the circle to the removed server. However, there is a high probability that the closest server already has the content, thereby eliminating the need to unnecessarily replicate the content stored at the removed server.

In various embodiments, the dispatcher <NUM> can use a <NUM>-step hashing technique with consistent server subsets to generate the ordered list of candidate servers. <FIG> shows a conceptual flow <NUM> of application of the <NUM>-step hashing technique to generate an ordered list of candidate servers.

At the first step of the conceptual flow <NUM>, a first consistent hashing technique is used to map object-IDs to server permutations <NUM>. Such a technique can be derived from Maglev hashing since it relies on server permutations <NUM> to assign buckets to servers. As shown in the conceptual flow <NUM>, instead of having a single server per bucket, a bucket can include a plurality of servers. Specifically, by the very nature of the Maglev technique, k server permutations are permutated. The variable k can be the number of buckets.

At the second step of the conceptual flow <NUM>, the diversity parameter α is used to pick a subset of servers from the permutation. The larger the diversity, the larger the subset of servers. Further, growing subsets can include each other as the diversity parameter is increased. For example, the diversity can be a 'number of servers', going from <NUM> to N.

At the third step of the conceptual flow <NUM>, a second consistent hashing technique is used to map the flow of the object, e.g. based on the flow information, into a selected subset of servers. This second consistent hashing technique can also leverage Maglev hashing. As a result, the ordered list of candidate servers can be generated based on the mapping of the flow of the objet to servers in the selected subset of servers.

Returning back to the example environment <NUM> shown in <FIG>, the dispatcher <NUM> can facilitate distribution of the request for the object through at least a portion of the server pool <NUM>. Specifically, the dispatcher <NUM> can facilitate distribution of the request through at least a portion of the server pool <NUM> after the dispatcher <NUM> identified the ordered list of candidate servers. More specifically, the dispatcher <NUM> can facilitate distribution of the request through at least a portion of the candidate servers using the ordered list of candidate servers. As will be discussed in greater detail later, the request for the object can be distributed through at least a portion of the server pool <NUM> in a sequential fashion according to the ordered list of candidate servers. The request can be distributed using an applicable data forwarding protocol. For example, the request can be distributed through HTTP-proxy, sequential HTTP requests, and network-level traffic steering using an applicable protocol, e.g. Segment Routing Local Block (SRLB0 or Multiprotocol Label Switching (MPLS). In particular, the request can be forwarded using a protocol that allows for candidate servers, as will be discussed in greater detail later, to accept or reject the request based on their local cache admission algorithm.

In facilitating distribution of the request for the object through the server pool <NUM>, the dispatcher <NUM> can send the request to a first candidate server in the ordered list of candidate servers. Specifically, in the example environment <NUM> shown in <FIG>, the dispatcher <NUM> can send the request to the third server S3.

Each candidate server in the server pool <NUM> that receives the request for the object can facilitate distribution of the request for the object by determining whether to accept or reject the request. If a candidate server decides to accept the request, then that candidate server can provide the object to the client <NUM>. Subsequently, the candidate server can refrain from forwarding the request to another candidate server if the candidate server accepts the request. Alternatively, if a candidate server decides to reject the request, then the request can be forwarded to another candidate server in the server pool <NUM>. Specifically, if the candidate server devices to reject the request, then the candidate server can forward the request to a next candidate server in the ordered list of candidate servers. This process can repeat itself until a candidate server in the ordered list of candidate servers accepts the request. In various embodiments, as the last candidate server in the ordered list of candidate servers was selected with heavy weighting of object locality, the last candidate server has the object stored locally. As a result, the last candidate server can fill the request for the object, thereby ensuring that the client <NUM> is able to access the object.

The candidate servers in the server pool <NUM> can determine whether to accept the request based on popularity characteristics of requested objects at the candidate servers. In particular, the candidate servers in the server pool <NUM> can determine whether to accept the request for the object based on popularity characteristics of the requested object at the candidate servers. Popularity characteristics include applicable characteristics related to requesting of an object at the candidate servers. For example, popularity characteristics of requested objects can include a number of times requests for the object are received at the candidate servers, e.g. each of the candidate storage nodes, whether the requests are accepted at the candidate servers, and whether the requests are rejected at the candidate servers. The popularity characteristics can be maintained on a per-node basis and the subsequent decision whether to accept the request for the object can be performed on a per-node basis. For example, a candidate server can determine whether to accept the request for the object based on the number of times the object has been requested at the specific candidate server. Therefore, the decision whether to accept the request for the object can be performed in a distributed fashion across the servers. As will be discussed in greater detail later, replication of the object across the candidate servers in the server pool <NUM> can therefore by controlled in a distributed fashion across the servers.

The candidate servers in the server pool <NUM> can use their local cache admission policies to determine whether to accept the request for the object. A local cache admission policy can include a list of the top most request objects, e.g. at a candidate server. Further, a local cache admission policy can include an applicable policy for controlling cache access to and cache storage of a requested object based on popularity characteristics of objects, including the requested object. Specifically, the cache admission policy can include an applicable policy that allows for caching of popular objects, e.g. based on object requests, at the candidate servers while refraining from caching unpopular objects. For example, the local cache admission policy can be implemented through a least frequently used (LFU) caching technique, 2Q cache replacement policy, LRU-K page replacement technique, and a least recently/frequently used (LRFU) caching technique.

The candidate servers in the server pool <NUM> can maintain local cache admission policies on a per-node basis. Specifically, the candidate servers in the server pool <NUM> can maintain local cache admission policies based on requests for objects received at the candidate servers and potentially based on whether the candidate servers accept the requests. For example, a candidate server can receive one hundred requests for a specific object. Subsequently, the candidate server can update its local cache admission policy to allow for caching of the requested object based on receipt of the one hundred requests. In various embodiments, a candidate server in the server pool <NUM> can maintain a local cache admission policy based on all requests for objects received at the candidate server.

If a candidate server in the server pool <NUM> accepts the request for the object then it can facilitate client access to the object, e.g. provide the object to the client <NUM>. In providing access to the object, the candidate server can determine whether the object is stored locally at the candidate server, e.g. in cache. If the candidate server determines that the object is stored locally, then the candidate server can provide the object to the client <NUM> from the local storage.

Alternatively, if the candidate server accepts the request for the object and determines that the object is not stored locally at the candidate server, then the candidate server can retrieve the object from a location in the storage system. Subsequently, the candidate server can copy the object into local storage at the candidate server. For example, the candidate server can retrieve the object from an applicable location, e.g. the last candidate server in the ordered list of candidate servers, and copy the object into local storage at the candidate server. In retrieving the object and copying the object into local storage at the candidate server, the candidate server can effectively replicate the object in the storage system. As the decision whether to accept the request for the object, and subsequently retrieve and copy the object, is made by the candidate server on per-node basis, object replication can be controlled in a distribute manner on a per-node basis. This can solve the previously described deficiencies of controlling object replication in storage systems in a centralized manner.

With respect to the example environment <NUM> shown in <FIG>, as described previously, the third server S3 can receive the request for the object from the dispatcher <NUM>. Specifically, as the third server S3 is the first candidate server in the ordered list of candidate servers, the third server S3 can receive the request for the object from the dispatcher <NUM>. In turn, the third server S3 can determine to reject the request for the object. Specifically, the third server S3 can determine to reject the request for the object based on a local cache admission policy of the third server S3 that is maintained based on requests for object received at the third server S3. Subsequently, the third server S3 can forward the request for the object to the next candidate server in the ordered list of candidate servers, which is the seventh server S7.

The seventh server S7 can receive the request for the object and determine whether to accept the request. Specifically, the seventh server S7 can use a local cache admission policy to determine whether to accept the request based on popularity. In the example environment <NUM> shown in <FIG>, the seventh server S7 accepts the request. Subsequently, the seventh server S7 can determine whether it has the object in local storage. If the object is already stored locally at the seventh server S7, then the seventh server S7 can provide the object to the client <NUM>. Alternatively, if the object is absent from local storage at the seventh server S7, then the seventh server S7 can retrieve the object and copy it into local storage, effectively replicating the object. Subsequently, the seventh server S7 can provide the object to the client <NUM>.

<FIG> illustrates a flowchart for an example method of controlling object replication based on popularity. The method shown in <FIG> is provided by way of example, as there are a variety of ways to carry out the method. Additionally, while the example method is illustrated with a particular order of steps, those of ordinary skill in the art will appreciate that <FIG> and the modules shown therein can be executed in any order and can include fewer or more modules than illustrated. Each module shown in <FIG> represents one or more steps, processes, methods or routines in the method.

At step <NUM>, the dispatcher <NUM> receives a request for an object from the client <NUM>. The dispatcher <NUM> can be implemented as part of the client <NUM>. Alternatively, the dispatcher <NUM> can be implemented remote from the client <NUM>, e.g. as a caching server.

At step <NUM>, the dispatcher <NUM> identifies candidate storage nodes of the storage system for serving the object to the client. Specifically, the dispatcher <NUM> can identify the candidate storage nodes by generating an ordered list of the candidate storage nodes using a two-dimensional consistent hashing function. More specifically, the dispatcher <NUM> can vary storage node diversity as input to the two-dimensional consistent hashing function in order to generate the ordered list of the candidate storage nodes.

At step <NUM>, distribution of the request through one or more candidate storage nodes is facilitated according to the ordered list of candidate storage nodes in order to fill the request for the object based on popularity characteristics of the requested object. Specifically, the dispatcher <NUM> can transmit the request for the object to a first candidate storage node in the list of the candidate storage nodes. Subsequently, the candidate storage nodes, including the first candidate storage node, can transmit the request sequentially according to the ordered list of candidate storage nodes based on whether the candidate storage nodes accept the request. Further, one of the candidate storage nodes, once accepting the request, can copy the object into local storage if the object is absent from local storage, effectively replicating the object within the storage system. Accordingly replication of the object in the storage system can be controlled in a distributed manner across the storage nodes and on a per-node basis.

The disclosure now turns to <FIG> and <FIG>, which illustrate example network devices and computing devices, such as switches, routers, load balancers, client devices, and so forth.

<FIG> illustrates a computing system architecture <NUM> wherein the components of the system are in electrical communication with each other using a connection <NUM>, such as a bus. Exemplary system <NUM> includes a processing unit (CPU or processor) <NUM> and a system connection <NUM> that couples various system components including the system memory <NUM>, such as read only memory (ROM) <NUM> and random access memory (RAM) <NUM>, to the processor <NUM>. The system <NUM> can include a cache <NUM> of high-speed memory connected directly with, in close proximity to, or integrated as part of the processor <NUM>. The system <NUM> can copy data from the memory <NUM> and/or the storage device <NUM> to the cache <NUM> for quick access by the processor <NUM>. In this way, the cache <NUM> can provide a performance boost that avoids processor <NUM> delays while waiting for data. These and other modules can control or be configured to control the processor <NUM> to perform various actions. Other system memory <NUM> may be available for use as well. The memory <NUM> can include multiple different types of memory with different performance characteristics. The processor <NUM> can include any general purpose processor and a hardware or software service, such as service <NUM><NUM>, service <NUM><NUM>, and service <NUM><NUM> stored in storage device <NUM>, configured to control the processor <NUM> as well as a special-purpose processor where software instructions are incorporated into the actual processor design. The processor <NUM> may be a completely self-contained computing system, containing multiple cores or processors, a bus, memory controller, cache, etc. A multi-core processor may be symmetric or asymmetric.

To enable user interaction with the computing device <NUM>, an input device <NUM> can represent any number of input mechanisms, such as a microphone for speech, a touch-sensitive screen for gesture or graphical input, keyboard, mouse, motion input, speech and so forth. An output device <NUM> can also be one or more of a number of output mechanisms known to those of skill in the art. In some instances, multimodal systems can enable a user to provide multiple types of input to communicate with the computing device <NUM>. The communications interface <NUM> can generally govern and manage the user input and system output. There is no restriction on operating on any particular hardware arrangement and therefore the basic features here may easily be substituted for improved hardware or firmware arrangements as they are developed.

The storage device <NUM> can include services <NUM>, <NUM>, <NUM> for controlling the processor <NUM>. Other hardware or software modules are contemplated. The storage device <NUM> can be connected to the system connection <NUM>. In one aspect, a hardware module that performs a particular function can include the software component stored in a computer-readable medium in connection with the necessary hardware components, such as the processor <NUM>, connection <NUM>, output device <NUM>, and so forth, to carry out the function.

<FIG> illustrates an example network device <NUM> suitable for performing switching, routing, load balancing, and other networking operations. Network device <NUM> includes a central processing unit (CPU) <NUM>, interfaces <NUM>, and a bus <NUM> (e.g., a PCI bus). When acting under the control of appropriate software or firmware, the CPU <NUM> is responsible for executing packet management, error detection, and/or routing functions. The CPU <NUM> preferably accomplishes all these functions under the control of software including an operating system and any appropriate applications software. CPU <NUM> may include one or more processors <NUM>, such as a processor from the INTEL X86 family of microprocessors. In some cases, processor <NUM> can be specially designed hardware for controlling the operations of network device <NUM>. In some cases, a memory <NUM> (e.g., non-volatile RAM, ROM, etc.) also forms part of CPU <NUM>. However, there are many different ways in which memory could be coupled to the system.

The interfaces <NUM> are typically provided as modular interface cards (sometimes referred to as "line cards"). Generally, they control the sending and receiving of data packets over the network and sometimes support other peripherals used with the network device <NUM>. Among the interfaces that may be provided are Ethernet interfaces, frame relay interfaces, cable interfaces, DSL interfaces, token ring interfaces, and the like. In addition, various very high-speed interfaces may be provided such as fast token ring interfaces, wireless interfaces, Ethernet interfaces, Gigabit Ethernet interfaces, ATM interfaces, HSSI interfaces, POS interfaces, FDDI interfaces, WIFI interfaces, <NUM>/<NUM>/<NUM> cellular interfaces, CAN BUS, LoRA, and the like. Generally, these interfaces may include ports appropriate for communication with the appropriate media. In some cases, they may also include an independent processor and, in some instances, volatile RAM. The independent processors may control such communications intensive tasks as packet switching, media control, signal processing, crypto processing, and management. By providing separate processors for the communications intensive tasks, these interfaces allow the master CPU <NUM> to efficiently perform routing computations, network diagnostics, security functions, etc..

Although the system shown in <FIG> is one specific network device of the present technology, it is by no means the only network device architecture on which the present technology can be implemented. For example, an architecture having a single processor that handles communications as well as routing computations, etc., is often used. Further, other types of interfaces and media could also be used with the network device <NUM>.

The network device <NUM> can also include an application-specific integrated circuit (ASIC), which can be configured to perform routing and/or switching operations. The ASIC can communicate with other components in the network device <NUM> via the bus <NUM>, to exchange data and signals and coordinate various types of operations by the network device <NUM>, such as routing, switching, and/or data storage operations, for example.

In some embodiments the computer-readable storage devices, media, and memories can include a cable or wireless signal containing a bit stream and the like.

Claim 1:
A method comprising:
receiving, at a dispatcher of a storage system, a request for an object from a client;
identifying, by the dispatcher, candidate storage nodes of the storage system for serving the object to the client by generating an ordered list of the candidate storage nodes using a two-dimensional consistent hashing function that depends on both a flow associated with the request for the object and the object itself; and
facilitating distribution of the request for the object through one or more candidate storage nodes of the candidate storage nodes according to the ordered list of the candidate storage nodes for filling the request for the object, wherein the one or more candidate storage nodes are configured to facilitate the distribution of the request for the object by selectively filling the request for the object to the client using cache admission policies formed based on popularity characteristics of requested objects at the one or more candidate storage nodes, wherein the one or more candidate storage nodes are configured to selectively fill the request for the object by:
determining, at a candidate storage node of the one or more candidate storage nodes, whether to accept the request for the object using a cache admission policy of the candidate storage node formed based on popularity characteristics of the requested objects, including popularity characteristics of the requested object, at the candidate storage node;
identifying whether the object is in local storage at the candidate storage node in response to accepting the request for the object at the candidate storage node; and
serving the object to the client from the local storage at the candidate storage node if it is identified that the object is in the local storage.