IBM AMQP

Reading Time: 3 minutes

Introduction

This blog post will concludes information about the IBM MQ product with the AMQP protocol capabilities as well as an intuitive sample Producer and Consumer applications that I have coded. Furthermore, I have deliberately gathered some definitions from the IBM’s main page and enriched the content with my reflections.

Prerequisites

In order to have a smooth and easy setup, I’ll use an official IBM MQ Light docker image which brings good benefits of:

  • A nice and intuitive UI that shows summary of Clients and Messages,
  • getting rid of the complex installation and configuration of the IBM MQ with AMQP support. have been there done that before.

On top of that the project is prepared using Maven, assuming that you have this tool already.

IBM MQ Light Docker Image

I’ll be using docker image straight ahead from the repository. A well-documented explanation can be found @ GitHub page

In my local setup docker is installed in a virtual machine thus, in the following chapters, you will see my connection string as “virtualcentos“. Anyway let’s gather the image and run the container:

sudo docker run \
  --env LICENSE=accept \
  --volume /var/example:/var/mqlight \
  --publish 5672:5672 \
  --publish 9180:9180 \
  --detach \
  ibmcom/mqlight:1.0

Docker will pull the latest image and open the ports of 5672 for Application Connection and 9180 for the Web Application. Once the container is up and running, hit the address http://localhost:9180 and see the container works as expected.

Source Code

I have written a sample application that cover the Event Producing and Consuming scenarios. The full code is available @ my GitHub Repository

After checking out the code, you can use these queries to test the system

curl -X POST http://localhost:8080/api/certificate -H "Content-Type: application/json" -d "{\"name\":\"myCertificate\",\"fingerprint\":\"34:AB:45:3e:6y:XX\"}" 

curl -X POST http://localhost:8080/api/credential -H "Content-Type: application/json" -d "{\"username\":\"root\",\"password\":\"p@$$w0rd\"}" 

Concepts

There are four concepts in the ecosystem which I’ll briefly summarize. It is important to apprehend these basics.

Message

Message is the simplest form of the data that is being transmitted across the network. A message can simply consist of String, Bytes or JSON. For JSON formats, the API client internally utilizes GSON.

Topic

Topic is the main entry point for publishing applications, messages initially arrive in a topic. Besides that, topic is also responsible of routing the messages to the right destinations. Topic can contain multiple “/” that will make sub topics. For proper wild cards, consult the documentation

Destination

Destinations hold the messages and are associated with topics. A destination can have one or multiple topics associated with it. If a message is sent to a topic without a destination, it will not be delivered to any application. In addition, Destinations are always created with a time-to-live value, which can be automatically set or programmatically set. Once the TTL is exceeded, the destination will be removed automatically.

Sharing

Sharing allows applications to exclusively set to share the same destination. Applications sharing the same destination will receive the messages in the Round Robin fashion which is that messages are shared among the applications

Message quality of service (QOS)

IBM MQ product takes the matter of assurance of the connections and messages in varieties:

  • Message quality of service (QOS)
  • Subscription time-to-live
  • Subscriber auto-confirm
  • Message persistence

The QOS topic is very vital for designing messaging durability and performance. You can mix up different scenarios with different settings. For more detailed answers consult the IBM documentation.

IBM MQ Light Non-blocking API

The Non-blocking API is provided by the IBM to be able to connect to the product. Here is the link to browse the content of the Java API. In the sample project, you can find the maven repository for the Java client, for other clients, you can browse to the IBM Page. In this section I am more interested in drawing your attention

Useful Resources

Russian Roulette in Testing

Reading Time: 4 minutes

Description

Russian Roulette, the dangerous Russian game that we are all familiar with from usually movies. The Urban Dictionary gives such small description; “A game where a revolver with one bullet is placed and spun. Then you take turns putting the gun to your head and pull the trigger. If it’s empty, you pass it on until someone dies or becomes extremely injured.

