Overview In one word, binary search is to search for a target in a sorted array. The idea is to shrink the search space to empty. It must be sorted because we can be sure how to shrink the search space and we normally reduce the search space by half so the time complexity is O(logN) where N is the size of entire search space. One common problem to understand Binary Search is how to identify the boundary of the search space. ...
Overview FLP impossibility is to prove there is no algorithm can really achieve totally correct consensus in asychronous system under assumption at most one process is faulty. The paper is very famous and also difficult to understand given the wording. This article is to explain FLP impossibility in a plain way. Aschronous System In FLP paper, there are some settings/assumptions made to describe an aschronous system which is used in the proof. This system has: ...
What is gRPC gRPC is a high performance open-source freature-rich RPC (remote procedure calls) framework developed by google. “g” stands for many different meaning like green, good and etc. It is a protocal that allows a program to execute a procedure of another program located in other computer without the developer explicitly coding the details for the remote interaction gRPC is one kind of s2s call and widely used to replace REST API in the backend due to: ...
Environment Setup I am using Gradle and Intellij Idea for this project (Maven setting can be found here). The Gradle setting is shown as following: plugins { id "com.google.protobuf" version "0.8.18" id "java" } group 'today.ihelio.grpc.tutorial' version '1.0-SNAPSHOT' sourceCompatibility = 15 repositories { mavenCentral() } dependencies { implementation 'junit:junit:4.13.1' testImplementation 'org.junit.jupiter:junit-jupiter-api:5.8.1' testRuntimeOnly 'org.junit.jupiter:junit-jupiter-engine:5.8.1' implementation group: 'com.google.protobuf', name: 'protobuf-java', version: '3.21.4' runtimeOnly group: 'com.google.protobuf', name: 'protobuf-java-util', version: '3.21.4' implementation group: 'io.grpc', name: 'grpc-all', version: '1.45.1' runtimeOnly group: 'io.grpc', name: 'grpc-services', version: '1.48.0' implementation group: 'javax.annotation', name: 'javax.annotation-api', version: '1.3.2' } test { useJUnitPlatform() } sourceSets { main { java { srcDirs 'build/generated/source/proto/main/grpc' srcDirs 'build/generated/source/proto/main/java' srcDirs 'src/main/resources' } } } protobuf { protoc { artifact = 'com.google.protobuf:protoc:3.21.4' } plugins { grpc { artifact = 'io.grpc:protoc-gen-grpc-java:1.49.0' } } generateProtoTasks { all()*.plugins { grpc {} } } } jar { from { configurations.runtimeClasspath.findAll { duplicatesStrategy = DuplicatesStrategy.EXCLUDE it.name.endsWith(".jar") }.collect { println 'add ' + it.name zipTree(it) } } } targetCompatibility = JavaVersion.VERSION_15 After we have the proto files, then we could just build the project to complie proto files and generate essential stubs. ...
Unary call is very simple to understand, it is essentially a normal REST API call. Each request will get a single response from the server. In this project, we implement unary call to create books in our store. First, we need create book_message.proto which is a book pojo carrying the related info of book. Simply speaking, each message is pojo we are gonna use in our service. syntax = "proto3"; package book; option java_multiple_files = true; option java_package = "today.ihelio.grpc"; import "sample_message.proto"; import "image_message.proto"; message Book { enum Genre { UNKNOWN = 0; FICTION = 1; MYSTERY = 2; THRILLER = 3; HORROR = 4; HISTORICAL = 5; ROMANCE = 6; SCI_FICTION = 7; } string id = 1; string name = 2; string author = 3; uint32 publish_year = 4; double price = 5; string publication = 6; uint32 rating = 7; uint32 rating_count = 8; double avg_rating = 9; repeated Sample sample = 10; repeated Image image = 11; repeated Genre genre = 12; optional uint32 popularity = 13; } To implement a message, we need speficy: ...
We will implement a function to upload image when we create the books like the cover and something else. And we would split the image into chunks and we upload them chunk by chunk until all data are transfered. As we defined earlier in the proto, we could have multiple images for one book. So we will need a function called uploadImage and uploade all images one by one. Let’s start with the proto of image: ...
Regarding server streaming, we will implement a simplified recommendation service to recommend the books based on the popularity. Like client streaming, we would need a response handler - StreamObserver<RecommendBookResponse> - to handle a sequential of responses given one request. Since this is a recommendation function, we would need search the books from our book store given the criteria. Thus we would need add a searchBook method to our book store. ...
We will speed it up a bit in this chapter after implementing unary call and one direction streaming. As always, we need implement our core logic which includes our book store which handles rating update and computing and book service which handls the request and return response. @Override public Book rateBook(String bookID, Integer rating) { Book book = inMemoryBookStore.getOrDefault(bookID, null); if (book == null) { throw NOT_FOUND.withDescription("book not found") .asRuntimeException(); } inMemoryBookStore.computeIfPresent(bookID, (k, v) -> { Integer oldRating = v.getRating(); Integer oldCount = v.getRatingCount(); return v.toBuilder() .setRating(rating + oldRating) .setRatingCount(oldCount + 1) .setAvgRating((rating + oldRating)/(float) (oldCount + 1)) .build(); }); return inMemoryBookStore.get(bookID); } we simply update the rating in our book store. ...
The four types of gRPC covers the majority use case when we design API under HTTP/2 since we could either send one request/response or multiple requests/responses in one call. And using proto buffer enables us to separate the implementation of service, server and client which are the three components we need develop for each RPC service. Though the service could also depend on several components. But the idea is the simple, we need implement service, server and client for each RPC service and we don’t have to stick with one language for server and client. ...
What is Quarkus Quarkus is a full-stack, Kubernetes-native Java framework that was developed by Red Hat. It first appeared in early 2019, aimed at optimizing Java specifically for containers and enabling it to become an effective platform in serverless environments. The motivation behind Quarkus was to breathe new life into the Java ecosystem for modern cloud-native applications. It seeks to overcome the traditional shortcomings of Java, like slow startup time and high memory consumption, which are particularly notable in containerized environments. Quarkus achieves this through ahead-of-time (AOT) compilation which drastically reduces the runtime memory overhead and speeds up the startup time, making Java a more competitive choice in the modern landscape of microservices and serverless architectures. ...