"How is memory managed in Python? Memory management in python is managed by Python private heap space. All Python objects and data structures are located in a private heap. The programmer does not have access to this private heap. The python interpreter takes care of this instead. The allocation of heap space for Python objects is done by Python’s memory manager. The core API gives access to some tools for the programmer to code. Python also has an inbuilt garbage collector, which recycles all the unused memory and so that it can be made available to the heap space. "

"What is Web Scraping? How do you achieve it in Python? Web Scrapping is a way of extracting the large amounts of information which is available on the web sites and saving it onto the local machine or onto the database tables. To scrap the web: load the web page which is interesting to you. To load the web page, use “requests” module. parse HTML from the web page to find the interesting information. Python has few modules for scraping the web. They are urllib2, scrapy, pyquery, BeautifulSoap, etc. "

"What is Dogpile effect? Dogpile effect is referred to the event when cache expires, and websites are hit by the multiple requests made by the client at the same time.------ How can you prevent Dogpile effect? This effect can be prevented by using semaphore lock. In this system when value expires, first process acquires the lock and starts generating new value."

"Directed acyclic graph (DAG) model Transcoding a video is computationally expensive and time-consuming. Besides, different content creators may have different video processing requirements. For instance, some content creators require watermarks on top of their videos, some provide thumbnail images themselves, and some upload high-definition videos, whereas others do not. To support different video processing pipelines and maintain high parallelism, it is important to add some level of abstraction and let client programmers define what tasks to execute. For example, Facebook’s streaming video engine uses a directed acyclic graph (DAG) programming model, which defines tasks in stages so they can be executed sequentially or parallelly.--------Here are some of the tasks that can be applied on a video file:-- • Inspection: Make sure videos have good quality and are not malformed.-- • Video encodings: Videos are converted to support different resolutions, codec, bitrates, etc.-- • Thumbnail. Thumbnails can either be uploaded by a user or automatically generated by the system.-- • Watermark: An image overlay on top of your video contains identifying information about your video."

"Video streaming flow Whenever you watch a video on YouTube, it usually starts streaming immediately and you do not wait until the whole video is downloaded. Downloading means the whole video is copied to your device, while streaming means your device continuously receives video streams from remote source videos. When you watch streaming videos, your client loads a little bit of data at a time so you can watch videos immediately and continuously. Before we discuss video streaming flow, let us look at an important concept: streaming protocol. This is a standardized way to control data transfer for video streaming. Popular streaming protocols are:------ • MPEG–DASH. MPEG stands for “Moving Picture Experts Group” and DASH stands for "Dynamic Adaptive Streaming over HTTP". • Apple HLS. HLS stands for “HTTP Live Streaming”. • Microsoft Smooth Streaming. • Adobe HTTP Dynamic Streaming (HDS)"

"Multi-master replication----This approach uses the databases’ auto_increment feature. Instead of increasing the next ID by 1, we increase it by k, where k is the number of database servers in use.This solves some scalability issues because IDs can scale with the number of database servers. However, this strategy has some major drawbacks: • Hard to scale with multiple data centers • IDs do not go up with time across multiple servers. • It does not scale well when a server is added or removed." ----"• Clock synchronization. In our design, we assume ID generation servers have the same clock. This assumption might not be true when a server is running on multiple cores. The same challenge exists in multi-machine scenarios. Solutions to clock synchronization are out of the scope of this book; however, it is important to understand the problem exists. Network Time Protocol is the most popular solution to this problem. For interested readers, refer to the reference material."-----"• Section length tuning. For example, fewer sequence numbers but more timestamp bits are effective for low concurrency and long-term applications. • High availability. Since an ID generator is a mission-critical system, it must be highly available."

"Twitter’s unique ID generation system called “snowflake” is inspiring and can satisfy our requirements.--• Sign bit: 1 bit. It will always be 0. This is reserved for future uses. It can potentially be used to distinguish between signed and unsigned numbers. • Timestamp: 41 bits. Milliseconds since the epoch or custom epoch. We use Twitter snowflake default epoch 1288834974657, equivalent to Nov 04, 2010, 01:42:54 UTC. • Datacenter ID: 5 bits, which gives us 2 ^ 5 = 32 datacenters. • Machine ID: 5 bits, which gives us 2 ^ 5 = 32 machines per datacenter. • Sequence number: 12 bits. For every ID generated on that machine/process, the sequence number is incremented by 1. The number is reset to 0 every millisecond. "

"The idea is to use a centralized auto_increment feature in a single database server (Ticket Server). Pros: • Numeric IDs. • It is easy to implement, and it works for small to medium-scale applications. Cons: Single point of failure. Single ticket server means if the ticket server goes down, all systems that depend on it will face issues. To avoid a single point of failure, we can set up multiple ticket servers. However, this will introduce new challenges such as data synchronization."

"UUID ----UUID is a 128-bit number used to identify information in computer systems. UUID has a very low probability of getting collusion. Quoted from Wikipedia, “after generating 1 billion UUIDs every second for approximately 100 years would the probability of creating a single duplicate reach 50%”.---In this design, each web server contains an ID generator, and a web server is responsible for generating IDs independently. Pros: • Generating UUID is simple. No coordination between servers is needed so there will not be any synchronization issues. • The system is easy to scale because each web server is responsible for generating IDs they consume. ID generator can easily scale with web servers. Cons: • IDs are 128 bits long, but our requirement is 64 bits. • IDs do not go up with time. • IDs could be non-numeric."

"Hinted handoff is used to handle temporary failures. What if a replica is permanently unavailable? To handle such a situation, we implement an anti-entropy protocol to keep replicas in sync. Anti-entropy involves comparing each piece of data on replicas and updating each replica to the newest version. A Merkle tree is used for inconsistency detection and minimizing the amount of data transferred. “A hash tree or Merkle tree is a tree in which every non-leaf node is labeled with the hash of the labels or values (in case of leaves) of its child nodes. Hash trees allow efficient and secure verification of the contents of large data structures”. Using Merkle trees, the amount of data needed to be synchronized is proportional to the differences between the two replicas, and not the amount of data they contain. In real-world systems, the bucket size is quite big. For instance, a possible configuration is one million buckets per one billion keys, so each bucket only contains 1000 keys."

"In a distributed system, it is insufficient to believe that a server is down because another server says so. Usually, it requires at least two independent sources of information to mark a server down. All-to-all multicasting is a straightforward solution. However, this is inefficient when many servers are in the system. A better solution is to use decentralized failure detection methods like gossip protocol. Gossip protocol works as follows: • Each node maintains a node membership list, which contains member IDs and heartbeat counters. • Each node periodically increments its heartbeat counter. • Each node periodically sends heartbeats to a set of random nodes, which in turn propagate to another set of nodes. • Once nodes receive heartbeats, membership list is updated to the latest info. • If the heartbeat has not increased for more than predefined periods, the member is considered as offline."

"Replication gives high availability but causes inconsistencies among replicas. Versioning and vector locks are used to solve inconsistency problems. Versioning means treating each data modification as a new immutable version of data. -----A vector clock is a [server, version] pair associated with a data item. It can be used to check if one version precedes, succeeds, or in conflict with others. Assume a vector clock is represented by D([S1, v1], [S2, v2], …, [Sn, vn]), where D is a data item, v1 is a version counter, and s1 is a server number, etc. If data item D is written to server Si, the system must perform one of the following tasks. • Increment vi if [Si, vi] exists.----- • Otherwise, create a new entry [Si, 1]."

"Consistent hashing is widely used in real-world systems, including some notable ones: • Partitioning component of Amazon’s Dynamo database- • Data partitioning across the cluster in Apache Cassandra - • Discord chat application - • Akamai content delivery network - • Maglev network load balancer -"

"Rate limiter headers How does a client know whether it is being throttled? And how does a client know the number of allowed remaining requests before being throttled? The answer lies in HTTP response headers. The rate limiter returns the following HTTP headers to clients: X-Ratelimit-Remaining: The remaining number of allowed requests within the window. X-Ratelimit-Limit: It indicates how many calls the client can make per time window. X-Ratelimit-Retry-After: The number of seconds to wait until you can make a request again without being throttled. When a user has sent too many requests, a 429 too many requests error and X-Ratelimit- Retry-After header are returned to the client."

"The sliding window counter algorithm is a hybrid approach that combines the fixed window counter and sliding window log. The algorithm can be implemented by two different approaches. Assume the rate limiter allows a maximum of 7 requests per minute, and there are 5 requests in the previous minute and 3 in the current minute. For a new request that arrives at a 30% position in the current minute, the number of requests in the rolling window is calculated using the following formula:--- • Requests in current window + requests in the previous window * overlap percentage of the rolling window and previous window.Using this formula, we get 3 + 5 * 0.7% = 6.5 request. Depending on the use case, the number can either be rounded up or down. In our example, it is rounded down to 6. Since the rate limiter allows a maximum of 7 requests per minute, the current request can go through. However, the limit will be reached after receiving one more request.---------Pros • It smooths out spikes in traffic because the rate is based on the average rate of the previous window. • Memory efficient. Cons • It only works for not-so-strict look back window. It is an approximation of the actual rate because it assumes requests in the previous window are evenly distributed. However, this problem may not be as bad as it seems. According to experiments done by Cloudflare , only 0.003% of requests are wrongly allowed or rate limited among 400 million requests."

"the fixed window counter algorithm has a major issue: it allows more requests to go through at the edges of a window. The sliding window log algorithm fixes the issue. It works as follows: • The algorithm keeps track of request timestamps. Timestamp data is usually kept in cache, such as sorted sets of Redis. • When a new request comes in, remove all the outdated timestamps. Outdated timestamps are defined as those older than the start of the current time window. • Add timestamp of the new request to the log. • If the log size is the same or lower than the allowed count, a request is accepted. Otherwise, it is rejected. ----Pros: • Rate limiting implemented by this algorithm is very accurate. In any rolling window, requests will not exceed the rate limit. Cons: • The algorithm consumes a lot of memory because even if a request is rejected, its timestamp might still be stored in memory."

"Fixed window counter algorithm works as follows: • The algorithm divides the timeline into fix-sized time windows and assign a counter for each window. • Each request increments the counter by one. • Once the counter reaches the pre-defined threshold, new requests are dropped until a new time window starts. Pros: • Memory efficient. • Easy to understand. • Resetting available quota at the end of a unit time window fits certain use cases. Cons: • Spike in traffic at the edges of a window could cause more requests than the allowed quota to go through."

"The leaking bucket algorithm is similar to the token bucket except that requests are processed at a fixed rate. It is usually implemented with a first-in-first-out (FIFO) queue. The algorithm works as follows: • When a request arrives, the system checks if the queue is full. If it is not full, the request is added to the queue. • Otherwise, the request is dropped. • Requests are pulled from the queue and processed at regular intervals. -----------Leaking bucket algorithm takes the following two parameters: • Bucket size: it is equal to the queue size. The queue holds the requests to be processed at a fixed rate. • Outflow rate: it defines how many requests can be processed at a fixed rate, usually in seconds. Pros: • Memory efficient given the limited queue size. • Requests are processed at a fixed rate therefore it is suitable for use cases that a stable outflow rate is needed. Cons: • A burst of traffic fills up the queue with old requests, and if they are not processed in time, recent requests will be rate limited. • There are two parameters in the algorithm. It might not be easy to tune them properly."

"The token bucket algorithm work as follows: • A token bucket is a container that has pre-defined capacity. Tokens are put in the bucket at preset rates periodically. Once the bucket is full, no more tokens are added. Each request consumes one token. When a request arrives, we check if there are enough tokens in the bucket. • If there are enough tokens, we take one token out for each request, and the request goes through. • If there are not enough tokens, the request is dropped.------The token bucket algorithm takes two parameters: • Bucket size: the maximum number of tokens allowed in the bucket • Refill rate: number of tokens put into the bucket every second. ----Pros: • The algorithm is easy to implement. • Memory efficient. • Token bucket allows a burst of traffic for short periods. A request can go through as long as there are tokens left. Cons: • Two parameters in the algorithm are bucket size and token refill rate. However, it might be challenging to tune them properly."

"In a network system, a rate limiter is used to control the rate of traffic sent by a client or a service. In the HTTP world, a rate limiter limits the number of client requests allowed to be sent over a specified period. If the API request count exceeds the threshold defined by the rate limiter, all the excess calls are blocked. --Prevent resource starvation caused by Denial of Service (DoS) attack. ---Reduce cost. Limiting excess requests means fewer servers and allocating more resources to high priority APIs. Rate limiting is extremely important for companies that use paid third party APIs. For example, you are charged on a per-call basis for the following external APIs: check credit, make a payment, retrieve health records, etc. Limiting the number of calls is essential to reduce costs.----- • Prevent servers from being overloaded. To reduce server load, a rate limiter is used to filter out excess requests caused by bots or users’ misbehavior.----you can implement a rate limiter at either the client or server-side. • Client-side implementation. Generally speaking, client is an unreliable place to enforce rate limiting because client requests can easily be forged by malicious actors. Moreover, we might not have control over the client implementation. • Server-side implementation. ----The HTTP 429 response status code indicates a user has sent too many requests. -----Rate limiting can be implemented using different algorithms, and each of them has distinct pros and cons. Here is a list of popular algorithms: • Token bucket--- • Leaking bucket--- • Fixed window counter--- • Sliding window log--- • Sliding window counter"

"• Eviction Policy: Once the cache is full, any requests to add items to the cache might cause existing items to be removed. This is called cache eviction. Least-recently-used (LRU) is the most popular cache eviction policy. Other eviction policies, such as the Least Frequently Used (LFU) or First in First Out (FIFO), can be adopted to satisfy different use cases."

."Braintree provides an API that allows you to process online payments with multiple payment methods, such as credit card, PayPal, Google Pay, and Apple Pay. You can learn more about Braintree at https://www.braintreepayments.com/. Braintree provides different integration options. The simplest is the Drop-in integration, which contains a preformatted payment form. However, in order to customize the behavior and experience of your checkout, you are going to use the advanced Hosted Fields integration. You can learn more about this integration at https://developers.braintreepayments.com/guides/hosted-fields/ overview/javascript/v3The Hosted Fields integration allows you to create your own payment form using custom styles and layouts. An iframe is added dynamically to the page using the Braintree JavaScript software development kit (SDK). The iframe includes the Hosted Fields payment form. When the customer submits the form, Hosted Fields collects the card details securely and attempts to tokenize them. If tokenization succeeds, you can send the generated token nonce to your view to make a transaction using the Python braintree module. A token nonce is a secure, one-time-use reference to payment information. It allows you to send sensitive payment information to Braintree without touching the raw data."

"replayable log–based approach has two primary benefits. First, it makes it easy to react to events that are happening now, with a toolset specifically designed for manipulating them. Second, it provides a central repository that can push whole datasets to wherever they may be needed. This is pretty useful if you run a global business with datacenters spread around the world, need to boot‐ strap or prototype a new project quickly, do some ad hoc data exploration, or build a complex service ecosystem that can evolve freely and independently. So there are some clear advantages to the event-driven approach (and there are of course advantages for the REST/RPC models too). But this is, in fact, only half the story. Streaming isn’t simply an alternative to RPCs that happens to work better for highly connected use cases; it’s a far more fundamental change in mindset that involves rethinking your business as an evolving stream of data, and your services as functions that transform these streams of data into something new."

"–------- Extract Services--------------- The third refactoring strategy is to turn existing modules within the monolith into standalone microservices. Each time you extract a module and turn it into a service, the monolith shrinks. Once you have converted enough modules, the monolith will cease to be a problem. Either it disappears entirely or it becomes small enough that it is just another service. Prioritizing Which Modules to Convert into Services A large, complex monolithic application consists of tens or hundreds of modules, all of which are candidates for extraction. Figuring out which modules to convert first is often challenging. A good approach is to start with a few modules that are easy to extract. This will give you experience with microservices in general and the extraction process in particular. After that, you should extract those modules that will give you the greatest benefit. Converting a module into a service is typically time consuming. You want to rank modules by the benefit you will receive. It is usually beneficial to extract modules that change frequently. Once you have converted a module into a service, you can develop and deploy it independently of the monolith, which will accelerate development. It is also beneficial to extract modules that have resource requirements significantly different from those of the rest of the monolith. It is useful, for example, to turn a module that has an in-memory database into a service, which can then be deployed on hosts, whether bare metal servers, VMs, or cloud instances, with large amounts of memory. Similarly, it can be worthwhile to extract modules that implement computationally expensive algorithms, since the service can then be deployed on hosts with lots of CPUs. By turning modules with particular resource requirements into services, you can make your application much easier and less expensive to scale. When figuring out which modules to extract, it is useful to look for existing coarse-grained boundaries (a.k.a seams). They make it easier and cheaper to turn modules into services. An example of such a boundary is a module that only communicates with the rest of the application via asynchronous messages. It can be relatively cheap and easy to turn that module into a microservice. -------How to Extract a Module--------------- The first step of extracting a module is to define a coarse-grained interface between the module and the monolith. It is mostly likely a bidirectional API, since the monolith will need data owned by the service and vice versa. It is often challenging to implement such an API because of the tangled dependencies and fine-grained interaction patterns between the module and the rest of the application. Business logic implemented using the Domain Model pattern is especially challenging to refactor because of numerous associations between domain model classes. You will often need to make significant code changes to break these dependencies. Once you implement the coarse-grained interface, you then turn the module into a free-standing service. To do that, you must write code to enable the monolith and the service to communicate through an API that uses an inter-process communication (IPC) mechanism. "

"---------Split Frontend and Backend-------- A strategy that shrinks the monolithic application is to split the presentation layer from the business logic and data access layers. A typical enterprise application consists of at least three different types of components: • Presentation layer – Components that handle HTTP requests and implement either a (REST) API or an HTML-based web UI. In an application that has a sophisticated user interface, the presentation tier is often a substantial body of code.-------- • Business logic layer – Components that are the core of the application and implement the business rules.---------- • Data-access layer – Components that access infrastructure components, such as databases and message brokers.-----------There is usually a clean separation between the presentation logic on one side and the business and data-access logic on the other. The business tier has a coarse-grained API consisting of one or more facades, which encapsulate business-logic components. This API is a natural seam along which you can split the monolith into two smaller applications. One application contains the presentation layer. The other application contains the business and data-access logic. After the split, the presentation logic application makes remote calls to the business logic application."

"– ------Stop Digging-------- The Law of Holes says that whenever you are in a hole you should stop digging. This is great advice to follow when your monolithic application has become unmanageable. In other words, you should stop making the monolith bigger. This means that when you are implementing new functionality you should not add more code to the monolith. Instead, the big idea with this strategy is to put that new code in a standalone microservice. As well as the new service and the legacy monolith, there are two other components. The first is a request router, which handles incoming (HTTP) requests. It is similar to the API gateway. The router sends requests corresponding to new functionality to the new service. It routes legacy requests to the monolith. The other component is the glue code, which integrates the service with the monolith. A service rarely exists in isolation and often needs to access data owned by the monolith. The glue code, which resides in either the monolith, the service, or both, is responsible for the data integration. The service uses the glue code to read and write data owned by the monolith.--------------------------------- There are three strategies that a service can use to access the monolith’s data: • Invoke a remote API provided by the monolith--------- • Access the monolith’s database directly----------- • Maintain its own copy of the data, which is synchronized with the monolith’s database--------------- The glue code is sometimes called an anti-corruption layer. That is because the glue code prevents the service, which has its own pristine domain model, from being polluted by concepts from the legacy monolith’s domain model. The glue code translates between the two different models. The term anti-corruption layer first appeared in the must-read book Domain Driven Design by Eric Evans and was then refined in a white paper. Developing an anti-corruption layer can be a non-trivial undertaking. But it is essential to create one if you want to grow your way out of monolithic hell. Implementing new functionality as a lightweight service has a couple of benefits. It prevents the monolith from becoming even more unmanageable. The service can be developed, deployed, and scaled independently of the monolith. You experience the benefits of the microservice architecture for each new service that you create. However, this approach does nothing to address the problems with the monolith. To fix those problems you need to break up the monolith."

"-----------Serverless Deployment--------- AWS Lambda is an example of serverless deployment technology. It supports Java, Node.js, and Python services. To deploy a microservice, you package it as a ZIP file and upload it to AWS Lambda. You also supply metadata, which among other things specifies the name of the function that is invoked to handle a request (a.k.a. an event). AWS Lambda automatically runs enough instances of your microservice to handle requests. You are simply billed for each request based on the time taken and the memory consumed. Of course, the devil is in the details, and you will see shortly that AWS Lambda has limitations. But the notion that neither you as a developer, nor anyone in your organization, need worry about any aspect of servers, virtual machines, or containers is incredibly appealing. A Lambda function is a stateless service. It typically handles requests by invoking AWS services. For example, a Lambda function that is invoked when an image is uploaded to an S3 bucket could insert an item into a DynamoDB images table and publish a message to a Kinesis stream to trigger image processing. A Lambda function can also invoke third-party web services. There are four ways to invoke a Lambda function: • Directly, using a web service request • Automatically, in response to an event generated by an AWS service such as S3, DynamoDB, Kinesis, or Simple Email Service • Automatically, via an AWS API Gateway to handle HTTP requests from clients of the application • Periodically, according to a cron-like schedule As you can see, AWS Lambda is a convenient way to deploy microservices. The requestbased pricing means that you only pay for the work that your services actually perform. Also, because you are not responsible for the IT infrastructure, you can focus on developing your application. There are, however, some significant limitations. Lambda functions are not intended to be used to deploy long-running services, such as a service that consumes messages from a third-party message broker. Requests must complete within 300 seconds. Services must be stateless, since in theory AWS Lambda might run a separate instance for each request. They must be written in one of the supported languages. Services must also start quickly; otherwise, they might be timed out and terminated."

"One way to deploy your microservices is to use the Multiple Service Instances per Host pattern. When using this pattern, you provision one or more physical or virtual hosts and run multiple service instances on each one. Multiple Service Instances per Host pattern has some significant drawbacks. One major drawback is that there is little or no isolation of the service instances, unless each service instance is a separate process. While you can accurately monitor each service instance’s resource utilization, you cannot limit the resources each instance uses. It’s possible for a misbehaving service instance to consume all of the memory or CPU of the host. There is no isolation at all if multiple service instances run in the same process. All instances might, for example, share the same JVM heap. A misbehaving service instance could easily break the other services running in the same process. Moreover, you have no way to monitor the resources used by each service instance. Another significant problem with this approach is that the operations team that deploys a service has to know the specific details of how to do it. Services can be written in a variety of languages and frameworks, so there are lots of details that the development team must share with operations. This complexity increases the risk of errors during deployment.----------Another way to deploy your microservices is the Service Instance per Host pattern. When you use this pattern, you run each service instance in isolation on its own host. There are two different specializations of this pattern: Service Instance per Virtual Machine and Service Instance per Container.------When you use Service Instance per Virtual Machine pattern, you package each service as a virtual machine (VM) image such as an Amazon EC2 AMI. Each service instance is a VM (for example, an EC2 instance) that is launched using that VM image. This is the primary approach used by Netflix to deploy its video streaming service. Netflix packages each of its services as an EC2 AMI using Aminator. Each running service instance is an EC2 instance. There are a variety tools that you can use to build your own VMs. You can configure your continuous integration (CI) server (for example, Jenkins) to invoke Aminator to package your services as an EC2 AMI.Packer is another option for automated VM image creation. Unlike Aminator, it supports a variety of virtualization technologies including EC2, DigitalOcean, VirtualBox, and VMware. The company Boxfuse has a compelling way to build VM images, which overcomes the drawbacks of VMs that I describe below. Boxfuse packages your Java application as a minimal VM image. These images are fast to build, boot quickly, and are more secure since they expose a limited attack surface. The company CloudNative has the Bakery, a SaaS offering for creating EC2 AMIs. You can configure your CI server to invoke the Bakery after the tests for your microservice pass. The Bakery then packages your service as an AMI. Using a SaaS offering such as the Bakery means that you don’t have to waste valuable time setting up the AMI creation infrastructure. The Service Instance per Virtual Machine pattern has a number of benefits. A major benefit of VMs is that each service instance runs in complete isolation. It has a fixed amount of CPU and memory and can’t steal resources from other services. Another benefit of deploying your microservices as VMs is that you can leverage mature cloud infrastructure. Clouds such as AWS provide useful features such as load balancing and autoscaling. Another great benefit of deploying your service as a VM is that it encapsulates your service’s implementation technology. Once a service has been packaged as a VM it becomes a black box. The VM’s management API becomes the API for deploying the service. Deployment becomes much simpler and more reliable. The Service Instance per Virtual Machine pattern has some drawbacks, however. One drawback is less efficient resource utilization. Each service instance has the overhead of an entire VM, including the operating system. Moreover, in a typical public IaaS, VMs come in fixed sizes and it is possible that the VM will be underutilized. Moreover, a public IaaS typically charges for VMs regardless of whether they are busy or idle. An IaaS such as AWS provides autoscaling, but it is difficult to react quickly to changes in demand. Consequently, you often have to overprovision VMs, which increases the cost of deployment. Another downside of this approach is that deploying a new version of a service is usually slow. VM images are typically slow to build due to their size. Also, VMs are typically slow to instantiate, again because of their size. Also, an operating system typically takes some time to start up. Note, however, that this is not universally true, since lightweight VMs such as those built by Boxfuse exist. -----------------When you use the Service Instance per Container pattern, each service instance runs in its own container. Containers are a virtualization mechanism at the operating system level. A container consists of one or more processes running in a sandbox. From the perspective of the processes, they have their own port namespace and root filesystem. You can limit a container’s memory and CPU resources. Some container implementations also have I/O rate limiting. Examples of container technologies include Docker and Solaris Zones.There are some drawbacks to using containers. While container infrastructure is rapidly maturing, it is not as mature as the infrastructure for VMs. Also, containers are not as secure as VMs, since the containers share the kernel of the host OS with one another. Another drawback of containers is that you are responsible for the undifferentiated heavy lifting of administering the container images. Also, unless you are using a hosted container solution such as Google Container Engine or Amazon EC2 Container Service (ECS), then you must administer the container infrastructure and possibly the VM infrastructure that it runs on. Also, containers are often deployed on an infrastructure that has per-VM pricing. Consequently, as described earlier, you will likely incur the extra cost of overprovisioning VMs in order to handle spikes in load. Interestingly, the distinction between containers and VMs is likely to blur. As mentioned earlier, Boxfuse VMs are fast to build and start. The Clear Containers project aims to create lightweight VMs. There is also growing interest in unikernels. Docker, Inc acquired Unikernel Systems in early 2016"