By now we have filled our heads up with this literature, let’s narrow the subject down on how I relate this blog post to the Russian Roulette. Well, the good news is that I’ll not suggest to play it of course, but it is a good metaphor of a situation that I have experienced and the word came to my mind. Here follows the background; recently I was reviewing my Colleagues’ PRs and I noticed such code snippets in the IT test that they were getting objects from positional access in list data structures and assuming that the objects in the zero, first and second positions allegedly had expected values.

After I read those test cases a few times, the notion of the Russian Roulette popped up in my head. Eventually I came up with proper solutions towards the prevention of such messy assertions. I’ll describe two situations along with my suggested solutions. Please assume that demonstrations simple and non complex to outline more the cause.

Last of all, to demonstrate my samples, I am using the mirror servers of Fedora Linux Distribution @ https://mirrors.fedoraproject.org/mirrorlist?repo=epel-7&arch=x86_64

Situation: Asserting a Single value in a Collection

While coding a method that gathers or filters a list from the persistence unit, we tend to iterate through the list, grab and assume that the Nth element will be our expected value. In essence, it may lead to a very naive behavior, here is a code snippet

@Test
    public void shouldFindPolishHostFromSecureEuropeanHostsRussianRoulette() {
        //given
        final String expectedAddress = "https://ftp.icm.edu.pl/pub/Linux/fedora/linux/epel/7/x86_64/";

        //when
        final List<Host> hosts = repository.findByAddressContaining("http");

        //then
        assertThat(hosts).isNotNull();
        assertThat(hosts.get(2).getAddress()).isEqualTo(expectedAddress);
    }

As you observe the code and apprehend the logic quickly, we are getting a list of servers that are non-secure only http protocol. Here we have a catch which is, we are very very sure that the second element in the list will be the expected one. In fact it can be, however here can possible things may occur in the future:

  • If you update the memory database package or switch to another one, the new alternative may return the values in a different order because of its internal design. Thus, your test will obviously fail,
  • When the next developer adds a new entry before or after your test data, such tests will most likely fail.

Solution: Implement ways to look for the Exact Figure

The title of the solution reveals the whole deal right. Which one is more feasible way to ensure integrity, assumption or precision? Obviously precision is the keyword here. Here is the code snippet:

 @Test
    public void shouldFindPolishHostFromSecureEuropeanHostsNonRussianRoulette() {
        //given
        final String expectedAddress = "https://ftp.icm.edu.pl/pub/Linux/fedora/linux/epel/7/x86_64/";

        //when
        final Host host = repository.findByAddress(expectedAddress);

        //then
        assertThat(host).isNotNull();
        assertThat(host.getAddress()).isEqualTo(expectedAddress);
    }

My suggestion is when we are exactly looking for a single value, we must be in true certainty, and look for an exact figure like in the above example. Implement methods that will query for certain values or search the persistence unit.

Situation: Asserting a Collection of values with hard coded values

Throughout my software development career, I always came across with such situations in which I have a list of expected values that must be ensured the computer had produced same or similar output. This situation can come from different varieties and sorts. Instead of discussing possibilities at the table, let’s look at this code snippet and begin a rare case:

 @Test
    public void shouldFindAllSecureEuropeanHostsRussianRoulette() {
        //given-when
        final List<Host> hosts = repository.findByAddressContaining("https");

        //then
        assertThat(hosts).isNotNull();
        assertThat(hosts.get(0).getAddress()).isEqualTo("https://mirror.karneval.cz/pub/linux/fedora/epel/7/x86_64/");
        assertThat(hosts.get(1).getAddress()).isEqualTo("https://ftp.icm.edu.pl/pub/Linux/fedora/linux/epel/7/x86_64/");
        assertThat(hosts.get(2).getAddress()).isEqualTo("https://ftp-stud.hs-esslingen.de/pub/epel/7/x86_64/");
    }

In this example, we are hard core assuming that the given Nth element will have such outcome as we type in. In this case I have the same failure point of predictions as I declared in the above situation, nothing more to address here.

Solution: Compare Collections with Collections

As we get the spoiler from the title wouldn’t it be nice to purely compare collections with collections? I must say, I really admire the way that I approached this situation and the solution as well as the testing frameworks support into it. Let’s apprehend my solution here

