diff options
| -rw-r--r-- | _bibliography/rpc.bib | 247 | ||||
| -rw-r--r-- | chapter/1/figures/grpc-benchmark.png | bin | 0 -> 17014 bytes | |||
| -rw-r--r-- | chapter/1/figures/grpc-client-transport-handler.png | bin | 0 -> 67834 bytes | |||
| -rw-r--r-- | chapter/1/figures/grpc-cross-language.png | bin | 0 -> 27394 bytes | |||
| -rw-r--r-- | chapter/1/figures/grpc-googleapis.png | bin | 0 -> 33354 bytes | |||
| -rw-r--r-- | chapter/1/figures/grpc-languages.png | bin | 0 -> 47003 bytes | |||
| -rw-r--r-- | chapter/1/figures/grpc-server-transport-handler.png | bin | 0 -> 60913 bytes | |||
| -rw-r--r-- | chapter/1/figures/hello-world-client.png | bin | 0 -> 30161 bytes | |||
| -rw-r--r-- | chapter/1/figures/hello-world-server.png | bin | 0 -> 13005 bytes | |||
| -rw-r--r-- | chapter/1/figures/http2-frame.png | bin | 0 -> 12057 bytes | |||
| -rw-r--r-- | chapter/1/figures/http2-stream-lifecycle.png | bin | 0 -> 49038 bytes | |||
| -rw-r--r-- | chapter/1/figures/protobuf-types.png | bin | 0 -> 19941 bytes | |||
| -rw-r--r-- | chapter/1/gRPC.md | 323 | ||||
| -rw-r--r-- | chapter/1/rpc.md | 259 | ||||
| -rw-r--r-- | chapter/2/1.png | bin | 0 -> 14176 bytes | |||
| -rw-r--r-- | chapter/2/10.png | bin | 0 -> 9834 bytes | |||
| -rw-r--r-- | chapter/2/11.png | bin | 0 -> 12134 bytes | |||
| -rw-r--r-- | chapter/2/12.png | bin | 0 -> 17071 bytes | |||
| -rw-r--r-- | chapter/2/13.png | bin | 0 -> 21547 bytes | |||
| -rw-r--r-- | chapter/2/14.png | bin | 0 -> 11405 bytes | |||
| -rw-r--r-- | chapter/2/15.png | bin | 0 -> 15262 bytes | |||
| -rw-r--r-- | chapter/2/2.png | bin | 0 -> 6152 bytes | |||
| -rw-r--r-- | chapter/2/3.png | bin | 0 -> 13719 bytes | |||
| -rw-r--r-- | chapter/2/4.png | bin | 0 -> 25404 bytes | |||
| -rw-r--r-- | chapter/2/5.png | bin | 0 -> 20821 bytes | |||
| -rw-r--r-- | chapter/2/6.png | bin | 0 -> 19123 bytes | |||
| -rw-r--r-- | chapter/2/7.png | bin | 0 -> 30068 bytes | |||
| -rw-r--r-- | chapter/2/8.png | bin | 0 -> 13899 bytes | |||
| -rw-r--r-- | chapter/2/9.png | bin | 0 -> 6463 bytes | |||
| -rw-r--r-- | chapter/2/futures.md | 304 | ||||
| -rw-r--r-- | chapter/6/being-consistent.md | 82 | ||||
| -rw-r--r-- | resources/img/rpc_chapter_1_ycog_10_steps.png | bin | 0 -> 24905 bytes |
32 files changed, 1114 insertions, 101 deletions
diff --git a/_bibliography/rpc.bib b/_bibliography/rpc.bib index b0e8932..266c603 100644 --- a/_bibliography/rpc.bib +++ b/_bibliography/rpc.bib @@ -112,3 +112,250 @@ author={Srinivasan, Raj}, year={1995} } + +@misc{microservices1rpc, + title={Delving Into the Microservices Architecture}, + author={Mueller, John}, + year={2015}, + url = {http://blog.smartbear.com/microservices/delving-into-the-microservices-architecture/}, +} + +@article{rpcorigin, + title={High-level framework for network-based resource sharing}, + author={White, James E}, + year={1975} +} + +@inproceedings{interweave1, + title={Integrating remote invocation and distributed shared state}, + author={Tang, Chunqiang and Chen, DeQing and Dwarkadas, Sandhya and Scott, Michael L}, + booktitle={Parallel and Distributed Processing Symposium, 2004. Proceedings. 18th International}, + pages={30}, + year={2004}, + organization={IEEE} +} + + +@inproceedings{interweave2, + title={Interweave: A middleware system for distributed shared state}, + author={Chen, DeQing and Dwarkadas, Sandhya and Parthasarathy, Srinivasan and Pinheiro, Eduardo and Scott, Michael L}, + booktitle={International Workshop on Languages, Compilers, and Run-Time Systems for Scalable Computers}, + pages={207--220}, + year={2000}, + organization={Springer} +} + +@inproceedings{interweave3, + title={Multi-level shared state for distributed systems}, + author={Chen, DeQing and Tang, Chunqiang and Chen, Xiangchuan and Dwarkadas, Sandhya and Scott, Michael L}, + booktitle={Parallel Processing, 2002. Proceedings. International Conference on}, + pages={131--140}, + year={2002}, + organization={IEEE} +} + +@article{offloading1, + title={A survey of computation offloading for mobile systems}, + author={Kumar, Karthik and Liu, Jibang and Lu, Yung-Hsiang and Bhargava, Bharat}, + journal={Mobile Networks and Applications}, + volume={18}, + number={1}, + pages={129--140}, + year={2013}, + publisher={Springer} +} + +@misc{ibis, + title={Ibis Communication middleware}, + author={Ibis}, + url = {https://www.cs.vu.nl/ibis/rmi.html}, +} + +@article{cuckoo, + title={Cuckoo: flexible compute-intensive task offloading in mobile cloud computing}, + author={Zhou, Zhigang and Zhang, Hongli and Ye, Lin and Du, Xiaojiang}, + journal={Wireless Communications and Mobile Computing}, + year={2016}, + publisher={Wiley Online Library} +} + +@inproceedings{maui, + title={MAUI: making smartphones last longer with code offload}, + author={Cuervo, Eduardo and Balasubramanian, Aruna and Cho, Dae-ki and Wolman, Alec and Saroiu, Stefan and Chandra, Ranveer and Bahl, Paramvir}, + booktitle={Proceedings of the 8th international conference on Mobile systems, applications, and services}, + pages={49--62}, + year={2010}, + organization={ACM} +} + +@article{docker, + title={Docker: lightweight linux containers for consistent development and deployment}, + author={Merkel, Dirk}, + journal={Linux Journal}, + volume={2014}, + number={239}, + pages={2}, + year={2014}, + publisher={Belltown Media} +} + +@inproceedings{selfdest, + title={RFID systems and security and privacy implications}, + author={Sarma, Sanjay E and Weis, Stephen A and Engels, Daniel W}, + booktitle={International Workshop on Cryptographic Hardware and Embedded Systems}, + pages={454--469}, + year={2002}, + organization={Springer} +} + +@misc{orcalenfs, + title={Overview of Secure RPC}, + author={Oracle}, + url = {https://docs.oracle.com/cd/E23823_01/html/816-4557/auth-2.html}, +} + +@misc{capnprotosecure, + title={Is Cap'n Proto Secure?}, + author={Kenton}, + url = {https://capnproto.org/faq.html#is-capn-proto-secure}, +} + + +@article{grid1, + title={High performance GridRPC middleware}, + author={Caniou, Yves and Caron, Eddy and Desprez, Fr{\'e}d{\'e}ric and Nakada, Hidemoto and Tanaka, Yoshio and Seymour, Keith}, + journal={Recent Developments in Grid Technology and Applications, Nova Science Publishers}, + pages={141--181}, + year={2008} +} + +@incollection{gridsolve1, + title={Gridsolve: The evolution of a network enabled solver}, + author={YarKhan, Asim and Dongarra, Jack and Seymour, Keith}, + booktitle={Grid-Based Problem Solving Environments}, + pages={215--224}, + year={2007}, + publisher={Springer} +} + +@article{gridsolve2, + title={Interactive Grid-access using Gridsolve and giggle}, + author={Hardt, M and Seymour, Keith and Dongarra, Jack and Zapf, M and Ruitter, NV}, + journal={Computing and Informatics}, + volume={27}, + number={2}, + pages={233--248}, + year={2012} +} + +@article{ninf, + title={Ninf-G: A reference implementation of RPC-based programming middleware for Grid computing}, + author={Tanaka, Yoshio and Nakada, Hidemoto and Sekiguchi, Satoshi and Suzumura, Toyotaro and Matsuoka, Satoshi}, + journal={Journal of Grid computing}, + volume={1}, + number={1}, + pages={41--51}, + year={2003}, + publisher={Springer} +} + +@article{erlang, + title={Concurrent programming in ERLANG}, + author={Armstrong, Joe and Virding, Robert and Wikstr{\"o}m, Claes and Williams, Mike}, + year={1993}, + publisher={Citeseer} +} + +@misc{Apigee, + title={Is Cap'n Proto Secure?}, + author={Surtani, Manick and Ho, Alan}, + url = {https://www.youtube.com/watch?v=-2sWDr3Z0Wo}, +} + +@misc{CoreSurfaceAPIs, + title={gRPC core APIs}, + author={Google}, + url = {https://github.com/grpc/grpc/tree/master/src/core}, +} + +@misc{gRPCCompanies, + title={About gRPC}, + author={Google}, + url = {http://www.grpc.io/about/}, +} + +@misc{gRPCLanguages, + title={gRPC Documentation}, + author={Google}, + url = {http://www.grpc.io/docs/}, +} + +@misc{gRPCProtos, + title={Google APIs}, + author={Google}, + url = {https://github.com/googleapis/googleapis/}, +} + +@misc{rpcimage, + title={Remote Procedure Call (RPC)}, + author={Taing, Nguonly}, + url = {http://lycog.com/distributed-systems/remote-procedure-call/}, + note = {Image URL: http://lycog.com/wp-content/uploads/2011/03/rpc-10-steps.png} +} + +@misc{trendrpcthrift, + title={Remote Procedure Call (RPC)}, + author={Google Trends}, + url = {https://www.google.com/trends/explore?cat=31&date=today%2012-m&q=apache%20thrift,grpc&hl=en-US} +} + +@misc{grpcauth, + title={GRPC Authentication}, + author={Google}, + url = {http://www.grpc.io/docs/guides/auth.html}, +} + +@misc{rfc707, + title={RFC 707: A high-level framework for network-based resource sharing}, + author={White, James E}, + year={1975}, + publisher={December} +} + +@techreport{rfc674, + title={RFC 674: Procedure call documents: Version 2}, + author={Postel, J and White, JE}, + year={1974} +} + +@article{rfc684, + title={RFC 684: Commentary on procedure calling as a network protocol}, + author={Schantz, Richard}, + year={1975} +} + +@misc{grpcbetter, + title={GRPC Authentication}, + author={Google}, + url = {https://www.quora.com/Is-GRPC-better-than-Thrift}, + publisher = {Quora} +} + +@misc{multiplexingthrift, + title={Added service multiplexing support}, + author={Yu, Lixin}, + url = {https://github.com/eleme/thriftpy/pull/88/commits/0877531f9246ca993c1d9af5d29cd009ee6ec7d4}, + publisher = {Github} +} + +@techreport{rfc5531, + title={RFC 5531: RPC: Remote Procedure Call Protocol Specification Version 2}, + author={Thurlow, R}, + year={2009} +} + +@techreport{rfc1831, + title={RFC 1831: RPC: Remote Procedure Call Protocol Specification Version 2}, + author={Srinivasan, R}, + year={1995} +} diff --git a/chapter/1/figures/grpc-benchmark.png b/chapter/1/figures/grpc-benchmark.png Binary files differnew file mode 100644 index 0000000..9f39c71 --- /dev/null +++ b/chapter/1/figures/grpc-benchmark.png diff --git a/chapter/1/figures/grpc-client-transport-handler.png b/chapter/1/figures/grpc-client-transport-handler.png Binary files differnew file mode 100644 index 0000000..edd5236 --- /dev/null +++ b/chapter/1/figures/grpc-client-transport-handler.png diff --git a/chapter/1/figures/grpc-cross-language.png b/chapter/1/figures/grpc-cross-language.png Binary files differnew file mode 100644 index 0000000..c600f67 --- /dev/null +++ b/chapter/1/figures/grpc-cross-language.png diff --git a/chapter/1/figures/grpc-googleapis.png b/chapter/1/figures/grpc-googleapis.png Binary files differnew file mode 100644 index 0000000..62718e5 --- /dev/null +++ b/chapter/1/figures/grpc-googleapis.png diff --git a/chapter/1/figures/grpc-languages.png b/chapter/1/figures/grpc-languages.png Binary files differnew file mode 100644 index 0000000..1f1c50d --- /dev/null +++ b/chapter/1/figures/grpc-languages.png diff --git a/chapter/1/figures/grpc-server-transport-handler.png b/chapter/1/figures/grpc-server-transport-handler.png Binary files differnew file mode 100644 index 0000000..fe895c0 --- /dev/null +++ b/chapter/1/figures/grpc-server-transport-handler.png diff --git a/chapter/1/figures/hello-world-client.png b/chapter/1/figures/hello-world-client.png Binary files differnew file mode 100644 index 0000000..c4cf7d4 --- /dev/null +++ b/chapter/1/figures/hello-world-client.png diff --git a/chapter/1/figures/hello-world-server.png b/chapter/1/figures/hello-world-server.png Binary files differnew file mode 100644 index 0000000..a51554b --- /dev/null +++ b/chapter/1/figures/hello-world-server.png diff --git a/chapter/1/figures/http2-frame.png b/chapter/1/figures/http2-frame.png Binary files differnew file mode 100644 index 0000000..59d6ed5 --- /dev/null +++ b/chapter/1/figures/http2-frame.png diff --git a/chapter/1/figures/http2-stream-lifecycle.png b/chapter/1/figures/http2-stream-lifecycle.png Binary files differnew file mode 100644 index 0000000..87333cb --- /dev/null +++ b/chapter/1/figures/http2-stream-lifecycle.png diff --git a/chapter/1/figures/protobuf-types.png b/chapter/1/figures/protobuf-types.png Binary files differnew file mode 100644 index 0000000..aaf3a1e --- /dev/null +++ b/chapter/1/figures/protobuf-types.png diff --git a/chapter/1/gRPC.md b/chapter/1/gRPC.md new file mode 100644 index 0000000..f6c47b7 --- /dev/null +++ b/chapter/1/gRPC.md @@ -0,0 +1,323 @@ +--- +layout: page +title: "gRPC" +by: "Paul Grosu (Northeastern U.), Muzammil Abdul Rehman (Northeastern U.), Eric Anderson (Google, Inc.), Vijay Pai (Google, Inc.), and Heather Miller (Northeastern U.)" +--- + +<h1> +<p align="center">gRPC</p> +</h1> + +<h4><em> +<p align="center">Paul Grosu (Northeastern U.), Muzammil Abdul Rehman (Northeastern U.), Eric Anderson (Google, Inc.), Vijay Pai (Google, Inc.), and Heather Miller (Northeastern U.)</p> +</em></h4> + +<hr> + +<h3><em><p align="center">Abstract</p></em></h3> + +<em>gRPC has been built from a collaboration between Google and Square as a public replacement of Stubby, ARCWire and Sake {% cite Apigee %}. The gRPC framework is a form of an Actor Model based on an IDL (Interface Description Language), which is defined via the Protocol Buffer message format. With the introduction of HTTP/2 the internal Google Stubby and Square Sake frameworks are now been made available to the public. By working on top of the HTTP/2 protocol, gRPC enables messages to be multiplexed and compressed bi-directionally as premptive streams for maximizing capacity of any microservices ecosystem. Google has also a new approach to public projects, where instead of just releasing a paper describing the concepts will now also provide the implementation of how to properly interpret the standard. +</em> + +<h3><em>Introduction</em></h3> + +In order to understand gRPC and the flexibity of enabling a microservices ecosystem to become into a Reactive Actor Model, it is important to appreciate the nuances of the HTTP/2 Protocol upon which it is based. Afterward we will describe the gRPC Framework - focusing specifically on the gRPC-Java implementation - with the scope to expand this chapter over time to all implementations of gRPC. At the end we will cover examples demonstrating these ideas, by taking a user from the initial steps of how to work with the gRPC-Java framework. + +<h3>1 <em>HTTP/2</em></h3> + +The HTTP 1.1 protocol has been a success for some time, though there were some key features which began to be requested by the community with the increase of distributed computing, especially in the area of microservices. The phenomenon of creating more modularized functional units that are organically constructed based on a <em>share-nothing model</em> with a bidirectional, high-throughput request and response methodology demands a new protocol for communication and integration. Thus the HTTP/2 was born as a new standard, which is a binary wire protocol providing compressed streams that can be multiplexed for concurrency. As many microservices implementations currently scan header messages before actually processing any payload in order to scale up the processing and routing of messages, HTTP/2 now provides header compression for this purpose. One last important benefit is that the server endpoint can actually push cached resources to the client based on anticipated future communication, dramatically saving client communication time and processing. + +<h3>1.1 <em>HTTP/2 Frames</em></h3> + +The HTTP/2 protocol is now a framed protocol, which expands the capability for bidirectional, asynchronous communication. Every message is thus part of a frame that will have a header, frame type and stream identifier aside from the standard frame length for processing. Each stream can have a priority, which allows for dependency between streams to be achieved forming a <em>priority tree</em>. The data can be either a request or response which allows for the bidirectional communication, with the capability of flagging the communication for stream termination, flow control with priority settings, continuation and push responses from the server for client confirmation. Below is the format of the HTTP/2 frame {% cite RFC7540 %}: + +<p align="center"> + <img src="figures/http2-frame.png" /><br> + <em>Figure 1: The encoding a HTTP/2 frame.</em> +</p> + +<h3>1.2 <em>Header Compression</em></h3> + +The HTTP header is one of the primary methods of passing information about the state of other endpoints, the request or response and the payload. This enables endpoints to save time when processing a large quantity to streams, with the ability to forward information along without wasting time to inspect the payload. Since the header information can be quite large, it is possible to now compress the them to allow for better throughput and capacity of stored stateful information. + +<h3>1.3 <em>Multiplexed Streams</em></h3> + +As streams are core to the implementation of HTTP/2, it is important to discuss the details of their implemenation in the protocol. As many streams can be open simultanously from many endpoints, each stream will be in one of the following states. Each stream is multiplexed together forming a chain of streams that are transmitted over the wire, allowing for asynchronous bi-directional concurrency to be performed by the receiving endpoint. Below is the lifecycle of a stream {% cite RFC7540 %}: + +<p align="center"> + <img src="figures/http2-stream-lifecycle.png" /><br> + <em>Figure 2: The lifecycle of a HTTP/2 stream.</em> +</p> + +To better understand this diagram, it is important to define some of the terms in it: + +<em>PUSH_PROMISE</em> - This is being performed by one endpoint to alert another that it will be sending some data over the wire. + +<em>RST_STREAM</em> - This makes termination of a stream possible. + +<em>PRIORITY</em> - This is sent by an endpoint on the priority of a stream. + +<em>END_STREAM</em> - This flag denotes the end of a <em>DATA</em> frame. + +<em>HEADERS</em> - This frame will open a stream. + +<em>Idle</em> - This is a state that a stream can be in when it is opened by receiving a <em>HEADERS</em> frame. + +<em>Reserved (Local)</em> - To be in this state is means that one has sent a PUSH_PROMISE frame. + +<em>Reserved (Remote)</em> - To be in this state is means that it has been reserved by a remote endpoint. + +<em>Open</em> - To be in this state means that both endpoints can send frames. + +<em>Closed</em> - This is a terminal state. + +<em>Half-Closed (Local)</em> - This means that no frames can be sent except for <em>WINDOW_UPDATE</em>, <em>PRIORITY</em>, and <em>RST_STREAM</em>. + +<em>Half-Closed (Remote)</em> - This means that a frame is not used by the remote endpoint to send frames of data. + +<h3>1.4 <em>Flow Control of Streams</em></h3> + +Since many streams will compete for the bandwidth of a connection, in order to prevent bottlenecks and collisions in the transmission. This is done via the <em>WINDOW_UPDATE</em> payload for every stream - and the overall connection as well - to let the sender know how much room the receiving endpoint has for processing new data. + +<h3>2 <em>Protocol Buffers with RPC</em></h3> + +Though gRPC was built on top of HTTP/2, an IDL had to be used to perform the communication between endpoints. The natural direction was to use Protocol Buffers is the method of stucturing key-value-based data for serialization between a server and client. At the time of the start of gRPC development only version 2.0 (proto2) was available, which only implemented data structures without any request/response mechanism. An example of a Protocol Buffer data structure would look something like this: + +``` +// A message containing the user's name. +message Hello { + string name = 1; +} +``` +<p align="center"> + <em>Figure 3: Protocol Buffer version 2.0 representing a message data-structure.</em> +</p> + +This message will also be encoded for highest compression when sent over the wire. For example, let us say that the message is the string <em>"Hi"</em>. Every Protocol Buffer type has a value, and in this case a string has a value of `2`, as noted in the Table 1 {% cite Protobuf-Types %}. + +<p align="center"> + <img src="figures/protobuf-types.png" /><br> + <em>Table 1: Tag values for Protocol Buffer types.</em> +</p> + +One will notice that there is a number associated with each field element in the Protocol Buffer definition, which represents its <em>tag</em>. In Figure 3, the field `name` has a tag of `1`. When a message gets encoded each field (key) will start with a one byte value (8 bits), where the least-significant 3-bit value encode the <em>type</em> and the rest the <em>tag</em>. In this case tag which is `1`, with a type of 2. Thus the encoding will be `00001 010`, which has a hexdecimal value of `A`. The following byte is the length of the string which is `2`, followed by the string as `48` and `69` representing `H` and `i`. Thus the whole tranmission will look as follows: + +``` +A 2 48 69 +``` + +Thus the language had to be updated to support gRPC and the development of a service message with a request and a response definition was added for version version 3.0.0 of Protocol Buffers. The updated implementation would look as follows {% cite HelloWorldProto %}: + +``` +// The request message containing the user's name. +message HelloRequest { + string name = 1; +} + +// The response message containing the greetings +message HelloReply { + string message = 1; +} + +// The greeting service definition. +service Greeter { + // Sends a greeting + rpc SayHello (HelloRequest) returns (HelloReply) {} +} +``` +<p align="center"> + <em>Figure 4: Protocol Buffer version 3.0.0 representing a message data-structure with the accompanied RPC definition.</em> +</p> + +Notice the addition of a service, where the RPC call would use one of the messages as the structure of a <em>Request</em> with the other being the <em>Response</em> message format. + +Once of these Proto file gets generated, one would then use them to compile with gRPC to for generating the <em>Client</em> and <em>Server</em> files representing the classical two endpoints of a RPC implementation. + +<h3>3 <em>gRPC</em></h3> + +gRPC was built on top of HTTP/2, and we will cover the specifics of gRPC-Java, but expand it to all the implementations with time. gRPC is a cross-platform framework that allows integration across many languages as denoted in Figure 5 {% cite gRPC-Overview %}. + +<p align="center"> + <img src="figures/grpc-cross-language.png" /><br> + <em>Figure 5: gRPC allows for asynchronous language-agnostic message passing via Protocol Buffers.</em> +</p> + +To ensure scalability, benchmarks are run on a daily basis to ensure that gRPC performs optimally under high-throughput conditions as illustrated in Figure 6 {% cite gRPC-Benchmark %}. + +<p align="center"> + <img src="figures/grpc-benchmark.png" /><br> + <em>Figure 6: Benchmark showing the queries-per-second on two virtual machines with 32 cores each.</em> +</p> + +To standardize, most of the public Google APIs - including the Speech API, Vision API, Bigtable, Pub/Sub, etc. - have been ported to support gRPC, and their definitions can be found at the following location: + +<p align="center"> + <img src="figures/grpc-googleapis.png" /><br> + <em>Figure 7: The public Google APIs have been updated for gRPC, and be found at <a href="https://github.com/googleapis/googleapis/tree/master/google">https://github.com/googleapis/googleapis/tree/master/google</a></em> +</p> + + +<h3>3.1 <em>Supported Languages</em></h3> + +The officially supported languages are listed in Table 2 {% cite gRPC-Languages %}. + +<p align="center"> + <img src="figures/grpc-languages.png" /><br> + <em>Table 2: Officially supported languages by gRPC.</em> +</p> + +<h3>3.2 <em>Authentication</em></h3> + +There are two methods of authentication that are available in gRPC: + +* SSL/TLS +* Google Token (via OAuth2) + +gRPC is flexible in that once can plug in their custom authentication system if that is preferred. + +<h3>3.3 <em>Development Cycle</em></h3> + +In its simplest form gRPC has a structured set of steps one goes about using it, which has this general flow: + +<em>1. Download gRPC for the language of interest.</em> + +<em>2. Implement the Request and Response definition in a ProtoBuf file.</em> + +<em>3. Compile the ProtoBuf file and run the code-generators for the the specific language. This will generate the Client and Server endpoints.</em> + +<em>4. Customize the Client and Server code for the desired implementation.</em> + +Most of these will require tweaking the Protobuf file and testing the throughput to ensure that the network and CPU capacities are optimally maximized. + +<h3>3.4 <em>The gRPC Framework (Stub, Channel and Transport Layer)</em></h3> + +One starts by initializing a communication <em>Channel</em> between <em>Client</em> to a <em>Server</em> and storing that as a <em>Stub</em>. The <em>Credentials</em> are provided to the Channel when being initialized. These form a <em>Context</em> for the Client's connection to the Server. Then a <em>Request</em> can be built based on the definition in the Protobuf file. The Request and associated expected<em>Response</em> is executed by the <em>service</em> constructed in the Protobuf file. The Response is them parsed for any data coming from the Channel. + +The connection can be asynchronous and bi-directionally streaming so that data is constantly flowing back and available to be read when ready. This allows one to treat the Client and Server as endpoints where one can even adjust not just the flow but also intercept and decoration to filter and thus request and retrieve the data of interest. + +The <em>Transport Layer</em> performs the retrieval and placing of binary protocol on the wire. For <em>gRPC-Java</em> has three implementations, though a user can implement their own: <em>Netty, OkHttp, and inProcess.</em> + +<h3>3.5 <em>gRPC Java</em></h3> + +The Java implementation of gRPC been built with Mobile platform in mind and to provide that capability it requires JDK 6.0 to be supported. Though the core of gRPC is built with data centers in mind - specifically to support C/C++ for the Linux platform - the Java and Go implementations are two very reliable platform to experiment the microservice ecosystem implementations. + +There are several moving parts to understanding how gRPC-Java works. The first important step is to ensure that the Client and Server stub inferface code get generated by the Protobuf plugin compiler. This is usually placed in your <em>Gradle</em> build file called `build.gradle` as follows: + +``` + compile 'io.grpc:grpc-netty:1.0.1' + compile 'io.grpc:grpc-protobuf:1.0.1' + compile 'io.grpc:grpc-stub:1.0.1' +``` + +When you build using Gradle, then the appropriate base code gets generated for you, which you can override to build your preferred implementation of the Client and Server. + +Since one has to implement the HTTP/2 protocol, the chosen method was to have a <em>Metadata</em> class that will convert the key-value pairs into HTTP/2 Headers and vice-versa for the Netty implementation via <em>GrpcHttp2HeadersDecoder</em> and <em>GrpcHttp2OutboundHeaders</em>. + +Another key insight is to understand that the code that handles the HTTP/2 conversion for the Client and the Server are being done via the <em>NettyClientHandler.java</em> and <em>NettyServerHandler.java</em> classes shown in Figures 8 and 9. + +<p align="center"> + <img src="figures/grpc-client-transport-handler.png" /><br> + <em>Figure 8: The Client Tranport Handler for gRPC-Java.</em> +</p> + +<p align="center"> + <img src="figures/grpc-server-transport-handler.png" /><br> + <em>Figure 9: The Server Tranport Handler for gRPC-Java.</em> +</p> + + +<h3>3.5.1 <em>Downloading gRPC Java</em></h3> + +The easiest way to download the gRPC-Java implementation is by performing the following command: + +``` +git clone -b v1.0.0 https://github.com/grpc/grpc-java.git +``` + +Next compile on a Windows machine using Gradle (or Maven) using the following steps - and if you are using any Firewall software it might be necessary to temporarily disable it while compiling gRPC-Java as sockets are used for the tests: + +``` +cd grpc-java +set GRADLE_OPTS=-Xmx2048m +set JAVA_OPTS=-Xmx2048m +set DEFAULT_JVM_OPTS="-Dfile.encoding=utf-8" +echo skipCodegen=true > gradle.properties +gradlew.bat build -x test +cd examples +gradlew.bat installDist +``` + +If you are having issues with Unicode (UTF-8) translation when using Git on Windows, you can try the following commands after entering the `examples` folder: + +``` +wget https://raw.githubusercontent.com/benelot/grpc-java/feb88a96a4bc689631baec11abe989a776230b74/examples/src/main/java/io/grpc/examples/routeguide/RouteGuideServer.java + +copy RouteGuideServer.java src\main\java\io\grpc\examples\routeguide\RouteGuideServer.java +``` + +<h3>3.5.2 <em>Running the Hello World Demonstration</em></h3> + +Make sure you open two Command (Terminal) windows, each within the `grpc-java\examples\build\install\examples\bin` folder. In the first of the two windows type the following command: + +``` +hello-world-server.bat +``` + +You should see the following: + +<p align="center"> + <img src="figures/hello-world-server.png" /><br> + <em>Figure 10: The Hello World gRPC Server.</em> +</p> + +In the second of the two windows type the following command: + +``` +hello-world-client.bat +``` + +You should see the following response: + +<p align="center"> + <img src="figures/hello-world-client.png" /><br> + <em>Figure 10: The Hello World gRPC Client and the response from the Server.</em> +</p> + +<h3>4 <em>Conclusion</em></h3> + +This chapter presented an overview of the concepts behing gRPC, HTTP/2 and will be expanded in both breadth and language implementations. The area of microservices one can see how a server endpoint can actually spawn more endpoints where the message content is the protobuf definition for new endpoints to be generated for load-balancing like for the classical Actor Model. + +## References + +` `[Apigee]: https://www.youtube.com/watch?v=-2sWDr3Z0Wo + +` `[Authentication]: http://www.grpc.io/docs/guides/auth.html + +` `[Benchmarks]: http://www.grpc.io/docs/guides/benchmarking.html + +` `[CoreSurfaceAPIs]: https://github.com/grpc/grpc/tree/master/src/core + +` `[ErrorModel]: http://www.grpc.io/docs/guides/error.html + +` `[gRPC]: https://github.com/grpc/grpc/blob/master/doc/g_stands_for.md + +` `[gRPC-Companies]: http://www.grpc.io/about/ + +` `[gRPC-Languages]: http://www.grpc.io/docs/ + +` `[gRPC-Protos]: https://github.com/googleapis/googleapis/ + +` `[Netty]: http://netty.io/ + +` `[RFC7540]: http://httpwg.org/specs/rfc7540.html + +` `[HelloWorldProto]: https://github.com/grpc/grpc/blob/master/examples/protos/ +helloworld.proto + +` `[Protobuf-Types]: https://developers.google.com/protocol-buffers/docs/encoding + +` `[gRPC-Overview]: http://www.grpc.io/docs/guides/ + +` `[gRPC-Languages]: http://www.grpc.io/about/#osp + +` `[gRPC-Benchmark]: http://www.grpc.io/docs/guides/benchmarking.html diff --git a/chapter/1/rpc.md b/chapter/1/rpc.md index a05022f..7688455 100644 --- a/chapter/1/rpc.md +++ b/chapter/1/rpc.md @@ -1,176 +1,239 @@ --- layout: page -title: "RPC is Not Dead: Rise, Fall and the Rise of RPC" +title: "RPC is Not Dead: Rise, Fall and the Rise of Remote Procedure Calls" by: "Muzammil Abdul Rehman and Paul Grosu" --- -## Introduction +## Introduction: *Remote Procedure Call* (RPC) is a design *paradigm* that allow two entities to communicate over a communication channel in a general request-response mechanism. It was initially built as a tool for outsourcing computation to a server in a distributed system, however, it has evolved over the years to build modular, scalable, distributed, language-agnostic ecosystem of applications. This RPC *paradigm* has been part of the driving force in creating truly revolutionizing distributed systems and giving rise to various communication schemes and protocols between diverse systems. -RPC *paradigm* has been implemented in various forms in our every-day systems. From lower level applications like Network File Systems{% cite sunnfs --file rpc %} and Remote Direct Memory Access{% cite rpcoverrdma --file rpc %} to access protocols to developing an ecosystem of microservices, RPC has been used everywhere. Some of the major examples of RPC include SunNFS{% cite sunnfs --file rpc %}, Twitter's Finagle{% cite finalge --file rpc %}, Apache Thrift{% cite thrift --file rpc %}, Java RMI{% cite rmipaper --file rpc %}, SOAP, CORBA{% cite corba --file rpc %}, Google's gRPC{% cite grpc --file rpc %}. +RPC *paradigm* has been implemented in various forms in our every-day systems. From lower level applications like Network File Systems{% cite sunnfs --file rpc %} and Remote Direct Memory Access{% cite rpcoverrdma --file rpc %} to access protocols to developing an ecosystem of microservices, RPC has been used everywhere. Some of the major examples of RPC include SunNFS{% cite sunnfs --file rpc %}, Twitter's Finagle{% cite finagle --file rpc %}, Apache Thrift{% cite thrift --file rpc %}, Java RMI{% cite rmipaper --file rpc %}, SOAP, CORBA{% cite corba --file rpc %}, Google's gRPC{% cite grpc --file rpc %}. -* adds paragraph about rise and fall - -RPC has evolved over the years. Starting off as a synchronous, insecure, request-response system, RPC has evolved into a secure, asynchronous, fault-tolerant, resilient *paradigm* that has influenced protocols and programming designs, like, HTTP, REST, and just about anything with a request-response system. It has transitioned to an asynchronous bidirectional communication for connecting services and devices across the internet. RPC has influenced various design paradigms and communication protocols. +RPC has evolved over the years. Starting off as a synchronous, insecure, request-response system, RPC has evolved into a secure, asynchronous, resilient *paradigm* that has influenced protocols and programming designs, like, HTTP, REST, and just about anything with a request-response system. It has transitioned to an asynchronous bidirectional communication for connecting services and devices across the internet. RPC has influenced various design paradigms and communication protocols. ## Remote Procedure Calls: -* Diagram of RPC: Local and remote endpoints, communication protocol. - *Remote Procedure Call paradigm* can be defined, at a high level, as a set of two language-agnostic communication *endpoints* connected over a network with one endpoint sending a request and the other endpoint generating a response based on that request. In the simplest terms, it's a request-response paradigm where the two *endpoints*/hosts have different *address space*. The host that requests a remote procedure can be referred to as *caller* and the host that responds to this can be referred to as *callee*. -The *endpoints* in the RPC can either be a client and a server, two nodes in a peer-to-peer network, two hosts in a grid computation system, or even two microservices. The RPC communcation is not limited to two hosts, rather could have multiple hosts or *endpoints* involved {% cite anycastrpc --file rpc %}. +The *endpoints* in the RPC can either be a client and a server, two nodes in a peer-to-peer network, two hosts in a grid computation system, or even two microservices. The RPC communication is not limited to two hosts, rather could have multiple hosts or *endpoints* involved {% cite anycastrpc --file rpc %}. + +<figure> + <img src="{{ site.baseurl }}/resources/img/rpc_chapter_1_ycog_10_steps.png" alt="RPC in 10 Steps." /> +<p>Fig1. - Remote Procedure Call{% cite rpcimage --file rpc %}.</p> +</figure> + +The simplest RPC implementation looks like Fig1. In this case, the *client*(or *caller*) and the *server*(or *callee*) are separated by a physical network. The main components of the system are the client routine/program, the client stub, the server routine/program, the server stub, and the network routines. The client program can only interact with the client stub that provides the interface of the remote server to the client. This stub also provides marshalling/pickling/serialization of the input arguments sent to the stub by the client routine. Similarly, the server stub provides a client interface to the server routines. Whenever a client routine has to perform a *remote procedure*, it calls the client stub, which serializes the input argument. This serialized data is sent to the server using OS network routines (TCP/IP). The data is serialized by the server stub, present to the server routines for the given arguments. The return value from the server routines is serialized again and sent over the network back to the client where it's deserialized by the client stub and presented to the client routine. This *remote procedure* is generally hidden from the client routine and it appears as a *local procedure* to the client. RPC services also require a discovery service/host-resolution mechanism to bootstrap the communication between the client and the server. + +One important feature of RPC is different *address space* {% cite implementingrpc --file rpc %} for all the endpoints, however, passing the locations to a global storage(Amazon S3, Microsoft Azure, Google Cloud Store) is not impossible. In RPC, all the hosts have separate *address spaces*. They can't share pointers or references to a memory location in one host. This *address space* isolation means that all the information is passed in the messages between the host communicating as a value (objects or variables) but not by reference. Since RPC is a *remote* procedure call, the values sent to the *remote* host cannot be pointers or references to a *local* memory. However, passing links to a global shared memory location is not impossible but rather dependent on the type of system (see *Applications* section for detail). + +Originally, RPC was developed as a synchronous, language-specific marshalling service with a custom network protocol to outsource computation {% cite implementingrpc --file rpc %}. It had registry-system to register all the servers. One of the earliest RPC-based system {% cite implementingrpc --file rpc %} was implemented in the Cedar programming language in early 1980's. The goal of this system was to provide similar programming semantics as local procedure calls. Developed for a LAN network with an inefficient network protocol and a *serialization* scheme to transfer information using the said network protocol, this system aimed at executing a *procedure*(also referred as *method* or a *function*) in a remote *address space*. The single-thread synchronous client and the server were written in an old *Cedar* programming language with a registry system used by the servers to *bind*(or register) their procedures. The clients used this registry system to find a specific server to execute their *remote* procedures. + +Modern RPC-based systems are language-agnostic, asynchronous, load-balanced systems. Authentication and authorization to these systems have been added as needed along with other security features. Most of these systems have fault-handling built into them as modules. + +RPC programs have a network (or a communication channel), therefore, they need to handle remote errors and be able to communication information successfully. Error handling generally varies and is categorized as *remote-host* or *network* failure handling. Depending on the type of the system, and the error, the caller (or the callee) return an error and these errors can be handled accordingly. For asynchronous RPC calls, it's possible to specify events to ensure progress. + +RPC implementations use a *serialization*(also referred to as *marshalling* or *pickling*) scheme on top of an underlying communication protocol (traditionally TCP over IP). These *serialization* schemes allow both the caller *caller* and *callee* to become language agnostic allowing both these systems to be developed in parallel without any language restrictions. Some examples of serialization schemes are JSON, XML, or Protocol Buffers {% cite grpc --file rpc %}. + +RPC allows different components of a larger system to be developed independently of one another. The language-agnostic nature combined with a decoupling of some parts of the system allows the two components (caller and callee) to scale separately and add new functionalities. This independent scaling of the system might lead to a mesh of interconnected RPC *services* facilitating one another. -* explain the diagram here. +### Examples of RPC -One important feature of RPC is different *address space* {% cite implementingrpc --file rpc %} for all the endpoints, however, passing the locations to a global storage(Amazon S3, Microsoft Azure, Google Cloud Store) is not impossible.In RPC, all the hosts have separate *address spaces*. They can't share pointers or references to a memory location in one host. This *address space* isolation means that all the information is passed in the messages between the host communicating as a value (objects or variables) but not by reference. Since RPC is a *remote* procedure call, the values sent to the *remote* host cannot be pointers or references to a *local* memory. However, passing links to a global shared memory location is not impossible but rather dependent on the type of system(see *Applications* section for detail). +RPC has become very predominant in modern systems. In the simplest RPC systems, a client connects to a server over a network connection and performs a *procedure*. This procedure could be as simple as `return "Hello World"` in your favorite programming language. However, the complexity of the of this remote procedure has no upper bound. -Originally, RPC was developed as a synchronous, language-specific marshalling service with a custom network protocol to outsource computation{% cite implementingrpc --file rpc %}. It had registry-system to register all the servers. One of the earliest RPC-based system{% cite implementingrpc --file rpc %} was implemented in the Cedar programming language in early 1980's. The goal of this system was to provide similar progamming semantics as local procedure calls. Developed for a LAN network with an inefficient network protocol and a *serialization* scheme to transfer information using the said network protocol, this system aimed at executing a *procedure*(also referred as *method* or a *function*) in a remote *address space*. The single-thread synchronous client and the server were written in an old *Cedar* programming language with a registry system used by the servers to *bind*(or register) their procedures. The clients used this registry system to find a specific server to execute their *remote* procedures. +Here's the code of this simple RPC server, written in Python3. +```python +from xmlrpc.server import SimpleXMLRPCServer -Modern RPC-based systems are language-agnostic, fault-tolerant, asynchronous, load-balanced systems. Authenticaiton and authorization to these systems have been added as needed along with other security features. +# a simple RPC function that returns "Hello World!" +def remote_procedure(n): + return "Hello World!" -RPC programs have a network, therefore, they need to handle remote errors and be able to communication information successfully. Error handling generally varies and is categorized as *remote-host* or *network* failure handling. Depending on the type of the system, and the error, the caller(or the callee) return an error and these errors can be handled accordingly. For asynchronous RPC calls, it's possible to specify events to ensure progress. +server = SimpleXMLRPCServer(("localhost", 8080)) +print("RPC Server listening on port 8080...") +server.register_function(remote_procedure, "remote_procedure") +server.serve_forever() +``` -RPC implementations use a *serialization*(also referred to as *marshalling* or *pickling*) scheme on top of an underlying communication protocol(traditionally TCP over IP). These *serialization* schemes allow both the caller *caller* and *callee* to become language agnostic allowing both these systems to be developed in parallel without any language restrictions. Some examples of serialization schemes are JSON, XML, or Protocol Buffers{% cite grpc --file rpc %}. +This code for a simple RPC client for the above server, written in Python3, is as follows. -RPC allows different components of a larger system to be developed independtly of one another. The language-agnostic nature combined with a decoupling of some parts of the system allows the two components(caller and callee) to scale separately and add new functionalities. +```python +import xmlrpc.client -Some RPC implementations have moved from a one-server model to a dynamically-created, load-balanced microservices. +with xmlrpc.client.ServerProxy("http://localhost:8080/") as proxy: + print(proxy.remote_procedure()) +``` -* Examples: - * One could view the internet as example of RPC.e.g TCP handshake(both act as server and client). - * First: Google Maps API(REST) - * SSL Handshake. +In the above example, we create a simple function called `remote_procedure` and *bind* it to port *8080* on *localhost*. The RPC client then connects to the server and *request* the `remote_procedure` with no input arguments. The server then *responds* with a return value of the `remote_procedure`. +One can even view the *three-way handshake* as an example of RPC paradigm. The *three-way handshake* is most commonly used in establishing a TCP connection. Here, a server-side application *binds* to a port on the server, and adds a hostname resolution entry is added to a DNS server(can be seen as a *registry* in RPC). Now, when the client has to connect to the server, it requests a DNS server to resolve the hostname to an IP address and the client sends a SYN packet. This SYN packet can be seen as a *request* to another *address space*. The server, upon receiving this, returns a SYN-ACK packet. This SYN-ACK packet from the server can be seen as *response* from the server, as well as a *request* to establish the connection. The client then *responds* with an ACK packet. ## Evolution of RPC: -RPC started in 1980’s and still continues as a relevant model of performing distributed computation, which initially was developed for a LAN and now can be globally implemented. +RPC paradigm was first proposed in 1980’s and still continues as a relevant model of performing distributed computation, which initially was developed for a LAN and now can be globally implemented. It has had a long and arduous journey to its current state. Here are the three main(overlapping) stages that RPC went through. -* RPC has evolved from what it was originally proposed. -* Chris’s thing: https://christophermeiklejohn.com/pl/2016/04/12/rpc.html -* diagram(maybe not): 4 lines, (y-axis: -1 to 1, x-axis 1980's 2016) +### The Rise: All Hail RPC(Early 1970's - Mid 1980's) -### The Rise: All Hail RPC +RPC started off strong. With RFCs{% cite rfc674 rfc707 --file rpc %} coming out and specifying the design of Remote Procedure Calls, followed by Nelson et. al{% cite implementingrpc --file rpc %} coming up with a first implementation for the Cedar programming language, RPC revolutionized systems in general and gave rise to one of the earliest distributed systems(apart from the internet, of course). -* RPC origin. +With these early achievements, people started using RPC as the defacto design choice. It became a Holy Grail in the systems community for a few years after the first implementation. - * Implementing RPC: [https://dl.acm.org/citation.cfm?id=357392](https://dl.acm.org/citation.cfm?id=357392) - * The RPC thesis(Nelson) - * More examples +### The Fall: RPC is Dead(Late 1970's - Late 1980's) -### The Fall: RPC is Dead +RPC, despite being an initial success, wasn't without flaws. Within a year of its inception, the limitation of the RPC started to catch up with it. RFC 684 criticized RPC for latency, failures, and the cost. It also focussed on message-passing systems as an alternative to RPC design. Similarly, a few years down the road, in 1988, Tenenbaum et. al presented similar concerns against RPC {%cite critiqueofrpc --file rpc %}. It talked about problems heterogeneous devices, message passing as an alternative, packet loss, network failure, RPC's synchronous nature, and highlighted that RPC is not a one-size-fits-all model. -* The fall of RPC/Criticism of RPC - * Limitations - * http://www.cs.vu.nl//~ast/afscheid/publications/euteco-1988.pdf - * Systems that use message passing. +### The Rise, Again: Long Live RPC(Early 1990's - Today) -### The Rise, Again: Long Live RPC +Despite facing problems in its early days, RPC withstood the test of time. Researchers realized the limitations of RPC and focussed on rectifying and instead of enforcing RPC, they started to use RPC in applications where it was needed. The designer started adding exception-handling, async, network failure handling and heterogenity between different languages/devices to RPC. -* gRPC -* XML SOAP -* Java RMI -* Finagle -* Thrift -* Apache Etch -* Sun RPC(ONC RPC) +Perhaps, the earliest system in this era was SunRPC {% cite sunnfs --file rpc %} used for the Sun Network File System(NFS). This SunRPC has gone under various additions and is now referred to as Open Network Computing RPC(ONC RPC). +Soon to follow SunRPC was the language-agnostic CORBA{% cite corba --file rpc %} which was followed by Java RMI{% cite rmipaper --file rpc %}. CORBA and RMI have also undergone various modifications as internet standards were set and TCP/IP became the norm. -#### Java Remote Method Invocation: -Java RMI (Java Remote Method Invocation){% cite rmibook --file rpc %} is a Java implementation for performing RPC (Remote Procedure Calls) between a client and a server. The client using a stub passes via a socket connection the information over the network to the server. The Remote Object Registry (ROR){% cite rmipaper --file rpc %} on the server contains the references to objects that can be accessed remotely and through which the client will connect to. The client then can request of the invocation of methods on the server for processing the requested call and then responds with the answer. RMI provides some security by being encoded but not encrypted, though that can be augmented by tunneling over a secure connection or other methods. +A new breed of RPC also started in this era(early 2000's), Async RPC, giving rise to systems that use *futures* and *promises*, like Finagle{% cite finagle --file rpc %} and Cap'n Proto(post-2010). +In the post-2000 era, MAUI{% cite maui --file rpc %}, Cap'n Proto{% cite capnproto --file rpc %}, gRPC{% cite grpc --file rpc %}, Thrift{% cite thrift --file rpc %} and Finagle{% cite finagle --file rpc %} have been released, which have significantly boosted the widespread use of RPC. A level overview of some of the most important RPC implementation is as follows. +#### Java Remote Method Invocation +Java RMI (Java Remote Method Invocation){% cite rmibook --file rpc %} is a Java implementation for performing RPC (Remote Procedure Calls) between a client and a server. The client using a stub passes via a socket connection the information over the network to the server. The Remote Object Registry (ROR){% cite rmipaper --file rpc %} on the server contains the references to objects that can be accessed remotely and through which the client will connect to. The client then can request of the invocation of methods on the server for processing the requested call and then responds with the answer. RMI provides some security by being encoded but not encrypted, though that can be augmented by tunneling over a secure connection or other methods. -#### CORBA: +#### CORBA CORBA (Common Object Request Broker Architecture){% cite corba --file rpc %} was created by the Object Management Group {% cite corbasite --file rpc %} to allow for language-agnostic communication among multiple computers. It is an object-oriented model defined via an Interface Definition Language (IDL) and the communication is managed through an Object Request Broker (ORB). Each client and server have an ORB by which they communicate. The benefits of CORBA is that it allows for multi-language implementations that can communicate with each other, but much of the criticism around CORBA relates to poor consistency among implementations. -#### XML-RPC and SOAP: +#### XML-RPC and SOAP +SOAP (Simple Object Access Protocol) is a successor of XML-RPC as a web-services protocol for communicating between a client and server. It was initially designed by a group at Microsoft {% cite soaparticle1 --file rpc %}. The SOAP message is an XML-formatted message composed of an envelope inside which a header and a body are provided. The body of the message contains the request and response of the message, which is transmitted over HTTP or SMTP. The benefit of such a protocol is that it provides the flexibility for transmission over multiple transport protocol, though parsing such messages could become a bottleneck. + +#### Thrift +Thrift is an RPC system created by Facebook and now part of the Apache Foundation {% cite thrift --file rpc %}. It is a language-agnostic IDL by which one generates the code for the client and server. It provides the opportunity for compressed serialization by customizing the protocol and the transport after the description file has been processed. + +#### Finagle +Finagle was generated by Twitter and is an RPC system written in Scala and can run on a JVM. It is based on three object types: Service objects, Filter objects and Future objects {% cite finagle --file rpc %}. The Future objects act by asynchronously being requested for a computation that would return a response at some time in the future. The Service objects are an endpoint that will return a Future upon processing a request. A Filter object transforms requests for further processing in case additional customization is required from a request. + +#### Open Network Computing RPC(ONC RPC) +ONC was originally introduced as SunRPC {%cite sunrpc --file rpc %} for the Sun NFS. The Sun NFS system had a stateless server, with client-side caching, unique file-handlers, and supported NFS read, write, truncate, unlink, etc operations. However, SunRPC was later revised as ONC in 1995 {%cite rfc1831 --file rpc %} and then in 2009 {%cite rfc5531 --file rpc %}. The IDL used in ONC(and SunRPC) is External Data Representation (XDR), a serialization mechanism specific to networks communication and therefore, ONC is limited to applications like Network File Systems. + +#### Mobile Assistance Using Infrastructure(MAUI) +The MAUI project {% cite maui --file rpc %}, developed by Microsoft is a computation offloading system for mobile systems. It's an automated system that offloads a mobile code to a dedicated infrastructure in order to increase the battery life of the mobile, minimize the load on the programmer and perform complex computations offsite. MAUI uses RPC as the communication protocol between the mobile and the infrastructure. + +#### gRPC + +gRPC has been built as a collaboration between Google and Square as a public replacement of Stubby, ARCWire, and Sake {% cite Apigee --file rpc %}. The IDL for gRPC is Protocol Buffers(also referred as ProtoBuf). + +gRPC provides a platform for scalable, bi-directional streaming using both synchronized and asynchronous communication. It multiplexes the requests over a single connection using header compression. This makes it possible for gRPC to be used for mobile clients where battery life and data usage are important. +The core library is in C -- except for Java and GO -- and surface APIs are implemented for all the other languages connecting through it{% cite CoreSurfaceAPIs --file rpc %}. -SOAP (Simple Object Access Protocol) is a successor of XML-RPC as a web-services protocol for communicating between a client and server. It was initially designed by a group at Microsoft {% cite soaparticle1 --file rpc %}. The SOAP message is a XML-formatted message composed of an envelope inside which a header and a body is provided. The body of the message contains the request and response of the message, which is transmitted over HTTP or SMTP. The benefits of such a protocol is that provides the flexibility for transmission of multiple tranport protocol, though parsing such messages could become a bottleneck. +Since Protocol Buffers has been utilized by many individuals and companies, gRPC makes it natural to extend their RPC ecosystems via gRPC. Companies like Cisco, Juniper and Netflix {% cite gRPCCompanies --file rpc %} have found it practical to adopt it. +A majority of the Google Public APIs, like their places and maps APIs, have been ported to gRPC ProtoBuf {% cite gRPCProtos --file rpc %} as well. +#### Cap'n Proto +CapnProto{% cite capnproto --file rpc %} is a data interchange RPC system between that bypasses data-encoding step(like JSON or ProtoBuf) to significantly improve the performance. It's developed by the original author of gRPC's ProtoBuf, but since it uses bytes(binary data) for encoding/decoding, it outperforms gRPC's ProtoBuf. It uses futures and promises to combine various remote operations into a single to save the transportation round-trips. -#### Thrift: -Thrift is a RPC created by Facebook and now part of the Apache Foundation {% cite thrift --file rpc %}. It is a language-agnostic IDL by which one generates the code for the client and server. It provides the opportunity for compressed serialization by customizing the protocol and the transport after the description file has been processed. +### The Heir to the Throne: gRPC or Thrift -#### Finagle: -Finagle was generated by Twitter and is an RPC written in Scala and can run on an JVM. It is based on three object types: Service objects, Filter objects and Future objects{% cite finagle --file rpc %}. The Future objects acts by asynchronously being requested for a computation that would return a response at some time in the future. The Service objects are an endpoint that will return a Future upon processing a request. A Filter object transforms requests for further processing in case additional customization is required from a request. +Although there are many candidates to be considered as top contenders for RPC throne, most of these are targeted for a specific type of application. ONC is generally specific to the Network File System(though it's being pushed as a standard), Cap'n Proto is relatively new and untested, MAUI is specific to mobile systems, the open-source Finagle is primarily being used at Twitter(not widespread), and the Java RMI simply doesn't even close anyways(sorry to burst your bubble Java fans). -#### Open Network Computing RPC: -* Pros and Cons +Probably, the most powerful, and practical systems out there are Apache Thrift and Google's gRPC, primarily because *variants* of these two systems have been developed and used by Facebook and Google, respectively. This might be considered as biased view against other RPC implementations, however, when one considers Big Data and Internet-scale, only these two companies (and these two systems) come close. -#### gRPC: +Thrift was actually released a few years ago, while the first stable release for gRPC came out in August 2016. However, despite being 'out there', Thrift is currently less popular than gRPC {%cite trendrpcthrift --file rpc %}. -### The Contenders for the Throne: gRPC, Thrift or RMI +gRPC {% cite gRPCLanguages --file rpc %} and Thrift, both, support most of the popular languages, including Java, C/C++, and Python. Thrift supports other languages, like Ruby, Erlang, Perl, Javascript, Node.js and OCaml while gRPC currently supports Node.js and Go. -* gRPC vs Thrift (maybe also Finagle) +The gRPC core is written in C(with the exception of Java and Go) and wrappers are written in other languages to communicate with the core, while the Thrift core is written in C++. + +gRPC also provides easier bi-drectional streaming communicaiton between the caller and callee. The client generally initiates the communication {% cite gRPCLanguages --file rpc %} and once the connection is established the client and the server can perform reads and writes independently of each other. However, bi-directional streaming in Thrift might be a little difficult to handle, since it focuses explicitly on a client-server model. To enable bi-directionaly, async streaming, one may have to run two seperate systems {%cite grpcbetter --file rpc%}. + +Thrift provides exception-handling as a message while the programmer has to handle exceptions in gRPC. In Thrift, exceptions can be returned built into the message, while in gRPC, the programmer explicitly defines this behaviour. This Thrift exception-handling makes it easier to write client-side applications. + +Although custom authentication mechanisms can be implemented in both these system, gRPC come with a Google-backed authentication using SSL/TLS and Google Tokens {% cite grpcauth --file rpc %}. + +Moreover, gRPC-based network communication is done using HTTP/2. HTTP/2 makes it feasible for communicating parties to multiplex network connections using the same port. This is more efficient(in terms of memory usage) as compared to HTTP/1.1. Since, gRPC communication is done HTTP/2, it means that gRPC can easily multiplex different services. As for Thrift, multiplexing services is possible, however, due to lack of support from underlying transport protocol, it is performed using a `TMulitplexingProcessor` class {% cite multiplexingthrift --file rpc %}. + +However, both gRPC and Thrift allow async RPC calls. This means that a client can send a request to the server and continue with its execution and the response from the server is processed it arrives. + + +The major comparison between gRPC and Thrift can be summed in this table. + +| Comparison | Thrift | gRPC | +| ----- | ----- | ----- | +| License | Apache2 | BSD | +| Sync/Async RPC | Both | Both | +| Supported Languages | C++, Java, Python, PHP, Ruby, Erlang, Perl, Haskell, C#, Cocoa, JavaScript, Node.js, Smalltalk, and OCaml | C/C++, Python, Go, Java, Ruby, PHP, C#, Node.js, Objective-C | +| Core Language | C++| C | +| Exceptions | Allows being built in the message | Implemented by the programmer | +| Authentication | Custom | Custom + Google Tokens | +| Bi-Directionality | Not straightforward | Straightforward | +| Multiplexing | Possible via | Possible via HTTP/2 | + +Although, it's difficult to specifically choose one over the other, however, with increasing popularity of gRPC, and the fact that it's still in early stages of development, the general trend{%cite trendrpcthrift --file rpc %} over the past year has started to shift in favor of gRPC and it's giving Thrift a run for its money. + +**Note:** This study is performed in December 2016 so the results are expected to change with time. ## Applications: -* RPC and shared state (Persistence Layer): - * http://ieeexplore.ieee.org/document/1302942/?arnumber=1302942&tag=1 - * http://ieeexplore.ieee.org/document/918991/?arnumber=918991 +Since its inception, various papers have been published in applying RPC paradigm to different domains, as well as using RPC implementations to create new systems. Here are some of applications and systems that incorporated RPC. -* Grid computing: - * https://link.springer.com/article/10.1023/A:1024083511032 +#### Shared State and Persistence Layer -* Mobile Systems(offloading and battery requirements): - * https://link.springer.com/article/10.1007/s11036-012-0368-0 +One major limitation (and the advantage) of RPC is considered the separate *address space* of all the machines in the network. This means that *pointers* or *references* to a data object cannot be passed between the caller and the callee. Therefore, Interweave {% cite interweave2 interweave1 interweave3 --file rpc %} is a middleware system that allows scalable sharing of arbitrary data-types and language-independent processes running heterogeneous hardware. Interweave is specifically designed and is compatible with RPC-based systems and allows easier access to the shared resources between different applications. It even allows passing C *pointers* between the caller and the callee. -* Embedded RPC: - * https://dl.acm.org/citation.cfm?id=1127840 +#### GridRPC -* Micro services architecture(ecosystem) +Grid computing is one of the most widely used applications of RPC paradigm. At a high level, it can be seen as a mesh (or a network) of computers connected with each other to for *grid* such each system can leverage resources from any other system in the network. -* RPC can be async +In the GridRPC paradigm, each computer in the network can act as the *caller* or the *callee* depending on the amount of resources required {% cite grid1 --file rpc %}. It's also possible for the same computer to act as the *caller* as well as the *callee* for *different* computations. -* Shared State +Some of the most popular implementations that allow one to have GridRPC-compliant middleware are GridSolve{% cite gridsolve1 gridsolve2 --file rpc %} and Ninf-G{% cite ninf --file rpc %}. Ninf is relatively older than GridSolve and was first published in the late 1990's. It's a simple RPC layer that also provides authentication and secure communication between the two parties. GridSolve, on the other hand, is relatively complex and provides a middleware for the communications using a client-agent-server model. -* microservices +#### Mobile Systems and Computation Offloading -* Futures and promises: RPC? +Mobile systems have become very powerful these days. With multi-core processors and gigabytes of RAM, they can undertake relatively complex computations without a hassle. Due to this advancement, they consume a larger amount of energy and hence, their batteries, despite becoming larger, drain quickly with usage. Moreover, mobile data (network bandwidth) is still limited and expensive. Due to these requirements, it's better to offload mobile computations from mobile systems when possible. RPC plays an important role in the communication for this *computation offloading*. Some of these services use Grid RPC technologies to offload this computation. Whereas, other technologies use an RMI(Remote Method Invocation) system for this. -### Streaming requests and buffered responses +The Ibis Project {% cite ibis --file rpc %} builds an RMI and GMI (Group Method Invocation) model to facilitate outsourcing computation. Cuckoo {% cite cuckoo --file rpc %} uses this Ibis communication middleware to offload computation. -### RPC in microservices ecosystem: +The Microsoft's MAUI Project {% cite maui --file rpc %} uses RPC communication and allows partitioning of .NET applications and "fine-grained code offload to maximize energy savings with minimal burden on the programmer". MAUI decides the methods to offload to the external MAUI server at runtime. -RPC started as a separate implements of REST, Streaming RPC, and now made possible of integration of all these implementations as a single abstraction for a user endpoint service. +#### Async RPC, Futures and Promises -* Creating new services. +Remote Procedure Calls can be asynchronous. Not only that but these async RPCs play in integral role in the *futures* and *promises*. *Future* and *promises* are programming constructs that where a *future* is seen as variable/data/return type/error while a *promise* is seen as a *future* that doesn't have a value, yet. We follow Finagle's {% cite finagle --file rpc %} definition of *futures* and *promises*, where the *promise* of a *future*(an empty *future*) is considered as a *request* while the async fulfillment of this *promise* by a *future* is seen as the *response*. This construct is primarily used for concurrent programming. -* Bootstrapping +Perhaps the most renowned systems using this type of RPC model are Twitter's Finagle{% cite finagle --file rpc %} and Cap'n Proto{% cite capnproto --file rpc %}. -* Load balancing - * Creating new services in Actor-Like model - * Fault tolerance - * Self-recovery +#### RPC in Microservices Ecosystem: -* Business and Persistence Layer were combined and the Persistence layer is not shared anymore, where each endpoints has its own persistent state: - * https://help.sap.com/saphelp_nwmobile711/helpdata/de/7e/d1a40b5bc84868b1606ce0dc72d88b/content.htm +RPC implementations have moved from a one-server model to multiple servers and on to dynamically-created, load-balanced microservices. RPC started as a separate implementations of REST, Streaming RPC, MAUI, gRPC, Cap'n Proto, and has now made it possible for integration of all these implementations as a single abstraction as a user *endpoint* service. The endpoints are the building blocks of *microservices*. These *microservices* interact with each other and applications and combine to give the feel of one large monolithic service. + +The use of RPC has allowed us to create new microservices on-the-fly. The microservices can not only created and bootstrapped at runtime but also have inherent features like load-balancing and failure-recovery. This bootstrapping might occur on the same machine, adding to a Docker container {% cite docker --file rpc %}, or across a network (using any combination of DNS, NATs or other mechanisms). + +RPC can be defined as the "glue" that holds all the microservices together{% cite microservices1rpc --file rpc %}. This means that RPC is one of the primary communication mechanism between different microservices running on different systems. A microservice requests another microservice to perform an operation/query. The other microservice, upon receiving such request, performs an operation and returns a response. This operation could vary from a simple computation to invoking another microservice creating a series of RPC events to creating new microservices on the fly to dynamically load balance the microservices system. + +An example of a microservices ecosystem that uses futures/promises is Finagle at Twitter. ## Security in RPC: -* Initially it was separate. - * Authentication, authorization issues have been resolved -* Now embedded in the protocol -* Security and Privacy in RPC - * Bugs in the libraries. - * Trust Issues between client and the server. - * http://static.usenix.org/publications/library/proceedings/sec02/full_papers/giffin/giffin_html/ - * Brewer’s view: https://people.eecs.berkeley.edu/~brewer/cs262b-2004/PODC-keynote.pdf - * E programming language: distributed object model/VAT + +The initial RPC implementation {% cite implementingrpc --file rpc %} was developed for an isolated LAN network and didn't focus much on security. There're various attack surfaces in that model, from the malicious registry, to a malicious server, to a client targeting for Denial-of-Service to Man-in-the-Middle attack between client and server. + +As time progressed and internet evolved, new standards came along, and RPC implementations became much more secure. Security, in RPC, is generally added as a *module* or a *package*. These modules have libraries for authentication and authorization of the communication services (caller and callee). These modules are not always bug-free and it's possible to gain unauthorized access to the system. Efforts are being made to rectify these situations by the security in general, using code inspection and bug bounty programs to catch these bugs before-hand. However, with time new bugs arise and this cycle continues. It's a vicious cycle between attackers and security experts, both of whom tries to outdo their opponent. + +For example, the Oracle Network File System uses a *Secure RPC*{% cite oraclenfs --file rpc %} to perform authentication in the NFS. This *Secure RPC* uses Diffie-Hellman authentication mechanism with DES encryption to allow only authorized users to access the NFS. Similarly, Cap'n Proto {% cite capnprotosecure --file rpc %} claims that it is resilient to memory leaks, segfaults, and malicious inputs and can be used between mutually untrusting parties. However, in Cap'n Proto "the RPC layer is not robust against resource exhaustion attacks, possibly allowing denials of service", nor has it undergone any formal verification {% cite capnprotosecure --file rpc %}. + +Although, it's possible to come up with a *Threat Model* that would make an RPC implementation insecure to use, however, one has to understand that using any distributed system increases the attack surface anyways and claiming one *paradigm* to be more secure than another would be a biased statement, since *paradigms* are generally an idea and it depends on different system designers to use these *paradigms* to build their systems and take care of features specific to real systems, like security and load-balancing. There's always a possibility of rerouting a request to a malicious server(if the registry gets hacked), or there's no trust between the *caller* and *callee*. However, we maintain that RPC *paradigm* is not secure or insecure(for that matter), and that the most secure systems are the ones that are in an isolated environment, disconnected from the public internet with a self-destruct mechanism{% cite self --file rpc %} in place, in an impenetrable bunker, and guarded by the Knights Templar(*they don't exist! Well, maybe Fort Meade comes close*). ## Discussion: -* RPC vs REST and other services. RPC influence. -* The future of RPC - * Where it shines. Not in message passing. - * RPC is not XYZ (HTTP, REST, …) though it has influenced. -## Conclusions(maybe not a heading): +RPC *paradigm* shines the most in *request-response* mechanisms. Futures and Promises also appear to a new breed of RPC. This leads one to question, as to whether every *request-response* system is a modified implementation to of the RPC *paradigm*, or does it actually bring anything new to the table? These modern communication protocols, like HTTP and REST, might just be a different flavor of RPC. In HTTP, a client *requests* a web page(or some other content), the server then *responds* with the required content. The dynamics of this communication might be slightly different from your traditional RPC, however, an HTTP Stateless server adheres to most of the concepts behind RPC *paradigm*. Similarly, consider sending a request to your favorite Google API. Say, you want to translate your latitude/longitude to an address using their Reverse Geocoding API, or maybe want to find out a good restaurant in your vicinity using their Places API, you'll send a *request* to their server to perform a *procedure* that would take a few input arguments, like the coordinates, and return the result. Even though these APIs follow a RESTful design, it appears to be an extension to the RPC *paradigm*. + +RPC paradigm has evolved over time. It has evolved to the extent that, currently, it's become very difficult differentiate RPC from non-RPC. For the past decades, researchers and industry leaders have tried to come up with *their* definition of RPC. The proponents of RPC paradigm view every *request-response* communication as an implementation the RPC paradigm while those against RPC try to explicitly come up with the bounds of RPC. RPC supporters consider it as the Holy Grail of distributed systems. They view it as the foundation of modern distributed communication. From Apache Thrift and ONC to HTTP and REST, they advocate it all as RPC while REST developers have strong opinions against RPC. + +Moreover, with modern global storage mechanisms, the need for RPC systems to have a separate *address space* seems to be slowly dissolving and disappearing into thin air. So, the question remains what *is* RPC and what * is not* RPC? This is an open-ended question. There is no unanimous agreement about what RPC should look like, except that it has communication between two *endpoints*. What we think of RPC is: -RPC is not dead: long live the Remote Procedure calls. +*"In the world of distributed systems, where every individual component of a system, be it a hard disk, a multi-core processor, or a microservice, is an extension of the RPC, it's difficult to come with a concrete definition of the RPC paradigm. Therefore, anything loosely associated with a request-response mechanism can be considered as RPC".* +<blockquote> +<p align="center"> +**RPC is not dead, long live RPC!** +</p> +</blockquote> ## References -{% bibliography --file rpc %}
\ No newline at end of file +{% bibliography --file rpc --cited %} diff --git a/chapter/2/1.png b/chapter/2/1.png Binary files differnew file mode 100644 index 0000000..1d98f19 --- /dev/null +++ b/chapter/2/1.png diff --git a/chapter/2/10.png b/chapter/2/10.png Binary files differnew file mode 100644 index 0000000..f54711d --- /dev/null +++ b/chapter/2/10.png diff --git a/chapter/2/11.png b/chapter/2/11.png Binary files differnew file mode 100644 index 0000000..7673d90 --- /dev/null +++ b/chapter/2/11.png diff --git a/chapter/2/12.png b/chapter/2/12.png Binary files differnew file mode 100644 index 0000000..7b2e13f --- /dev/null +++ b/chapter/2/12.png diff --git a/chapter/2/13.png b/chapter/2/13.png Binary files differnew file mode 100644 index 0000000..a2b8457 --- /dev/null +++ b/chapter/2/13.png diff --git a/chapter/2/14.png b/chapter/2/14.png Binary files differnew file mode 100644 index 0000000..5027666 --- /dev/null +++ b/chapter/2/14.png diff --git a/chapter/2/15.png b/chapter/2/15.png Binary files differnew file mode 100644 index 0000000..4f2c188 --- /dev/null +++ b/chapter/2/15.png diff --git a/chapter/2/2.png b/chapter/2/2.png Binary files differnew file mode 100644 index 0000000..a75c08b --- /dev/null +++ b/chapter/2/2.png diff --git a/chapter/2/3.png b/chapter/2/3.png Binary files differnew file mode 100644 index 0000000..9cc66b5 --- /dev/null +++ b/chapter/2/3.png diff --git a/chapter/2/4.png b/chapter/2/4.png Binary files differnew file mode 100644 index 0000000..8cfec98 --- /dev/null +++ b/chapter/2/4.png diff --git a/chapter/2/5.png b/chapter/2/5.png Binary files differnew file mode 100644 index 0000000..b86de04 --- /dev/null +++ b/chapter/2/5.png diff --git a/chapter/2/6.png b/chapter/2/6.png Binary files differnew file mode 100644 index 0000000..aaafdbd --- /dev/null +++ b/chapter/2/6.png diff --git a/chapter/2/7.png b/chapter/2/7.png Binary files differnew file mode 100644 index 0000000..7183fb6 --- /dev/null +++ b/chapter/2/7.png diff --git a/chapter/2/8.png b/chapter/2/8.png Binary files differnew file mode 100644 index 0000000..d6d2e0e --- /dev/null +++ b/chapter/2/8.png diff --git a/chapter/2/9.png b/chapter/2/9.png Binary files differnew file mode 100644 index 0000000..1b67a45 --- /dev/null +++ b/chapter/2/9.png diff --git a/chapter/2/futures.md b/chapter/2/futures.md index 5c56e92..45d2d0b 100644 --- a/chapter/2/futures.md +++ b/chapter/2/futures.md @@ -1,11 +1,309 @@ --- layout: page title: "Futures" -by: "Joe Schmoe and Mary Jane" +by: "Kisalaya Prasad and Avanti Patil" --- -Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum. {% cite Uniqueness --file futures %} +#Introduction + +As human beings we have an ability to multitask ie. we can walk, talk and eat at the same time except when you sneeze. Sneeze is like a blocking activity from the normal course of action, because it forces you to stop what you’re doing for a brief moment and then you resume where you left off. Activities like multitasking are called multithreading in computer lingo. In contrast to this behaviour, computer processors are single threaded. So when we say that a computer system has multi-threaded environment, it is actually just an illusion created by processor where processor’s time is shared between multiple processes. Sometimes processor gets blocked when some tasks are hindered from normal execution due to blocking calls. Such blocking calls can range from IO operations like read/write to disk or sending/receiving packets to/from network. Blocking calls can take disproportionate amount of time compared to the processor’s task execution i.e. iterating over a list. + + +The processor can either handle blocking calls in two ways: +- **Synchronous method**: As a part of running task in synchronous method, processor continues to wait for the blocking call to complete the task and return the result. After this processor will resume processing next task. Problem with this kind of method is CPU time not utilized in an ideal manner. +- **Asynchronous method**: When you add asynchrony, you can utilize the time of CPU to work on some other task using one of the preemptive time sharing algorithm. Now when the asynchronous call returns the result, processor can again switch back to the previous process using preemption and resume the process from the point where it’d left off. + +In the world of asynchronous communications many terminologies were defined to help programmers reach the ideal level of resource utilization. As a part of this article we will talk about motivation behind rise of Promises and Futures, we will explain programming model associated with it and discuss evolution of this programming construct, finally we will end this discussion with how this construct helps us today in different general purpose programming languages. + + +<figure class="main-container"> + <img src="./1.png" alt="timeline" /> +</figure> + +#Motivation + + +A “Promise” object represents a value that may not be available yet. A Promise is an object that represents a task with two possible outcomes, success or failure and holds callbacks that fire when one outcome or the other has occurred. + + +The rise of promises and futures as a topic of relevance can be traced parallel to the rise of asynchronous or distributed systems. This seems natural, since futures represent a value available in Future which fits in very naturally with the latency which is inherent to these heterogeneous systems. The recent adoption of NodeJS and server side Javascript has only made promises more relevant. But, the idea of having a placeholder for a result came in significantly before than the current notion of futures and promises. + + +Thunks can be thought of as a primitive notion of a Future or Promise. According to its inventor P. Z. Ingerman, thunks are "A piece of coding which provides an address". They were designed as a way of binding actual parameters to their formal definitions in Algol-60 procedure calls. If a procedure is called with an expression in the place of a formal parameter, the compiler generates a thunk which computes the expression and leaves the address of the result in some standard location. + + +The first mention of Futures was by Baker and Hewitt in a paper on Incremental Garbage Collection of Processes. They coined the term - call-by-futures to describe a calling convention in which each formal parameter to a method is bound to a process which evaluates the expression in the parameter in parallel with other parameters. Before this paper, Algol 68 also presented a way to make this kind of concurrent parameter evaluation possible, using the collateral clauses and parallel clauses for parameter binding. + + +In their paper, Baker and Hewitt introduced a notion of Futures as a 3-tuple representing an expression E consisting of (1) A process which evaluates E, (2) A memory location where the result of E needs to be stored, (3) A list of processes which are waiting on E. But, the major focus of their work was not on role of futures and the role they play in Asynchronous distributed computing, and focused on garbage collecting the processes which evaluate expressions not needed by the function. + + +The Multilisp language, presented by Halestead in 1985 built upon this call-by-future with a Future annotation. Binding a variable to a future expression creates a process which evaluates that expression and binds x to a token which represents its (eventual) result. This design of futures influenced the paper of design of Promises in Argus by Liskov and Shrira in 1988. Building upon the initial design of Future in Multilisp, they extended the original idea by introducing strongly typed Promises and integration with call streams.This made it easier to handle exception propagation from callee to the caller and also to handle the typical problems in a multi-computer system like network failures. This paper also talked about stream composition, a notion which is similar to promise pipelining today. + + +E is an object-oriented programming language for secure distributed computing, created by Mark S. Miller, Dan Bornstein, and others at Electric Communities in 1997. One of the major contribution of E was the first non-blocking implementation of Promises. It traces its routes to Joule which was a dataflow programming language. The notion of promise pipelining in E is inherited from Joule. + + +Among the modern languages, Python was perhaps the first to come up with something on the lines of E’s promises with the Twisted library. Coming out in 2002, it had a concept of Deferred objects, which were used to receive the result of an operation not yet completed. They were just like normal objects and could be passed along, but they didn’t have a value. They supported a callback which would get called once the result of the operation was complete. + + +Promises and javascript have an interesting history. In 2007 inspired by Python’s twisted, dojo came up with it’s own implementation of of dojo.Deferred. This inspired Kris Zyp to then come up with the CommonJS Promises/A spec in 2009. Ryan Dahl introduced the world to NodeJS in the same year. In it’s early versions, Node used promises for the non-blocking API. When NodeJS moved away from promises to its now familiar error-first callback API, it left a void for a promises API. Q.js was an implementation of Promises/A spec by Kris Kowal around this time. FuturesJS library by AJ ONeal was another library which aimed to solve flow-control problems without using Promises in the strictest of senses. In 2011, JQuery v1.5 first introduced Promises to its wider and ever-growing audience. The API for JQuery was subtly different than the Promises/A spec. With the rise of HTML5 and different APIs, there came a problem of different and messy interfaces. A+ promises aimed to solve this problem. From this point on, leading from widespread adoption of A+ spec, promises was finally made a part of ECMAScript® 2015 Language Specification. Still, a lack of backward compatibility and additional features provided means that libraries like BlueBird and Q.js still have a place in the javascript ecosystem. + + +#Different Definitions + + +Future, promise, Delay or Deferred generally refer to same synchronisation mechanism where an object acts as a proxy for a yet unknown result. When the result is discovered, promises hold some code which then gets executed. The definitions have changed a little over the years but the idea remained the same. + + +In some languages however, there is a subtle difference between what is a Future and a Promise. +“A ‘Future’ is a read-only reference to a yet-to-be-computed value”. +“A ‘Promise’ is a pretty much the same except that you can write to it as well.” + + +In other words, you can read from both Futures and Promises, but you can only write to Promises. You can get the Future associated with a Promise by calling the future method on it, but conversion in the other direction is not possible. Another way to look at it would be, if you Promise something, you are responsible for keeping it, but if someone else makes a Promise to you, you expect them to honor it in Future. + + +More technically, in Scala, “SIP-14 – Futures and Promises” defines them as follows: +A future is as a placeholder object for a result that does not yet exist. +A promise is a writable, single-assignment container, which completes a future. Promises can complete the future with a result to indicate success, or with an exception to indicate failure. + + +C# also makes the distinction between futures and promises. In C#, futures are implemented as Task<T> and in fact in earlier versions of the Task Parallel Library futures were implemented with a class Future<T> which later became Task<T>. The result of the future is available in the readonly property Task<T>.Result which returns T + + +In Javascript world, Jquery introduces a notion of Deferred objects which are used to represent a unit of work which is not yet finished. Deferred object contains a promise object which represent the result of that unit of work. Promises are values returned by a function, while the deferred object can be canceled by its caller. + + +In Java 8, the Future<T> interface has methods to check if the computation is complete, to wait for its completion, and to retrieve the result of the computation when it is complete. CompletableFutures can be thought of as Promises as their value can be set. But it also implements the Future interface and therefore it can be used as a Future too. Promises can be thought of as a future with a public set method which the caller (or anybody else) can use to set the value of the future. + +# Semantics of Execution + +Over the years promises and futures have been implemented in different programming languages and created a buzz in parallel computing world. We will take a look at some of the programming languages who designed frameworks to enhance performance of applications using Promises and futures. + +## Fork-Join + +Doing things in parallel is usually an effective way of doing things in modern systems. The systems are getting more and more capable of running more than one things at once, and the latency associated with doing things in a distributed environment is not going away anytime soon. Inside the JVM, threads are a basic unit of concurrency. Threads are independent, heap-sharing execution contexts. Threads are generally considered to be lightweight when compared to a process, and can share both code and data. The cost of context switching between threads is cheap. But, even if we claim that threads are lightweight, the cost of creation and destruction of threads in a long running threads can add up to something significant. A practical way is address this problem is to manage a pool of worker threads. + + +In Java executor is an object which executes the Runnable tasks. Executors provides a way of abstracting out how the details of how a task will actually run. These details, like selecting a thread to run the task, how the task is scheduled are managed by the object implementing the Executor interface. Threads are an example of a Runnable in java. Executors can be used instead of creating a thread explicitly. + + +Similar to Executor, there is an ExecutionContext as part of scala.concurrent. The basic intent behind it is same as an Executor : it is responsible for executing computations. How it does it can is opaque to the caller. It can create a new thread, use a pool of threads or run it on the same thread as the caller, although the last option is generally not recommended. Scala.concurrent package comes with an implementation of ExecutionContext by default, which is a global static thread pool. + + +ExecutionContext.global is an execution context backed by a ForkJoinPool. ForkJoin is a thread pool implementation designed to take advantage of a multiprocessor environment. What makes fork join unique is that it implements a type of work-stealing algorithm : idle threads pick up work from still busy threads. ForkJoinPool manages a small number of threads, usually limited to the number of processor cores available. It is possible to increase the number of threads, if all of the available threads are busy and wrapped inside a blocking call, although such situation would typically come with a bad system design. ForkJoin framework work to avoid pool-induced deadlock and minimize the amount of time spent switching between the threads. + + +Futures are generally a good way to reason about asynchronous code. A good way to call a webservice, add a block of code to do something when you get back the response, and move on without waiting for the response. They’re also a good framework to reason about concurrency as they can be executed in parallel, waited on, are composable, immutable once written and most importantly, are non blocking. in Scala, futures (and promises) are based on ExecutionContext. + + +In Scala, futures are created using an ExecutionContext. This gives the users flexibility to implement their own ExecutionContext if they need a specific behavior, like blocking futures. The default ForkJoin pool works well in most of the scenarios. Futures in scala are placeholders for a yet unknown value. A promise then can be thought of as a way to provide that value. A promise p completes the future returned by p.future. + + +Scala futures api expects an ExecutionContext to be passed along. This parameter is implicit, and usually ExecutionContext.global. An example : + + +<figure class="main-container"> + <img src="./2.png" alt="timeline" /> +</figure> + +In this example, the global execution context is used to asynchronously run the created future. Taking another example, + +<figure class="main-container"> + <img src="./3.png" alt="timeline" /> +</figure> + +It is generally a good idea to use callbacks with Futures, as the value may not be available when you want to use it. + +So, how does it all work together ? + +As we mentioned, Futures require an ExecutionContext, which is an implicit parameter to virtually all of the futures API. This ExecutionContext is used to execute the future. Scala is flexible enough to let users implement their own Execution Contexts, but let’s talk about the default ExecutionContext, which is a ForkJoinPool. + + +ForkJoinPool is ideal for many small computations that spawn off and then come back together. Scala’s ForkJoinPool requires the tasks submitted to it to be a ForkJoinTask. The tasks submitted to the global ExecutionContext is quietly wrapped inside a ForkJoinTask and then executed. ForkJoinPool also supports a possibly blocking task, using ManagedBlock method which creates a spare thread if required to ensure that there is sufficient parallelism if the current thread is blocked. To summarize, ForkJoinPool is an really good general purpose ExecutionContext, which works really well in most of the scenarios. + + + +## Event Loops + +Modern systems typically rely on many other systems to provide the functionality they do. There’s a file system underneath, a database system, and other web services to rely on for the information. Interaction with these components typically involves a period where we’re doing nothing but waiting for the response back. This is single largest waste of computing resources. + + +Javascript is a single threaded asynchronous runtime. Now, conventionally async programming is generally associated with multi-threading, but we’re not allowed to create new threads in Javascript. Instead, asynchronicity in Javascript is achieved using an event-loop mechanism. + + +Javascript has historically been used to interact with the DOM and user interactions in the browser, and thus an event-driven programming model was a natural fit for the language. This has scaled up surprisingly well in high throughput scenarios in NodeJS. + + +The general idea behind event-driven programming model is that the logic flow control is determined by the order in which events are processed. This is underpinned by a mechanism which is constantly listening for events and fires a callback when it is detected. This is the Javascript’s event loop in a nutshell. + + +A typical Javascript engine has a few basic components. They are : +- **Heap** +Used to allocate memory for objects +- **Stack** +Function call frames go into a stack from where they’re picked up from top to be executed. +- **Queue** + A message queue holds the messages to be processed. + + +Each message has a callback function which is fired when the message is processed. These messages can be generated by user actions like button clicks or scrolling, or by actions like HTTP requests, request to a database to fetch records or reading/writing to a file. + + +Separating when a message is queued from when it is executed means the single thread doesn’t have to wait for an action to complete before moving on to another. We attach a callback to the action we want to do, and when the time comes, the callback is run with the result of our action. Callbacks work good in isolation, but they force us into a continuation passing style of execution, what is otherwise known as Callback hell. + +<figure class="main-container"> + <img src="./4.png" alt="timeline" /> +</figure> + +**Programs must be written for people to read, and only incidentally for machines to execute.** - *Harold Abelson and Gerald Jay Sussman* + +Promises are an abstraction which make working with async operations in javascript much more fun. Moving on from a continuation passing style, where you specify what needs to be done once the action is done, the callee simply returns a Promise object. This inverts the chain of responsibility, as now the caller is responsible for handling the result of the promise when it is settled. + +The ES2015 spec specifies that “promises must not fire their resolution/rejection function on the same turn of the event loop that they are created on.” This is an important property because it ensures deterministic order of execution. Also, once a promise is fulfilled or failed, the promise’s value MUST not be changed. This ensures that a promise cannot be resolved more than once. + +Let’s take an example to understand the promise resolution workflow as it happens inside the Javascript Engine. + +Suppose we execute a function, here g() which in turn, calls function f(). Function f returns a promise, which, after counting down for 1000 ms, resolves the promise with a single value, true. Once f gets resolved, a value true or false is alerted based on the value of the promise. + + +<figure class="main-container"> + <img src="./5.png" alt="timeline" /> +</figure> + +Now, javascript’s runtime is single threaded. This statement is true, and not true. The thread which executes the user code is single threaded. It executes what is on top of the stack, runs it to completion, and then moves onto what is next on the stack. But, there are also a number of helper threads which handle things like network or timer/settimeout type events. This timing thread handles the counter for setTimeout. + +<figure class="main-container"> + <img src="./6.png" alt="timeline" /> +</figure> + +Once the timer expires, the timer thread puts a message on the message queue. The queued up messages are then handled by the event loop. The event loop as described above, is simply an infinite loop which checks if a message is ready to be processed, picks it up and puts it on the stack for it’s callback to be executed. + +<figure class="main-container"> + <img src="./7.png" alt="timeline" /> +</figure> + +Here, since the future is resolved with a value of true, we are alerted with a value true when the callback is picked up for execution. + +<figure class="main-container"> + <img src="./8.png" alt="timeline" /> +</figure> + +Some finer details : +We’ve ignored the heap here, but all the functions, variables and callbacks are stored on heap. +As we’ve seen here, even though Javascript is said to be single threaded, there are number of helper threads to help main thread do things like timeout, UI, network operations, file operations etc. +Run-to-completion helps us reason about the code in a nice way. Whenever a function starts, it needs to finish before yielding the main thread. The data it accesses cannot be modified by someone else. This also means every function needs to finish in a reasonable amount of time, otherwise the program seems hung. This makes Javascript well suited for I/O tasks which are queued up and then picked up when finished, but not for data processing intensive tasks which generally take long time to finish. +We haven’t talked about error handling, but it gets handled the same exact way, with the error callback being called with the error object the promise is rejected with. + + +Event loops have proven to be surprisingly performant. When network servers are designed around multithreading, as soon as you end up with a few hundred concurrent connections, the CPU spends so much of its time task switching that you start to lose overall performance. Switching from one thread to another has overhead which can add up significantly at scale. Apache used to choke even as low as a few hundred concurrent users when using a thread per connection while Node can scale up to a 100,000 concurrent connections based on event loops and asynchronous IO. + + +##Thread Model + + +Oz programming language introduced an idea of dataflow concurrency model. In Oz, whenever the program comes across an unbound variable, it waits for it to be resolved. This dataflow property of variables helps us write threads in Oz that communicate through streams in a producer-consumer pattern. The major benefit of dataflow based concurrency model is that it’s deterministic - same operation called with same parameters always produces the same result. It makes it a lot easier to reason about concurrent programs, if the code is side-effect free. + + +Alice ML is a dialect of Standard ML with support for lazy evaluation, concurrent, distributed, and constraint programming. The early aim of Alice project was to reconstruct the functionalities of Oz programming language on top of a typed programming language. Building on the Standard ML dialect, Alice also provides concurrency features as part of the language through the use of a future type. Futures in Alice represent an undetermined result of a concurrent operation. Promises in Alice ML are explicit handles for futures. + + +Any expression in Alice can be evaluated in it's own thread using spawn keyword. Spawn always returns a future which acts as a placeholder for the result of the operation. Futures in Alice ML can be thought of as functional threads, in a sense that threads in Alice always have a result. A thread is said to be touching a future if it performs an operation that requires the value future is a placeholder for. All threads touching a future are blocked until the future is resolved. If a thread raises an exception, the future is failed and this exception is re-raised in the threads touching it. Futures can also be passed along as values. This helps us achieve the dataflow model of concurrency in Alice. + + +Alice also allows for lazy evaluation of expressions. Expressions preceded with the lazy keyword are evaluated to a lazy future. The lazy future is evaluated when it is needed. If the computation associated with a concurrent or lazy future ends with an exception, it results in a failed future. Requesting a failed future does not block, it simply raises the exception that was the cause of the failure. + +#Implicit vs. Explicit Promises + + +We define Implicit promises as ones where we don’t have to manually trigger the computation vs Explicit promises where we have to trigger the resolution of future manually, either by calling a start function or by requiring the value. This distinction can be understood in terms of what triggers the calculation : With Implicit promises, the creation of a promise also triggers the computation, while with Explicit futures, one needs to triggers the resolution of a promise. This trigger can in turn be explicit, like calling a start method, or implicit, like lazy evaluation where the first use of a promise’s value triggers its evaluation. + + +The idea for explicit futures were introduced in the Baker and Hewitt paper. They’re a little trickier to implement, and require some support from the underlying language, and as such they aren’t that common. The Baker and Hewitt paper talked about using futures as placeholders for arguments to a function, which get evaluated in parallel, but when they’re needed. Also, lazy futures in Alice ML have a similar explicit invocation mechanism, the first thread touching a future triggers its evaluation. + +Implicit futures were introduced originally by Friedman and Wise in a paper in 1978. The ideas presented in that paper inspired the design of promises in MultiLisp. Futures are also implicit in Scala and Javascript, where they’re supported as libraries on top of the core languages. Implicit futures can be implemented this way as they don’t require support from language itself. Alice ML’s concurrent futures are also an example of implicit invocation. + +# Promise Pipelining +One of the criticism of traditional RPC systems would be that they’re blocking. Imagine a scenario where you need to call an API ‘a’ and another API ‘b’, then aggregate the results of both the calls and use that result as a parameter to another API ‘c’. Now, the logical way to go about doing this would be to call A and B in parallel, then once both finish, aggregate the result and call C. Unfortunately, in a blocking system, the way to go about is call a, wait for it to finish, call b, wait, then aggregate and call c. This seems like a waste of time, but in absence of asynchronicity, it is impossible. Even with asynchronicity, it gets a little difficult to manage or scale up the system linearly. Fortunately, we have promises. + +<figure class="main-container"> + <img src="./9.png" alt="timeline" /> +</figure> + +Futures/Promises can be passed along, waited upon, or chained and joined together. These properties helps make life easier for the programmers working with them. This also reduces the latency associated with distributed computing. Promises enable dataflow concurrency, which is also deterministic, and easier to reason. + +The history of promise pipelining can be traced back to the call-streams in Argus and channels in Joule. In Argus, Call streams are a mechanism for communication between distributed components. The communicating entities, a sender and a receiver are connected by a stream, and sender can make calls to receiver over it. Streams can be thought of as RPC, except that these allow callers to run in parallel with the receiver while processing the call. When making a call in Argus, the caller receives a promise for the result. In the paper on Promises by Liskov and Shrira, they mention that having integrated futures into call streams, next logical step would be to talk about stream composition. This means arranging streams into pipelines where output of one stream can be used as input of the next stream. They talk about composing streams using fork and coenter. + + +Modern promise specifications, like one in Javascript comes with methods which help working with promise pipelining easier. In javascript, a Promises.all method is provided, which takes in an iterable over Promises, and returns a new Promise which gets resolved when all the promises in the iterable get resolved. There’s also a race method, which returns a promise which is resolved when the first promise in the iterable gets resolved. + + +In scala, futures have a onSuccess method which acts as a callback to when the future is complete. This callback itself can be used to sequentially chain futures together. But this results in bulkier code. Fortunately, Scala api comes with combinators which allow for easier combination of results from futures. Examples of combinators are map, flatmap, filter, withFilter. + +# Handling Errors + +In a synchronous programming model, the most logical way of handling errors is a try...catch block. + +<figure class="main-container"> + <img src="./10.png" alt="timeline" /> +</figure> + + +Unfortunately, the same thing doesn’t directly translate to asynchronous code. + +<figure class="main-container"> + <img src="./11.png" alt="timeline" /> +</figure> + +In javascript world, some patterns emerged, most noticeably the error-first callback style, also adopted by Node. Although this works, but it is not very composable, and eventually takes us back to what is called callback hell. Fortunately, Promises come to the rescue. + + +Although most of the earlier papers did not talk about error handling, the Promises paper by Liskov and Shrira did acknowledge the possibility of failure in a distributed environment. They talked about propagation of exceptions from the called procedure to the caller and also about call streams, and how broken streams could be handled. E language also talked about broken promises and setting a promise to the exception of broken references. + +In modern languages, Promises generally come with two callbacks. One to handle the success case and other to handle the failure. + +<figure class="main-container"> + <img src="./12.png" alt="timeline" /> +</figure> + +In Javascript, Promises also have a catch method, which help deal with errors in a composition. Exceptions in promises behave the same way as they do in a synchronous block of code : they jump to the nearest exception handler. + + +<figure class="main-container"> + <img src="./13.png" alt="timeline" /> +</figure> + +The same behavior can be written using catch block. + +<figure class="main-container"> + <img src="./14.png" alt="timeline" /> +</figure> + + +#Futures and Promises in Action + + +##Twitter Finagle + + +Finagle is a protocol-agnostic, asynchronous RPC system for the JVM that makes it easy to build robust clients and servers in Java, Scala, or any JVM-hosted language. It uses idea of Futures to encapsulate concurrent tasks and are analogous to threads, but even more lightweight. + + +##Correctables +Correctables were introduced by Rachid Guerraoui, Matej Pavlovic, and Dragos-Adrian Seredinschi at OSDI ‘16, in a paper titled Incremental Consistency Guarantees for Replicated Objects. As the title suggests, Correctables aim to solve the problems with consistency in replicated objects. They provide incremental consistency guarantees by capturing successive changes to the value of a replicated object. Applications can opt to receive a fast but possibly inconsistent result if eventual consistency is acceptable, or to wait for a strongly consistent result. Correctables API draws inspiration from, and builds on the API of Promises. Promises have a two state model to represent an asynchronous task, it starts in blocked state and proceeds to a ready state when the value is available. This cannot represent the incremental nature of correctables. Instead, Correctables have a updating state when it starts. From there on, it remains in updating state during intermediate updates, and when the final result is available, it transitions to final state. If an error occurs in between, it moves into an error state. Each state change triggers a callback. + +<figure class="main-container"> + <img src="./15.png" alt="timeline" /> +</figure> + +##Folly Futures +Folly is a library by Facebook for asynchronous C++ inspired by the implementation of Futures by Twitter for Scala. It builds upon the Futures in the C++11 Standard. Like Scala’s futures, they also allow for implementing a custom executor which provides different ways of running a Future (thread pool, event loop etc). + + +##NodeJS Fiber +Fibers provide coroutine support for v8 and node. Applications can use Fibers to allow users to write code without using a ton of callbacks, without sacrificing the performance benefits of asynchronous IO. Think of fibers as light-weight threads for nodejs where the scheduling is in the hands of the programmer. The node-fibers library doesn’t recommend using raw API and code together without any abstractions, and provides a Futures implementation which is ‘fiber-aware’. ## References -{% bibliography --file futures %}
\ No newline at end of file +{% bibliography --file futures %} diff --git a/chapter/6/being-consistent.md b/chapter/6/being-consistent.md new file mode 100644 index 0000000..233d987 --- /dev/null +++ b/chapter/6/being-consistent.md @@ -0,0 +1,82 @@ +--- +layout: page +title: "Being Consistent" +by: "Aviral Goel" +--- + +## Replication and Consistency +Availability and Consistency are the defining characteristics of any distributed system. As dictated by the CAP theorem, accommodating network partitions requires a trade off between the two properties. Modern day large scale internet based distributed systems have to be highly available. To manage huge volumes of data (big data) and to reduce access latency for geographically diverse user base, their data centers also have to be geographically spread out. Network partitions which would otherwise happen with a low probability on a local network become certain events in such systems. To ensure availability in the event of partitions, these systems have to replicate data objects. This begs the question, how to ensure consistency of these replicas? It turns out there are different notions of consistency which the system can adhere to. + +* **Strong Consistency** implies linearizability of updates, i.e., all updates applied to a replicated data type are serialized in a global total order. This means that any update will have to be simultaneously applied to all other replicas. Its obvious that this notion of consistency is too restrictive. A single unavailable node will violate this condition. Forcing all updates to happen synchronously will impact system availability negatively. This notion clearly does not fit the requirements of highly available fault tolerant systems. + +* **Eventual Consistency** is a weaker model of consistency that does not guarantee immediate consistency of all replicas. Any local update is immediately executed on the replica. The replica then sends its state asynchronously to other replicas. As long as all replicas share their states with each other, the system eventually achieves stability. Each replica finally contains the same value. During the execution, all updates happen asynchronously at all replicas in a non-deterministic order. So replicas can be inconsistent between updates. If updates arrive concurrently at a replica, a consensus protocol can be employed to ensure that both updates taken together do not violate an invariant. If they do, a rollback has to be performed and the new state is communicated to all the other replicas. + +Most large scale distributed systems try to be **Eventually Consistent** to ensure high availability and partition-tolerance. But conflict resolution is hard. There is little guidance on correct approaches to consensus and its easy to come up with an error prone ad-hoc approach. What if we side-step conflict resolution and rollback completely? Is there a way to design data structures which do not require any consensus protocols to merge concurrent updates? + +## A Distributed Setting + +### TODO need to write pseudocode. Will finish this part with the detailed explanation of CRDTs in the next chapter. +Consider a replicated counter. Each node can increment the value of its local copy. The figure below shows three nodes which increment their local copies at arbitrary time points and each replica sends its value asynchronously to the other two replicas. Whenever it recieves the value of its replica, it adds it to its current value. If two values are received concurrently, both will be added together to its current value. So merging replicas in this example becomes trivial. + +Let's take a look at another interesting generalization of this. Integer Vector + + +We can make an interesting observation from the previous examples: + +__*All distributed data structures don't need conflict resolution*__ + +This raises the following question: + +__*How can we design a distributed structure such that we don't need conflict resolution?*__ + +The answer to this question lies in an algebraic structure called the **join semilattice**. + +## Join Semilattice +A join-semilattice or upper semilattice is a *partial order* `≤` with a *least upper bound* (LUB) `⊔` for all pairs. +`m = x ⊔ y` is a Least Upper Bound of `{` `x` `,` `y` `}` under `≤` iff `∀m′, x ≤ m′ ∧ y ≤ m′ ⇒ x ≤ m ∧ y ≤ m ∧ m ≤ m′`. + +`⊔` is: + +**Associative** + +`(x ⊔ y) ⊔ z = x ⊔ (y ⊔ z)` + +**Commutative** + +`x ⊔ y = y ⊔ x` + +**Idempotent** + +`x ⊔ x = x` + +The examples we saw earlier were of structures that could be modeled as join semilattices. The merge operation for the increment only counter is the summation function and for the integer vector it is the per-index maximum of the vectors being merged. +So, if we can model the state of the data structure as a partially ordered set and design the merge operation to always compute the "larger" of the two states, its replicas will never need consensus. They will always converge as execution proceeds. Such data structures are called CRDTs (Conflict-free Replicated Data Type). But what about consistency of these replicas? + +## Strong Eventual Consistency (SEC) +We discussed a notion of consistency, *Eventual Consistency*, in which replicas eventually become consistent if there are no more updates to be merged. But the update operation is left unspecified. Its possible for an update to render the replica in a state that causes it to conflict with a later update. In this case the replica may have to roll back and use consensus to ensure that all replicas do the same to ensure consistency. This is complicated and wasteful. But if replicas are modeled as CRDTs, the updates never conflict. Regardless of the order in which the updates are applied, all replicas will eventually have equivalent state. Note that no conflict arbitration is necessary. This kind of Eventual Consistency is a stronger notion of consistency than the one that requires conflict arbitration and hence is called *Strong Eventual Consistency*. + +### Strong Eventual Consistency and CAP Theorem + +Let's study SEC data objects from the perspective of CAP theorem. + +#### 1. Consistency and Network Partition +Each distributed replica will communicate asynchronously with other reachable replicas. These replicas will eventually converge to the same value. There is no consistency guarantee on the value of replicas not reachable due to network conditions and hence this condition is strictly weaker than strong consistency. But as soon as those replicas can be reached, they will also converge in a self-stabilizing manner. + +#### 2. Availability and Network Partition +Each distributed replica will always be available for local reads and writes regardless of network partitions. In fact, if there are n replicas, a single replica will function even if the remaining n - 1 replicas crash simultaneously. This **provides an extreme form of availability**. + +SEC facilitates maximum consistency and availability in the event of network partitions by relaxing the requirement of global consistency. Note that this is achieved by virtue of modeling the data objects as join semilattices. + +#### Strong Eventual Consistency and Linearizability +In a distributed setting, a replica has to handle concurrent updates. In addition to its sequential behavior, a CRDT also has to ensure that its concurrent behavior also ensures strong eventual consistency. This makes it possible for CRDTs to exhibit behavior that is simply not possible for sequentially consistent objects. +Consider a set CRDT used in a distributed setting. One of the replicas p<sub>i</sub> executes the sequence `add(a); remove(b)`. Another replica p<sub>j</sub> executes the sequence `add(b); remove(a)`. Now both send their states asynchronously to another replica p<sub>k</sub> which has to merge them concurrently. Same element exists in one of the sets and does not exist in the other set. There are multiple choices that the CRDT designer can make. Let's assume that the implementation always prefers inclusion over exclusion. So in this case, p<sub>k</sub> will include both `a` and `b`. +Now consider a sequential execution of the two sequences on set data structure. The order of execution will be either `add(a); remove(b); add(b); remove(a)` or `add(b); remove(a); add(a); remove(b)`. In both cases one of the elements is excluded. This is different from the state of the CRDT set implementation. +Thus, strong eventually consistent data structures can be sequentially inconsistent. +Similarly, if there are `n` sequentially consistent replicas, then they would need consensus to ensure a single order of execution of operations across all replicas. But if `n - 1` replicas crash, then consensus cannot happen. This makes the idea of sequential consistency incomparable to that of strong eventual consistency. + +## What Next? +This chapter introduced Strong Eventual Consistency and the formalism behind CRDTs, join semilattices, which enables CRDTs to exhibit strong eventual consistency. The discussion however does not answer an important question: + +__*Can all standard data structures be designed as CRDTs?*__ + +The next chapter sheds more light on the design of CRDTs and attempts to answer this question. diff --git a/resources/img/rpc_chapter_1_ycog_10_steps.png b/resources/img/rpc_chapter_1_ycog_10_steps.png Binary files differnew file mode 100644 index 0000000..86c7432 --- /dev/null +++ b/resources/img/rpc_chapter_1_ycog_10_steps.png |