"One way to achieve atomicity is for the application to publish events using a multi-step process involving only local transactions. The trick is to have an EVENT table, which functions as a message queue, in the database that stores the state of the business entities. The application begins a (local) database transaction, updates the state of the business entities, inserts an event into the EVENT table, and commits the transaction. A separate application thread or process queries the EVENT table, publishes the events to the Message Broker, and then uses a local transaction to mark the events as published. The Order Service inserts a row into the ORDER table and inserts an Order Created event into the EVENT table. The Event Publisher thread or process queries the EVENT table for unpublished events, publishes the events, and then updates the EVENT table to mark the events as published. This approach has several benefits and drawbacks. One benefit is that it guarantees an event is published for each update without relying on 2PC. Also, the application publishes business-level events, which eliminates the need to infer them. One drawback of this approach is that it is potentially error-prone since the developer must remember to publish events. A limitation of this approach is that it is challenging to implement when using some NoSQL databases because of their limited transaction and query capabilities. This approach eliminates the need for 2PC by having the application use local transactions to update state and publish events. ------------Another way to achieve atomicity without 2PC is for the events to be published by a thread or process that mines the database’s transaction or commit log. The application updates the database, so changes are recorded in the database’s transaction log. The Transaction Log Miner thread or process reads the transaction log and publishes events to the Message Broker. An example of this approach is the open source LinkedIn Databus project. Databus mines the Oracle transaction log and publishes events corresponding to the changes. LinkedIn uses Databus to keep various derived data stores consistent with the system of record. Another example is the streams mechanism in AWS DynamoDB, which is a managed NoSQL database. A DynamoDB stream contains the time-ordered sequence of changes (create, update, and delete operations) made to the items in a DynamoDB table in the last 24 hours. An application can read those changes from the stream and, for example, publish them as events. Transaction log mining has various benefits and drawbacks. One benefit is that it guarantees that an event is published for each update without using 2PC. Transaction log mining can also simplify the application by separating event publishing from the application’s business logic. A major drawback is that the format of the transaction log is proprietary to each database and can even change between database versions. Also, it can be difficult to reverse engineer the high-level business events from the low-level updates recorded in the transaction log. Transaction log mining eliminates the need for 2PC by having the application do one thing: update the database.--------------------vent sourcing achieves atomicity without 2PC by using a radically different, event-centric approach to persisting business entities. Rather than store the current state of an entity, the application stores a sequence of state-changing events. The application reconstructs an entity’s current state by replaying the events. Whenever the state of a business entity changes, a new event is appended to the list of events. Since saving an event is a single operation, it is inherently atomic. Events persist in an Event Store, which is a database of events. The store has an API for adding and retrieving an entity’s events. The Event Store also behaves like the Message Broker in the architectures we described previously. It provides an API that enables services to subscribe to events. The Event Store delivers all events to all interested subscribers. The Event Store is the backbone of an event-driven microservices architecture. Event sourcing has several benefits. It solves one of the key problems in implementing an event-driven architecture and makes it possible to reliably publish events whenever state changes. As a result, it solves data consistency issues in a microservices architecture. Also, because it persists events rather than domain objects, it mostly avoids the objectrelational impedance mismatch problem. Event sourcing also provides a 100% reliable audit log of the changes made to a business entity and makes it possible to implement temporal queries that determine the state of an entity at any point in time. Another major benefit of event sourcing is that your business logic consists of loosely coupled business entities that exchange events. This makes it a lot easier to migrate from a monolithic application to a microservices architecture.Event sourcing also has some drawbacks. It is a different and unfamiliar style of programming and so there is a learning curve. The event store only directly supports the lookup of business entities by primary key. You must use command query responsibility separation (CQRS) to implement queries. As a result, applications must handle eventually consistent data."

"Modern applications store and process diverse kinds of data, and a relational database is not always the best choice. For some use cases, a particular NoSQL database might have a more convenient data model and offer much better performance and scalability. For example, it makes sense for a service that stores and queries text to use a text search engine such as Elasticsearch. Similarly, a service that stores social graph data should probably use a graph database, such as Neo4j. Consequently, microservices-based applications often use a mixture of SQL and NoSQL databases, the so-called polyglot persistence approach. A partitioned, polyglot-persistent architecture for data storage has many benefits, including loosely coupled services and better performance and scalability. However, it does introduce some distributed data management challenges. The first challenge is how to implement business transactions that maintain consistency across multiple services. To see why this is a problem, let’s take a look at an example of an online B2B store. The Customer Service maintains information about customers, including their credit lines. The Order Service manages orders and must verify that a new order doesn’t violate the customer’s credit limit. In the monolithic version of this application, the Order Service can simply use an ACID transaction to check the available credit and create the order. In contrast, in a microservices architecture the ORDER and CUSTOMER tables are private to their respective services. The Order Service cannot access the CUSTOMER table directly. It can only use the API provided by the Customer Service. The Order Service could potentially use distributed transactions, also known as two-phase commit (2PC). However, 2PC is usually not a viable option in modern applications. The CAP theorem requires you to choose between availability and ACID-style consistency, and availability is usually the better choice. Moreover, many modern technologies, such as most NoSQL databases, do not support 2PC. Maintaining data consistency across services and databases is essential, so we need another solution."

"Segregating the functionalities of an application into a separate process can be viewed as a Sidecar pattern. The sidecar design pattern allows you to add a number of capabilities to your application without additional configuration code for third-party components. As a sidecar is attached to a motorcycle, similarly in software architecture a sidecar is attached to a parent application and extends/enhances its functionalities. A sidecar is loosely coupled with the main application."

"A service registry consists of a cluster of servers that use a replication protocol to maintain consistency. Netflix Eureka is a good example of a service registry. It provides a REST API for registering and querying service instances. Netflix achieves high availability by running one or more Eureka servers in each Amazon EC2 availability zone. Each Eureka server runs on an EC2 instance that has an Elastic IP address. DNS TEXT records are used to store the Eureka cluster configuration, which is a map from availability zones to a list of the network locations of Eureka servers. When a Eureka server starts up, it queries DNS to retrieve the Eureka cluster configuration, locates its peers, and assigns itself an unused Elastic IP address. Eureka clients – services and service clients – query DNS to discover the network locations of Eureka servers. Clients prefer to use a Eureka server in the same availability zone. However, if none is available, the client uses a Eureka server in another availability zone------- Other examples of service registries include: • etcd – A highly available, distributed, consistent, key-value store that is used for shared configuration and service discovery. Two notable projects that use etcd are Kubernetes and Cloud Foundry.--------- • Consul – A tool for discovering and configuring services. It provides an API that allows clients to register and discover services. Consul can perform health checks to determine service availability.--------- • Apache ZooKeeper – A widely used, high-performance coordination service for distributed applications. Apache ZooKeeper was originally a subproject of Hadoop, but is now a separate, top-level project.-------- Some systems such as Kubernetes, Marathon, and AWS do not have an explicit service registry. Instead, the service registry is just a built-in part of the infrastructure."

"------Why Use Service Discovery?------ Let’s imagine that you are writing some code that invokes a service that has a REST API or Thrift API. In order to make a request, your code needs to know the network location (IP address and port) of a service instance. In a traditional application running on physical hardware, the network locations of service instances are relatively static. For example, your code can read the network locations from a configuration file that is occasionally updated.Service instances have dynamically assigned network locations. Moreover, the set of service instances changes dynamically because of autoscaling, failures, and upgrades. Consequently, your client code needs to use a more elaborate service discovery mechanism. There are two main service discovery patterns: client-side discovery and server-side discovery. ----------When using client-side discovery pattern, the client is responsible for determining the network locations of available service instances and load balancing requests across them. The client queries a service registry, which is a database of available service instances. The client then uses a load-balancing algorithm to select one of the available service instances and makes a request. The network location of a service instance is registered with the service registry when it starts up. It is removed from the service registry when the instance terminates. The service instance’s registration is typically refreshed periodically using a heartbeat mechanism. Netflix OSS provides a great example of the client-side discovery pattern. Netflix Eureka is a service registry. It provides a REST API for managing service-instance registration and for querying available instances. Netflix Ribbon is an IPC client that works with Eureka to load balance requests across the available service instances. The client-side discovery pattern has a variety of benefits and drawbacks. This pattern is relatively straightforward and, except for the service registry, there are no other moving parts. Also, since the client knows about the available services instances, it can make intelligent, application-specific load-balancing decisions such as using hashing consistently. One significant drawback of this pattern is that it couples the client with the service registry. You must implement client-side service discovery logic for each programming language and framework used by your service clients.-----------The client makes a request to a service via a load balancer. The load balancer queries the service registry and routes each request to an available service instance. As with client-side discovery, service instances are registered and deregistered with the service registry. The AWS Elastic Load Balancer (ELB) is an example of a server-side discovery router. ELB is commonly used to load balance external traffic from the Internet. However, you can also use ELB to load balance traffic that is internal to a virtual private cloud (VPC). A client makes requests (HTTP or TCP) via the ELB using its DNS name. The ELB load balances the traffic among a set of registered Elastic Compute Cloud (EC2) instances or EC2 Container Service (ECS) containers. There isn’t a separately visible service registry. Instead, EC2 instances and ECS containers are registered with the ELB itself. Some deployment environments such as Kubernetes and Marathon run a proxy on each host in the cluster. The proxy plays the role of a server-side discovery load balancer. In order to make a request to a service, a client routes the request via the proxy using the host’s IP address and the service’s assigned port. The proxy then transparently forwards the request to an available service instance running somewhere in the cluster. One great benefit of this pattern is that details of discovery are abstracted away from the client. Clients simply make requests to the load balancer. This eliminates the need to implement discovery logic for each programming language and framework used by your service clients."

" RAML ( RESTful API Modeling Language ) belongs to API tools, whereas Swagger is a dependency-free collection of UI that belongs to Documentation as Service and Tools. -------- RAML, also known as RESTful API Modeling Language and Swagger, is also known as Open API/ OAS.----- RAML manages the whole API lifecycle from design to sharing, whereas Swagger is a dependency-free collection of JavaScript, HTML and CSS, which in return generate good documentation RAML belongs to the tech stack of API Tools, whereas Swagger can be classified as ‘Documentation as Services and Tools.------------ RAML provides an easy way of writing API’ and is reusable, human-friendly, whereas Swagger is an API Compliant and ‘Open Source.-------------------- RAML is YAML based language with a hierarchical style format, whereas Swagger is referred to as language-agnostic. YAML used Python-style indentation.----------------- In comparison, both RAML and Swagger are capable and compatible with many languages such as Java, .NET, JavaScript, Node.js, Python, Ruby, PHP, Scala, Go and many more. Additionally, RAML supports Elixer and Pearl, whereas Swagger supports Coldfusion, D, Eiffel, Groovy, Erlang, Typescript and Clojure. Since REST does not have a standard to describe or publish RESTful API’s, WSDL describes these standards. One of these standards is RAML.----------- RAML and Open API/ Swagger are two descriptive languages that have gained importance in RESTful services.------------- RAML describes API’s endpoints, whereas Swagger supports JSON format."

"There are a large number of open source messaging systems to choose from, including RabbitMQ, Apache Kafka, Apache ActiveMQ, and NSQ. At a high level, they all support some form of messages and channels. They all strive to be reliable, high-performance, and scalable. However, there are significant differences in the details of each broker’s messaging model.************ There are many advantages to using messaging:--------- • Decouples the client from the service – A client makes a request simply by sending a message to the appropriate channel. The client is completely unaware of the service instances. It does not need to use a discovery mechanism to determine the location of a service instance.******* • Message buffering – With a synchronous request/response protocol, such as HTTP, both the client and service must be available for the duration of the exchange. In contrast, a message broker queues up the messages written to a channel until the consumer can process them. This means, for example, that an online store can accept orders from customers even when the order fulfillment system is slow or unavailable. The order messages simply queue up.------------ • Flexible client-service interactions – Messaging supports all of the interaction styles .--------------- • Explicit inter-process communication – RPC-based mechanisms attempt to make invoking a remote service look the same as calling a local service. However, because of the laws of physics and the possibility of partial failure, they are in fact quite different. Messaging makes these differences very explicit so developers are not lulled into a false sense of security.--------------- There are, however, some downsides to using messaging: • Additional operational complexity – The messaging system is yet another system component that must be installed, configured, and operated. It’s essential that the message broker be highly available, otherwise, system reliability is impacted. ------------- • Complexity of implementing request/response-based interaction – Request/response style interaction requires some work to implement. Each request message must contain a reply channel identifier and a correlation identifier. The service writes a response message containing the correlation ID to the reply channel. The client uses the correlation ID to match the response with the request. It is often easier to use an IPC mechanism that directly supports request/response. "

"There are lots of different IPC technologies to choose from. Services can use synchronous request/response-based communication mechanisms such as HTTP-based REST or Thrift. Alternatively, they can use asynchronous, message-based communication mechanisms such as AMQP or STOMP ****(STOMP is the Simple (or Streaming) Text Orientated Messaging Protocol. STOMP provides an interoperable wire format so that STOMP clients can communicate with any STOMP message broker to provide easy and widespread messaging interoperability among many languages, platforms and brokers.). ******* There are also a variety of different message formats. Services can use human-readable, text-based formats such as JSON or XML. Alternatively, they can use a binary format (which is more efficient) such as Avro or Protocol Buffers. ---------When using messaging, processes communicate by asynchronously exchanging messages. A client makes a request to a service by sending it a message. If the service is expected to reply, it does so by sending a separate message back to the client. Since the communication is asynchronous, the client does not block waiting for a reply. Instead, the client is written assuming that the reply will not be received immediately. -----*A message consists of headers (metadata such as the sender) and a message body. Messages are exchanged over channels. Any number of producers can send messages to a channel. Similarly, any number of consumers can receive messages from a channel. There are two kinds of channels, point-to-point and publish-subscribe: ******* • A point‑to‑point channel delivers a message to exactly one of the consumers that are reading from the channel. Services use point‑to‑point channels for the one‑to‑one interaction styles.--------- • A publish‑subscribe channel delivers each message to all of the attached consumers. Services use publish‑subscribe channels for the one‑to‑many interaction styles "

"The strategies for dealing with partial failures include:-------- • Network timeouts – Never block indefinitely and always use timeouts when waiting for a response. Using timeouts ensures that resources are never tied up indefinitely.------ • Limiting the number of outstanding requests – Impose an upper bound on the number of outstanding requests that a client can have with a particular service. If the limit has been reached, it is probably pointless to make additional requests, and those attempts need to fail immediately.--------------------- • Circuit breaker pattern – Track the number of successful and failed requests. If the error rate exceeds a configured threshold, trip the circuit breaker so that further attempts fail immediately. If a large number of requests are failing, that suggests the service is unavailable and that sending requests is pointless. After a timeout period, the client should try again and, if successful, close the circuit breaker.------------ • Provide fallbacks – Perform fallback logic when a request fails. For example, return cached data or a default value, such as an empty set of recommendations."

"An API Gateway is a server that is the single entry point into the system. It is similar to the Facade pattern from object-oriented design. The API Gateway encapsulates the internal system architecture and provides an API that is tailored to each client. It might have other responsibilities such as authentication, monitoring, load balancing, caching, request shaping and management, and static response handling.The API Gateway is responsible for request routing, composition, and protocol translation. All requests from clients first go through the API Gateway. It then routes requests to the appropriate microservice. The API Gateway will often handle a request by invoking multiple microservices and aggregating the results. It can translate between web protocols such as HTTP and WebSocket and web-unfriendly protocols that are used internally. The API Gateway can also provide each client with a custom API. It typically exposes a coarse-grained API for mobile clients.A great example of an API Gateway is the Netflix API Gateway. The Netflix streaming service is available on hundreds of different kinds of devices including televisions, set-top boxes, smartphones, gaming systems, tablets, etc. Initially, Netflix attempted to provide a one-size-fits-all API for their streaming service. However, they discovered that it didn’t work well because of the diverse range of devices and their unique needs. Today, they use an API Gateway that provides an API tailored for each device by running device-specific adapter code. An adapter typically handles each request by invoking, on average, six to seven backend services. The Netflix API Gateway handles billions of requests per day. The API Gateway also has some drawbacks. It is yet another highly available component that must be developed, deployed, and managed. There is also a risk that the API Gateway becomes a development bottleneck. Developers must update the API Gateway in order to expose each microservice’s endpoints. It is important that the process for updating the API Gateway be as lightweight as possible. Otherwise, developers will be forced to wait in line in order to update the gateway. Despite these drawbacks, however, for most real-world applications it makes sense to use an API Gateway. The API Gateway needs to know the location (IP address and port) of each microservice with which it communicates. In a traditional application, you could probably hardwire the locations, but in a modern, cloud-based microservices application, finding the needed locations is a non-trivial problem. Infrastructure services, such as a message broker, will usually have a static location, which can be specified via OS environment variables. However, determining the location of an application service is not so easy. Application services have dynamically assigned locations. Also, the set of instances of a service changes dynamically because of autoscaling and upgrades. Consequently, the API Gateway, like any other service client in the system, needs to use the system’s service discovery mechanism: either server-side discovery or client-side discovery.The API Gateway could also return cached data if that is available. For example, since product prices change infrequently, the API Gateway could return cached pricing data if the pricing service is unavailable. The data can be cached by the API Gateway itself or be stored in an external cache, such as Redis or Memcached. By returning either default data or cached data, the API Gateway ensures that system failures minimally impact the user experience."

"A microservices-based application is a distributed system and must use an inter-process communication mechanism. There are two styles of inter-process communication. One option is to use an asynchronous, messaging-based mechanism. Some implementations use a message broker such as JMS or AMQP. Others, such as Zeromq, are brokerless and the services communicate directly. The other style of inter-process communication is a synchronous mechanism such as HTTP or Thrift. A system will typically use both asynchronous and synchronous styles. It might even use multiple implementations of each style. Consequently, the API Gateway will need to support a variety of communication mechanisms. "

"MQTT (MQ Telemetry Transport) is a lightweight open messaging protocol that provides resource-constrained network clients with a simple way to distribute telemetry information in low-bandwidth environments. it is an ideal protocol for machine-to-machine (M2M) communication. A client can send messages to the broker (publish) and receive messages from the broker (subscribe). When sending a message to the broker, an MQTT topic must be specified, which can be used to further process the message. The practical benefit of communication via MQTT is that it relieves the internal network and can still communicate with any number of different systems. Using special software, such as OPC Router, data can be published to other systems. Systems of this kind can be, for example, SAP, OPC UA, SQL or REST. Data from non-MQTT-capable sources can be transferred to other systems for further processing as a Publisher. The reliable message protocol MQTT can accelerate internal communication and create bandwidth capacities. -------------------------------------------------------------------------------------------------- AMQP and MQTT are binary messaging protocols that work on top of TCP/IP. They allow message exchange between systems and applications irrespective of the underlying hardware & software stack. Binary messaging protocols are more efficient than text protocols as they have lesser processing requirements. Both of them are suitable for IoT applications, but they’re optimized for different requirements. MQTT generally serves high-latency, low-bandwidth networks with thousands of embedded devices better. On the other hand, AMQP works better in large, enterprise-wide applications with highly customized and involved messaging requirements."

" Advanced Message Queuing Protocol (AMQP) is an application layer protocol that focuses on process-to-process communication across IP networks. An encoding schema and a set of procedures allow for two different servers to communicate regardless of the technology used. Overall, the goal of AMQP is to enable message passing through broker services over TCP/IP connections. AMQP is considered a compact protocol, since it’s a binary protocol, meaning that everything sent over AMQP is binary data. A binary protocol avoids sending useless data over the wire.Broker (or server) plays a crucial role in AMQP protocol enablement. It is responsible for connection building that ensure better data routing and queuing at the client-side. The job of queues generation and message acknowledgement is taken care of by consumer. Redirection of data taken from exchanges and its placement in queues is taken care of by producer. It has asynchronous communication nature. It has guaranteed message delivery. It provides publish/subscribe interface."

"Thrift is a lightweight, language-independent software stack with an associated code generation mechanism for RPC. Thrift provides clean abstractions for data transport, data serialization, and application-level processing. Thrift includes a complete stack for creating clients and servers. Thrift is more compact than HTTP, and can easily be extended to support things like encryption, compression, non-blocking IO, etc. Thrift can be set up to use HTTP and JSON pretty easily if you want it (say if your client is somewhere on the internet and needs to pass firewalls) Thrift supports persistent connections and avoids the continuous TCP and HTTP handshakes that HTTP incurs."

"? Implementing a reverse proxy server, and using the other capabilities of NGINX, gives you architectural flexibility. A reverse proxy server, static and application file caching, and SSL/TLS and HTTP/2 termination all take load off your application, freeing it to “do what only it” – the application – “can do”. NGINX also serves as a load balancer, a crucial role in microservices implementations. The advanced features in NGINX Plus, including sophisticated load-balancing algorithms, multiple methods for session persistence, and management and monitoring, are especially useful with microservices. (NGINX has recently added support for service discovery using DNS SRV records, a cutting-edge feature.) And, as mentioned in this chapter, NGINX can help in automating the deployment of microservices. In addition, NGINX provides the necessary functionality to power the three models in the NGINX Microservices Reference Architecture. The Proxy Model uses NGINX as an API Gateway; the Router Mesh model uses an additional NGINX server as a hub for inter-process communication; and the Fabric Model uses one NGINX server per microservice, controlling HTTP traffic and, optionally, implementing SSL/TLS between microservices, a breakthrough capability. "

"Kibana is an open-source visualization and exploration tool used for application monitoring, log analysis, time-series analysis applications. It also provides in-built features like statistical graphs (histograms, pie charts, line graphs, etc.). It is a part of the ELK stack; therefore, it also provides inbuilt integration with the Elasticsearch search engine. Splunk is visualization software used to analyze logs and machine-generated data, application monitoring, security, and web applications. It can represent the data in its inbuilt dashboards, graphs, etc. Splunk provides a SaaS interface (Software as a service) that analyzes machine data very efficiently. Splunk belongs to the Log management/analysis category, whereas Kibana can be classified into the monitoring tools category.Kibana is completely open-source. Splunk is a licensed software (SaaS), and its services are charged. Splunk has three versions. Splunk Enterprise: As the name suggests, it is used by large organizations and enterprises. Splunk cloud: It is a platform on which users can develop their applications. It can be hosted on the AWS cloud as well. Splunk Lite: This is a free trial with limited features for users to get a feel of what it can do.LinkedIn, Netflix, StackOverflow are few organizations that use Kibana. Bosch, Cisco, Adobe are few organizations that use Splunk."

"A continuous integration and continuous deployment (CI/CD) pipeline is a series of steps that must be performed in order to deliver a new version of software. CI/CD pipelines are a practice focused on improving software delivery throughout the software development life cycle via automation. A pipeline is a process that drives software development through a path of building, testing, and deploying code, also known as CI/CD. By automating the process, the objective is to minimize human error and maintain a consistent process for how software is released. Tools that are included in the pipeline could include compiling code, unit tests, code analysis, security, and binaries creation. For containerized environments, this pipeline would also include packaging the code into a container image to be deployed across a hybrid cloud. CI/CD is the backbone of a DevOps methodology, bringing developers and IT operations teams together to deploy software. "

"Circuit breaker is a design pattern used in software development. It is used to detect failures and encapsulates the logic of preventing a failure from constantly recurring, during maintenance, temporary external system failure, or unexpected system difficulties. Different States of Circuit Breaker--- Closed--- Open--- Half Open---"

"External configuration: All environment-specific configurations such as connection strings, application properties and URLs should be loaded from an external configuration file. The CI/CD pipeline can inject the environment-specific configuration values during the build. • Service discovery: A centralized service discovery module should handle the responsibilities such as service registra tion/ de-registration and request routing, based on service health. For client side service discovery service registry is used for load balancing and for server side service discovery, server side load balancing is used. • Circuit breaker: When one of the services in the request-processing pipeline fails, the circuit breaker is responsible in terms of handling the failure and preventing the cascading of the error. The circuit breaker can monitor the error from a dependent service and fallback to a default handler in case of error. Netflix Hysterix is an example of a circuit breaker Blue green deployment pattern: In order to seamlessly deploy the newer version of microservices with minimal downtime, we can maintain two identical production instances (blue instance and green instance), one of which will be live, serving the requests at any time. During production deployment, we can update the non-live instance and route traffic to it. • Access Token: Due to the stateless nature of microservices, each request should securely pass the user identity. Access tokens such as JSON Web Token (JWT) encapsulates the claim details in microservices architecture. • Auditing: Log the user actions such as authentication, password changes in logs that are centralized, immutable, and secure for auditing purposes. • Exception Logging: Logs all service exceptions in a central location and provides notification feature. • Microservice chassis: Reuse an existing microservices framework such as Spring Boot to leverage in-built features such as configuration handling, logging, request filtering etc. "

"Log aggregation: Since microservices are deployed into individual containers, the logs generated by each of the containers (a.k.a pods) need to be aggregated to create a centralized log repository. Microservices can log to standard output or to a log file. The log management systems such as Splunk or Kibana can aggregate the log stream in real time to a centralized log repository and we can query the real-time logs. • Performance monitoring: Performance monitoring services such as Prometheus, AppDynamics and NewRelic can be used to monitor the performance metrics of microservices. The performance metrics are depicted visually and we can configure the performance thresholds and notification triggers. • Distributed tracing: When the request flows across various layers and microservices, it is necessary to trace the request end-to-end for error handling and for performance troubleshooting scenarios. In distributed tracking, we create a unique request ID (such as x-request-id) that is passed across all layers and microservices and logged for troubleshoot ing purposes. • Health check pattern: In order to properly distribute the load and route the traffic accordingly, each microservice has to publish health check endpoint (such as /health) that provides the status of the overall health of the service. The health check service should check the status of dependent systems (such as databases, storage systems) and host connectivity to provide the overall health status of the service."

"Shared database: Though not a recommended approach, when we are decomposing a monolith application to microservices, the approach can comprise a single being shared by multiple microservices. Once the transformation is complete, each service should gets its own database. • Command Query Responsibility Segregation (CQRS): Database handling is split into two categories, the command part for handling data creation, update, deletion and the query part that uses materialized views to retrieve data. The materialized view is updated by subscribing to data change events. Event sourcing pattern is used along with CQRS to create immutable events. • Saga pattern: When a business transaction needs to manage data consistency that is spread across multiple databases, we could use Saga pattern. As a part of the Saga pattern, each transaction is orchestrated locally or centrally to execute it entirely and handle the failure/rollback scenario. For instance, if a business transaction needs to handle data related to order and customer service, each of these services produces and listens to each other to handle the transaction. "

"API gateway pattern: An API gateway provides a centralized access point for invoking a microservice. The API gateway handles security (such as authentication, authorization), governance (such as logging service, monitoring service), request routing, protocol transformation, data transformation and the aggregation of responses from multiple services. • Aggregation pattern: When a single microservice needs responses from multiple microservices, a composite service can take the responsibility of aggregating the response. • UI composition pattern: The end user interface layer is laid out into various sections, which individually invokes the corresponding microservice asynchronously. Modern user interfaces use single page applications (SPA) built by Angular or ReactJS frameworks. • Backend for frontend: Instead of creating a general-purpose microservice, we can design a microservice and its response specifically for the client agents (such as desktop browsers, mobile devices etc.). This tight coupling of client agents with the corresponding backend service helps us to efficiently create response data. "

"ROUTING, LOAD BALANCING, AND CACHING------------ This layer mainly has components to route requests to specific consumers, load balance them, and cache the response. The details of these components have been provided below:------------ • API Gateway: Gateway/ proxy for the client to access microservices. All cross-cutting functionalities like security, loaded balancing, governance, protocol transformation, analytics, performance management, payload transformation etc. are implemented here. --------- • Service discovery: It works as a directory service for all microservices in a domain. API gateway consults with the service directory to route all client requests. The inter service communication also leverages service directory. ------- • Load balancer: The load balancer is responsible for routing the requests to the microservice instance.---------- • Caching: Static data (such as images, text files etc.) and service response will be cached for optimal performance. Systems such as AWS CloudFront provide edge-side caching and systems such as Redis provide in-memory caching. -------- • Circuit breaker: This component is used to detect service failure and provide fallback."

"SOA (Service-oriented Architecture) is a designing pattern and Microservice is an implementation methodology to implement SOA or we can say Microservice is a type of SOA.-----------SOA*****Business units are dependent on each other.-Software size is bigger than the conventional software.-SOA applications are built to perform multiple business tasks.-Monolithic in nature.----------Microservice ********All business units are independent of each other.-Software size is small.-Microservice applications are built to perform a single business task.-Fully scaled.-Less cost-effective."