@Test
    public void shouldFindAllSecureEuropeanHostsNonRussianRoulette() {
        //given
        ArrayList<String> expectedHosts = new ArrayList<>(Arrays.asList("https://mirror.karneval.cz/pub/linux/fedora/epel/7/x86_64/",
                "https://ftp.icm.edu.pl/pub/Linux/fedora/linux/epel/7/x86_64/",
                "https://ftp-stud.hs-esslingen.de/pub/epel/7/x86_64/"));
        //when
        final List<Host> hosts = repository.findByAddressContaining("https");

        //then
        final List<String> hostNames = hosts.stream().map(Host::getAddress).collect(Collectors.toList());
        assertThat(hosts).isNotNull();
        assertThat(hostNames).isNotNull();
        assertThat(hostNames).containsAnyElementsOf(expectedHosts);
    }

The code is very simple to understand its purpose, in this solution I really don’t need to know in which position I get what outcome. The importance here is to ensure the computer had prepared the output that has the desired output, it as simple as that. Furthermore, the testing framework provides such method that ensures the output meets the expectation

Bonus Solution: Extracted Properties of Collections

I asked my colleague at work for a favor of evaluation my work and I was really curious about his opinion and thoughts. He had pointed me some features from the AssertJ library that I find very useful and the feature Assertions on Iterables can be quite comprehensive as well. In basic terms I also added a new test to simply cover the concept up

@Test
    public void shouldFindAllSecureEuropeanHostsNonRussianRouletteNonStream() {
        //given
        ArrayList<String> expectedHosts = new ArrayList<>(Arrays.asList("https://mirror.karneval.cz/pub/linux/fedora/epel/7/x86_64/",
                "https://ftp.icm.edu.pl/pub/Linux/fedora/linux/epel/7/x86_64/",
                "https://ftp-stud.hs-esslingen.de/pub/epel/7/x86_64/"));
        //when
        final List<Host> hosts = repository.findByAddressContaining("https");

        //then
        assertThat(hosts).isNotNull();
        assertThat(hosts).extracting("address")
                .containsAnyElementsOf(expectedHosts);
    }

In my sample I only demonstrated the “extracting” that eliminated my stream operation. On the other hand I’d like to share some links that will demonstrate way more advanced test cases than my humble test.

Conclusion

Assumptions can be evil in programming. Unless you work on sorted data structures that will guarantee the order, still assuming the positional access can be malicious, my sincere suggestion is that we shall always strive for best practices to overcome such bad habits, thus we won’t waste time on fixing unnecessary test cases. You can find the full solution at my Github repository @ https://github.com/tugrulaslan/BlogCodeSnippets/tree/master/RussianRoulette

Featured Image Courtesy telegraph.co.uk – https://i.telegraph.co.uk/multimedia/archive/02500/Russian_roulette_2500016k.jpg

Heap

Reading Time: 3 minutes

Description

Heap is a tree-based data structure with some special attributes embedded into it.  Heap Data Structure has such characteristics;

  • It is a form of Complete Binary Tree,
  • It has a root node and its key is compared to the children nodes and the comparison is constantly carried out whenever a new node is aimed to be inserted.

In addition to the characteristics, the Heap can be internally implemented using Array or Priority Queues. The common practice is usually done with the Priority Queue.

Types of Heap

Heap Data Structure has mainly two types. These types correspond to how the order of the Heap is placed. Let’s have a look at the types in details;

Min Heap

Min Heap Tree

The values of children are greater than or equal to the value of their parents; which indicates that parent nodes tend to have lower values than the children nodes.

Max Heap


Max Heap Tree

The values of children are less than or equal to the value of their parents; which indicates that parent nodes tend to have greater values than the children nodes.

Complexity of Heap

The Time and Space complexities are summed up into a common table given as:

Usage Areas of Heap

Heap Data Structure makes great use in the following areas:

  1. Heap Sort: Very efficient sorting algorithm whose time complexities are all the same O (n log n),
  2. Priority Queues: The Priority version of Queue benefits efficiently from the Heap Data structure that provides insertion, deletion extract maximum and decrease key operations in the O (log n) time complexity

Terminology

Heapify

Heapifying is a recursive process of turning the Heap to the Max Heap type, our algorithm will go towards the non-leaf nodes and look for the largest node in the tree and in all possibilities, raise the greater values above top contentiously.

Max Heap

Parent Node

Left node of the Tree the presentation in the array: (index -1) / 2;

Left Node

Left node of the Tree the presentation in the array: 2 * index + 1;

Right Node

Right node of the Tree the presentation in the array: 2 * index + 2;

Heap Sort

Heap sort is a very efficient algorithm that performs very well in sorting arrays.

Time Complexity

All the cases are O(n log n)

Space Complexity

O(1)

Heap Sort Code

You can checkout my GitHub repository @ https://github.com/tugrulaslan/BlogCodeSnippets/tree/master/SortingAlgorithms

Radix Sort

Reading Time: 2 minutes

Definition

The optimal algorithm for the numbers range from 1 to n2. Radix Sort algorithm favors of Counting Sort internally to sort the array. The given keys consists of the digits in each element in the array.
It starts from the Least Significant Digit which is the left digit, then goes to the Most Significant Digit which means to the right.

Each digit goes to a corresponding numbered buckets. After the buckets is filled with the elements in the array, the elements are sorted once again according to the bin position. Let’s us see an example illustration to better apprehend the logic, we will sort the numbers “551, 12, 346, 311”;

Visual Array Status of Sorting Phases by Radix Sort
Statuses of Buckets in each pass

Now we have more or less how the Radix Sort works out internally. There is one gap I’d like to point what happens to 12 which has two digits compared to the others that have three digits. Well in this situation such numbers are appended with leading 0s and they always sit on the bucket zero.
n numbers consisting of k digits

Complexity

Time Complexity

n: number of elements
k: the range of the keys for each number. We will also repeat the operation for this amount.
All of the Time Complexities of Radix Sort is always O(n*k)

Space Complexity

Space complexity of Radix Sort is O(n+k)

Code

You can checkout my GitHub repository @ https://github.com/tugrulaslan/BlogCodeSnippets/tree/master/SortingAlgorithms

Linked List

Reading Time: 3 minutes

Definition

Linked List a linear data structure like Arrays, but its internal is completely different compared to other data structures. Let’s first have a visual look how the data structure looks like

The internal of Linked List

As you can see in the above image Linked List maintains a list of objects linked to them, as also the name suggests the same approach. To conclude some characteristics in Linked List;

  1. Each node has a next pointer/reference to the next or previous object then we are iterating through these references,
  2. The last nodes are usually null,
  3. However, the next/previous references  do not refer to null in certain times(in the following chapters, I’ll demonstrate the reasons)

Linked list is used in some data structures like Queues and Stacks internally. Check them out separately and see how Linked List fits in their requirements.

Advantages

  1. No size limitation compared to the arrays,
  2. It is not costly to insert and remove in between nodes, where as it is very costly especially with heavier arrays because all the elements will be shifted,

Disadvantages

  1. Random data access is not possible, the whole data structure must be traversed to access the designated object,
  2. Storage to the next and previous nodes takes up some memory space.

Time and Space Complexity

image courtesy of  bigocheatsheet.com

Types of Linked Lists

Linked List has some varieties of implementations that often confuse us. I’ll show all the implementations in sub sections with visuals, descriptions and codes that will let you interact more and apprehend the slightest differences better.

Singly Linked List

In a Singly Linked List the traversal is unidirectional, each node refers to the next node in the link, and there is no reference to previous nodes.  The last node’s next refers to Null.

See the Implementation “SinglyLinkedList.java” and the Unit Test “SinglyLinkedListUnitTest.java” to apprehend all the operations and internals of the Singly Linked List.

Doubly Linked List

Doubly Linked List maintains a bidirectional path, thus it contains next and previous links, where next refers to the next node, and previous refers to the previous node. This maintenance comes with an extra overhead. Last of all, first node’s previous and last node’s next are Null.

See the Implementation “SinglyLinkedList.java” and the Unit Test “DoublyLinkedListUnitTest.java” to apprehend all the operations and internals of the Doubly Linked List.

Circular Linked List