"Load testing is an important part of predicting how your service is going to behave over time. When we are performing load testing, we shouldn't just ask simple questions, such as "How many requests per second is our system capable of serving?" Instead, we should try to understand how our whole system performs under various load conditions. In order to answer this question, we need to understand the infrastructure that makes up our system and the dependencies that a particular service has. For example, is the service behind a load-balancer? How about a CDN? What other caching mechanisms are used? All of these questions and more can be answered by our systems having good observability. Vegeta is an open-source load testing utility designed to test HTTP services with a constant request rate. It's a versatile tool that can be used as a command-line utility or a library. Vegeta allows you to specify targets as URLs in a separate file—optionally with custom headers and request bodies—that can be used as an input to the command-line tool. The command-line tool can then attack the targets in the file, with various options to control the request rate and duration, as well as other variables.Gatling is an open source load testing tool that allows users to script custom scenarios using a Scala-based DSL. Scenarios can go beyond simple straight path testing and involve multiple steps, even simulating user behavior, such as pauses and making decisions about how to proceed based on output in the test. Gatling can be used to automate the load testing of microservices or even browser-based web applications.Vegeta excels at this type of testing, but because it is fed attack targets from a static file, you cannot use Vegeta to build dynamic request paths based on the responses from previous requests. Because Gatling uses a DSL to script load testing scenarios, it's possible to make a request, capture some element of the response, and use that output to make decisions about future requests. "

"Alerting infrastructure is not something you want to build yourself. PagerDuty is an SaaS tool that allows you to create escalation policies and schedules for teams of engineers who are on-call for specific services. Using PagerDuty, you can set up a rotating schedule so that an engineer on a team of five, for example, can expect to be on-call one week in every five. Escalation policies allow you to configure a set of steps in case the on-call engineer is unavailable (perhaps they're driving their car on the freeway). Escalation policies are often configured to page a secondary on-call schedule, a manager, or even the entire team in the event that an incident goes unacknowledged for a certain amount of time. Using a system such as PagerDuty allows engineers on a team to enjoy much-needed off-call time while knowing that customer-impacting incidents will be responded to promptly"

"Prometheus is an open source monitoring and alerting toolkit originally developed in 2012 at SoundCloud. It was inspired by Borgmon at Google. In contrast to the push model employed by systems such as statsd, Prometheus uses a pull model for collecting metrics. Instead of each service being responsible for pushing metrics to a statsd server, Prometheus is responsible for scraping an endpoint exposed by services that have metrics. This inversion of responsibilities provides some benefits when operating metrics at scale. Targets in Prometheus can be configured manually or via service discovery. In contrast to the hierarchical format that systems such as Graphite use to store metrics data, Prometheus employs a multidimensional data model. Time-series data in Prometheus is identified by a metric name (such as http_request_duration_seconds) and one or more labels (such as service=message-service and method=POST). This format can make it easier to standardize metrics across a number of different applications, which is particularly valuable in a microservices architecture. "

""Infrastructure as Code is the process of managing infrastructure-provisioning and maintenance through machine-readable code files rather than manually. Using code to describe the infrastructure allows for effective versioning, reviews, and rollbacks of changes to a system. Being able to automate the process of bringing up a database node or adding a compute node to a cluster frees developers up to worry about their applications, relatively assured that they are not leaving old configurations out in the wild. Together with immutable infrastructure, Infrastructure as Code provides an additional safety net against a system being compromised by vulnerable, forgotten components. HashiCorp Terraform is an open source infrastructure as code (IaC) software tool that allows DevOps engineers to programmatically provision the physical resources an application requires to run. Infrastructure as code is an IT practice that manages an application's underlying IT infrastructure through programming."

"Together with traces and metrics, logs are an essential component of an observable system. Logs are an ordered, timestamped sequence of events that originated in a particular system.In a microservice architecture, the increased complexity of having multiple services makes having good logs essential. The exact criteria that makes logs good is subjective, but generally speaking, good logs should help an engineer piece together events that may have led to a specific error state or bug. Logs are usually organized by levels, a configurable toggle that allows a developer to instruct a service to be more or less verbose with the information sent to logs. While essential for observing the behavior of systems in production, logs can also present privacy and security risks. Having too much information sent from systems to logs can give a would-be attacker information about users of your system, or sensitive information such as tokens or keys that can be used to attack other parts of your system. Having a microservice architecture spreads out this possible attack surface, making it even more important to have a carefully planned strategy for how your services should log information."

" Some organizations go one step further and introduce continuous failure injection as a way of ensuring that systems are handling common failure scenarios smoothly. In early 2011, Netflix announced the creation of the Simian Army—a suite of tools designed to inject common failures into a production environment. Arguably the most famous member of the Simian Army, Chaos Monkey, randomly shuts down nodes in a production environment. The Simian Army tools have been open sourced and are available to use in your own organization. Hosted commercial services have been developed to help automate chaos engineering. Gremlin is a hosted product designed to help teams run Gameday exercises by providing access to a library of "attacks" executed through agents installed on nodes in your environment. Gremlin provides an API and a web interface that allows users to configure attacks designed to spike resource usage (CPU, memory, disk), simulate random failures by killing processes or rebooting hosts, and simulate common network conditions, such as latency and Network Time Protocol (NTP) drift. Having a product like Gremlin lowers the amount of upfront effort needed to start doing failure injection.Another open source tool is the Chaos toolkit, a CLI tool designed to make it easier to design and run experiments."

"There are many great synchronous frameworks to build microservices with Python, like Bottle, Pyramid with Cornice, or Flask."

"The Content Delivery Network (CDN) improves performance and availability by delivering content through a globally distributed network of proxy servers. When a user (usually through their mobile device) makes a request to your API through a CDN, they will create a network connection with one of many points of presence (PoPs), based on their geographic location. Instead of having to make roundtrips to the origin data center for every single request, content can be cached at the edge of a CDN, greatly reducing the response time for the user and reducing unnecessary, costly traffic to the origin. CDNs are a requirement if you plan to have a global user base. If every request to your application's API has to perform a full roundtrip to a single origin, you'll create a subpar experience for users in parts of the world physically distant from the data center that you host your applications in. Even if you host your applications in multiple data centers, you'll never be able to create as high-performing an experience for as many users as you can using a CDN. In addition to performance, CDNs can improve the availability of your application. As we discussed in the previous recipe, many entities in your system are read much more frequently than they are written. In these cases, you can configure your CDN to cache payloads from a service for a specific amount of time (commonly specified by a TTL or time-to-live). Caching responses from your service reduces the amount of traffic to your origin, making it harder to run out of capacity (compute, storage, or network). Additionally, if your service starts to experience high latency, or total or partial failure, the CDN can be configured to serve cached responses instead of continuing to send traffic to a failing service. This allows you to at least be able to serve content to users in the event of service downtime. Some CDN providers have APIs that allow you to automatically invalidate a resource. In these cases, you can instrument your microservice to invalidate a resource just as you would using a Redis- or Memcached-based cache, as discussed in the previous recipe. There are many different CDN providers out there. Some of the large ones include Akamai and Edgecast. Amazon Web Services provides a CDN offering, called CloudFront, that can be configured to serve requests to origin servers in AWS or static resources hosted in S3 buckets. One of the more developer-friendly offerings in the CDN market is from a company called Fastly. Fastly is built using Varnish, an open source web-application accelerator. As a provider, Fastly allows you to upload your own Varnish Configuration Language (VCL) files, effectively allowing you to create caching rules based on any aspect of the request (incoming headers, path segments, query string parameters, and so on). Additionally, Fastly provide a Fast Purge API that allows you to invalidate resources based on a URI."

"The solution to prevent thundering herds is to add a backoff algorithm that exponentially increases the wait period between retries and gives up after a certain number of failures. This approach is referred to as capped exponential backoff. Adding an exponentiallyincreasing sleep function between retries accomplishes half of what we're after—clients will slow down their retry attempts, distributing load over time. Unfortunately, client retries will still be clustered, resulting in periods of time where your service is being hammered by many concurrent requests. The second half of our strategy addresses this problem by adding a randomized value or jitter to our sleep function to distribute the retries over time. To summarize, our retry strategy has the following three requirements:--- Retries must be spaced out using an exponential backoff--- Retries must be randomized by adding jitter---------- Retries must terminate after a specific amount of time------- Most HTTP libraries will have support for a retry strategy that meets these requirements.--------"

"Reliability is becoming an increasingly popular topic in the world of distributed systems. Job postings for Site Reliability Engineers (SRE) or chaos engineers are becoming common, and as more and more organizations move toward cloud-native technologies, it's becoming impossible to ignore that system failure is always a reality. Networks will experience congestion, switches, other hardware components will fail, and a whole host of potential failure modes in systems will surprise us in production. It is impossible to completely prevent failures, so we should try to design our systems to be as tolerant of failure as possible. Microservices provide interesting and useful opportunities to design for reliability. Because microservices encourage us to break our systems into services encapsulating single responsibilities, we can use a number of useful reliability patterns to isolate failures when they do occur. Microservice architectures also present a number of challenges when planning for reliability. Increased reliance on network requests, heterogeneous configurations, multiple data stores and connection pools, and different technical stacks all contribute to an inherently more complex environment where different styles of failure modes can surface. ----------------------Failures in distributed systems can be difficult to debug. A symptom (spikes in latency or a high error rate) can appear far away from the underlying cause (slow database query, garbage collection cycles causing a service to slow down the processing of requests). Sometimes a complete outage can be the result of a failure in a small part of the system, especially when components of the system are having difficulty handling increases in load. Whenever possible, we want to prevent failures in one part of a system from cascading to other parts, causing widespread and hard-to-debug production issues. Furthermore, if a failure is temporary, we'd like our system to be able to self-repair when the failure is over. If a specific service is experiencing problems because of a temporary spike in load, we should design our system in such a way that it prevents requests to the unhealthy service, allowing it time to recover before beginning to send it traffic again. Circuit breakers are used in houses to prevent the overuse of electricity from heating up the internal wiring and burning the house down. A circuit is tripped if the breaker detects that it is being overused and cannot handle the amount of current being drawn from it. After some time passes, the circuit can be closed again, allowing the system to function normally. This same approach can be translated to software and applied to microservice architectures. When a service invokes another service, we should wrap the RPC call in a circuit breaker. If the request fails repeatedly, indicating that the service is unhealthy, the circuit breaker is opened, preventing any further requests from being attempted. The invoking service can then "fail fast" and decide how to handle the failure mode. After a configurable period of time, we can allow another request through, and if it succeeds, close the circuit again, allowing the system to resume normal operation. Some frameworks, such as Twitter's Finagle, automatically wrap RPCs in circuit breakers, keeping track of failures and automatically managing the state of the breaker. Open source service-mesh software, such as Conduit and Linkerd, automatically add circuit breakers to RPCs as well. "

"We can use asynchronous methods to make service calls that are handled in separate threads. This is essential because blocking on network I/O would severely limit the number of incoming requests our service would be able to handle. A service that blocks on the network I/O would only be able to handle a relatively small number of requests per process, requiring us to spend more resources on horizontal scaling. ----------When building multiple microservices, consistency and conventions between services start to make a real impact. When problems arise in a microservice architecture, you can end up spending time debugging many services—being able to make certain assumptions about the nature of a particular service interface can save a lot of time and mental energy. Having a consistent way of doing RPC also allows you to codify certain concerns into libraries that can be easily shared between services. Things such as authentication, how headers should be interpreted, what information is included in a response body, and how to request paginated responses can be made simpler by having a consistent approach. Additionally, the way that errors are reported should be made as consistent as possible. Because the microservice architectures commonly consist of services written in different programming languages by different teams, any efforts toward consistent RPC semantics will have to be implemented, probably as libraries, in as many languages as you have used to build services. This can be cumbersome but is well worth the effort for the consistency clients can assume when speaking to a variety of services. ------------------JSON and HTTP are simple, straightforward solutions for data transportation and definition that should serve the purposes of many microservice architectures. If you want type safety and often better performance, however, it can be worthwhile to look at binary solutions such as Thrift or gRPC. Apache Thrift is an interface definition language (IDL) and binary transport protocol invented at Facebook. It allows you to specify APIs by defining the structs (which are similar to objects in most languages) and exceptions that your service exposes. Thrift interfaces defined in the IDL are used to generate code in a supported language that is then used to manage the RPC calls. Supported languages include C, C++, Python, Ruby, and Java. The benefits of a binary protocol such as Thrift are primarily improved performance and type safety. Depending on the JSON library used, serializing and deserializing large JSON payloads can be quite expensive and JSON does not have any type system that clients can use when handling responses. Additionally, because Thrift includes an IDL that can be used to generate code in any supported language, it's easy to let Thrift handle the generation of both client and server code, cutting down the amount of manual work needing to be done. Because Apache Thrift doesn't use HTTP as the transport layer, services that export Thrift interfaces start their own Thrift server.------------gRPC is an RPC framework originally invented at Google. Unlike Thrift, gRPC makes use of existing technologies, specifically protocol buffers, for its IDL and HTTP/2 for its transport layer. Instead of the Thrift IDL, types and services are defined in a .proto file. The .proto file can then be used to generate code using the protocol buffer's compiler. " "

"APIs are contracts between clients and servers. Backward-incompatible changes to APIs can cause unexpected errors for clients of the service. In a microservices architecture, precautions have to be taken to ensure that changes to a service's API do not unintentionally cause cascading problems throughout the system."

"All of our service-to-service communication recipes have involved having one service call one or more other services directly. This is necessary when the response from the downstream service is required to fulfill the user's request. This isn't always required , however. In cases when you want to react to an event in the system, for example, when you want to send an email or notification or when you want to update an analytics store, using an event-driven architecture is preferable. In this design, one service produces a message to a broker and another application consumes that message and performs an action. This has the benefit of decoupling the publisher from the consumer (so your message service doesn't have to worry about sending email notifications, for instance) and also removing potentially expensive operations off the critical path of the user's request. The event-driven architecture also provides some level of fault tolerance as consumers can fail, and messages can be replayed to retry any failed operations. Apache Kafka is an open source stream-processing platform. At its core, it is an event broker architected as a distributed transaction log."

"Server-side load balancing is a well-established and battle-tested way to distribute load to an application. It has drawbacks, however, in that there is an upper limit to the amount of incoming connections that a single load balancer can handle. This can be at least partially solved with round-robin DNS, which would distribute load to a number of load balancers, but this configuration can quickly become cumbersome and costly. Load balancer applications can also become points of failure in an already-complex microservices architecture. An increasingly popular alternative to server-side load balancing is client-side load balancing. In this convention, clients are responsible for distributing requests evenly to running instances of a service. Clients can keep track of latency and failure rates from nodes and opt to reduce the amount of traffic to nodes that are experiencing high latency or high failure rates. This method of load balancing can be extremely effective and simple, especially in large-scale applications. Ribbon is an open source library developed by Netflix that, among other features, provides support for client-side load balancing."

"There are a number of techniques for load balancing, including round-robin DNS or DNS geolocation. The simplest and most common form of load balancing for microservices is to use a software program that forwards requests to one of a cluster of backend servers. There are a number of different ways load can be distributed, based on the specific load-balancing algorithm used by the load balancer we choose. Simple load-balancing algorithms include round-robin and random choice. More often, in real-world production applications, we'll opt for a load-balancing algorithm that takes reported metrics, such as load or the number of active connections, into account when choosing a node in a cluster to forward a request to. There are a number of popular open source applications that can perform effective load balancing for microservices. HAProxy is a popular open source load balancer that can do TCP and HTTP load balancing. NGINX is a popular open source web server that can be effectively used as a reverse proxy, application server, load balancer, or even HTTP cache. Nowadays, more organizations are in positions to develop microservices that are deployed on cloud platforms, such as Amazon Web Services or Google Cloud Platform, which each have solutions for server-side load balancing. AWS provides a load-balancing solution called Elastic Load Balancing (ELB). ELB can be configured to forward traffic to a member of an Auto Scaling Groups. Auto Scaling Groups are collections of EC2 instances that are treated as a logical group. ELB use health checks (TCP or HTTP) that help the load balancer determine whether to forward traffic to a particular EC2 instance."

" The topologies of microservice architectures are constantly changing. Nodes are being added and removed through auto-scaling, and we have to assume that some nodes will fail either completely or by serving requests with unacceptably high latency. As a microservice architecture grows, you'll need to consider a more feature-rich service-discovery mechanism. When choosing a service-discovery mechanism, the data store used to back your service registry is extremely important. You want a well-tested, battle-worn system. Apache ZooKeeper is an open-source hierarchical key-value store commonly used for distributed locking, service discovery, maintaining configuration information, and other distributed coordination tasks. The development of ZooKeeper was in part motivated by a paper published by Google in 2006 that described Chubby, an internally-developed system for distributed lock storage."

"When discussing service-to-service communication, it's useful to visualize the flow of information in our system. Data flows in both directions–from the client (upstream) to the database, or event bus (downstream) in the form of requests, and back again in the form of responses. When we refer to upstream services, we are describing components of the system that are closer to the user in the flow of information. When we refer to downstream services, we are describing components of the system that are further away from the user–in other words, the user makes a request that is routed to a service that then makes requests to other, downstream services. "

"One of the benefits of using an API Gateway to provide access to microservices is that you can create a single, cohesive API for a specific client. In most cases, you'll want to create a specific API for mobile clients, perhaps even one API for iOS and one for Android. This implementation of API Gateways is commonly referred to as the Backend for Frontend (BFF) because it provides a single logical backend for each frontend application. A web application has very different needs than a mobile device.Failures in a complex system can be hard to diagnose. Often, the symptom can appear far away from the cause. Users might start experiencing higher-than-normal error rates during login because of some downstream service that manages profile pictures or something else tangentially related to user profiles. An error in one service can often propagate needlessly to a user request and adversely impact user experience and therefore trust in your application. Additionally, a failing service can have cascading effects, turning a small system outage into a high-severity, customer-impacting incident. It's important when designing microservices to consider failure isolation and decide how you want to handle different failure scenarios. A number of patterns can be used to improve the resiliency of distributed systems. Circuit breakers are a common pattern used to back off from making requests to a temporarily overwhelmed service. Circuit breakers were first described in Michael Nygard's book Release It!. A calling service defaults to a closed state, meaning requests are sent to the downstream service.If the calling service receives too many failures too quickly, it can change the state of its circuit breaker to open, and start failing fast. Instead of waiting for the downstream service to fail again and adding to the load of the failing service, it just sends an error to upstream services, giving the overwhelmed service time to recover. After a certain amount of time has passed, the circuit is closed again and requests start flowing to the downstream service. There are many available frameworks and libraries that implement circuit breakers. Some frameworks, such as Twitter's Finagle, automatically wrap every RPC call in a circuit breaker.Hystrix is a general-purpose, fault-tolerance library that structures isolated code as commands. When a command is executed, it checks the state of a circuit breaker to decide whether to issue or short circuit the request. ------------In addition to techniques such as circuit breaking, rate limiting can be an effective way to prevent cascading failures in a distributed system. Rate limiting can be effective at preventing spam, protecting against Denial of Service (DoS) attacks, and protecting parts of a system from becoming overloaded by too many simultaneous requests. Typically implemented as either a global or per-client limit, rate limiting is usually part of a proxy or load balancer.Most rate-limiting implementations use the leaky-bucket algorithm—an algorithm that originated in computer network switches and telecommunications networks. As the name suggests, the leaky-bucket algorithm is based on the metaphor of a bucket with a small leak in it that controls a constant rate. Water is poured into the bucket in bursts, but the leak guarantees that water exists in the bucket at a steady, fixed rate. If the water is poured in faster than the water exits the bucket, eventually the bucket will overflow. In this case, the overflow represents requests that are dropped. It's certainly possible to implement your own rate-limiting solution; there are even implementations of the algorithms out there that are open source and available to use. It's a lot easier, however, to use a product such as NGINX to do rate limiting for you."

" Using an edge proxy server to expose your service to the public internet allows you to factor out most of the shared concerns a publicly exposed service must address. Requirements such as request routing, load shedding, back pressure, and authentication can all be handled in a single edge proxy layer instead of being duplicated by every service you need to have exposed to the internet. An edge proxy is a proxy server that sits on the edge of your infrastructure, providing access to internal services. You can think of an edge proxy as the “front door” to your internal service architecture—it allows clients on the internet to make requests to internal services you deploy. There are multiple open source edge proxies that have a robust feature set and community, so we don't have to write and maintain our own edge proxy server. One of the most popular open source edge proxy servers is called Zuul and is built by Netflix. Zuul is an edge service that provides dynamic routing, monitoring, resiliency, security, and more. Zuul is packaged as a Java library. Services written in the Java framework Spring Boot can use an embedded Zuul service to provide edge-proxy functionality. ------------------------Logging, metrics, and configuration are all functionalities that are commonly copied from service to service, resulting in a large amount of boilerplate and copied and pasted code. As your architecture grows and you develop more services, this kind of setup becomes harder and harder to maintain. The usual result is that you end up with a bunch of different ways of doing logging, metrics, service discovery, and so on, which results in systems that are hard to debug and maintain. Changing something as simple as a metrics namespace or adding a feature to your service discovery clients can require the coordination of multiple teams and code bases. More realistically, your microservices architecture will continue to grow with inconsistent logging, metrics, and service discovery conventions, making it harder for developers to operate, contributing to overall operational pain. The sidecar pattern describes a pattern whereby you extend the functionality of a service with a separate process or container running on the same machine. Common functionalities, such as metrics, logging, service discovery, configuration, or even network RPC, can be factored out of your application and handled by a sidecar service running alongside it. This pattern makes it easy to standardize shared concerns within your architecture by implementing them in a separate process that can be used by all of your services. A common method for implementing a sidecar is to build a small, separate process that exposes some functionality over a commonly used protocol, such as HTTP. Imagine, for instance, that you want all of your services to use a centralized service-discovery service instead of relying on DNS hosts and ports to be set in each application's configuration. To accomplish this, you'd need to have up-to-date client libraries for your service-discovery service available in all of the languages that your services and monolith are written in. A better way would be to run a sidecar parallel to each service that runs a service-discovery client. Your services could then proxy requests to the sidecar and have it determine where to send them. As an added benefit, you could configure the sidecar to emit consistent metrics around network RPC requests made between services.-"

"A bounded context is a term from Domain Driven Design (DDD) and it defines the area of a system within which a particular model makes sense. "------------- "Migrating data from a monolith database to a new store fronted by a new service, without any impact on availability or consistency, is a difficult but common task when making the transition to microservices. Using our fictional photo-messaging application, we can imagine a scenario where we want to create a new microservice responsible for handling media uploads. In this scenario, we'd follow a common dual-writing pattern:--------- Before writing a new service to handle media uploads, we'll assume that the monolith architecture looks something like the following diagram, where HTTP requests are being handled by the monolith, which presumably reads the multipart/form-encoded content body as a binary object and stores the file in a distributed file store (Amazon's S3 service, for example). Metadata about the file is then written to a database table, called attachments, ------------------After writing a new service, you now have two write paths. In the write path in the monolith, make a call to your service so that you're replicating the data in the monolith database as well as the database fronted by your new service. You're now duplicating new data and can write a script to backfill older data.--------------. Find all read paths in your Client and Monolith code, and update them to use your new service. All reads will now be going to your service, which will be able to give consistent results. 4. Find all write paths in your Client and Monolith code, and update them to use your new service. All reads and writes are now going to your service, and you can safely delete old data and code paths"

"gRPC is a modern open source high-performance Remote Procedure Call (RPC) framework that can run in any environment. It can efficiently connect services in and across data centers with pluggable support for load balancing, tracing, health checking, and authentication. It is also applicable in last mile of distributed computing to connect devices, mobile applications, and browsers to backend services. -Define your service using Protocol Buffers, a powerful binary serialization toolset, and language, - Install runtime and dev environments with a single line and also scale to millions of RPCs per second with the framework,- Automatically generate idiomatic client and server stubs for your service in a variety of languages and platforms,- Bi-directional streaming and fully integrated pluggable authentication with HTTP/2-based transport. **********As gRPC heavily uses HTTP/2, it is impossible to call a gRPC service from a web browser directly. No modern browser provides the control needed over web requests to support a gRPC client. Therefore, a proxy layer and gRPC-web are required to perform conversions between HTTP/1.1 and HTTP/2.Communication like REST API is possible in gRPC using Unary operations, but when it comes to streaming, gRPC allows full-duplex streaming and uses static paths for communication which eliminates the latency added by path parsing and query parameters. As a result, its performance is better than that of REST API.gRPC uses HTTP/2, which multiplexes multiple calls on a single TCP connection. All gRPC calls over that connection go to one endpoint.What is the difference between REST APIs and gRPC? REST APIs generally use JSON or XML message formats, while gRPC uses protocol buffers. To signal errors, REST APIs use HTTP status codes, while gRPC uses error codes. gRPC's message sizes tend to be dramatically smaller than those of REST APIs."

"gRPC is a modern open source high-performance Remote Procedure Call (RPC) framework that can run in any environment. It can efficiently connect services in and across data centers with pluggable support for load balancing, tracing, health checking, and authentication. It is also applicable in last mile of distributed computing to connect devices, mobile applications, and browsers to backend services. -Define your service using Protocol Buffers, a powerful binary serialization toolset, and language, - Install runtime and dev environments with a single line and also scale to millions of RPCs per second with the framework,- Automatically generate idiomatic client and server stubs for your service in a variety of languages and platforms,- Bi-directional streaming and fully integrated pluggable authentication with HTTP/2-based transport."

"The Common Object Request Broker Architecture (CORBA) is a standard developed by the Object Management Group (OMG) to provide interoperability among distributed objects. CORBA is the world's leading middleware solution enabling the exchange of information, independent of hardware platforms, programming languages, and operating systems. CORBA is essentially a design specification for an Object Request Broker (ORB), where an ORB provides the mechanism required for distributed objects to communicate with one another, whether locally or on remote devices, written in different languages, or at different locations on a network. The CORBA Interface Definition Language, or IDL, allows the development of language and location-independent interfaces to distributed objects. Using CORBA, application components can communicate with one another no matter where they are located, or who has designed them. CORBA provides location transparency to be able to execute these applications. CORBA is often described as a "software bus" because it is a software-based communications interface through which objects are located and accessed. The illustration below identifies the primary components seen within a CORBA implementation.CORBA supports many existing languages. CORBA also supports mixing these languages within a single distributed application. CORBA supports both distribution and Object Orientation. CORBA is an industry standard. This creates competition among vendors and ensures that quality implementations exist. The use of the CORBA standard also provides the developer with a certain degree of portability between implementations. Note: application source is not 100% portable between different CORBA products. CORBA provides a high degree of interoperability. This insures that distributed objects built on top of different CORBA products can communicate. Large companies do not need to mandate a single CORBA product for all development. Over 600 companies back CORBA, including hardware companies, software companies, and cable companies, phone companies, banks, etc. WHAT OTHER TYPES OF DISTRIBUTED SYSTEMS DOES CORBA COMPETE WITH? DCE DCOM EJB RPC (remote procedure calls) Shared memory based interaction Named Pipe communication Socket level programming Message Queuing Other IPC (inter-process communication) mechanisms Database tables, triggers and polling."

"Typical implementations of this abstraction are reliable transport protocols such as TCP on the Internet. By using a reliable point-to-point communication protocol, the application is free from dealing explicitly with issues such as acknowledgments, timeouts, message retransmissions, flow control, and a number of other issues that are encapsulated by the protocol interface."

"In practice, the authenticated perfect links abstraction can be implemented by the TLS protocol on the Internet or by using so-called tunnels constructed with the secure shell (SSH) protocol. These protocols protect the confidentiality and the integrity of transported messages; for providing authenticated links, encryption is not needed and might be turned off to improve performance."