Circular Linked List is the last variation of the implementation. I would like to call the Circular Linked List as the spiced up version of the Singly and Doubly Linked List implementations in my own terms. In addition, as the name suggests, the basic internal is that the Linked List is being circular. Now time to clear out the 3rd element in the definition and explain
two distinct characteristics in the Circular Linked List;

  1. The head and the tail of the data structure don’t point to NULL, but head’s previous reference, points to tail and tail’s next reference points to the head,
  2. Circular List can be made using Singly or Doubly Linked List implementations.
Singly Circular Linked List

Doubly Circular Linked List

Operations

Operation description goes here

  • isEmpty: Checks whether the Linked List is empty,
  • insertFirst: Inserts the given Node to the head of Linked List,
  • insertAfter: Inserts the given Node after the existing Node in Linked List, 
  • insertLast: Inserts the given Node at the end of Linked List, 
  • deleteFirst: Deletes the Node in the head of Linked List,
  • deleteNode: Deletes the given Node in Linked List,
  • deleteLast: Deletes the given Node from the end of Linked List,
  • containsIterativeSearch: Iteratively searches Linked List,
  • containsRecursiveSearch: Recursively searches Linked List.

Code

The code can be also found in my Github Repository @ https://github.com/tugrulaslan/BlogCodeSnippets/tree/master/DataStructures To see how the code works, you can also check its Unit Test.

Queue

Reading Time: 2 minutes

Definition

Queue is a linear data structure that maintains FIFO setting; First In First Out. Queue comes in two possible internal implementations; Singly Linked List or Array. When think of FIFO, we can assume a group of people waiting queued up for buying a cinema ticket. The first person in the queue gets to buy the ticket and it follows the rest of the people in the queue.

Sample Queue Usage Areas

  • Hardware Scheduling; CPUs and Disks are properly scheduled in the concurrent environments,
  • Asynchronous communication makes a great use case while two processes wait for each other to respond in sequence

Implementation

In the internally Queue can implement Singly Linked List or Array. Eventually the Time Complexity of the operations will slightly differ. In this stackoverflow Article, there are more insights and argument about the implementations. In my own implementation I preferred to use the Singly Linked List implementation.

Complexity of Queue

Since the internals of implementations differ for each variationSingly Linked List and Array, the operations can differ. The given table is suitable for Singly Linked List implementation;


image courtesy of  bigocheatsheet.com

Operations on Queue


Queue has three vital operations that we need to cover up. In some other languages and Stack implementations definitely have other additional operations like Java’s Queue implementation. However, these below operations are fundamental properties of the Queue data structure:

  • enqueue:  inserts the element to the head of the stack,
  • denqueue: removes the element from the head  and returns
    denqueued the value,
  • peek: returns the head data but doesn’t delete it, takes a peek at it.

Code

The code can be also found in my Github Repository @ https://github.com/tugrulaslan/BlogCodeSnippets/tree/master/DataStructures to see how the code works, you can also check its Unit Test.

Stack

Reading Time: 2 minutes

Definition

Stack is a very usable data structure that brings the LIFO setting into the game. Let’s elaborate LIFO; LIFO is the abbreviation of Last-In-First-Out. What does LIFO really mean for us? The intentions may vary and one of them is to have a pile of things stacked down to the bottom and take one from the top. Let’s apprehend the below illustration:

Yes, we understood it well. In the LIFO setting we insert towards bottom and and take from the top.

Sample Stack Usage Areas

  • In text editors “Undo” operations while we intend to revert an unwanted entry,
  • Browsers’ back buttons; make use of a similar way to be able to navigate to the earlier pages,
  • Recursive methods also utilize stack very well; starting from the first call till the last, all of the method executions are added on top of each other.

Implementation

In the internally Stack can implement Singly Linked List or Array. Eventually the Time Complexity of the operations will slightly differ. In this stackoverflow Article, there are more insights and argument about the implementations. In my own implementation I preferred to use the Singly Linked List implementation.

Complexity of Stack

Since the internals of implementations differ for each variation; Singly Linked List and Array, the operations can differ. The given table is suitable for Singly Linked List implementation;

image courtesy of  bigocheatsheet.com

Operations on Stack

Stack has three vital operations that we need to cover up. In some other languages and Stack implementations definitely have other additional operations like Java’s Stack implementation. However, these below operations are fundamental properties of the Stack data structure:

  • push: pushes the element on top of stack
  • pop: pops the element from the top and returns popped the value
  • peek: returns the head data but doesn’t delete it, takes a peek at it.

Code

The code can be also found in my Github Repository @ https://github.com/tugrulaslan/BlogCodeSnippets/tree/master/DataStructures to see how the code works, you can also check its Unit Test.

Shell Sort

Reading Time: 1 minute

Definition

Shell Sort is a variation of the Insertion Sort. Shell Sort is very fast algorithm that is compact in code size. A gap in other words a distance is set that will be used between the elements in the array
Sub lists are made out of the elements in the gap and the sub lists are compared. In the comparison lower element goes to the left and greater is on the right.
The process continues, later on the gap gets smaller until it becomes one. After the gap reaches to one, then the Insertion Sort is applied to sort the rest. Depending of this gap the time complexity of the algorithm varies.

Code

The code can be also found in my Github Repository @ https://github.com/tugrulaslan/BlogCodeSnippets/tree/master/SortingAlgorithms

Insertion Sort

Reading Time: 1 minute

Definition

The 1st element is assumed to be sorted and the iteration starts from the second element towards the end. The difference in this algorithm compared to Bubble Sort,
it compares the element that are on the left of it. It all means that the sorting goes not forward, but backwards from the right to the left.
This algorithm is sufficient on smaller data sets like Bubble Sort, because its Time complexity is  O(n2).
In the implementations of the Insertion Sort only space complexity changes;
*. Imperative: O(1)
*. Recursive: O(n) because of the stacks that are created
The both imperative and the recursive versions are very similar, except in the recursive version, the comparison will start when the i is in second elements index which is 2

Code

The code can be also found in my Github Repository @ https://github.com/tugrulaslan/BlogCodeSnippets/tree/master/SortingAlgorithms

Merge Sort

Reading Time: 2 minutes

Definition

Merge sort yet another sorting algorithm that benefits from the divide-and-conquer principle.  The main goal in this algorithm is to split the given array into individuals and merge them back during the course of the comparison.
Merge Sort seems kind of similar to the Merge sort, in the Comparison below you can study the differences and similarities. However, there is one challenge as I see in this algorithm is the merge. I find this part very complex, but besides its very easy to apprehend the algorithm.

Complexity Analysis

Time Complexity

  1. Best Case: O(n log n),
  2. Average Case: O(n log n),
  3. Worse Case: O(n log n)

Space Complexity

O(n)

Comparison to Quick Sort

In general terms, the Merge Sort is often compared to the Quick Sort. In some sense, they tend to act similarly as they inherit the same divide-and-conquer principle, to address a few of differences;

  • Merge Sort demands a copy of the data structure, whereas Quick Sort applies the changes with no requirement of extra space allocated,
  • Both of the algorithms split the given data structure. However, alternatively Merge Sort intends to split from the half to divide the left and right subsets into individual elements, whereas the Quick Sort picks a partition point and swaps the lower and greater values in the right and the left directions.

Operations

  1. The algorithm divides the array into half smaller chunks until the individual items left with by using recursion,
  2. once individuals created, they are compared and merged back from smaller to larger arrays
  3. Merge sort requires extra space allocation which makes it space complexity as O(n), whereas Quick Sort only keeps a space while swapping which makes its space complexity as O(log n). However the only similarity is that because of the recursive calls, the stack traces will be created upon each call that’s also considered as a space

Terms

  • leftPointer: A pointer of the left/begin of the array
  • rightPointer: A pointer of the right/endof the array
  • middleElementPointer: Represents the element in the center of the array
  • leftArray: The elements of the left side as a temporary storage
  • rightArray: The elements of the rıght side as a temporary storage

Code

You can checkout my GitHub repository @ https://github.com/tugrulaslan/BlogCodeSnippets/tree/master/SortingAlgorithms