"A combination of (1) a process abstraction, (2) a link abstraction, and possibly (3) a failure-detector abstraction defines a distributed-system model. A recurring tool for designing fault-tolerant algorithms for a set of N processes are quorums. A quorum is a set of processes with special properties. A quorum in a system with N crash-fault process abstractions (according to the fail-stop, fail-noisy, fail-silent, or fail-recovery system model) is any majority of processes, i.e., any set of more than N/2 processes (equivalently, any set of (N+1)/ 2 or more processes). Several algorithms rely on quorums and exploit the fact that every two quorums overlap in at least one process. Note that even if f < N/2 processes fail by crashing, there is always at least one quorum of non-crashed processes in such systems. In a system consisting of arbitrary-fault process abstractions, two majority quorums may not intersect in a correct process. A Byzantine quorum tolerating f faults is a set of more than (N + f)/2 processes (equivalently, any set of (N+f+1)/ 2 or more processes). Two Byzantine quorums always overlap in at least one correct process. To see why this is the case, note that in any Byzantine quorum, there might be f Byzantine processes."

"A log-structured merge-tree (LSM tree) is a data structure typically used when dealing with write-heavy workloads. The write path is optimized by only performing sequential writes. LSM trees are the core data structure behind many databases, including BigTable, Cassandra, Scylla, and RocksDB. LSM trees are persisted to disk using a Sorted Strings Table (SSTable) format. SSTables are a format for storing key-value pairs in which the keys are in sorted order. An SSTable will consist of multiple sorted files called segments. These segments are immutable once they are written to disk. This is solved by using an in-memory tree structure. This is frequently referred to as a memtable, but the underlying data structure is generally some form of a sorted tree like a red-black tree. Once the red-black tree has enough entries, it is flushed to the disk as a segment on disk in sorted order. This allows us to write the segment file as a single sequential write even though the inserts may occur in any order. Compaction is a background process that is continuously combining old segments together into newer segments. Once the compaction process has written a new segment for the input segments, the old segment files are deleted. Whenever a delete request is received, a unique marker called a tombstone is written for that key. Writes are stored in an in-memory tree (also known as a memtable). Any supporting data structures (bloom filters and sparse index) are also updated if necessary. When a read comes in we check the bloom filter. If the bloom filter indicates that the value is not present then we tell the client that the key could not be found. If the bloom filter indicates that the value is present then we begin iterating over our segment files from newest to oldest. For each segment file, we check a sparse index and scan the offsets where we expect the key to be found until we find the key. We'll return the value as soon as we find it in a segment file."

"Concurrency control is provided in a database to: (i) enforce isolation among transactions. (ii) preserve database consistency through consistency preserving execution of transactions. (iii) resolve read-write and write-read conflicts. Various concurrency control techniques are: 1. Two-phase locking Protocol (2PC) -------Locking is an operation which secures: permission to read, OR permission to write a data item. Two phase locking is a process used to gain ownership of shared resources without creating the possibility of deadlock. The 3 activities taking place in the two phase update algorithm are: (i). Lock Acquisition (ii). Modification of Data (iii). Release Lock Two phase locking prevents deadlock from occurring in distributed systems by releasing all the resources it has acquired, if it is not possible to acquire all the resources required without waiting for another process to finish using a lock.----------------- 2. Time stamp ordering Protocol -----This protocol is to order the transactions based on their Timestamps. A schedule in which the transactions participate is then serializable and the only equivalent serial schedule permitted has the transactions in the order of their Timestamp Values. ---------- 3. Multi-version concurrency control (MVCC)-----------Multiversion schemes keep old versions of data item to increase concurrency. Multiversion 2 phase locking: Each successful write results in the creation of a new version of the data item written. Timestamps are used to label the versions. When a read(X) operation is issued, select an appropriate version of X based on the timestamp of the transaction.------------ 4. Validation concurrency control (VCC) 5. Three Phase Commit Protocol (3PC)-----Instead of directly noting the commit decision in its persistent storage, the coordinator first ensures that at least ‘k’ other sites know that it intended to commit transaction. In a situation where coordinator fails, remaining sites are bound to first select new coordinator. This new coordinator checks status of the protocol from the remaining sites. If the coordinator had decided to commit, at least one of other ‘k’ sites that it informed will be up and will ensure that commit decision is respected. The new coordinator restarts third phase of protocol if any of rest sites knew that old coordinator intended to commit transaction. Otherwise, new coordinator aborts the transaction--------------"

"In terms of messages, the performance of the “Log Delivered” algorithm is similar to that of the “Eliminate Duplicates” algorithm. However, algorithm “Log Delivered” requires one log operation every time a new message is received. Delivery is implemented by exposing a log maintained in stable storage. The upper layer is, therefore, required to keep its own record of which messages in the log it has already processed. Thus, the upper layer will generally have the ability to eliminate duplicates and can often operate using the weaker abstraction of stubborn links, avoiding the use of more expensive logged perfect links.<<<<<<

"The perfect point-to-point links abstraction uses crash-stop processes, where a process may crash only once and a correct process never crashes. But the crash-recovery process abstraction, as used by logged perfect links, may crash a finite number of times and is still called correct if it always recovers from a crash. The reliable delivery property requires only that a message is eventually log-delivered if the sender never crashes (and not if the sender is merely correct, as for link abstractions with processes subject to crash faults)."

"With the stubborn links abstraction, it is up to the target process to check whether a given message has already been delivered or not. Adding mechanisms for detecting and suppressing message duplicates, in addition to mechanisms for message retransmission, allows us to build an even higher-level primitive: the perfect links abstraction, sometimes also called the reliable links abstraction. Perfect links are characterized by three properties. The reliable delivery property together with the no duplication property ensures that every message sent by a correct process is delivered by the receiver exactly once if the receiver is also correct. The third property, no creation, is the same as in the other link abstractions"

"Fair-loss links are characterized by three properties. The fair-loss property guarantees that a link does not systematically drop every message. Therefore, if the sender process and the recipient process are both correct, and if the sender keeps retransmitting a message, the message is eventually delivered. The finite duplication property intuitively ensures that the network does not repeatedly perform more retransmissions than that performed by the sending process. Finally, the no creation property ensures that no message is created or corrupted by the network."

"A digital signature scheme provides data authentication in systems with multiple entities that need not share any information beforehand. Physical realizations of digital signatures associate a public-key/private-key pair with an entity. The private key is given to the entity and must remain secret; the public key is accessible to anyone. With the private key, the entity can produce a signature for a statement of its choice. The public key is associated with the identity of an entity, and everyone with access to the public key can verify that the signature on the statement is valid. It is infeasible for any entity that does not know the private key to come up with a statement that was never signed and to forge a valid signature on it.Digital signatures are based on public-key cryptography (or asymmetric cryptography); because of their underlying mathematical structure, they add considerable computational overhead compared to the symmetric cryptographic primitives."

"Message-Authentication Codes (MACs) A message-authentication code (MAC) authenticates data between two entities. It is based on a shared symmetric key, which is known only to the sender and to the receiver of a message, but to nobody else. For a message of its choice the sender can compute an authenticator for the receiver. Given an authenticator and a message, the receiver can verify that the message has indeed been authenticated by the sender. It is infeasible for any other entity than the sender and the verifier to come up with a message that was never authenticated and to produce an authenticator that the receiver accepts as valid during verification."

"Algorithms that operate in untrusted environments, where messages may be exposed to a malicious adversary, rely on cryptographic methods for their protection. The basic cryptographic primitives considered here are: hash functions, MACs, and digital signatures. The physical implementations of the cryptographic abstractions usually rely on some keys being present at all processes. Distributing the right keys to all participants in a distributed computation is the task of key management"

"When a distributed system operates in an untrusted environment, some of its components may become exposed to an adversary or even fall under its control. A relatively benign form of adversarial action occurs when a process leaks information obtained in an algorithm to an outside entity. The outsider may eavesdrop on multiple processes in this way and correlate all leaked pieces of information with each other. Faults of this kind threaten the confidentiality of the data handled by an algorithm, such as the privacy of messages that are disseminated by a broadcast algorithm or the secrecy of data written to a storage abstraction. We call this an eavesdropping fault of a process.Eavesdropping faults typically affect communication links before they affect the processes; hence, one usually assumes that if any process is susceptible to eavesdropping faults then all communication links are also affected by eavesdropping and leak all messages to the adversary. Eavesdropping can be prevented by cryptography, in particular by encrypting communication messages and stored data. "

"According to the crash-recovery abstraction, a process can crash and stop to send messages, but might recover later. This can be viewed as an omission fault, with one exception, however: a process might suffer amnesia when it crashes and lose its internal state. This significantly complicates the design of algorithms because, upon recovery, the process might send new messages that contradict messages that the process might have sent prior to the crash. To cope with this issue, we sometimes assume that every process has, in addition to its regular volatile memory, a stable storage (also called a log), which can be accessed through store and retrieve operations. Upon recovery, we assume that a process is aware that it has crashed and recovered. In particular, a specific  Recovery  event is assumed to be automatically generated by the runtime environment whenever the process recovers, in a similar manner to the  Init  event that is generated whenever a process starts executing some algorithm. The processing of the  Recovery  event should, for instance, retrieve the relevant state of the process from stable storage before the processing of other events is resumed. The process might, however, have lost all the remaining data that was preserved in volatile memory. This data should thus be properly reinitialized. The  Init  event is considered atomic with respect to recovery. More precisely, if a process crashes in the middle of its initialization procedure and recovers say, without having finished the procedure properly, the process resumes again with processing the initialization procedure and then continues to process the  Recovery  event"

"An omission fault occurs when a process does not send (or receive) a message that it is supposed to send (or receive) according to its algorithm. In general, omission faults are due to buffer overflows or network congestion that cause messages to be lost. With an omission, the process deviates from the algorithm assigned to it by dropping some messages that should have been exchanged with other processes."

"It is also important to notice that, in practice, the crash-stop process abstraction neither precludes the possibility of recovery nor does it mean that recovery should be prevented for a given algorithm (assuming a crash-stop process abstraction) to behave correctly. It simply means that the algorithm should not rely on some of the processes to recover in order to pursue its execution. These processes might not recover or might recover only after a long period encompassing the crash detection and then the restarting delay. In some sense, an algorithm that is not relying on crashed processes to recover would typically be faster than an algorithm relying on some of the processes to recover."

"Useful distributed services are supposed to provide both liveness and safety properties. Formulating an abstraction with only one kind of property is usually a sign for a flawed specification. Consider, for instance, the traditional interprocess communication service of a reliable, ordered data stream: it ensures that messages exchanged between two processes are neither lost nor duplicated, and are received in the order in which they were sent. As we pointed out, requiring that messages are not lost is a liveness property. Requiring that messages are not duplicated and that they are received in the order in which they were sent are safety properties."

"After exchanging some messages, the processes may be faced with several alternative plans of action. They may need to reach a consensus on a common plan, out of several alternatives, and each participating process may have initially its own plan, different from the plans of the other processes. ------------------------- • In some cases, it may be acceptable for the cooperating processes to take a given step only if all other processes also agree that such a step should take place. If this condition is not met, all processes must agree that the step should not take place. This form of agreement is crucial in the processing of distributed transactions, where this problem is known as the atomic commitment problem. ------------------------------------- • Processes may not only need to agree on which actions they should execute but also need to agree on the order in which these actions should be executed. This form of agreement is the basis of one of the most fundamental techniques to replicate computation in order to achieve fault tolerance, and it is called the totalorder broadcast problem.

"A quorum is the minimum number of votes that a distributed transaction has to obtain in order to be allowed to perform an operation in a distributed system. A quorum-based technique is implemented to enforce consistent operation in a distributed system."

"Nakamoto consensus is as it is defined in the Bitcoin whitepaper where nodes vote to enforce the rules used to build the blocks that make up the Bitcoin public ledger. It is a Byzantine fault tolerant consensus algorithm that utilises the concept of Proof of Work and economic incentives to manage decision making rights. Nakamoto consensus defines an honest node as a node that seeks out the longest valid chain of blocks and applies proof of work to extend that chain. In this context, the longest chain represents greatest proof of work effort on the valid chain. If the majority of nodes are honest, then the honest chain will grow with the greatest proof of work and outrun any other competing chains. By choosing which chain to build upon, the nodes vote to enforce the rules that govern the protocol, and use of the Blockchain as a global financial ledger with legal and regulatory oversight. Through Nakamoto consensus, proof of work on the longest chain becomes an economic and technical barrier for any attacker to overcome. At the same time, the block reward as an economic incentive drives the node to follow the consensus, encouraging honesty and cooperation between competing enterprise Miners. The security of Nakamoto consensus has been studied by academia and tested in the real world since 2009."

"practical Byzantine Fault Tolerance(pBFT)---------Practical Byzantine Fault Tolerance is a consensus algorithm introduced in the late 90s by Barbara Liskov and Miguel Castro. pBFT was designed to work efficiently in asynchronous(no upper bound on when the response to the request will be received) systems. It is optimized for low overhead time. Its goal was to solve many problems associated with already available Byzantine Fault Tolerance solutions. Application areas include distributed computing and blockchain. Byzantine Fault Tolerance(BFT) is the feature of a distributed network to reach consensus(agreement on the same value) even when some of the nodes in the network fail to respond or respond with incorrect information. The objective of a BFT mechanism is to safeguard against the system failures by employing collective decision making(both – correct and faulty nodes) which aims to reduce to influence of the faulty nodes. BFT is derived from Byzantine Generals’ Problem.-------------- Types of Byzantine Failures: There are two categories of failures that are considered. One is fail-stop(in which the node fails and stops operating) and other is arbitrary-node failure. Some of the arbitrary node failures are given below : Failure to return a result Respond with an incorrect result Respond with a deliberately misleading result Respond with a different result to different parts of the system--------------Advantages of pbft: Energy efficiency : pBFT can achieve distributed consensus without carrying out complex mathematical computations(like in PoW). Zilliqa employs pBFT in combination with PoW-like complex computations round for every 100th block. Transaction finality : The transactions do not require multiple confirmations(like in case of PoW mechanism in Bitcoin where every node individually verifies all the transactions before adding the new block to the blockchain; confirmations can take between 10-60 minutes depending upon how many entities confirm the new block) after they have been finalized and agreed upon. Low reward variance : Every node in the network takes part in responding to the request by the client and hence every node can be incentivized leading to low variance in rewarding the nodes that help in decision making.---------------pBFT consensus rounds are broken into 4 phases: The client sends a request to the primary(leader) node. The primary(leader) node broadcasts the request to the all the secondary(backup) nodes. The nodes(primary and secondaries) perform the service requested and then send back a reply to the client. The request is served successfully when the client receives ‘m+1’ replies from different nodes in the network with the same result, where m is the maximum number of faulty nodes allowed.----------Limitations of pBFT: The pBFT consensus model works efficiently only when the number of nodes in the distributed network is small due to the high communication overhead that increases exponentially with every extra node in the network. Sybil attacks : The pBFT mechanisms are susceptible to Sybil attacks, where one entity(party) controls many identities. As the number of nodes in the network increase, sybil attacks become increasingly difficult to carry out. But as pBFT mechanisms have scalability issues too, the pBFT mechanism is used in combination with other mechanism(s). Scaling : pBFT does not scale well because of its communication(with all the other nodes at every step) overhead. As the number of nodes in the network increase(increases as O(n^k), where n is the messages and k is the number of nodes), so does the time taken to respond to the request. Platforms using pBFT variants: Zilliqa – pBFT in combination with PoW consensus Hyperledger Fabric – permissioned version of pBFT Tendermint – pBFT + DPoS(Delegated Proof-of-Stake) Variations of pBFT: To enhance the quality and performance of pBFT for specific use cases and conditions, many variations were proposed and employed. Some of them are : RBFT – Redundant BFT ABsTRACTs Q/U HQ – Hybrid Quorum Protocol for BFT Adapt Zyzzyva – Speculative Byzantine Fault Tolerance Aardvark"

"A consensus algorithm is a process in computer science used to achieve agreement on a single data value among distributed processes or systems. These algorithms are designed to achieve reliability in a network involving multiple users or nodes. Solving this issue -- known as the consensus problem -- is important in distributed computing and multi-agent systems such as those seen in cryptocurrency blockchain networks.Consensus algorithms are vital in large-scale, fault-tolerant systems because they enable a set of distributed/replicated machines or servers to work as a coherent group and agree on system state, even in the presence of failures or outages. To achieve this, the algorithm sets a threshold, or the number of member machines that must reach consensus or agreement. As they solve a consensus problem, consensus algorithms assume some processes and systems will be unavailable and that only a portion of the nodes will respond. They also assume some communications will be lost during transmission. However, a response is required from the available nodes. For example, an algorithm may require that at least 51% of nodes respond to achieve consensus or agreement on a data value or network state.Consensus algorithms synchronize state machine replicas and ensure consistency among them. They're often used to achieve trust and security across a decentralized computer network, such as blockchain, and are very useful for recordkeeping. In addition to blockchain and cryptocurrencies, these algorithms support many real-world computing and digital systems, including: replication of state machines, Google's PageRank, load balancing, smart power grids, clock synchronization and control of unmanned aerial vehicles like drones.-------------------1. Proof of Work The PoW algorithm is one of the oldest types of consensus algorithms. First introduced in 1993 -- and reintroduced in 2008 by Bitcoin founder Satoshi Nakamoto -- the central idea of PoW is to have nodes solve complex mathematical puzzles and make as many guesses as possible in the fastest possible time. In cryptocurrency blockchains based on the PoW algorithm, miners or validators -- also known as participant nodes -- must prove that the work they've done and submitted gives them the right to add new transactions to the blockchain. They must solve a complex mathematical problem by finding a cryptographic hash of a particular block.it maintains network security and is fairly resistant to cyber attacks like DDoS attacks.----------------- Delayed Proof of Work (dPoW) is a modified version of the PoW consensus algorithm. In this consensus method, the blockchain network takes periodic snapshots of itself which are then written into a block on the network as part of a notarization process. This process helps to create a backup of the entire system on the blockchain.-----------------------------Proof of Stake (PoS) is considered an alternative to PoW. Unlike PoW, PoS requires little specialized hardware or software resources to mine cryptocurrencies since it doesn't involve solving complex computational problems. Rather, crypto validators lock up or stake some of their coins in a wallet. They then validate blocks if they discover a block that can be added to the blockchain. Validators get a reward -- or their stake increases -- proportionate to their bets based on the blocks added to the blockchain. Since the algorithm is incentive-based, it consumes less computational energy than PoW.-------------Delegated Proof of Stake (DPoS) is considered a more efficient and democratic version of PoS. This algorithm is based on a voting system in which delegates or witnesses vote for their favorite validators to achieve consensus during the generation and validation of blocks. Besides validating transactions, delegates also help maintain the integrity, reliability and transparency of the blockchain network.-----------------The Proof of Authority (PoA) consensus algorithm is a more efficient and scalable alternative to the power-hungry and less scalable PoW algorithm. Furthermore, in PoA, block validators stake their reputation and identities rather than coins, making the system more secure than PoS. Essentially, a PoA-based blockchain network is secured by a limited number of validating nodes. These nodes are trusted parties that are arbitrarily chosen and pre-approved to verify blocks and transactions. These participants act as system moderators and help create a more scalable mechanism than PoW.---------------------Proof of Burn (PoB) is being tested as a viable and sustainable alternative to PoW and PoS algorithms. PoB is like PoW, but it consumes much less computational energy. This is because its block validation process on the blockchain doesn't require computational resources or hardware. Instead, miners "burn" or invest coins in the blockchain to achieve consensus.-----------A hybrid PoW/PoS mechanism counterbalances the weaknesses of PoW and PoS algorithms. It starts by having PoW miners create new blocks to add to a blockchain. After the blocks are created, PoS miners vote to confirm or reject them. During the process, they stake a portion of their tokens as in the PoS algorithm."

"Sybil Attack is a type of attack seen in peer-to-peer networks in which a node in the network operates multiple identities actively at the same time and undermines the authority/power in reputation systems. The main aim of this attack is to gain the majority of influence in the network to carry out illegal(with respect to rules and laws set in the network) actions in the system. A single entity(a computer) has the capability to create and operate multiple identities(user accounts, IP address-based accounts). To outside observers, these multiple fake identities appear to be real unique identities."

""Paxos — A distributed consensus algorithm-----Paxos is an algorithm that is used to achieve consensus among a distributed set of computers that communicate via an asynchronous network. The Paxos protocol was introduced in 1989 by Leslie Lamport, named after a fictional legislative consensus system used on the Paxos island in Greece. To maintain the same ordering of commands among multiple replicas so that all the replicas eventually converge to the same value.One or more clients proposes a value to Paxos and we have consensus when a majority of systems running Paxos agrees on one of the proposed values. Paxos is widely used and is legendary in computer science since it is the first consensus algorithm that has been rigorously proved to be correct. Paxos simply selects a single value from one or more values that are proposed to it and lets everyone know what that value is. A run of the Paxos protocol results in the selection of single proposed value. If you need to use Paxos to create a replicated log (for a replicated state machine, for example), then you need to run Paxos repeatedly. This is called multi-Paxos. There are some optimizations that could be implemented for multi-Paxos but we will not discuss those here. Paxos provides abortable consensus. This means that some processes abort the consensus if there is contention while others decide on the value. Those processes that decide have to agree on the same value. Aborting allows a process to terminate rather than be blocked indefinitely. When a client proposes a value to Paxos, it is possible that the proposed value might fail if there was a competing concurrent proposal that won. The client will then have to propose the value again to another run of the Paxos algorithm.----------------------Paxos has three entities: Proposers: Receive requests (values) from clients and try to convince acceptors to accept their proposed values. Acceptors: Accept certain proposed values from proposers and let proposers know if something else was accepted. A response from an acceptor represents a vote for a particular proposal. Learners: Announce the outcome. In practice, a single node may run proposer, acceptor, and learner roles. It is common for Paxos to coexist with the service that requires consensus (e.g., distributed storage) on a set of replicated servers, with each server taking on all three roles rather than using separate servers dedicated to Paxos. For the sake of discussing the protocol, however, we consider these to be independent entities.********************Engineering Paxos for the real world------------------------ Paxos defines a protocol for single-value distributed consensus but does not consider other factors that are needed to get Paxos to run in real environments. Some of these factors are: ------------------------------------------ Single run vs. multi-run: Paxos yields consensus for a single value. Much of the time, we need to make consensus decisions repeatedly, such as keeping a replicated log or state machine synchronized. For this we need to run Paxos multiple times. This environment is called multi-Paxos. -------------------- Group management: The cluster of systems that are running Paxos needs to be administered. We need to be able to add systems to the group, remove them, and detect if any processes, entire systems, or network links are dead. Each proposer needs to know the set of acceptors so it can communicate with them and needs to know the learners (if those are present). Paxos is a fault-tolerant protocol but the mechanisms for managing the group are outside of its scope. We can turn to something like the group membership service of Isis virtual synchrony to track this.--------------- Byzantine failures: We assumed that none of the systems running Paxos suffer Byzantine failures. That is, either they run and communicate correctly or they stay silent. In real life, however, Byzantine failures do exist. We can guard against network problems with mechanisms such as checksums or, if we fear malicious interference, digital signatures. However, we do need to worry about a misbehaving proposer that may inadvertantly set its proposal ID to infinity (e.g., INFINITY in math.h in C or math.inf in Python if using floats; otherwise INT_MAX in C or sys.maxint in Python). This puts the Paxos protocol into a state where acceptors will have to reject any other proposal.--------------- Location of servers: Possibly the most common use of Paxos is in implementing replicated state machines, such as a distributed storage system. To ensure that replicas are consistent, incoming operations must be processed in the same order on all systems. A common way of doing this is to use a replicated log. That is, each of the servers will maintain a log that is sequenced identically to the logs on the other servers. A consensus algorithm will decide the next value that goes on the log. Then, each server simply processes the log in order and applies the requested operations. In these environments, and most others, each server also serves as a Paxos node, running the functions of proposer, acceptor, and learner. A client can send a message to any server, which invokes some operation that updates the replicated state machine (e.g., replicated storage service). In this case, the proposer will often be co-resident with the server that the client contacted. The request from the user is the value for a proposal that will be originated by that node. The proposer on that node manages its proposal ID numbers and sends proposals to all the acceptors it can reach, including itself. These acceptors accept the requests via the Paxos protocol. When the node knows that consensus has been reached, the operation can be applied to the log and propagated to the other servers. If another node tries to propose something concurrently, one of the proposals will be told that another proposal has already been accepted and it will get a different value so it will carry out the Paxos protocol to achieve consensus on that accepted value. It will then have to try again later, running Paxos again, to get its own value into the log.------------------Livelock: If the rate of incoming requests from different replicas is higher than the acceptance rate, each request will be rejected by a newer request with a higher number, resulting in no request being committed even if the system is up and running. This situation is called Livelock.---------Egalitarian Paxos, Flexible Paxos"

"The Publish/Subscribe pattern, also known as pub/sub, is an architectural design pattern that provides a framework for exchanging messages between publishers and subscribers. This pattern involves the publisher and the subscriber relying on a message broker that relays messages from the publisher to the subscribers. The host (publisher) publishes messages (events) to a channel that subscribers can then sign up to. Although Pub/Sub is based on earlier design patterns like message queuing and event brokers, it is more flexible and scalable. The key to this is the fact Pub/Sub enables the movement of messages between different components of the system without the components being aware of each other’s identity.Chat applications are a classic use case of the Pub/Sub pattern. In a chat application, participants can subscribe to chat rooms which have a designated Pub/Sub topic. When a user sends a message to a chat room, her chat app instance publishes the message on that chat room’s topic. Subscribers of the topic receive the message.Event messaging: pub/sub powers many realtime interactions across domains like EdTech, B2B platforms, and delivery logistics. As we shop online more frequently for a wider variety of goods, package delivery has become commonplace. Logistics companies need to use delivery resources more efficiently. To optimize delivery, dispatching systems need up-to-date information on where their drivers are. Pub/sub event messaging helps logistics companies do this. Dispatchers need to access drivers’ location information on demand, ideally continually. Having this data at the ready allows them to better predict arrival times and improve routing solutions. Dispatching systems also send out information such as cancellations, traffic information, and new package pickups."

"Open Connect is the name of the global network that is responsible for delivering Netflix TV shows and movies to our members world-wide. This type of network is typically referred to as a “Content Delivery Network” or “CDN” because its job is to deliver internet-based content (via HTTP/HTTPS) efficiently by bringing the content that people watch close to where they’re watching it. The Open Connect network shares some characteristics with other CDNs, but also has some important differences. Netflix began the Open Connect initiative in 2011, as a response to the ever-increasing scale of Netflix streaming. We started the program for two reasons: 1) As Netflix grew to be a significant portion of overall traffic on consumer Internet Service Provider (ISP) networks, it became important to be able to work with those ISPs in a direct and collaborative way. 2) Creating a content delivery solution customized for Netflix allowed us to design a proactive, directed caching solution that is much more efficient than the standard demand-driven CDN solution, reducing the overall demand on upstream network capacity by several orders of magnitude.All of our OCA deployments, whether in IXPs or embedded in ISP networks, are constantly monitored by the Open Connect Operations team to ensure reliability and efficiency. We troubleshoot and proactively fix most issues remotely with minimal input required from our ISP partners. If partners wish to monitor their own embedded OCAs’ status and performance, we provide a Partner Portal where they can do so. If hardware performance degrades to the point where a server is no longer functioning in the range of our quality standards, we simply replace it - at no cost to our partners."

"where it may be beneficial to shard a database: The amount of application data grows to exceed the storage capacity of a single database node. The volume of writes or reads to the database surpasses what a single node or its read replicas can handle, resulting in slowed response times or timeouts. The network bandwidth required by the application outpaces the bandwidth available to a single database node and any read replicas, resulting in slowed response times or timeouts. Before sharding, you should exhaust all other options for optimizing your database. Some optimizations you might want to consider include: Setting up a remote database. Implementing caching. Upgrading to a larger server. "

"Partitioning is the database process where very large tables are divided into multiple smaller parts. By splitting a large table into smaller, individual tables, queries that access only a fraction of the data can run faster because there is less data to scan. The main goal of partitioning is to aid in maintenance of large tables and to reduce the overall response time to read and load data for particular SQL operations. <-----------Horizontal partitioning — also known as sharding-------->Sharding is actually a type of database partitioning, more specifically, Horizontal Partitioning. Sharding, is replicating [copying] the schema, and then dividing the data based on a shard key onto a separate database server instance, to spread load. For example, queries that filter data based on short date ranges are ideal for horizontal sharding since the date range will necessarily limit querying to only a subset of the servers. Every distributed table has exactly one shard key. A shard key can contain any number of columns.Con: If the value whose range is used for sharding isn’t chosen carefully, the partitioning scheme will lead to unbalanced servers.<----------- Vertical partitioning--------->Vertical sharding is effective when queries tend to return only a subset of columns of the data. For example, if some queries request only names, and others request only addresses, then the names and addresses can be sharded onto separate servers.An ideal scenario for this type of partition is when you don’t need all the information about the customer in your query. Divide data for a specific feature to their own server. When you have different types of data in your database, such as names, dates, and pictures. You could keep the string values in SQL DB (expensive), and pictures in an Azure Blob (cheap). Pro: Straightforward to implement. Low impact on the application. Con: To support the growth of the application, a database may need further partitioning.*********Directory-based partitioning A lookup service that knows the partitioning scheme and abstracts it away from the database access code. Allow the addition of DB servers or change of partitioning schema without impacting the application. Con: Can be a single point of failure.--------------Sharding and partitioning are both about breaking up a large data set into smaller subsets. The difference is that sharding implies the data is spread across multiple computers while partitioning does not. Partitioning is about grouping subsets of data within a single database instance. In many cases, the terms sharding and partitioning are even used synonymously, especially when preceded by the terms “horizontal” and “vertical.” Thus, “horizontal sharding” and “horizontal partitioning” can mean the same thing.--------------->Key or hash-based partitioning: Apply a hash function to some key attribute of the entry to get the partition number.---Problem 1. Adding new servers may require changing the hash function, which would need a redistribution of data and downtime for the service. 2. Workaround: consistent hashing.--------> Round-robin partitioning With n partitions, the i tuple is assigned to partition i % n.----------->Joins and denormalization Joins will not be performance efficient since data has to be compiled from multiple servers. Workaround: denormalize the database so that queries can be performed from a single table. But this can lead to data inconsistency.----------><-------Referential integrity Difficult to enforce data integrity constraints (e.g. foreign keys). Workaround 1. Referential integrity is enforced by the application code. 2. Applications can run SQL jobs to clean up dangling references.----->"

"Apache ZooKeeper is a service used by a cluster (group of nodes) to coordinate between themselves and maintain shared data with robust synchronization techniques. ZooKeeper is itself a distributed application providing services for writing a distributed application. The common services provided by ZooKeeper are as follows − Naming service − Identifying the nodes in a cluster by name. It is similar to DNS, but for nodes. Configuration management − Latest and up-to-date configuration information of the system for a joining node. Cluster management − Joining / leaving of a node in a cluster and node status at real time. Leader election − Electing a node as leader for coordination purpose. Locking and synchronization service − Locking the data while modifying it. This mechanism helps you in automatic fail recovery while connecting other distributed applications like Apache HBase. Highly reliable data registry − Availability of data even when one or a few nodes are down. Distributed applications offer a lot of benefits, but they throw a few complex and hard-to-crack challenges as well. ZooKeeper framework provides a complete mechanism to overcome all the challenges. Race condition and deadlock are handled using fail-safe synchronization approach. Another main drawback is inconsistency of data, which ZooKeeper resolves with atomicity."

"Redis is an open source in-memory data store, which is often used as a distributed cache. You can configure an Azure Redis Cache for an Azure-hosted ASP.NET Core app, and use an Azure Redis Cache for local development. Scalability, High Availability, Fault-tolerance are crucial to the large scale services running online today. Businesses cannot afford to have their services go offline. Think about health services, stock markets, military. They have no scope for going down. They are distributed across multiple nodes with a pretty solid amount of redundancy. What Are the Different Types Of Distributed Caching Strategies?Cache Aside This is the most common caching strategy, in this approach the cache works along with the database trying to reduce the hits on it as much as possible. The data is lazy loaded in the cache. When the user sends a request for particular data. The system first looks for it in the cache. If present it’s simply returned from it. If not, the data is fetched from the database, the cache is updated and is returned to the user<*****Cache Aside ----------> This kind of strategy works best with read-heavy workloads. The kind of data which is not much frequently updated, for instance, user profile data in a portal. His name, account number etc.<**********Read-Through--------> This strategy is pretty similar to the Cache Aside strategy with the subtle differences such as in the Cache Aside strategy the system has to fetch information from the database if it is not found in the cache but in Read-through strategy, the cache always stays consistent with the database. The cache library takes the onus of maintaining the consistency with the backend; The Information in this strategy too is lazy loaded in the cache, only when the user requests it. So, for the first time when information is requested it results in a cache miss, the backend has to update the cache while returning the response to the user. <************Write-Through In this strategy, every information written to the database goes through the cache. Before the data is written to the DB, the cache is updated with it. This maintains high consistency between the cache and the database though it adds a little latency during the write operations as data is to be updated in the cache additionally. This works well for write-heavy workloads like online massive multiplayer games.<**************Write-Back-------->In the Write-back caching strategy the data is directly written to the cache instead of the database. And the cache after some delay as per the business logic writes data to the database. If there are quite a heavy number of writes in the application. Developers can reduce the frequency of database writes to cut down the load & the associated costs. A risk in this approach is if the cache fails before the DB is updated, the data might get lost. Again this strategy is used with other caching strategies to make the most out of these.The popular distributed caches used in the industry are Eh-cache, Memcache, Redis, Riak, Hazelcast. Memcache is used by Google Cloud in its Platform As A Service. It is a high performant distributed key-value store primarily used in alleviating the database load. It’s like a large hash table distributed across several machines. Enabling data access in O(1) i’e constant time. Besides having the key-value pair Redis is an open-source in-memory distributed system which supports other data structures too such as distributed lists, queues, strings, sets, sorted sets. Besides caching, Redis is also often treated as a NoSQL data store."

"A distributed cache is a system that pools together the random-access memory (RAM) of multiple networked computers into a single in-memory data store used as a data cache to provide fast access to data. While most caches are traditionally in one physical server or hardware component, a distributed cache can grow beyond the memory limits of a single computer by linking together multiple computers–referred to as a distributed architecture or a distributed cluster–for larger capacity and increased processing power. Distributed caches are especially useful in environments with high data volume and load. The distributed architecture allows incremental expansion/scaling by adding more computers to the cluster, allowing the cache to grow in step with the data growth."

"Consistent Hashing is a distributed hashing scheme that operates independently of the number of servers or objects in a distributed hash table. It powers many high-traffic dynamic websites and web applications. A hash function is a function that maps one piece of data—typically describing some kind of object, often of arbitrary size—to another piece of data, typically an integer, known as hash code, or simply hash. Using a hash function ensures that resources required by computer programs are efficiently stored in memory and that in-memory data structures are loaded evenly to make information retrieval more efficient. n the classic hashing method, we always assume that: The number of memory locations is known, and This number never changes. It’s common for a cluster to scale up and down, and there are always unexpected failures in a distributed system. The problem in a distributed system with simple rehashing —moving the placement of every key — is that state is stored on each node. A small change in the cluster size could result in a reshuffle of all the data in the cluster. As the cluster size grows, this becomes unsustainable because the amount of work required for each hash change grows linearly with cluster size. It represents the resource requestors (which I shall refer to as ‘requests’) and the server nodes in a virtual ring structure known as a hashring. The number of locations is no longer fixed, but the ring is considered to have an infinite number of points, and the server nodes can be placed at random locations on this ring. (Of course, choosing this random number again can be done using a hash function, but the second step of dividing it by the number of available locations is skipped as it is no longer a finite number). The requests, that is, the users, computers or serverless programs, which are analogous to keys in the classic hashing approach, are also placed on the same ring using the same hash function. we can use a simple data structure that comprises the following: An array of hashes that correspond to nodes in the ring. A map (hash table) for finding the node corresponding to a particular request."

"By default, these XMPP chats are unencrypted. That's where OMEMO comes in. With OMEMO end-to-end encryption, XMPP offers comparable security to Signal, Session, and any other private chat app you've heard of, but without the risks involved with being dependent on one centralized platform. OMEMO is an extension that adds end-to-end encryption to XMPP. It isn't the first. Other methods came first, such as OpenPGP and OTR (Off-the-Record Communication). What OMEMO offers is not merely end-to-end encryption, but multi-end-to-multi-end encryption. Hence the name, OMEMO Multi-End Message and Object Encryption (yes, it's a recursive acronym). What does multi-end-to-multi-end encryption mean? In short, it means that when you send a message from your laptop, you can still view that message from your phone and any other device signed in to your account. The recipient can then view the message on any of their devices as well. Yet OMEMO keeps messages encrypted on the various servers, so only you and the intended recipient can read them. OMEMO was originally based on the Signal Protocol, which Open Whisper Systems created for the Signal app. Unlike the Signal Protocol, which is centralized, OMEMO needs to handle encryption across multiple servers. OMEMO began as a 2015 Google Summer of Code project to implement multi-end-to-multi-end encryption into the Conversations Android app. OMEMO doesn't just allow for private messages. You can also transfer files privately as well.Forward secrecy. This means the encryption keys are stored on your device, and any device that does not have access to the messages at the time they are sent is unable to view the message."

"XMPP Protocol--------->XMPP is a short form for Extensible Messaging Presence Protocol. XMPP (also known as Jabber) is well-established instant messaging protocol millions have used. Various popular messaging apps began as XMPP chat clients before morphing into something walled off and proprietary. In simpler terms, XMPP is a decentralized messaging standard akin to email. Anyone can create an XMPP account on one server and chat with someone registered on another server. Like email, no one company has either access to or control over everyone's data. You can choose from different XMPP providers, just like you can choose between different email providers. Why use XMPP? Privacy: XMPP is as private as you want it to be. By default, it isn't inherently private. Decentralization: Centralized services come with many conveniences. It's easy to find contacts to message, everyone has the same experience, and updates can go out to everyone simultaneously. Flexibility and Choice: With most chat platforms, you're stuck using the official messaging app or website. Longevity."

"A coder or encoder encodes a data stream or a signal for transmission or storage, possibly in encrypted form, and the decoder function reverses the encoding for playback or editing. Codecs are used in videoconferencing, streaming media, and video editing applications. Two principal techniques are used in codecs, pulse-code modulation and delta modulation. Codecs are often designed to emphasize certain aspects of the media to be encoded. For example, a digital video (using a DV codec) of a sports event needs to encode motion well but not necessarily exact colors, while a video of an art exhibit needs to encode color and surface texture well. Audio codecs for cell phones need to have very low latency between source encoding and playback. In contrast, audio codecs for recording or broadcast can use high-latency audio compression techniques to achieve higher fidelity at a lower bit-rate."

"Traces allow developers to: • debug issues affecting very specific requests, which can be used to investigate support requests; • debug rare issues that affect only an extremely small fraction of requests; • debug issues that affect a large fraction of requests, like high response times for requests that hit a specific subset of service instances; • Identify bottlenecks in the end-to-end request path; • Identify which clients hit which downstream services and in what proportion (also referred to as resource attribution), which can be used for rate-limiting or billing purposes. When a request begins, it’s assigned a unique trace id. The trace id is propagated from one stage to another at every fork in the local execution flow from one thread to another and from caller to callee in a network call (through HTTP headers, for example). Each stage is represented with a span — an event containing the trace id. When a span ends, it’s emitted to a collector service, which assembles it into a trace by stitching it together with the other spans belonging to the same trace. Popular distributed tracing collectors include Open Zipkin, and AWS X-ray. Tracing is challenging to retrofit into an existing system as it requires every component in the request path to be modified and propagate the trace context from one stage to the other. And it’s not just the components that are under your control that need to support tracing; the frameworks and open source libraries you use need to support it as well, just like third-party services." .

"A log is an immutable list of time-stamped events that happened over time. An event can have different formats. In its simplest form, it’s just free-form text. It can also be structured and represented with a textual format like JSON, or a binary one like Protobuf. When structured, an event is typically represented with a bag of key-value pairs. Logs can originate from your services and external dependencies, like message brokers, proxies, databases, etc. Most languages offer libraries that make it easy to emit structured logs. Logs are typically dumped to disk files, which are rotated every so often, and forwarded by an agent to an external log collector asynchronously, like an ELK stack or AWS CloudWatch logs. Logs provide a wealth of information about everything that’s happening in a service. They are particularly helpful for debugging purposes, as they allow us to trace back the root cause from a symptom, like a service instance crash. They also help to investigate long-tail behaviors that are missed by metrics represented with averages and percentiles, which can’t help explain why a specific user request is failing. Logs are very simple to emit, particularly free-form textual ones. But that’s pretty much the only advantage they have compared to metrics and other instrumentation tools. Logging libraries can add overhead to your services if misused, especially when they are not asynchronous and logging blocks while writing to stdout or disk. Also, if the disk fills up due to excessive logging, the service instance might get itself into a degraded state. At best, you lose logging, and at worst, the service instance stops working if it requires disk access to handle requests. Ingesting, processing, and storing a massive trove of data is not cheap either, no matter whether you plan to do this in-house or use a third-party service. Although structured binary logs are more efficient than textual ones, they are still expensive due to their high dimensionality. Finally, but not less important, logs have a high noise to signal ratio because they are fine-grained and service-specific, which makes it challenging to extract useful information from them."

"At the core of observability, we find telemetry sources like metrics, event logs, and traces. Metrics are stored in time-series data stores that have high throughput, but struggle to deal with metrics that have many dimensions. Conversely, event logs and traces end up in transactional stores that can handle high-dimensional data well, but struggle with high throughput. Metrics are mainly used for monitoring, while event logs and traces mainly for debugging. Observability is a superset of monitoring. While monitoring is focused exclusively on tracking the health of a system, observability also provides tools to understand and debug it. Monitoring on its own is good at detecting failure symptoms, but less so to explain their root cause."

"A distributed system is never 100% healthy at any given time as there can always be something failing. A whole range of failure modes can be tolerated, thanks to relaxed consistency models and resiliency mechanisms like rate limiting, retries, and circuit breakers. Unfortunately, they also increase the system’s complexity. And with more complexity, it becomes increasingly harder to reason about the multitude of emergent behaviours the system might experience. "

"Once the incident has been mitigated, the next step is to brainstorm ways to prevent it from happening again. The more widespread the impact was, the more time you should spend on this. Incidents that burned a significant fraction of an SLO’s error budget require a postmortem. A postmortem’s goal is to understand an incident’s root cause and come up with a set of repair items that will prevent it from happening again. There should also be an agreement in the team that if an SLO’s error budget is burned or the number of alerts spirals out of control, the whole team stops working on new features to focus exclusively on reliability until a healthy on-call rotation has been restored."

": Dashboards should be tailored to their audience. This dashboard displays metrics about the system’s public API endpoints, which helps operators identifying problematic paths during an incident. For each endpoint, the dashboard exposes several metrics related to request messages, request handling and response messages, like: • Number of requests received or messaged pulled from a messaging broker, size of requests, authentication issues, etc. • Request handling duration, availability and response time of external dependencies, etc. • Counts per response type, size of responses, etc.**************** Service dashboard******A service dashboard displays service-specific implementation details, which require a deep understanding of its inner workings. Unlike the previous dashboards, this one is primarily used by the team that owns the service. Beyond service-specific metrics, a service dashboard should also contain metrics for upstream dependencies like load balancers and messaging queues, and downstream dependencies like data stores. This dashboard offers a first entry point into the behavior of a service when debugging. As we will later learn when discussing observability, this high-level view is just the starting point. The operator typically drills down into the metrics by segmenting them further, and eventually reaches for raw logs and traces to get more detail."

"A service-level objective (SLO) defines a range of acceptable values for an SLI within which the service is considered to be in a healthy state . An SLO sets the expectation to its users of how the service should behave when it’s functioning correctly. Service owners can also use SLOs to define a service-level agreement (SLA) with their users — a contractual agreement that dictates what happens when an SLO isn’t met, typically resulting in financial consequences. For example, an SLO could define that 99% of API calls to endpoint X should complete below 200 ms, as measured over a rolling window of 1 week. Another way to look at it, is that it’s acceptable for up to 1% of requests within a rolling week to have a latency higher than 200 ms. That 1% is also called the error budget, which represents the number of failures that can be tolerated. SLOs are helpful for alerting purposes and help the team prioritize repair tasks with feature work. For example, the team can agree that when an error budget has been exhausted, repair items will take precedence over new features until the SLO is restored. Also, an incident’s importance can be measured by how much of the error budget has been burned. An incident that burned 20% of the error budget needs more afterthought than one that burned only 1%. Smaller time windows force the team to act quicker and prioritize bug fixes and repair items, while longer windows are better suited to make long-term decisions about which projects to invest in. Therefore it makes sense to have multiple SLOs with different window sizes. How strict should SLOs be? Choosing the right target range is harder than it looks. If it’s too loose, you won’t detect userfacing issues; if it’s too strict, you will waste engineering time micro-optimizing and get diminishing returns. Even if you could guarantee 100% reliability for your system, you can’t make guarantees for anything that your users depend on to access your service that is outside your control, like their last-mile connection. Thus, 100% reliability doesn’t translate into a 100% reliable experience for users."

"one of the main use cases for metrics is alerting. That doesn’t mean we should create alerts for every possible metric out there — for example, it’s useless to be alerted in the middle of the night because a service had a big spike in memory consumption a few minutes earlier. In this section, we will discuss one specific metric category that lends itself well for alerting. A service-level indicator (SLI) is a metric that measures one aspect of the level of service provided by a service to its users, like the response time, error rate, or throughput. SLIs are typically aggregated over a rolling time window and represented with a summary statistic, like average or percentile. SLIs are best defined with a ratio of two metrics, good events over total number of events, since they are easy to interpret: 0 means the service is broken and 1 that everything is working as expected. These are some commonly used SLIs for services: • Response time — The fraction of requests that are completed faster than a given threshold. • Availability — The proportion of time the service was usable, defined as the number of successful requests over the total number of requests. • Quality — The proportion of requests served in an undegraded state (assuming the system degrades gracefully). • Data completeness (for storage systems) — The proportion of records persisted to a data store that can be successfully accessed later."

"A metric is a numeric representation of information measured over a time interval and represented as a time-series, like the number of requests handled by a service. Conceptually, a metric is a list of samples, where each sample is represented by a floating-point number and a timestamp. Modern monitoring systems allow a metric to be tagged with a set of key-value pairs called labels, which increases the dimensionality of the metric. Essentially, every distinct combination of labels is a different metric. This has become a necessity as modern services can have a large amount of metadata associated with each metric, like datacenter, cluster, node, pod, service, etc. High-cardinality metrics make it easy to slice and dice the data, and eliminate the instrumentation cost of manually creating a metric for each label combination. A service should emit metrics about its load, internal state, and availability and performance of downstream service dependencies. Combined with the metrics emitted by downstream services, this allows operators to identify problems quickly. The agent batches these events and emits them periodically to a remote telemetry service, which persists them in a dedicated data store for event logs. For example, this is the approach taken by Azure Monitor’s log-based metrics5 . As you can imagine, this is quite expensive since the load on the backend increases with the number of events ingested. Events are also costly to aggregate at query time — suppose you want to retrieve the number of failures in North Europe over the past month; you would have to issue a query that requires fetching, filtering, and aggregating potentially trillions of events within that time period. Is there a way to reduce costs at query time? Because metrics are time-series, they can be modeled and manipulated with mathematical tools. The samples of a time-series can be pre-aggregated over pre-specified time periods (e.g., 1 second, 5 minutes, 1 hour, etc.) and represented with summary statistics such as the sum, average, or percentiles. For example, the telemetry backend can pre-aggregate metrics over one or more time periods at ingestion time. The backend can create multiple pre-aggregates with different periods. Then at query time, the pre-aggregated metric with the best period that satisfies the query is chosen. For example, CloudWatch6 (the telemetry backend used by AWS) pre-aggregates data as it’s ingested. We can take this idea one step further and also reduce ingestion costs by having the local telemetry agents pre-aggregate metrics on the client side. Client and server-side pre-aggregation drastically reduces bandwidth, compute, and storage requirements for metrics. However, it comes at a cost; operators lose the flexibility to re-aggregate metrics after they have been ingested, as they no longer have access to the original events that generated them. For example, if a metric is pre-aggregated over a period of time of 1 hour, it can’t later be re-aggregated over a period of 5 min without the original events. Because metrics are mainly used for alerting and visualization purposes, they are usually persisted in pre-aggregated form in a timeseries data store since querying pre-aggregated data can be several order of magnitudes more efficient than the alternative."

"Blackbox monitoring is good at detecting the symptoms when something is broken; in contrast, white-box monitoring can help identify the root cause of known hard-failure modes before users are impacted. As a rule of thumb, if you can’t design away a hard-failure mode, you should add monitoring for it. The longer a system has been around, the better you will understand how it can fail and what needs to be monitored."

"A variety of health signals can be used to make that decision, such as: • the result of end-to-end tests; • health metrics like latencies and errors; • alerts; • and health endpoints. Monitoring just the health signals of the service being rolled out is not enough. The CD pipeline should also monitor the health of upstream and downstream services to detect any indirect impact of the rollout. The pipeline should allow enough time to pass between one step and the next (bake time) to ensure that it was successful, as some issues can appear only after some time has passed. For example, a performance degradation could be visible only at peak time. The CD pipeline can further gate the bake time on the number of requests seen for specific API endpoints to guarantee that the API surface has been properly exercised. To speed up the release, the bake time can be reduced after each step succeeds and confidence is built up. When a health signal reports a degradation, the CD pipeline stops. At that point, it can either roll back the artifact automatically, or trigger an alert to engage the engineer on-call, who needs to decide whether a rollback is warranted or not . Based on their input, the CD pipeline retries the stage that failed (e.g., perhaps because something else was going into production at the time), or rolls back the release entirely. The operator can also stop the pipeline and wait for a new artifact with a hotfix to be rolled forward. This might be necessary if the release can’t be rolled back because a backward-incompatible change has been introduced. Since rolling forward is much riskier than rolling back, any change introduced should always be backward compatible as a rule of thumb. The most common cause for backward-incompatibility is changing the serialization format used either for persistence or IPC purposes. To safely introduce a backward-incompatible change, it needs to be broken down into multiple backward-compatible changes . For example, suppose the messaging schema between a producer and a consumer service needs to change in a backward incompatible way. In this case, the change is broken down into three smaller changes that can individually be rolled back safely: In the prepare change, the consumer is modified to support both the new and old messaging format. • In the activate change, the producer is modified to write the messages in the new format. • Finally, in the cleanup change, the consumer stops supporting the old messaging format altogether. This change should only be released once there is enough confidence that the activated change won’t need to be rolled back. An automated upgrade-downgrade test part of the CD pipeline in pre-production can be used to validate whether a change is actually safe to roll back or not."

" A checklist can help the reviewer not to forget anything important: • Does the change include unit, integration, and end-to-end tests as needed? • Does the change include metrics, logs, and traces? • Can this change break production by introducing a backward-incompatible change, or hitting some service limit? • Can the change be rolled back safely, if needed? Code changes shouldn’t be the only ones going through this review process. For example, cloud resource templates, static assets, end-to-end tests, and configuration files should all be version-controlled in a repository (not necessarily the same) and be treated just like code. The same service can then have multiple CD pipelines, one for each repository, that can potentially run in parallel. I can’t stress enough the importance of reviewing and releasing configuration changes with a CD pipeline. One of the most common causes of production failures are configuration changes applied globally without any prior review or testing. Once the change has been merged into the repository’s main branch, the CD pipeline moves to the build stage, in which the repository’s content is built and packaged into a deployable release artifact."

"You can use a test double in place of a real dependency to reduce the test’s size, making it faster and less prone to intermittent failures. There are different types of test doubles: • A fake is a lightweight implementation of an interface that behaves similarly to a real one. For example, an in-memory version of a database is a fake. • A stub is a function that always returns the same value no matter which arguments are passed to it. • Finally, a mock has expectations on how it should be called, and it’s used to test the interactions between objects. The problem with test doubles is that they don’t resemble how the real implementation behaves with all its nuances. The less the resemblance is, the less confidence you should have that the test using the double is actually useful. Therefore, when the real implementation is fast, deterministic, and has few dependencies, use that rather than a double. If that’s not the case, you have to decide how realistic you want the test double to be, as there is a tradeoff between its fidelity and the test’s size. When using the real implementation is not an option, use a fake maintained by the same developers of the dependency, if one is available. Stubbing, or mocking, are last-resort options as they offer the least resemblance to the actual implementation, which makes tests that use them brittle. For integration tests, a good compromise is to use mocking with contract tests . A contract test defines the request it intends to send to an external dependency and the response it expects to receive from it. This contract is then used by the test to mock the external dependency. For example, a contract for a REST API consists of an HTTP request and response pair. To ensure that the contract doesn’t break, the test suite of the external dependency uses the same contract to simulate a client and ensure that the expected response is returned."

"An end-to-end test validates behavior that spans multiple services in the system, like a user-facing scenario.These tests usually run in shared environments, like staging or production. Because of their scope, they are slow and more prone to intermittent failures. End-to-end tests should not have any impact on other tests or users sharing the same environment. Among other things, that requires services to have good fault isolation mechanisms, like rate-limiting, to prevent buggy tests from affecting the rest of the system. End-to-end tests can be painful and expensive to maintain. For example, when an end-to-end test fails, it’s not always obvious which service is responsible and deeper investigation is required. But they are a necessary evil to ensure that user-facing scenarios work as expected across the entire application. They can uncover issues that tests with smaller scope can’t, like unanticipated side effects and emergent behaviors. One way to minimize the number of end-to-end tests is to frame them as user journey tests. A user journey test simulates a multistep interaction of a user with the system (e.g. for e-commerce service: create an order, modify it, and finally cancel it). Such a test usually requires less time to run than splitting the test into N separate end-to-end tests. As the scope of a test increases, it becomes more brittle, slow, and costly. Intermittently-failing tests are nearly as bad as no tests at all, as developers stop having any confidence in them and eventually ignore their failures. When possible, prefer tests with smaller scope as they tend to be more reliable, faster, and cheaper. A good trade-off is to have a large number of unit tests, a smaller fraction of integration tests, and even fewer end-to-end tests."

"The SUT represents the scope of the test, and depending on it, the test can be categorized as either a unit test, an integration test, or an end-to-end test. A unit test validates the behavior of a small part of the codebase, like an individual class. A good unit test should be relatively static in time and change only when the behavior of the SUT changes — refactoring, fixing a bug, or adding a new feature shouldn’t require a unit test to change. To achieve that, a unit test should: • use only the public interfaces of the SUT; • test for state changes in the SUT (not predetermined sequence of actions); • test for behaviors, i.e., how the SUT handles a given input when it’s in a specific state. An integration test has a larger scope than a unit test, since it verifies that a service can interact with its external dependencies as expected. This definition is not universal, though, because integration testing has different meanings for different people. Martin Fowler makes the distinction between narrow and broad integration tests. A narrow integration test exercises only the code paths of a service that communicate with an external dependency, like the adapters and their supporting classes. In contrast, a broad integration test exercises code paths across multiple live services."

"One of the main reasons to build distributed services is to be able to withstand single-process failures. Since you are designing your system under the assumption that any process can crash at any time, your service needs to be able to deal with that eventuality. For a process’s crash to not affect your service’s health, you should ensure ideally that: there are other processes that are identical to the one that crashed that can handle incoming requests; • requests are stateless and can be served by any process; • any non-volatile state is stored on a separate and dedicated data store so that when the process crashes its state isn’t lost; • all shared resources are leased so that when the process crashes, the leases expire and the resources can be accessed by other processes; • the service is always running slightly over-scaled to withstand the occasional individual process failures. Because crashes are inevitable and your service is prepared for them, you don’t have to come up with complex recovery logic when a process gets into some weird degraded state — you can just let it crash. A transient but rare failure can be hard to diagnose and fix. Crashing and restarting the affected process gives operators maintaining the service some breathing room until the root-cause can be identified, giving the system a kind of self-healing property. Imagine that a latent memory leak causes the available memory to decrease over time. When a process doesn’t have more physical memory available, it starts to swap back and forth to the page file on disk. This swapping is extremely expensive and degrades the process’s performance dramatically. If left unchecked, the memory leak would eventually bring all processes running the service on their knees. Would you rather have the processes detect they are degraded and restart themselves, or try to debug the root cause for the degradation at 3 AM? To implement this pattern, a process should have a separate background thread that wakes up periodically — a watchdog — that monitors its health. For example, the watchdog could monitor the available physical memory left. When any monitored metric breaches a configured threshold, the watchdog considers the process degraded and deliberately restarts it. The watchdog’s implementation needs to be well-tested and monitored since a bug could cause the processes to restart continuously."

"A liveness health test is the most basic form of checking the health of a process. The load balancer simply performs a basic HTTP request to see whether the process replies with a 200 (OK) status code. A local health test checks whether the process is degraded or in some faulty state. The process’s performance typically degrades when a local resource, like memory, CPU, or disk, is either close enough to be fully saturated, or is completely saturated. To detect a degradation, the process compares one or more local metrics, like memory available or remaining disk space, with some fixed upper and lower-bound thresholds. When a metric is above an upper-bound threshold, or below a lower-bound one, the process reports itself as unhealthy. A more advanced, and also harder check to get right, is the dependency health check. This type of health check detects a degradation caused by a remote dependency, like a database, that needs to be accessed to handle incoming requests. The process measures the response time, timeouts, and errors of the remote calls directed to the dependency. If any measure breaks a predefined threshold, the process reports itself as unhealthy to reduce the load on the downstream dependency. But here be dragons : if the downstream dependency is temporarily unreachable, or the health-check has a bug, then it’s possible that all the processes behind the load balancer fail the health check. In that case, a naive load balancer would just take all service instances out of rotation, bringing the entire service down! A smart load balancer instead detects that a large fraction of the service instances is being reported as unhealthy and considers the health check to no longer be reliable. Rather than continuing to remove processes from the pool, it starts to ignore the health-checks altogether so that new requests can be sent to any process in the pool."

"If the server is behind a load balancer and can communicate that it’s overloaded, the balancer can stop sending requests to it. The process can expose a health endpoint that when queried performs a health check that either returns 200 (OK) if the process can serve requests, or an error code if it’s overloaded and doesn’t have more capacity to serve requests. The health endpoint is periodically queried by the load balancer. If the endpoint returns an error, the load balancer considers the process unhealthy and takes it out of the pool. Similarly, if the request to the health endpoint times out, the process is also taken out of the pool. Health checks are critical to achieving high availability; if you have a service with 10 servers and one is unresponsive for some reason, then 10% of the requests will fail, which will cause the service’s availability to drop to 90%."

"The goal of the bulkhead pattern is to isolate a fault in one part of a service from taking the entire service down with it. The pattern is named after the partitions of a ship’s hull. If one partition is damaged and fills up with water, the leak is isolated to that partition and doesn’t spread to the rest of the ship. Some clients can create much more load on a service than others. Without any protections, a single greedy client can hammer the system and degrade every other client. We have seen some patterns, like rate-limiting, that help prevent a single client from using more resources than it should. But rate-limiting is not bulletproof. You can rate-limit clients based on the number of requests per second; but what if a client sends very heavy or poisonous requests that cause the servers to degrade? In that case, rate-limiting wouldn’t help much as the issue is intrinsic with the requests sent by that client, which could eventually lead to degrading the service for every other client. When everything else fails, the bulkhead pattern provides guaranteed fault isolation by design. The idea is to partition a shared resource, like a pool of service instances behind a load balancer, and assign each user of the service to a specific partition so that its requests can only utilize resources belonging to the partition it’s assigned to. Consequently, a heavy or poisonous user can only degrade the requests of users within the same partition. For example, suppose there are 10 instances of a service behind a load balancer, which are divided into 5 partitions . In that case, a problematic user can only ever impact 20 percent of the service’s instances. The problem is that the unlucky users who happen to be on the same partition as the problematic one are fully impacted. Can we do better?We can introduce virtual partitions that are composed of a random subset of instances. This can make it much more unlikely for another user to be allocated to the exact same virtual partition. You need to be careful when applying the bulkhead pattern; if you take it too far and create too many partitions, you lose all the economy-of-scale benefits of sharing costly resources across a set of users that are active at different times. You also introduce a scaling problem. Scaling is simple when there are no partitions and every user can be served by any instance, as you can just add more instances. It’s not that easy with a partitioned pool of instances as some partitions are much hotter than others."

"we need to store two integers per API key, one for each bucket. When a new request comes in, the process receiving it could fetch the bucket, update it and write it back to the data store. But, that wouldn’t work because two processes could update the same bucket concurrently, which would result in a lost update. To avoid any race conditions, the fetch, update, and write operations need to be packaged into a single transaction. Although this approach is functionally correct, it’s costly. There are two issues here: transactions are slow, and executing one per request would be crazy expensive as the database would have to scale linearly with the number of requests. On top of that, for each request a process receives, it needs to do an outgoing call to a remote data store. What should it do if it fails? Let’s address these issues. Rather than using transactions, we can use a single atomic get-and-increment operation that most data stores provide. Alternatively, the same can be emulated with a compare-and-swap . Atomic operations have much better performance than transactions. Now, rather than updating the database on each request, the process can batch bucket updates in memory for some time, and flush them asynchronously to the database at the end of it. This reduces the shared state’s accuracy, but it’s a good trade-off as it reduces the load on the database and the number of requests sent to it.What happens if the database is down? Remember the CAP theorem’s essence: when there is a network fault, we can either sacrifice consistency and keep our system up, or maintain consistency and stop serving requests. In our case, temporarily rejecting all incoming requests just because the database used for rate-limiting is not reachable could be very damaging to the business. Instead, it’s safer to keep serving requests based on the last state read from the store."

"With bucketing, we can compress the information about the number of requests seen in a way that doesn’t grow as the number of requests does. Now that we have a memory-friendly representation, how can we use it to implement rate-limiting? The idea is to use a sliding window that moves in real-time across the buckets, keeping track of the number of requests within it. The sliding window represents the interval of time used to decide whether to rate-limit or not. The window’s length depends on the time unit used to define the quota, which in our case is 1 minute. But, there is a caveat: a sliding window can overlap with multiple buckets. To derive the number of requests under the sliding window, we have to compute a weighted sum of the bucket’s counters, where each bucket’s weight is proportional to its overlap with the sliding window. We only have to store as many buckets as the sliding window can overlap with at any given time. For example, with a 1-minute window and a 1-minute bucket length, the sliding window can touch at most 2 buckets. And if it can touch at most two buckets, there is no point to store the third oldest bucket, the fourth oldest one, and so on. To summarize, this approach requires two counters per API key, which is much more efficient in terms of memory than the naive implementation storing a list of requests per API key."

"Rate-limiting, or throttling, is a mechanism that rejects a request when a specific quota is exceeded. A service can have multiple quotas, like for the number of requests seen, or the number of bytes received within a time interval. Quotas are typically applied to specific users, API keys, or IP addresses. For example, if a service with a quota of 10 requests per second, per API key, receives on average 12 requests per second from a specific API key, it will on average, reject 2 requests per second tagged with that API key. When a service rate-limits a request, it needs to return a response with a particular error code so that the sender knows that it failed because a quota has been breached. For services with HTTP APIs, the most common way to do that is by returning a response with status code 429 (Too Many Requests). The response should include additional details about which quota has been breached and by how much; it can also include a Retry-After header indicating how long to wait before making a new request: HTTP/1.1 429 Too Many Requests Retry-After: 60 If the client application plays by the rules, it stops hammering the service for some time, protecting it from non-malicious users monopolizing it by mistake. This protects against bugs in the clients that, for one reason or another, cause a client to repeatedly hit a downstream service for no good reason. Rate-limiting is also used to enforce pricing tiers; if a user wants to use more resources, they also need to be prepared to pay more. This is how you can offload your service’s cost to your users: have them pay proportionally to their usage and enforce pricing tiers with quotas. You would think that rate-limiting also offers strong protection against a denial-of-service (DDoS) attack, but it only partially protects a service from it. Nothing forbids throttled clients from continuing to hammer a service after getting 429s. And no, ratelimited requests aren’t free either — for example, to rate-limit a request by API key, the service has to pay the price to open a TLS connection, and to the very least download part of the request to read the key. Although rate-limiting doesn’t fully protect against DDoS attacks, it does help reduce their impact. Economies of scale are the only true protection against DDoS attacks. If you run multiple services behind one large frontend service, no matter which of the services behind it are attacked, the frontend service will be able to withstand the attack by rejecting the traffic upstream. The beauty of this approach is that the cost of running the frontend service is amortized across all the services that are using it. Although rate-limiting has some similarities to load shedding, they are different concepts. Load shedding rejects traffic based on the local state of a process, like the number of requests concurrently processed by it; rate-limiting instead sheds traffic based on the global state of the system, like the total number of requests concurrently processed for a specific API key across all service instances"

"Load-shedding and load leveling don’t address an increase in load directly, but rather protect a service from getting overloaded. To handle more load, the service needs to be scaled out. This is why these protection mechanisms are typically combined with autoscaling, which detects that the service is running hot and automatically increases its scale to handle the additional load."

"A server has very little control over how many requests it receives at any given time, which can deeply impact its performance. The operating system has a connection queue per port with a limited capacity that, when reached, causes new connection attempts to be rejected immediately. But typically, under extreme load, the server crawls to a halt before that limit is reached as it starves out of resources like memory, threads, sockets, or files. This causes the response time to increase to the point the server becomes unavailable to the outside world. When a server operates at capacity, there is no good reason for it to keep accepting new requests since that will only end up degrading it. "

"The circuit breaker is implemented as a state machine that can be in one of three states: open, closed and half-open. In the closed state, the circuit breaker is merely acting as a passthrough for network calls. In this state, the circuit breaker tracks the number of failures, like errors and timeouts. If the number goes over a certain threshold within a predefined time-interval, the circuit breaker trips and opens the circuit. When the circuit is open, network calls aren’t attempted and fail immediately. As an open circuit breaker can have business implications, you need to think carefully what should happen when a downstream dependency is down. If the down-stream dependency is non-critical, you want your service to degrade gracefully, rather than to stop entirely. Think of an airplane that loses one of its non-critical sub-systems in flight; it shouldn’t crash, but rather gracefully degrade to a state where the plane can still fly and land. Another example is Amazon’s front page; if the recommendation service is not available, the page should render without recommendations. It’s a better outcome than to fail the rendering of the whole page entirely. After some time has passed, the circuit breaker decides to give the downstream dependency another chance, and transitions to the half-open state. In the half-open state, the next call is allowed to pass-through to the downstream service. If the call succeeds, the circuit breaker transitions to the closed state; if the call fails instead, it transitions back to the open state. That’s really all there is to understand how a circuit breaker works, but the devil is in the details. How many failures are enough to consider a downstream dependency down? How long should the circuit breaker wait to transition from the open to the half-open state? It really depends on your specific case; only by using data about past failures can you make an informed decision."

"Suppose your service uses timeouts to detect communication failures with a downstream dependency, and retries to mitigate transient failures. If the failures aren’t transient and the downstream dependency keeps being unresponsive, what should it do then? If the service keeps retrying failed requests, it will necessarily become slower for its clients. In turn, this slowness can propagate to the rest of the system and cause cascading failures. To deal with non-transient failures, we need a mechanism that detects long-term degradations of downstream dependencies and stops new requests from being sent downstream in the first place. After all, the fastest network call is the one you don’t have to make. This mechanism is also called a circuit breaker, inspired by the same functionality implemented in electrical circuits. A circuit breaker’s goal is to allow a sub-system to fail without bringing down the whole system with it. To protect the system, calls to the failing sub-system are temporarily blocked. Later, when the sub-system recovers and failures stop, the circuit breaker allows calls to go through again. Unlike retries, circuit breakers prevent network calls entirely, which makes the pattern particularly useful for long-term degradations. In other words, retries are helpful when the expectation is that the next call will succeed, while circuit breakers are helpful when the expectation is that the next call will fail."

"When you make a network call, you can configure a timeout to fail the request if there is no response within a certain amount of time. If you make the call without setting a timeout, you tell your code that you are 100% confident that the call will succeed. Would you really take that bet? Unfortunately, some network APIs don’t have a way to set a timeout in the first place. When the default timeout is infinity, it’s all too easy for a client to shoot itself in the foot. As mentioned earlier, network calls that don’t return lead to resource leaks at best. Timeouts limit and isolate failures, stopping them from cascading to the rest of the system. And they are useful not just for network calls, but also for requesting a resource from a pool and for synchronization primitives like mutexes. To drive the point home on the importance of setting timeouts, let’s take a look at some concrete examples. JavaScript’s XMLHttpRequest is the web API to retrieve data from a server asynchronously. Its default timeout is zero , which means there is no timeout. Client-side timeouts are as crucial as server-side ones. There is a maximum number of sockets your browser can open for a particular host. If you make network requests that never return, you are going to exhaust the socket pool. When the pool is exhausted, you are no longer able to connect to the host. The fetch web API is a modern replacement for XMLHttpRequest that uses Promises. When the fetch API was initially introduced, there was no way to set a timeout at all . Browsers have recently added experimental support for the Abort API4 to support timeouts. Things aren’t much rosier for Python. The popular requests library uses a default timeout of infinity. Modern HTTP clients for Java and .NET do a much better job and usually come with default timeouts. For example, .NET Core HttpClient has a default timeout of 100 seconds . It’s lax but better than not setting a timeout at all. As a rule of thumb, always set timeouts when making network calls, and be wary of third-party libraries that do network calls or use internal resource pools but don’t expose settings for timeouts. And if you build libraries, always set reasonable default timeouts and make them configurable for your clients. Ideally, you should set your timeouts based on the desired false timeout rate . Say you want to have about 0.1% false timeouts; to achieve that, you should set the timeout to the 99.9th percentile of the remote call’s response time, which you can measure empirically. You also want to have good monitoring in place to measure the entire lifecycle of your network calls, like the duration of the call, the status code received, and if a timeout was triggered. We will talk about monitoring later in the book, but the point I want to make here is that you have to measure what happens at the integration points of your systems, or you won’t be able to debug production issues when they show up. Ideally, you want to encapsulate a remote call within a library that sets timeouts and monitors it for you so that you don’t have to remember to do this every time you make a network call. No matter which language you use, there is likely a library out there that implements some of the resiliency and transient fault-handling patterns introduced in this chapter, which you can use to encapsulate your system’s network calls. Using a language-specific library is not the only way to wrap your network calls; you can also leverage a reverse proxy co-located on the same machine which intercepts all the remote calls that your process makes . The proxy enforces timeouts and also monitors the calls, relinquishing your process from the responsibility to do so."

"Every system has a limit to how much load it can withstand without scaling. Depending on how the load increases, you are bound to hit that brick wall sooner or later. One thing is an organic increase in load that gives you the time to scale out your service accordingly, but another is a sudden and unexpected spike. For example, consider the number of requests received by a service in a period of time. The rate and the type of incoming requests can change over time, and sometimes suddenly, for a variety of reasons: • The requests might have a seasonality — depending on the hour of the day, the service is going to get hit by users in different countries. • Some requests are much more expensive than others and abuse the system in ways you might have not anticipated, like scrapers slurping in data from your site at super-human speed. • Some requests are malicious, like DDoS attacks that try to saturate your service’s bandwidth, denying access to the service for legitimate users. To withstand unexpected load, you need to prepare beforehand."

"From an observer’s point of view, a very slow process is not very different from one that isn’t running at all — neither can perform useful work. Resource leaks are one of the most common causes of slow processes. Whenever you use resources, especially when they have been leased from a pool, there is a potential for leaks. Memory is the most well-known source of leaks. A memory leak causes a steady increase in memory consumption over time. Runtimes with garbage collection don’t help much either; if a reference to an object that is no longer needed is kept somewhere, the object won’t be deleted by the garbage collector. A memory leak keeps consuming memory until there is no more of it, at which point the operating system starts swapping memory pages to disk constantly, while the garbage collector kicks in more frequently trying its best to release any shred of memory. The constant paging and the garbage collector eating up CPU cycles make the process slower. Eventually, when there is no more physical memory, and there is no more space in the swap file, the process won’t be able to allocate more memory, and most operations will fail. Memory is just one of the many resources that can leak. For example, if you are using a thread pool, you can lose a thread when it blocks on a synchronous call that never returns. If a thread makes a synchronous blocking HTTP call without setting a timeout, and the call never returns, the thread won’t be returned to the pool. Since the pool has a fixed size and keeps losing threads, it will eventually run out of threads. You might think that making asynchronous calls, rather than synchronous ones, would help in the previous case. However, modern HTTP clients use socket pools to avoid recreating TCP connections and pay a hefty performance fee. If a request is made without a timeout, the connection is never returned to the pool. As the pool has a limited size, eventually there won’t be any connections left. On top of that, the code you write isn’t the only one accessing memory, threads, and sockets. The libraries your application depends on access the same resources, and they can do all kinds of shady things. Without digging into their implementation, assuming it’s open in the first place, you can’t be sure whether they can wreak havoc or not."

"why the client hasn’t received a response so far: • the server is slow; • the client’s request has been dropped by a network switch, router or proxy; • the server has crashed while processing the request; • or the server’s response has been dropped by a network switch, router or proxy. Slow network calls are the silent killers of distributed systems. Because the client doesn’t know whether the response is on its way or not, it can spend a long time waiting before giving up, if it gives up at all. The wait can in turn cause degradations that are extremely hard to debug. "

"A single point of failure is the most glaring cause of failure in a distributed system; if it were to fail, that one component would bring down the entire system with it. In practice, systems can have multiple single points of failure. A service that starts up by needing to read a configuration from a non-replicated database is an example of a single point of failure; if the database isn’t reachable, the service won’t be able to (re)start. A more subtle example is a service that exposes an HTTP API on top of TLS using a certificate that needs to be manually renewed. If the certificate isn’t renewed by the time it expires, then all clients trying to connect to it wouldn’t be able to open a connection with the service. Single points of failure should be identified when the system is architected before they can cause any harm. The best way to detect them is to examine every component of the system and ask what would happen if that component were to fail. Some single points of failure can be architected away, e.g., by introducing redundancy, while others can’t. In that case, the only option left is to minimize the blast radius."

"When a cache miss occurs, the missing data item has to be requested from the remote dependency, and the cache has to be updated with it. This can happen in two ways: • The client, after getting an “item-not-found” error from the cache, requests the data item from the dependency and updates the cache. In this case, the cache is said to be a side cache. • Alternatively, if the cache is inline, the cache communicates directly with the dependency and requests the missing data item. In this case, the client only ever accesses the cache. Because a cache has a maximum capacity for holding entries, an entry needs to be evicted to make room for a new one when its capacity is reached. Which entry to remove depends on the eviction policy used by the cache and the client’s access pattern. One commonly used policy is to evict the least recently used (LRU) entry. A cache also has an expiration policy that dictates for how long to store an entry. For example, a simple expiration policy defines the maximum time to live (TTL) in seconds. When a data item has been in the cache for longer than its TTL, it expires and can safely be evicted. The expiration doesn’t need to occur immediately, though, and it can be deferred to the next time the entry is requested. In fact, that might be preferable — if the dependency is temporarily unavailable, and the cache is inline, it can opt to return an entry with an expired TTL to the client rather than an error."

"What if any replica could accept writes from clients? In that case, there wouldn’t be any leader(s), and the responsibility of replicating and resolving conflicts would be offloaded entirely to the clients. For this to work, a basic invariant needs to be satisfied. Suppose the data store has N replicas. When a client sends a write request to the replicas, it waits for at least W replicas to acknowledge it before moving on. And when it reads an entry, it does so by querying R replicas and taking the most recent one from the response set. Now, as long as 𝑊 + 𝑅 > 𝑁, the write and replica set intersect, which guarantees that at least one record in the read set will reflect the latest write. The writes are always sent to all N replicas in parallel; the W parameter determines just the number of responses the client has to receive to complete the request. The data store’s read and write throughput depend on how large or small R and W are. For example, a workload with many reads benefits from a smaller R, but in turn, that makes writes slower and less available. Like in multi-leader replication, a conflict resolution strategy needs to be used when two or more writes to the same record happen concurrently. Leaderless replication is even more complex than multi-leader replication, as it’s offloading the leader responsibilities to the clients, and there are edge cases that affect consistency even when 𝑊 + 𝑊 > 𝑁 is satisfied. For example, if a write succeeded on less than W replicas and failed on the others, the replicas are left in an inconsistent state."

"In multi-leader replication, there is more than one node that can accept writes. This approach is used when the write throughput is too high for a single node to handle, or when a leader needs to be available in multiple data centers to be geographically closer to its clients. The replication happens asynchronously since the alternative would defeat the purpose of using multiple leaders in the first place. This form of replication is generally best avoided when possible as it introduces a lot of complexity. The main issue with multiple leaders are conflicting writes; if the same data item is updated concurrently by two leaders, which one should win? To resolve conflicts, the data store needs to implement a conflict resolution strategy. The simplest strategy is to design the system so that conflicts are not possible; this can be achieved under some circumstances if the data has a homing region. For example, if all the European customer requests are always routed to the European data center, which has a single leader, there won’t be any conflicting writes. There is still the possibility of a data center going down, but that can be mitigated with a backup data center in the same region, replicated with single-leader replication. If assigning requests to specific leaders is not possible, and every client needs to be able to write to every leader, conflicting writes will inevitably happen. One way to deal with a conflict updating a record is to store the concurrent writes and return them to the next client that reads the record. The client will try to resolve the conflict and update the data store with the resolution. In other words, the data store “pushes the can down the road” to the clients. Alternatively, an automatic conflict resolution method needs to be implemented, for example: • The data store could use the timestamps of the writes and let the most recent one win. This is generally not reliable because the nodes’ physical clocks aren’t perfectly synchronized. Logical clocks are better suited for the job in this case. • The data store could allow the client to upload a custom conflict resolution procedure, which can be executed by the data store whenever a conflict is detected. • Finally, the data store could leverage data structures that provide automatic conflict resolution, like a conflict-free replicated data type (CRDT). CRDTs are data structures that can be replicated across multiple nodes, allowing each replica to update its local version independently from others while resolving inconsistencies in a mathematically sound way."

"Fully synchronous or asynchronous replication are extremes that provide some advantages at the expense of others. Most data stores have replication strategies that use a combination of the two. For example, in Raft, the leader replicates its writes to a majority before returning a response to the client. And in PostgreSQL, you can configure a subset of replicas to receive updates synchronously rather than asynchronously."

"If the servers behind a load balancer are stateless, scaling out is as simple as adding more servers. But when there is state involved, some form of coordination is required. Replication is the process of storing a copy of the same data in multiple nodes. If the data is static, replication is easy: just copy the data to multiple nodes, add a load balancer in front of it, and you are done. The challenge is dealing with dynamically changing data, which requires coordination to keep it in sync. Replication and sharding are techniques that are often combined, but are orthogonal to each other. For example, a distributed data store can divide its data into N partitions and distribute them over K nodes. Then, a state-machine replication algorithm like Raft can be used to replicate each partition R times"

"Geo load balancing infers the location of the client from its IP. To mitigate these performance issues, you can distribute the traffic to different data centers located in different regions. But how do you ensure that the clients communicate with the geographically closest L4 load balancer? This is where DNS geo load balancing comes in — it’s an extension to DNS that considers the location of the client inferred from its IP, and returns a list of the geographically closest L4 LB VIPs . The LB also needs to take into account the capacity of each data center and its health status."

"An application layer load balancer is an HTTP reverse proxy that farms out requests over a pool of servers. The LB receives an HTTP request from a client, inspects it, and sends it to a backend server. There are two different TCP connections at play here, one between the client and the L7 LB and another between the L7 LB and the server. Because a L7 LB operates at the HTTP level, it can demultiplex individual HTTP requests sharing the same TCP connection. This is even more important with HTTP 2, where multiple concurrent streams are multiplexed on the same TCP connection, and some connections can be several orders of magnitude more expensive to handle than others. The LB can do smart things with application traffic, like rate limiting requests based on HTTP headers, terminate TLS connections, or force HTTP requests belonging to the same logical session to be routed to the same backend server. For example, the LB could use a specific cookie to identify which logical session a specific request belongs to. Just like with a L4 LB, the session identifier can be mapped to a server using consistent hashing. The caveat is that sticky sessions can create hotspots as some sessions are more expensive to handle than others. If it sounds like a L7 LB has some overlapping functionality with an API gateway, it’s because they both are HTTP proxies, and therefore their responsibilities can be blurred. A L7 LB is typically used as the backend of a L4 LB to load balance requests sent by external clients from the internet. Although L7 LBs offer more functionality than L4 LBs, they have a lower throughput in comparison, which makes L4 LBs better suited to protect against certain DDoS attacks, like SYN floods. A drawback of using a dedicated load-balancing service is that all the traffic needs to go through it and if the LB goes down, the service behind it is no longer reachable. Additionally, it’s one more service that needs to be operated and scaled out. When the clients are internal to an organization, the L7 LB functionality can alternatively be bolted onto the clients directly using the sidecar pattern. In this pattern, all network traffic from a client goes through a process co-located on the same machine. This process implements load balancing, rate-limiting, authentication, monitoring, and other goodies. The sidecar processes form the data plane of a service mesh9 , which is configured by a corresponding control plane. This approach has been gaining popularity with the rise of microservices in organizations that have hundreds of services communicating with each other. Popular sidecar proxy load balancers as of this writing are NGINX, HAProxy, and Envoy. The advantage of using this approach is that it distributes the load-balancing functionality to the clients, removing the need for a dedicated service that needs to be scaled out and maintained. The con is a significant increase in the system’s complexity.-***Also referred to as a layer 7 (L7) load balancer since layer 7 is the application layer in the OSI model.***-"

"A more flexible load balancing solution can be implemented with a load balancer that operates at the TCP level of the network stack through which all traffic between clients and servers needs to go through. When a client creates a new TCP connection with a LB’s VIP, the LB picks a server from the pool and henceforth shuffles the packets back and forth for that connection between the client and the server. How does the LB assign connections to the servers, though? A connection is identified by a tuple (source IP/port, destination IP/port). Typically, some form of hashing is used to assign a connection tuple to a server. To minimize the disruption caused by a server being added or removed from the pool, consistent hashing is preferred over modular hashing. To forward packets downstream, the LB translates each packet’s source address to the LB address and its destination address to the server’s address. Similarly, when the LB receives a packet from the server, it translates its source address to the LB address and its destination address to the client’s address As the data going out of the servers usually has a greater volume than the data coming in, there is a way for servers to bypass the LB and respond directly to the clients using a mechanism called direct server return , but this is beyond the scope of this section. Because the LB is communicating directly with the servers, it can detect unavailable ones (e.g., with a passive health check) and automatically take them out of the pool improving the reliability of the backend service. Although load balancing connections at the TCP level is very fast, the drawback is that the LB is just shuffling bytes around without knowing what they actually mean. Therefore, L4 LBs generally don’t support features that require higher-level network protocols, like terminating TLS connections or balancing HTTP sessions based on cookies. A load balancer that operates at a higher level of the network stack is required to support these advanced use cases."

"A passive health check is performed by the LB as it routes incoming requests to the servers downstream. If a server isn’t reachable, the request times out, or the server returns a non-retriable status code (e.g., 503), the LB can decide to take that server out from the pool. Instead, an active health check requires support from the downstream servers, which need to expose a health endpoint signaling the server’s health state."

"The most basic form of load balancing can be implemented with DNS. Suppose you have a couple of servers that you would like to load balance requests over. If these servers have publicly reachable IP addresses, you can add those to the service’s DNS record and have the clients pick one when resolving the DNS address.If one of the two servers goes down, the DNS server will happily continue serving its IP address unaware of the failure. You can manually reconfigure the DNS record to take out the problematic IP, changes are not applied immediately due to the nature of DNS caching."

"Service discovery is the mechanism used by the LB to discover the available servers in the pool it can route requests to. There are various ways to implement it. For example, a simple approach is to use a static configuration file that lists the IP addresses of all the servers. However, this is quite painful to manage and keep upto-date. A more flexible solution can be implemented with DNS. Finally, using a data store provides the maximum flexibility at the cost of increasing the system’s complexity. One of the benefits of using a dynamic service discovery mechanism is that servers can be added and removed from the LB’s pool at any time. This is a crucial functionality that cloud providers leverage to implement autoscaling , i.e., the ability to automatically spin up and tear down servers based on their load."

"Arguably the easiest way to add more capacity to a service is to create more instances of it and have some way of routing, or balancing, requests to them. The thinking is that if one instance has a certain capacity, then 2 instances should have a capacity that is twice that. Creating more service instances can be a fast and cheap way to scale out a stateless service, as long as you have taken into account the impact on its dependencies. For example, if every service instance needs to access a shared data store, eventually, the data store will become a bottleneck, and adding more service instances to the system will only strain it further. The routing, or balancing, of requests across a pool of servers is implemented by a network load balancer. A load balancer (LB) has one or more physical network interface cards(NIC) mapped to one or more virtual IP (VIP) addresses. A VIP, in turn, is associated with a pool of servers. The LB acts as a middle-man between clients and servers — the clients only see the VIP exposed by the LB and have no visibility of the individual servers associated with it. Distributing requests across servers has many benefits. Because clients are decoupled from servers and don’t need to know their individual addresses, the number of servers behind the LB can be increased or reduced transparently. And since multiple redundant servers can interchangeably be used to handle requests, a LB can detect faulty ones and take them out of the pool, increasing the service’s availability. At a high level, a LB supports several core features beyond load balancing, like service discovery and health-checks."

"The idea behind hash partitioning is to use a hash function to assign keys to partitions, which shuffles — or uniformly distributes — keys across partitions. Another way to think about it is that the hash function maps a potentially nonuniformly distributed key space to a uniformly distributed hash space. For example, a simple version of hash partitioning can be implemented with modular hashing, i.e., hash(key) mod N. Although this approach ensures that the partitions contain more or less the same number of entries, it doesn’t eliminate hotspots if the access pattern is not uniform. If there is a single key that is accessed significantly more often than others, then all bets are off. In this case, the partition that contains the hot key needs to be split further down. Alternatively, the key needs to be split into multiple sub-keys, for example, by adding an offset at the end of it. Using modular hashing can become problematic when a new partition is added, as all keys have to be reshuffled across partitions. Shuffling data is extremely expensive as it consumes network bandwidth and other resources from nodes hosting partitions. Ideally, if a partition is added, only 𝐾/𝑁 keys should be shuffled around, where 𝐾 is the number of keys and 𝑁 the number of partitions. A hashing strategy that guarantees this property is called stable hashing. Ring hashing is an example of stable hashing. With ring hashing, a function maps a key to a point on a circle. The circle is then split into partitions that can be evenly or pseudo-randomly spaced, depending on the specific algorithm. When a new partition is added, it can be shown that most keys don’t need to be shuffled around. For example, with consistent hashing , both the partition identifiers and keys are randomly distributed on a circle, and each key is assigned to the next partition that appears on the circle in clockwise order. The main drawback of hash partitioning compared to range partitioning is that the sort order over the partitions is lost. However, the data within an individual partition can still be sorted based on a secondary key."

"With range partitioning, the data is split into partitions by key range in lexicographical order, and each partition holds a continuous range of keys. The data can be stored in sorted order on disk within each partition, making range scans fast. Splitting the key-range evenly doesn’t make much sense though if the distribution of keys is not uniform, like in the English dictionary. Doing so creates unbalanced partitions that contain significantly more entries than others. Another issue with range partitioning is that some access patterns can lead to hotspots. For example, if a dataset is range partitioned by date, all writes for the current day end up in the same partition, which degrades the data store’s performance."

"When a dataset no longer fits on a single node, it needs to be partitioned across multiple nodes. Partitioning is a general technique that can be used in a variety of circumstances, like sharding TCP connections across backends in a load balancer. We will anchor it to the implementation of a sharded key-value store. When a client sends a request to a partitioned data store to read or write a key, the request needs to be routed to the node responsible for the partition the key belongs to. One way to do that is to use a gateway service that can route the request to the right place knowing how keys are mapped to partitions and partitions to nodes. The mapping between keys and partitions, and other metadata, is typically maintained in a strongly-consistent configuration store, like etcd or Zookeeper. But how are keys mapped to partitions in the first place? At a high level, there are two ways to implement the mapping using either range partitioning or hash partitioning. "

"Reference plus blob Transmitting a large binary object (blob) like images, audio files, or video can be challenging or simply impossible, depending on the medium. For example, message brokers limit the maximum size of messages that can be written to a channel; Azure Storage queues limit messages to 64 KB, AWS Kinesis to 1 MB, etc. So how do you transfer large blobs of hundreds of MBs with these strict limits? You can upload a blob to an object storage service, like AWS S3 or Azure Blob Storage, and then send the URL of the blob via message (this pattern is sometimes referred to as queue plus blob). The downside is that now you have to deal with two services, the message broker and the object store, rather than just the message broker, which increases the system’s complexity. A similar approach can be used to store large blobs in databases — rather than storing a blob in a database directly, you only store some metadata containing an external reference to the actual blob. The advantage of this solution is that it minimizes data being transferred back and forth to and from the data store, improving its performance while reducing the required bandwidth. Also, the cost per byte of an object store designed to persist large objects that infrequently change, if at all, is lower than the one of a generic data store. Of course, the downside is that you lose the ability to transactionally update the blob with its metadata and potentially other records in the data store. For example, suppose a transaction inserts a new record in the data store containing an image. In this case, the image won’t be visible until the transaction completes; that won’t be the case if the image is stored in an external store, though. Similarly, if the record is later deleted, the image is automatically deleted as well; but if the image lives outside the store, it’s your responsibility to delete it. Whether storing blobs outside of your data store is acceptable or not depends on your specific use cases."

"One of the main advantages of using a messaging broker is that it makes the system more robust to outages. Producers can continue to write messages to a channel even if one or more consumers are not available or are degraded. As long as the rate of arrival of messages is lower or equal to the rate they are being deleted from the channel, everything is great. When that is no longer true, and consumers can’t keep up with producers, a backlog starts to build up. A messaging channel introduces a bi-modal behavior in the system. In one mode, there is no backlog, and everything works as expected. In the other, a backlog builds up, and the system enters a degraded state. The issue with a backlog is that the longer it builds up, the more resources and/or time it will take to drain it. There are several reasons for backlogs, for example: • more producers came online, and/or their throughput increased, and the consumers can’t match their rate; • the consumers have become slower to process individual messages, which in turn decreased their deletion rate; • the consumers fail to process a fraction of the messages, which are picked up again by other consumers until they eventually end up in the dead letter channel. This can cause a negative feedback loop that delays healthy messages and wastes the consumers’ processing time. To detect backlogs, you should measure the average time a message waits in the channel to be read for the first time. Typically, brokers attach a timestamp of when the message was first written to it. The consumer can use that timestamp to compute how long the message has been waiting in the channel by comparing it to the timestamp taken when the message was read. Although the two timestamps have been generated by two physical clocks that aren’t perfectly synchronized , the measure still provides a good indication of the backlog."

"• Channels are point-to-point and support an arbitrary number of producers and consumers. • Messages are delivered to consumers at-least-once. • While a consumer is processing a message, the message remains persisted in the channel, but other consumers can’t read it for the duration of a visibility timeout. The visibility timeout guarantees that if the consumer crashes while processing the message, the message will become visible to other consumers again when the timeout triggers. When the consumer is done processing the message, it deletes it from the channel preventing it from being received by any other consumer in the future. The above guarantees are very similar to what cloud services such as Amazon’s SQS and Azure Storage Queues offer."

"A message channel is implemented by a messaging service, like AWS SQS or Kafka. The messaging service, or broker, acts as a buffer for messages. It decouples producers from consumers so that they don’t need to know the consumers’ addresses, how many of them there are, or whether they are available. Different message brokers implement the channel abstraction differently depending on the tradeoffs and the guarantees they offer. For example, you would think that a channel should respect the insertion order of its messages, but you will find that some implementations, like SQS standard queues, don’t offer any strong ordering guarantees. Why is that? Because a message broker needs to scale out just like the applications that use it, its implementation is necessarily distributed. And when multiple nodes are involved, guaranteeing order becomes challenging as some form of coordination is required. Some brokers, like Kafka, partition a channel into multiple sub-channels, each small enough to be handled entirely by a single process. The idea is that if there is a single broker process responsible for the messages of a sub-channel, then it should be trivial to guarantee their order. In this case, when messages are sent to the channel, they are partitioned into sub-channels based on a partition key. To guarantee that the message order is preserved end-to-end, only a single consumer process can be allowed to read from a sub-channel . Because the channel is partitioned, it suffers from several drawbacks. For example, a specific partition can become much hotter than the others, and the single consumer reading from it might not be able to keep up with the load. In that case, the channel needs to be repartitioned, which can temporarily degrade the broker since messages need to be reshuffled across all partitions. Later in the chapter, we will learn more about the pros and cons of partitioning. why not having to guarantee the order of messages makes the implementation of a broker much simpler. Ordering is just one of the many tradeoffs a broker needs to make, such as: • delivery guarantees, like at-most-once or at-least-once; • message durability guarantees; • latency; • messaging standards supported, like AMQP; • support for competing consumers; • broker limits, such as the maximum supported size of messages."

"State machine replication can be used for much more than just replicating data since it’s a solution to the consensus problem. Consensus2 is a fundamental problem studied in distributed systems research, which requires a set of processes to agree on a value in a fault-tolerant way so that: • every non-faulty process eventually agrees on a value; • the final decision of every non-faulty process is the same everywhere; • and the value that has been agreed on has been proposed by a process. Consensus has a large number of practical applications. For example, a set of processes agreeing which one should hold a lock or commit a transaction are consensus problems in disguise. As it turns out, deciding on a value can be solved with state machine replication. Hence, any problem that requires consensus can be solved with state machine replication too."

"Raft is based on a technique known as state machine replication. The main idea behind it is that a single process, the leader, broadcasts the operations that change its state to other processes, the followers. If the followers execute the same sequence of operations as the leader, then the state of each follower will match the leader’s. Unfortunately, the leader can’t simply broadcast operations to the followers and call it a day, as any process can fail at any time, and the network can lose messages. This is why a large part of the algorithm is dedicated to fault-tolerance. When the system starts up, a leader is elected using Raft’s leader election algorithm. The leader is the only process that can make changes to the replicated state. It does so by storing the sequence of operations that alter the state into a local ordered log, which it then replicates to the followers; it’s the replication of the log that allows the state to be replicated across processes. When the leader wants to apply an operation to its local state, it first appends a new log entry for the operation into its log. At this point, the operation hasn’t been applied to the local state just yet; it has only been logged. The leader then sends a so-called AppendEntries request to each follower with the new entry to be added. This message is also sent out periodically, even in the absence of new entries, as it acts as a heartbeat for the leader. When a follower receives an AppendEntries request, it appends the entry it received to its log and sends back a response to the leader to acknowledge that the request was successful. When the leader hears back successfully from a majority of followers, it considers the entry to be committed and executes the operation on its local state. The leader keeps track of the highest committed index in the log, which is sent in all future AppendEntries requests. A follower only applies a log entry to its local state when it finds out that the leader has committed the entry. Because the leader needs to wait only for a majority of followers, it can make progress even if some processes are down, i.e., if there are 2𝑓 + 1 followers, the system can tolerate up to 𝑓 failures. The algorithm guarantees that an entry that is committed is durable and will eventually be executed by all the processes in the system, not just those that were part of the original majority. So far, we have assumed there are no failures, and the network is reliable. Let’s relax these assumptions. If the leader fails, a follower is elected as the new leader. But, there is a caveat: because the replication algorithm only needs a majority of the processes to make progress, it’s possible that when a leader fails, some processes are not up-to-date. To avoid that an out-of-date process becomes the leader, a process can’t vote for one with a less up-to-date log. In other words, a process can’t win an election if it doesn’t contain all committed entries. To determine which of two processes’ logs is more up-todate, the index and term of their last entries are compared. If the logs end with different terms, the log with the later term is more upto-date. If the logs end with the same term, whichever log is longer is more up-to-date. Since the election requires a majority vote, and a candidate’s log must be at least as up-to-date as any other process in that majority to win the election, the elected process will contain all committed entries. What if a follower fails? If an AppendEntries request can’t be delivered to one or more followers, the leader will retry sending it indefinitely until a majority of the followers successfully appended it to their logs. Retries are harmless as AppendEntries requests are idempotent, and followers ignore log entries that have already been appended to their logs. So what happens when a follower that was temporarily unavailable comes back online? The resurrected follower will eventually receive an AppendEntries message with a log entry from the leader. The AppendEntries message includes the index and term number of the entry in the log that immediately precedes the one to be appended. If the follower can’t find a log entry with the same index and term number, it rejects the message, ensuring that an append to its log can’t create a hole. It’s as if the leader is sending a puzzle piece that the follower can’t fit in its version of the puzzle. When the AppendEntries request is rejected, the leader retries sending the message, this time including the last two log entries — this is why we referred to the request as AppendEntries, and not as AppendEntry. This dance continues until the follower finally accepts a list of log entries that can be appended to its log without creating a hole. Although the number of messages exchanged can be optimized, the idea behind it is the same: the follower waits for a list of puzzle pieces that perfectly fit its version of the puzzle."

"The problem here is that by the time the process writes the content to the store, it might no longer be the leader and a lot might have happened since it was elected. For example, the operating system might have preempted and stopped the process, and several seconds will have passed by the time it’s running again. So how can the process ensure that it’s still the leader then? It could check one more time before writing to the store, but that doesn’t eliminate the race condition, it just makes it less likely. To avoid this issue, the data store downstream needs to verify that the request has been sent by the current leader. One way to do that is by using a fencing token. A fencing token5 is a number that increases every time that a distributed lock is acquired — in other words, it’s a logical clock. When the leader writes to the store, it passes down the fencing token to it. For example, if there are momentarily two leaders and they both perform the same idempotent operation, no harm is done. Although having a leader can simplify the design of a system as it eliminates concurrency, it can become a scaling bottleneck if the number of operations performed by the leader increases to the point where it can no longer keep up. When that happens, you might be forced to re-design the whole system. Also, having a leader introduces a single point of failure with a large blast radius; if the election process stops working or the leader isn’t working as expected, it can bring down the entire system with it. You can mitigate some of these downsides by introducing partitions and assigning a different leader per partition, but that comes with additional complexity. This is the solution many distributed data stores use. Before considering the use of a leader, check whether there are other ways of achieving the desired functionality without it. For example, optimistic locking is one way to guarantee mutual exclusion at the cost of wasting some computing power. Or perhaps high availability is not a requirement for your application, in which case having just a single process that occasionally crashes and restarts is not a big deal. As a rule of thumb, if you must use leader election, you have to minimize the work it performs and be prepared to occasionally have more than one leader if you can’t support fencing tokens end-to-end."

"Raft’s leader election algorithm is implemented with a state machine in which a process is in one of three states. • the follower state, in which the process recognizes another one as the leader; • the candidate state, in which the process starts a new election proposing itself as a leader; • or the leader state, in which the process is the leader. In Raft, time is divided into election terms of arbitrary length. An election term is represented with a logical clock, a numerical counter that can only increase over time. A term begins with a new election, during which one or more candidates attempt to become the leader. The algorithm guarantees that for any term there is at most one leader. But what triggers an election in the first place? When the system starts up, all processes begin their journey as followers. A follower expects to receive a periodic heartbeat from the leader containing the election term the leader was elected in. If the follower doesn’t receive any heartbeat within a certain time period, a timeout fires and the leader is presumed dead. At that point, the follower starts a new election by incrementing the current election term and transitioning to the candidate state. It then votes for itself and sends a request to all the processes in the system to vote for it, stamping the request with the current election term. The process remains in the candidate state until one of three things happens: it wins the election, another process wins the election, or some time goes by with no winner:The candidate wins the election — The candidate wins the election if the majority of the processes in the system vote for it. Each process can vote for at most one candidate in a term on a first-come-first-served basis. This majority rule enforces that at most one candidate can win a term. If the candidate wins the election, it transitions to the leader state and starts sending out heartbeats to the other processes. • Another process wins the election — If the candidate receives a heartbeat from a process that claims to be the leader with a term greater than, or equal the candidate’s term, it accepts the new leader and returns to the follower state. If not, it continues in the candidate state. You might be wondering how that could happen; for example, if the candidate process was to stop for any reason, like for a long GC pause, by the time it resumes another process could have won the election. • A period of time goes by with no winner — It’s unlikely but possible that multiple followers become candidates simultaneously, and none manages to receive a majority of votes; this is referred to as a split vote. When that happens, the candidate will eventually time out and start a new election. The election timeout is picked randomly from a fixed interval to reduce the likelihood of another split vote in the next election. "

A vector clock is a logical clock that guarantees that if two operations can be ordered by their logical timestamps, then one must have happened-before the other. A vector clock is implemented with an array of counters, one for each process in the system. And similarly to how Lamport clocks are used, each process has its own local copy of the clock. A process updates its local vector clock based on the following rules: • Initially, the counters in the array are set to 0. • When an operation occurs, the process increments its own counter in the array by one. • When the process sends a message, it increments its own counter in the array by one and sends a copy of the array with the message. • When the process receives a message, it merges the array it received with the local one by taking the maximum of the two arrays element-wise. Finally, it increments its own counter in the array by one.

A Lamport clock is a logical clock based on this idea. Every process in the system has its own local logical clock implemented with a numerical counter that follows specific rules: • The counter is initialized with 0. • The process increments its counter before executing an operation. • When the process sends a message, it increments its counter and sends a copy of it in the message. • When the process receives a message, its counter is updated to 1 plus the maximum of its current logical timestamp and the message’s timestamp.

The Network Time Protocol (NTP ) is used to synchronize clocks. The challenge is to do so despite the unpredictable latencies introduced by the network. A NTP client estimates the clock skew by correcting the timestamp received by a NTP server with the estimated network latency. Armed with an estimate of the clock skew, the client can adjust its clock, causing it to jump forward or backward in time.

A ping is a periodic request that a process sends to another to check whether it’s still available. The process expects a response to the ping within a specific time frame. If that doesn’t happen, a timeout is triggered that marks the destination as dead. However, the process will keep regularly sending pings to it so that if and when it comes back online, it will reply to a ping and be marked as available again. A heartbeat is a message that a process periodically sends to another to inform it that it’s still up and running. If the destination doesn’t receive a heartbeat within a specific time frame, it triggers a timeout and marks the process that missed the heartbeat as dead. If that process comes later back to life and starts sending out heartbeats, it will eventually be marked as available again. Pings and heartbeats are typically used when specific processes frequently interact with each other, and an action needs to be taken as soon as one of them is no longer reachable. If that’s not the case, detecting failures just at communication time is good enough.

The partially synchronous model assumes that the system behaves synchronously most of the time, but occasionally it can regress to an asynchronous mode. This model is typically representative enough of practical systems.

The asynchronous model assumes that sending a message or executing an operation on a node can take an unbounded amount of time. Unfortunately, many problems can’t be solved under this assumption; if sending messages can take an infinite amount of time, algorithms can get stuck and not make any progress at all.

The synchronous model assumes that sending a message or executing an operation never takes over a certain amount of time. This is very unrealistic in the real world, where we know sending messages over the network can potentially take a very long time, and nodes can be stopped by, e.g., garbage collection cycles or page faults.

Byzantine node models are typically used to model safety-critical systems like airplane engine systems, nuclear power plants, financial systems, and other systems where a single entity doesn’t fully control all the nodes.

We can also model the different types of node failures we expect to happen: ---------------------------------------------------------------------- • The arbitrary-fault model assumes that a node can deviate from its algorithm in arbitrary ways, leading to crashes or unexpected behavior due to bugs or malicious activity. The arbitrary fault model is also referred to as the “Byzantine” model for historical reasons. Interestingly, it can be theoretically proven that a system with Byzantine nodes can tolerate up to 1 /3 of faulty nodes and still operate correctly. ------------------------------------------------------ • The crash-recovery model assumes that a node doesn’t deviate from its algorithm, but can crash and restart at any time, losing its in-memory state. ----------------------------------------------------- • The crash-stop model assumes that a node doesn’t deviate from its algorithm, but if it crashes it never comes back online.

some models for communication links: -------------------------------------------------------------------------------------------------------------- • The fair-loss link model assumes that messages may be lost and duplicated. If the sender keeps retransmitting a message, eventually it will be delivered to the destination. ----------------------------------------------------------------------------------------------------------------- • The reliable link model assumes that a message is delivered exactly once, without loss or duplication. A reliable link can be implemented on top of a fair-loss one by de-duplicating messages at the receiving side. --------------------------------------------------------------------------------------------------------------- • The authenticated reliable link model makes the same assumptions as the reliable link, but additionally assumes that the receiver can authenticate the message’s sender.

Status codes between 200 and 299 are used to communicate success. For example, 200 (OK) means that the request succeeded, and the body of the response contains the requested resource. ---------------------------------------------------------------------- Status codes between 300 and 399 are used for redirection. For example, 301 (Moved Permanently) means that the requested resource has been moved to a different URL, specified in the response message Location header. ------------------------------------------------------------------------------------------------- Status codes between 400 and 499 are reserved for client errors. A request that fails with a client error will usually continue to return the same error if it’s retried, as the error is caused by an issue with the client, not the server. Because of that, it shouldn’t be retried. ---------------------------------------------------------------------- These client errors are common: • 400 (Bad Request) — Validating the client-side input has failed. • 401 (Unauthorized) — The client isn’t authorized to access a resource. • 403 (Forbidden) — The user is authenticated, but it’s not allowed to access a resource. • 404 (Not Found) — The server couldn’t find the requested resource. ---------------------------------------------------------------------------------------------- Status codes between 500 and 599 are reserved for server errors. A request that fails with a server error can be retried as the issue that caused it to fail might be fixed by the time the retry is processed by the server. These are some typical server status codes: • 500 (Internal Server Error) — A generic server error. • 502 (Bad Gateway) — Indicates an invalid response from an upstream server. • 503 (Service Unavailable) — Indicates that the server can’t currently serve the request, but might be able to in the future.

Request methods can be classified depending on whether they are safe and idempotent. A safe method should not have any visible side effects and can be safely cached. An idempotent method can be executed multiple times, and the end result should be the same as if it was executed just a single time.

"Seam carving algorithm is to perform content-aware resizing of images. This allows images to be resized without losing meaningful content from cropping or scaling. The idea is to locate the image's optimal seams, connected pixel paths going from top to bottom or left to right, to remove or insert while preserving the photorealism of the image. Furthermore, manipulating the gradient energy map that describes how optimal a seam allows for functionality such as object removal. "

Breadth First Traversal (Or Level Order Traversal)---- Extra Space required for Level Order Traversal is O(w) where w is maximum width of Binary Tree. In level order traversal, queue one by one stores nodes of different level. Extra Space required for Depth First Traversals is O(h) where h is maximum height of Binary Tree. In Depth First Traversals, stack (or function call stack) stores all ancestors of a node.*************************** *Depth First Traversals 1.Inorder Traversal (Left-Root-Right) 2.Preorder Traversal (Root-Left-Right) 3.Postorder Traversal (Left-Right-Root) ***************************** Depth First Traversals are typically recursive and recursive code requires function call overheads. The most important points is, BFS starts visiting nodes from the root while DFS starts visiting nodes from leaves. So if our problem is to search something that is more likely to closer to the root, we would prefer BFS. And if the target node is close to a leaf, we would prefer DFS.

Cycle sort is a comparison-based sorting algorithm that forces array to be factored into the number of cycles where each of them can be rotated to produce a sorted array. It is an in-place and unstable sorting algorithm. It is optimal in terms of a number of memory writes. It minimizes the number of memory writes to sort. Each value is either written zero times if it’s already in its correct position or written one time to its correct position. It is based on the idea that array to be sorted can be divided into cycles. Cycles can be visualized as a graph. Best case time complexity: O(n^2) , Average case time complexity:O(n^2), Worst case time complexity:O(n^2) , Space complexity:O(1) ,

Floyd's cycle-finding algorithm is a pointer algorithm that uses only two pointers, which move through the sequence at different speeds. It is also called the "tortoise and the hare algorithm", alluding to Aesop's fable of The Tortoise and the Hare. Traverse linked list using two pointers. Move one pointer(slow pointer) by one and another pointer(fast pointer) by two. If these pointers meet at the same node then there is a loop. If pointers do not meet then linked list doesn’t have a loop.

Heap sort is based on the algorithm of priority queue and it gives the best sorting time. The basic strategy is to build a binary heap of N elements which takes O(N) time. Heap sort is a comparison based sorting algorithm and has time complexity O(nlogn) in the average case. Heap sort is an in-place algorithm as it needs O(1) of auxiliary space. Heap sort uses heap and operations on heap can change the relative order of items with the same key values. Heap sort is not a stable sort. Heap sort is an implementation of selection sort using the input array as a heap representing a descending priority queue. Heap sort algorithm is divided into two phases. In the first phase, the max-heap is created and the second phase (selection phase) deletes the elements from the priority queue using sift down operation. Heap sort is slower than Shell sort because Shell sort uses Sedgewick’s increment sequence. The total running time of a heap sort algorithm is mathematically found to be O(N log N). To perform deletion operation in a heap, we require 2 arrays and that occupies extra memory space and hence increases running time. The time taken to perform a deletion of a minimum element is mathematically found to be O( log N). The max-heap is also known as descending heap. Max-heap of size n is an almost complete binary tree of n nodes such that the element at each node is less than or equal to the element at its parent node. Heap sort uses fewer comparisons than other sorting algorithms and hence it is an extremely stable algorithm. According to a theorem, the average number of comparisons used to heap sort a random permutation of N distinct items is found to be 2N log N-O(N log log N). The worst case complexity of Heap sort is O(nlogn). Quick sort is more efficient than Heap sort because Heap sort requires twice as much time as Quick sort for randomly sorted input. Smooth sort is a variation of Heap sort. Smooth sort has O(nlogn) worst case time complexity like Heap sort. But Smooth sort takes O(n) time to sort the nearly sorted input array. Introsort is a hybrid sorting algorithm that combines Quick sort and Heap sort to retain the advantages of both. It has worst-case speed of Heap sort and the average case speed of Quick sort. For n elements, it takes nlogn time. So if it takes logn time, then number of elements is (n)(logn)/nlogn which is 1.

In the median of three techniques the median of the first, last, and middle element is chosen as the pivot. It is done so as to avoid the worst case of quick sort in which the time complexity shoots to O(n^2).A median of three quick sort helps in avoiding the worst-case time complexity of O(n^2) which occurs in case when the input array is already sorted. However, the average case and best case time complexities remain unaltered. Auxiliary space complexity of median of three quick sort is O(log n) which is used for storing call stack formed due to recursion. Note that the algorithms with space complexity as O(log n) also qualifies as in-place algorithms as the value of log n is close to 1. Median of three quick sort like standard quick sort is also not a stable sorting algorithm. It is because the elements with the same values are not guaranteed to appear in the same relative order in the output sorted array.

Streaming Algorithms • Input is presented as a sequence of items. • Input can be examined in only a few passes (typically just one). • Use limited memory available to them (much less than the input size) • limited processing time per item. • These constraints may mean that an algorithm produces an approximate answer based on a summary or "sketch" of the data stream in memory.

Offline Algorithm: All input information is available to the algorithm and processed simultaneously by the algorithm. With the complete set of input information, the algorithm finds a way to efficiently process the inputs and obtain an optimal solution. For example: Selection Sort. Online Algorithm: Inputs come on the fly i.e. all input information is not available to the algorithm simultaneously but rather part by part as a sequence or over time. Upon the availability of input, the algorithm has to take immediate decision without any knowledge of future input information. In this process, the algorithm produces a sequence of decisions that will have an impact on the final quality of its overall performance. Example of Online Algorithms are : 1. Insertion sort 2. Perceptron 3. Reservoir sampling 4. Greedy algorithm 5. Adversary model 6. Metrical task systems 7. Odds algorithm Online Problems: There are many problems that offer more than one online algorithm as solution: 1. Canadian Traveller Problem 2. Linear Search Problem 3. K-server problem 4. Job shop scheduling problem 5. List update problem 6. Bandit problem 7. Secretary problem

In internal sorting, all the data to sort is stored in memory at all times while sorting is in progress. In external sorting, data is stored outside memory (like on disk) and only loaded into memory in small chunks. Some of the common algorithms that use this sorting feature are : Bubble Sort, Insertion Sort, and Quick Sort. External sorting is usually applied in cases when data can't fit into memory entirely. They are comparatively slower than internal sorting algorithms. For example, merge sort algorithm. It sorts chunks that each fit in RAM, then merges the sorted chunks together.

A sorting algorithm is said to be adaptive, if it takes advantage of already 'sorted' elements in the list that is to be sorted. That is, while sorting if the source list has some element already sorted, adaptive algorithms will take this into account and will try not to re-order them. A non-adaptive algorithm is one that does not take into account the elements which are already sorted. They try to force every single element to be re-ordered to confirm their sortedness. For example – Quick sort is an adaptive sorting algorithm because the time complexity of Quick sort depends on the initial input sequence. If input is already sorted then time complexity becomes O(n^2) and if the input sequence is not sorted then time complexity becomes O(n logn). Some adaptive sorting algorithms are : Bubble Sort, Insertion Sort and Quick Sort. On the other hand some non-adaptive sorting algorithms are : Selection Sort, Merge Sort, and Heap Sort.

Quick sort is a divide ((partition) the array based on the pivot element and sort accordingly) and conquer algorithm. Quick sort first partitions a large array into two smaller sub-arrays. And then recursively sorts the sub-arrays. The entire array is divided into two partitions, 1st sub-array containing elements less than the pivot element and 2nd sub-array containing elements greater than the pivot element. Quick Sort is randomized by placing the input data in the randomized fashion in the array or by choosing a random element in the array as a pivot. The worst-case performance of a quick sort algorithm is mathematically found to be O(N^2) when the input array is already sorted. In Quick sort, the worst case behavior occurs when the partitioning routine produces two sub-arrays one with n – 1 element and the other with 0 elements. The best case and average case analysis of a quick sort algorithm are mathematically found to be O(N log N). The array is partitioned into equal halves, using the Divide and Conquer master theorem, the complexity is found to be O(nlogn). The best case analysis of quick sort occurs when the partition splits the array into two subarrays, each of size no more than n/2 since one is of size n/2 and one of size (n/2) – 1. Insertion sort is used along with quick sort to sort the sub-arrays. It is used only at the end.Quick sort uses join operation since join is a faster operation than merge sort. In stable sorting algorithm, the records with equal keys appear in the same order in the sorted sequence as they appear in the input unsorted sequence. Quick sort does not preserve the relative order of equal sort items. Therefore, the Quick sort is not a stable sort. Quick sort is a space-optimised version of the binary tree sort. In binary sort tree, the elements are inserted sequentially into the binary search tree and Quick sort organises elements into a tree that is implied by the recursive calls.

The merge function in the bottom-up merge sort takes O(n) time which is placed inside the for loop. The loop runs for O(log n) time, thus the overall time complexity of the code becomes O(n log n). The auxiliary space complexity of bottom-up merge sort is the same as the standard merge sort as both use the same algorithm for merging the sorted arrays which take O(n) space. But bottom-up merge sort does not need to maintain a call stack. Bottom-up merge sort uses the iterative method in order to implement sorting. It begins by merging a pair of an adjacent array of size 1 each and then merging arrays of size 2 each in the next step and so on. Bottom-up merge sort like standard merge sort is a stable sort. This implies that the relative position of equal valued elements in the input and sorted array remains the same. Bottom-up merge sort unlike standard merge sort uses an iterative algorithm for sorting. Thus, it saves auxiliary space required by the call stack.

Time complexity of standard merge sort is O(n log n) and that of in-place merge sort is O(n^2). So the time complexity of in-place merge sort is more than that of standard merge sort.

In place version of merge sort has a greater time complexity as compared to its standard version. It is because the merging in in-place merge sort takes place in O(n^2) time whereas in standard version it takes O(n) time.

Bottom up merge sort that does not use recursion uses the iterative method in order to implement sorting. It begins by merging a pair of adjacent array of size 1 each and then merge arrays of size 2 each in the next step and so on.

Tim sort is a hybrid sorting algorithm as it uses more than one sorting algorithm internally. It makes use of merge sort and insertion sort.

"The stability of a sorting algorithm is concerned with how the algorithm treats equal (or repeated) elements. Stable sorting algorithms preserve the relative order of equal elements, while unstable sorting algorithms don’t. In other words, stable sorting maintains the position of two equal elements relative to one another. ****************************************************************************************************************** When equal elements are indistinguishable, such as with integers, or more generally, any data where the entire element is the key, stability is not an issue. Stability is also not an issue if all keys are different. ----------------------------------------------------------------------------------------------------------------------------------Insertion Sort — Stable. ********************************* Selection Sort — Unstable. ********************************** Bubble Sort — Stable. ********************************* Merge Sort — Stable. ********************************** Shell Sort — Unstable. **************************** Timsort — Stable. ******************************* quick ----Unstable.

Merge Sort is an “Non-Adaptive” Sorting algorithm, because the order of the elements in the input array doesn’t matter, time complexity will always be O(nlogn). *************************************************************************************************************** Adaptive sorting algorithms: 1. Bubble Sort 2. Insertion Sort 3. Quick Sort ---------------------------------------------------------------------------------------------------------------------------------- Non-adaptive sorting algorithms: 1. Selection Sort 2. Merge Sort 3. Heap Sort

1. Manacher's algorithm is a very handy algorithm with a short implementation that can make many programming tasks, such as finding the number of palindromic substrings or finding the longest palindromic substring, very easy and efficient. *************************************************************************************************************** 2. Kadane's algorithm is able to find the maximum sum of a contiguous subarray in an array with a runtime of O(n). *************************************************************************************************************** 3. The Lee algorithm is one possible solution for maze routing problems based on Breadth-first search. It always gives an optimal solution, if one exists, but is slow and requires considerable memory. *************************************************************************************************************** 4. Johnson's algorithm is a shortest path algorithm that deals with the all pairs shortest path problem. The all pairs shortest path problem takes in a graph with vertices and edges, and it outputs the shortest path between every pair of vertices in that graph.

In order to accommodate large data sets, computers have a hierarchy of different kinds of memories, which vary in terms of their size and distance from the CPU. Closest to the CPU are the internal registers that the CPU itself uses. Access to such locations is very fast, but there are relatively few such locations. At the second level in the hierarchy are one or more memory caches. This memory is considerably larger than the register set of a CPU, but accessing it takes longer. At the third level in the hierarchy is the internal memory, which is also known as main memory or core memory. The internal memory is considerably larger than the cache memory, but also requires more time to access. Another level in the hierarchy is the external memory, which usually consists of disks, CD drives, DVD drives, and/or tapes. This memory is very large, but it is also very slow. Data stored through an external network can be viewed as yet another level in this hierarchy, with even greater storage capacity, but even slower access. Thus, the memory hierarchy for computers can be viewed as consisting of five or more levels, each of which is larger and slower than the previous level. During the execution of a program, data is routinely copied from one level of the hierarchy to a neighboring level, and these transfers can become a computational bottleneck

Arithmetic expressions, such as ((a + b) ∗ (c + d))/e, are evaluated by the interpreter using an operand stack.we described how to evaluate an arithmetic expression using a postorder traversal of an explicit expression tree. We described that algorithm in a recursive way; however, this recursive description can be simulated using a nonrecursive process that maintains an explicit operand stack. A simple binary operation, such as a+ b, is computed by pushing a on the stack, pushing b on the stack, and then calling an instruction that pops the top two items from the stack, performs the binary operation on them, and pushes the result back onto the stack. Likewise, instructions for writing and reading elements to and from memory involve the use of pop and push methods for the operand stack.

In the mark-sweep garbage collection algorithm, we associate a “mark” bit with each object that identifies whether that object is live. When we determine at some point that garbage collection is needed, we suspend all other activity and clear the mark bits of all the objects currently allocated in the memory heap. We then trace through the active namespaces and we mark all the root objects as “live.” We must then determine all the other live objects—the ones that are reachable from the root objects. To do this efficiently, we can perform a depth-first search on the directed graph that is defined by objects reference other objects. In this case, each object in the memory heap is viewed as a vertex in a directed graph, and the reference from one object to another is viewed as a directed edge. By performing a directed DFS from each root object, we can correctly identify and mark each live object. This process is known as the “mark” phase. Once this process has completed, we then scan through the memory heap and reclaim any space that is being used for an object that has not been marked. At this time, we can also optionally coalesce all the allocated space in the memory heap into a single block, thereby eliminating external fragmentation for the time being. This scanning and reclamation process is known as the “sweep” phase, and when it completes, we resume running the suspended program. Thus, the mark-sweep garbage collection algorithm will reclaim unused space in time proportional to the number of live objects and their references plus the size of the memory heap.

Cycle Detection Although it is clear that an object with a reference count of zero cannot be a live object, it is important to recognize that an object with a nonzero reference count need not qualify as live. There may exist a group of objects that have references to each other, even though none of those objects are reachable from a root object. For example, a running Python program may have an identifier, data, that is a reference to a sequence implemented using a doubly linked list. In this case, the list referenced by data is a root object, the header and trailer nodes that are stored as attributes of the list are live objects, as are all the intermediate nodes of the list that are indirectly referenced and all the elements that are referenced as elements of those nodes. If the identifier, data, were to go out of scope, or to be reassigned to some other object, the reference count for the list instance may go to zero and be garbage collected, but the reference counts for all of the nodes would remain nonzero, stopping them from being garbage collected by the simple rule above. Every so often, in particular when the available space in the memory heap is becoming scarce, the Python interpreter uses a more advanced form of garbage collection to reclaim objects that are unreachable, despite their nonzero reference counts. There are different algorithms for implementing cycle detection. (The mechanics of garbage collection in Python are abstracted in the gc module, and may vary depending on the implementation of the interpreter.)

Within the state of every Python object is an integer known as its reference count. This is the count of how many references to the object exist anywhere in the system. Every time a reference is assigned to this object, its reference count is incremented, and every time one of those references is reassigned to something else, the reference count for the former object is decremented. The maintenance of a reference count for each object adds O(1) space per object, and the increments and decrements to the count add O(1) additional computation time per such operations. The Python interpreter allows a running program to examine an object’s reference count. Within the sys module there is a function named getrefcount that returns an integer equal to the reference count for the object sent as a parameter. It is worth noting that because the formal parameter of that function is assigned to the actual parameter sent by the caller, there is temporarily one additional reference to that object in the local namespace of the function at the time the count is reported. The advantage of having a reference count for each object is that if an object’s count is ever decremented to zero, that object cannot possibly be a live object and therefore the system can immediately deallocate the object (or place it in a queue of objects that are ready to be deallocated).

"Only immutable data types are deemed hashable in Python. This restriction is meant to ensure that a particular object’s hash code remains constant during that object’s lifespan. This is an important property for an object’s use as a key in a hash table. A problem could occur if a key were inserted into the hash table, yet a later search were performed for that key based on a different hash code than that which it had when inserted; the wrong bucket would be searched. Among Python’s built-in data types, the immutable int, float, str, tuple, and frozenset classes produce robust hash codes, via the hash function."

"While it is essential to use handcrafted test suites, it is also advantageous to run the program on a large collection of randomly generated inputs. The random module in Python provides several means for generating random numbers, or for randomizing the order of collections. The dependencies among the classes and functions of a program induce a hierarchy. Namely, a component A is above a component B in the hierarchy if A depends upon B, such as when function A calls function B, or function A relies on a parameter that is an instance of class B. There are two main testing strategies, top-down and bottom-up, which differ in the order in which components are tested. Top-down testing proceeds from the top to the bottom of the program hierarchy. It is typically used in conjunction with stubbing, a boot-strapping technique that replaces a lower-level component with a stub, a replacement for the component that simulates the functionality of the original. For example, if function A calls function B to get the first line of a file, when testing A we can replace B with a stub that returns a fixed string. Bottom-up testing proceeds from lower-level components to higher-level components. For example, bottom-level functions, which do not invoke other functions, are tested first, followed by functions that call only bottom-level functions, and so on. Similarly a class that does not depend upon any other classes can be tested before another class that depends on the former. This form of testing is usually described as unit testing, as the functionality of a specific component is tested in isolation of the larger software project. If used properly, this strategy better isolates the cause of errors to the component being tested, as lower-level components upon which it relies should have already been thoroughly tested."

"A common tool for developing an initial high-level design for a project is the use of CRC cards. Class-Responsibility-Collaborator (CRC) cards are simple index cards that subdivide the work required of a program. The main idea behind this tool is to have each card represent a component, which will ultimately become a class in the program. We write the name of each component on the top of an index card. On the left-hand side of the card, we begin writing the responsibilities for this component. On the right-hand side, we list the collaborators for this component, that is, the other components that this component will have to interact with to perform its duties. The design process iterates through an action/actor cycle, where we first identify an action (that is, a responsibility), and we then determine an actor (that is, a component) that is best suited to perform that action. The design is complete when we have assigned all actions to actors. In using index cards for this process (rather than larger pieces of paper), we are relying on the fact that each component should have a small set of responsibilities and collaborators. Enforcing this rule helps keep the individual classes manageable."

RAID---Redundant Arrays of Independent Disks (disk organization techniques that manage a large number of disks, providing a view of a single disk. Bit-level Stripping: split the bits of each byte across disks. Block-level Stripping: with n disks, blocking i of file goes to disk (i mod n) + 1 (Block, data units that fit in sectors on the track, that is, the smallest data unit that can be written to disk)

Scheduling Algorithm Optimization: 1.Max CPU Utilization 2.Max Throughput 3.Min turnaround time 4.Min waiting time 5.Min response time

Parity Check:A parity check is the process that ensures accurate data transmission between nodes during communication. A parity bit is appended to the original data bits to create an even or odd bit number; the number of bits with value one. The source then transmits this data via a link, and bits are checked and verified at the destination. Data is considered accurate if the number of bits (even or odd) matches the number transmitted from the source. As an example, if the original data is 1010001, there are three 1s. When even parity checking is used, a parity bit with value 1 is added to the data’s left side to make the number of 1s is even; transmitted data becomes 11010001. However, if odd parity checking is used, then parity bit value is zero; 01010001. If the original data contains an even number of 1s (1101001), then parity bit of value 1 is added to the data’s left side to make the number of 1s odd, if odd parity checking is used and data transmitted becomes 11101001. Redundant array of independent disks (RAID) also use an enhanced form of protection based on parity that check horizontal and vertical parity. A second set of parity data is written across all drives to avoid loss in case of error. When a RAID drive fails its parity check, data is rebuilt using parity information coupled with data on the other disks. The bits on the remaining drives are added up. If they add up to an odd number, the correct information on the failed drive had to be even, and vice-versa.

Installing iCurlHTTP "We can also use apps that can compose and send HTTP requests from mobile devices to work with our RESTful Web Services. For example, we can work with the iCurlHTTP app on iOS devices such as iPad and iPhone: https://itunes.apple.com/us/app/icurlhttp/id611943891. On Android devices, we can work with the HTTP Request app: https://play.google.com/store/apps/details?id=air.http.request&hl=en."

"Stoplight is a very useful GUI tool that focuses on helping architects and developers to model complex APIs. If we need to consume our RESTful Web Service in many different programming languages, we will find Stoplight extremely helpful. Stoplight provides an HTTP request maker that allows us to compose and send requests and generate the necessary code to make them in different programming languages, such as JavaScript, Swift, C#, PHP, Node, and Go, among others. Stoplight provides a web version and is also available as a standalone app in Linux, macOS, and Windows. You can download the versions of Stoplight from the following URL: http://stoplight.io/."

From the official documentation: An object is hashable if it has a hash value which never changes during its lifetime, and can be compared to other objects. Hashability makes an object usable as a dictionary key and a set member, because these data structures use the hash value internally. All of Python’s immutable built-in objects are hashable while mutable containers are not.

"The threading and multiprocessing packages both provide an object-oriented interface to the underlying mechanics. Futures are able to encapsulate a lot of the messy details into a single object. AsyncIO uses coroutine objects to make our code read as though it runs synchronously, while hiding ugly and complicated implementation details behind a very simple loop abstraction."

"AsyncIO can be used for a few different concurrent tasks, but it was specifically designed for network I/O. Most networking applications, especially on the server side, spend a lot of time waiting for data to come in from the network. This can be solved by handling each client in a separate thread, but threads use up memory and other resources. AsyncIO uses coroutines as a sort of lightweight thread. The library provides its own event loop, obviating the need for the several lines long the while loop in the previous example. However, event loops come with a cost. When we run code in an async task on the event loop, that code must return immediately, blocking neither on I/O nor on long-running calculations. This is a minor thing when writing our own code, but it means that any standard library or third-party functions that block on I/O have to have non-blocking versions created"

"Futures wrap either multiprocessing or threading depending on what kind of concurrency we need (tending toward I/O versus tending toward CPU). They don't completely solve the problem of accidentally altering shared state, but they allow us to structure our code such that it is easier to track down when we do so. Futures provide distinct boundaries between the different threads or processes. Similar to the multiprocessing pool, they are useful for call and answer type interactions, in which processing can happen in another thread and then at some point in the future (they are aptly named, after all), you can ask it for the result. It's really just a wrapper around multiprocessing pools and thread pools, but it provides a cleaner API and encourages nicer code."

"If we need more control over communication between processes, we can use a Queue. Queue data structures are useful for sending messages from one process into one or more other processes. Any picklable object can be sent into a Queue, but remember that pickling can be a costly operation, so keep such objects small. To illustrate queues, let's build a little search engine for text content that stores all relevant entries in memory. This is not the most sensible way to build a text-based search engine, but I have used this pattern to query numerical data that needed to use CPU-intensive processes to construct a chart that was then rendered to the user."

"The multiprocessing library is designed for when CPU-intensive jobs need to happen in parallel and multiple cores are available (almost all computers, even a little smartwatch, have multiple cores). Multiprocessing is not useful when the processes spend a majority of their time waiting on I/O (for example, network, disk, database, or keyboard), but it is the way to go for parallel computation."

"In order to efficiently manage memory, garbage collection, and calls to machine code in native libraries, Python has a utility called the global interpreter lock, or GIL. It's impossible to turn off, and it means that threads are useless in Python for one thing that they excel at in other languages: parallel processing. The GIL's primary effect, for our purposes, is to prevent any two threads from doing work at the exact same time, even if they have work to do. In this case, doing work means using the CPU, so it's perfectly okay for multiple threads to access the disk or network; the GIL is released as soon as the thread starts to wait for something. "

"The main problem with threads is also their primary advantage. Threads have access to all the program's memory and thus all the variables. This can too easily cause inconsistencies in the program state. Python offers the queue.Queue class to do this; its functionality is basically the same as multiprocessing.Queue, which we will discuss in the next section."

"Concurrency is the art of making a computer do (or appear to do) multiple things at once. Historically, this meant inviting the processor to switch between different tasks many times per second. In modern systems, it can also literally mean doing two or more things simultaneously on separate processor cores. Concurrency is not inherently an object-oriented topic, but Python's concurrent systems provide object-oriented interfaces, as we've covered throughout the book. This chapter will introduce you to the following topics: *Threads *Multiprocessing *Futures *AsyncIO "

"The most popular tool for testing code coverage is called, memorably enough, coverage.py. It can be installed like most other third-party libraries, using the pip install coverage command. We can use the coverage.py module with pytest as well. We'll need to install the pytest plugin for code coverage, using pip install pytest-coverage. The plugin adds several command-line options to pytest, the most useful being --cover-report, which can be set to html, report, or annotate (the latter actually modifies the original source code to highlight any lines that were not covered)"

"The facade pattern is designed to provide a simple interface to a complex system of components. For complex tasks, we may need to interact with these objects directly, but there is often a typical usage for the system for which these complicated interactions aren't necessary. The facade pattern allows us to define a new object that encapsulates this typical usage of the system. Any time we want access to common functionality, we can use the single object's simplified interface. "

"the adapter pattern is designed to interact with existing code. We would not design a brand new set of objects that implement the adapter pattern. Adapters are used to allow two preexisting objects to work together, even if their interfaces are not compatible. "

"The template pattern is useful for removing duplicate code; it's intended to support the Don't Repeat Yourself principle When to Use Object-Oriented Programming. It is designed for situations where we have several different tasks to accomplish that have some, but not all, steps in common. The common steps are implemented in a base class, and the distinct steps are overridden in subclasses to provide custom behavior. In some ways, it's like a generalized strategy pattern, except similar sections of the algorithms are shared using a base class.

"The singleton pattern is one of the most controversial patterns; many have accused it of being an anti-pattern, a pattern that should be avoided, not promoted. In Python, if someone is using the singleton pattern, they're almost certainly doing something wrong, probably because they're coming from a more restrictive programming language. So, why discuss it at all? Singleton is one of the most famous of all design patterns. It is useful in overly object-oriented languages, and is a vital part of traditional object-oriented programming. More relevantly, the idea behind singleton is useful, even if we implement the concept in a totally different way in Python."

"The strategy pattern is used to choose an algorithm at runtime; generally, only one of those algorithms is going to be chosen for a particular use case. The state pattern, on the other hand, is designed to allow switching between different states dynamically, as some process evolves. In code, the primary difference is that the strategy pattern is not typically aware of other strategy objects. In the state pattern, either the state or the context needs to know which other states that it can switch to."

"The state pattern is structurally similar to the strategy pattern, but its intent and purpose are very different. The goal of the state pattern is to represent state-transition systems: systems where it is obvious that an object can be in a specific state, and that certain activities may drive it to a different state. To make this work, we need a manager, or context class that provides an interface for switching states. Internally, this class contains a pointer to the current state. Each state knows what other states it is allowed to be in and will transition to those states depending on actions invoked upon it."

"The strategy pattern is a common demonstration of abstraction in object-oriented programming. The pattern implements different solutions to a single problem, each in a different object. The client code can then choose the most appropriate implementation dynamically at runtime."

"The observer pattern is useful for state monitoring and event handling situations. This pattern allows a given object to be monitored by an unknown and dynamic group of observer objects."

"The decorator pattern allows us to wrap an object that provides core functionality with other objects that alter this functionality. Any object that uses the decorated object will interact with it in exactly the same way as if it were undecorated (that is, the interface of the decorated object is identical to that of the core object). There are two primary uses of the decorator pattern: *Enhancing the response of a component as it sends data to a second component *Supporting multiple optional behaviors

"The composite pattern allows complex tree-like structures to be built from simple components. These components, called composite objects, are able to behave sort of like a container and sort of like a variable, depending on whether they have child components. Composite objects are container objects, where the content may actually be another composite object. The composite pattern is commonly useful in file/folder-like trees. Regardless of whether a node in the tree is a normal file or a folder, it is still subject to operations such as moving, copying, or deleting the node. We can create a component interface that supports these operations, and then use a composite object to represent folders, and leaf nodes to represent normal files."

"The abstract factory pattern is normally used when we have multiple possible implementations of a system that depend on some configuration or platform issue. The calling code requests an object from the abstract factory, not knowing exactly what class of object will be returned. The underlying implementation returned may depend on a variety of factors, such as current locale, operating system, or local configuration. Common examples of the abstract factory pattern include code for operating-systemindependent toolkits, database backends, and country-specific formatters or calculators. An operating-system-independent GUI toolkit might use an abstract factory pattern that returns a set of WinForm widgets under Windows, Cocoa widgets under Mac, GTK widgets under Gnome, and QT widgets under KDE. Django provides an abstract factory that returns a set of object relational classes for interacting with a specific database backend (MySQL, PostgreSQL, SQLite, and others) depending on a configuration setting for the current site. If the application needs to be deployed in multiple places, each one can use a different database backend by changing only one configuration variable. Different countries have different systems for calculating taxes, subtotals, and totals on retail merchandise; an abstract factory can return a particular tax calculation object."

The command pattern adds a level of abstraction between actions that must be done and the object that invokes those actions, normally at a later time. In the command pattern, client code creates a Command object that can be executed at a later date. This object knows about a receiver object that manages its own internal state when the command is executed on it. The Command object implements a specific interface (typically, it has an execute or do_action method, and also keeps track of any arguments required to perform the action. Finally, one or more Invoker objects execute the command at the correct time.

The flyweight pattern is a memory optimization pattern. The flyweight pattern ensures that objects that share a state can use the same memory for that shared state. It is normally implemented only after a program has demonstrated memory problems. It may make sense to design an optimal configuration from the beginning in some situations, but bear in mind that premature optimization is the most effective way to create a program that is too complicated to maintain. The flyweight pattern is useful when dealing with large numbers of objects with simple repeated elements that would use a large amount of memory if individually stored. It is common to hold shared data in external data structures and pass it to the objects temporarily when they are used.