Distributed Systems

Examples of Distributed Systems

(data, service, other actors; open ended)

2) Intranets ( CoDoKi, Fig. 1.2)

 computing ( CoDoKi Fig 1.3 )

MapReduce

Better Techniques

 Difference between a Distributed System and Distributed Computing

Distributed-Computing: Distributed computing is where multiple computing units are connected to achieve a common task. 

The larger computing power enables a lot more tasks to be performed than in a single unit, and searches can be coordinated for efficiency. Successes usually give the finder credit.

Distributed-System: A distributed system consists of a collection of autonomous computers, connected through a network and distribution middleware, which enables computers to coordinate their activities and to share the resources of the system so that users perceive the system as a single, integrated computing facility.

Advantages of Distributed Systems

Disadvantages of Distributed Systems

Structure 

Thick Web Client 

Web Delivery 

Fundamentals

 Layered Protocols

Use related characteristics

Development related characteristics

Evolution-related characteristics

 Distributed System Architectures

 In this blog, I would like to talk about the available Distributed System architectures that we see today and how they are being utilized in our day to day applications. 

Distributed system architectures are bundled up with components and connectors. 

Components can be individual nodes or important components in the architecture whereas connectors are the ones that connect each of these components. 

Component: A modular unit with well-defined interfaces; replaceable; reusable

Connector: A communication link between modules which mediates coordination or cooperation among components

So the idea behind distributed architectures is to have these components presented on different platforms, where components can communicate with each other over a communication network in order to achieve specifics objectives.

Architectural Styles

 There are four different architectural styles, plus the hybrid architecture when it comes to distributed systems.  

The basic idea is to organize logically different components, and distribute those computers over the various machines.

• Layered Architecture
• Object-Based Architecture
• Data-centered Architecture
• Event-Based Architecture
• Hybrid Architecture

Layered Architecture

The layered architecture separates layers of components from each other, giving it a much more modular approach. 

A well-known example of this is the OSI model that incorporates a layered architecture when interacting with each of the components. 

Each interaction is sequential where a layer will contact the adjacent layer and this process continues until the request is been catered to. 

But in certain cases, the implementation can be made so that some layers will be skipped, which is called cross-layer coordination.

 Through cross-layer coordination, one can obtain better results due to the performance increase. 

 The layers on the bottom provide a service to the layers on the top. 

The request flows from top to bottom, whereas the response is sent from bottom to top. 

The advantage of using this approach is that, the calls always follow a predefined path, and that each layer can be easily replaced or modified without affecting the entire architecture.

 The following image is the basic idea of a layered architecture style.

 Object-Based Architecture

 This architecture style is based on the loosely coupled arrangement of objects. 

This has no specific architecture like layers. Like in layers, this does not have a sequential set of steps that need to be carried out for a given call. 

Each of the components is referred to as objects, where each object can interact with other objects through a given connector or interface. 

These are much more direct where all the different components can interact directly with other components through a direct method call.

As shown in the above image, communication between object happens as method invocations.
These are generally called Remote Procedure Calls (RPC). 

Some popular examples are Java RMI, Web Services and REST API Calls. This has the following properties.

This architecture style is less structured.

component = object

connector = RPC or RMI

When decoupling these processes in space, people wanted the components to be anonymous and replaceable. 

And the synchronization process needed to be asynchronous, which has led to Data Centered Architectures and Event-Based Architectures.

Data Centered Architecture

As the title suggests, this architecture is based on a data center, where the primary communication happens via a central data repository. 

This common repository can be either active or passive.

 This is more like a producer-consumer problem. 

The producers produce items to a common data store, and the consumers can request data from it. 

This common repository could even be a simple database.

 But the idea is that the communication between objects happening through this shared common storage. 

This supports different components (or objects) by providing a persistent storage space for those components (such as a MySQL database). 

All the information related to the nodes in the system is stored in this persistent storage. In event-based architectures, data is only sent and received by those components who have already subscribed.

 Some popular examples are distributed file systems, producer-consumer, and web-based data services.

Event-Based Architecture

 The entire communication in this kind of a system happens through events. When an event is generated, it will be sent to the bus system.

 With this, everyone else will be notified telling that such an event has occurred.

 So, if anyone is interested, that node can pull the event from the bus and use it.

 Sometimes these events could be data or even URLs to resources. So the receiver can access whatever the information is given in the event and process accordingly.

 processes communicate through the propagation of events.

 These events occasionally carry data.

 An advantage in this architectural style is that components are loosely coupled.

 So it is easy to add, remove and modify components in the system.

 Some examples are the publisher-subscriber system, Enterprise Services Bus (ESB) and akka.io.

 One major advantage is that these heterogeneous components can contact the bus, through any communication protocol. 

But an ESB or a specific bus has the capability to handle any type of incoming request and process accordingly.

This architectural style is based on the publisher-subscriber architecture. Between each node, there is no direct communication or coordination. Instead, objects which are subscribed to the service communicate through the event bus. 

The event-based architecture supports several communication styles. 

• Publisher-subscriber
• Broadcast
• Point-to-Point

The major advantages of this architecture are that the Components are decoupled in space - loosely coupled.

System Level Architecture

The two major system level architectures that we use today are Client-server and Peer-to-peer (P2P).  We use these two kinds of services in our day to day lives, but the difference between these two are often misinterpreted.

Client-Server Architecture

The client-server architecture has two major components.

The client and the server. The Server is where all the processing, computing and data handling is happening, whereas the Client is where the user can access the services and resources given by the Server (Remote Server).

 The clients can make requests from the Server, and the Server will respond accordingly.

Generally, there is only one server that handles the remote side. But to be on the safe side, we do use multiple servers will load balancing techniques.

As one common design feature, the client-Server architecture has a centralized security database.

This database contains security details like credentials and access details.

Users can't log in to a server, without the security credentials.

So, it makes this architecture a bit more stable and secure than Peer to Peer.

The stability comes where the security database can allow resource usage in a much more meaningful way.

  But on the other hand, the system might get low, as the server only can handle a limited amount of workload at a given time.

Advantages:

• Easier to Build and Maintain

• Better Security

• Stable

Disadvantages:

• Single point of failure

• Less scalable

Peer to Peer (P2P)

The general idea behind peer to peer is where there is no central control in a distributed system. The basic idea is that, each node can either be a client or a server at a given time. If the node is requesting something, it can be known as a client, and if some node is providing something, it can be known as a server. In general, each node is referred to as a Peer.

In this network, any new node has to first join the network.

 After joining in, they can either request a service or provide a service.

The initiation phase of a node (Joining of a node), can vary according to the implementation of a network.

There are two ways in how a new node can get to know, what other nodes are providing.

Centralized Lookup Server - The new node has to register with the centralized look up server an mention the services it will be providing, on the network. So, whenever you want to have a service, you simply have to contact the centralized look up the server and it will direct you to the relevant service provider.

Decentralized System - A node desiring for specific services must, broadcast and ask every other node in the network, so that whoever is providing the service will respond. 

A Comparison Between Client Server and Peer to Peer Architectures

                                      

Middleware in Distributed Applications

If we look at Distributed systems today, they lack the uniformity and consistency.

Various heterogeneous devices have taken over the world where distributed system cater to all these devices in a common way.

One way distributed systems can achieve uniformity is through a common layer to support the underlying hardware and operating systems.

This common layer is known as a middleware, where it provides services beyond what is already provided by Operating systems,  to enable various features and components of a distributed system to enhance its functionality better.

 This layer provides a certain data structures and operations that allow processes and users on far-flung machines to inter-operate and work together in a consistent way.

The image given below, depicts the usage of a middleware to inter-connect various kinds of nodes together.

 According to Andrew Tannenbaum, middleware is like the operating system of distributed systems.

Centralized vs Decentralized Architectures

The two main structures that we see within distributed system overlays are Centralized and Decentralized architectures.

The centralized architecture can be explained by a simple client-server architecture where the server acts as a central unit.

This can also be considered as centralized look up table with the following characteristics.

➽Low overhead

➽Single point of failure

➽Easy to Track

➽AdditionalOverhead.

When it comes to distributed systems, we are more interested in studying more on the overlay and unstructured network topologies that we can see today.

In general, the peer to peer systems that we see today can be separated into three unique sections.

Structured P2P: nodes are organized following a specific distributed data structure

Unstructured P2P: nodes have randomly selected neighbors

Hybrid P2P: some nodes are appointed special functions in a well-organized fashion

Structured P2P Architecture

The meaning of the word structured is that the system already has a predefined structure that other nodes will follow.

Every structured network inherently suffers from poor scalability, due to the need for structure maintenance.

 In general, the nodes in a structured overlay network are formed in a logical ring, with nodes being connected to the this ring.

In this ring, certain nodes are responsible for certain services.

A common approach that can be used to tackle the coordination between nodes, is to use distributed hash tables (DHTs).

A traditional hash function converts a unique key into a hash value, that will represent an object in the network.

The hash function value is used to insert an object in the hash table and to retrieve it.

In a DHT, each key is assigned to a unique hash, where the random hash value needs to be of a very large address space, in order to ensure uniqueness.

A mapping function is being used to assign objects to nodes based on the hash function value.

A look up based on the hash function value, returns the network address of the node that stores the requested object.

Hash Function: Takes a key and produces a unique hash value

Mapping Function: Map the hash value to a specific node in the system

Lookup table: Return the network address of the node represented by the unique hash value.

Unstructured P2P Systems

There is no specific structure in these systems, hence the name "unstructured networks".

Due to this reason, the scalability of the unstructured p2p systems is very high.

These systems rely on randomized algorithms for constructing an overlay network.

 As in structured p2p systems, there is no specific path for a certain node.

 It's generally random, where every unstructured system tried to maintain a random path.

Due to this reason, the search of a certain file or node is never guaranteed in unstructured systems.

The basic principle is that each node is required to randomly select another node, and contact it. 

• Let each peer maintain a partial view of the network, consisting of n other nodes

• Each node P periodically selects a node Q from its partial view

• P and Q exchange information and exchange members from their respective partial views

Hybrid P2P Systems

Hybrid systems are often based on both client server architectures and p2p networks.

A famous example is Bittorrent, which we use everyday.

The torrent search engines provide a client server architecture, where the trackers provide a structured p2p overlay.

The rest of the nodes, which are also known as leechers and seeders, become the unstructured overlay of the network, allowing it to scale itself as needed and further.

 More on how Bittorrent works in the distributed context, will be written in a future blog.

 Summary of Structured and Unstructured P2P Systems

Monolithic Architecture

Monolith means composed all in one piece. 

The Monolithic application describes a single-tiered software application in which different components combined into a single program from a single platform.

Components can be:

• Authorization➦ responsible for authorizing a user

• Presentation➦ responsible for handling HTTP requests and responding with either HTML or JSON/XML (for web services APIs).

• Business logic➦ the application’s business logic.

• Database layer➦ data access objects responsible for accessing the database.

• Application integration➦ integration with other services (e.g. via messaging or REST API). Or integration with any other Data sources.

• Notification module➦ responsible for sending email notifications whenever needed.

Example of Monolithic Approach

Consider an example of an E-commerce application, that authorizes customer, takes an order, check products inventory, authorize payment and ships ordered products.

This application consists of several components including an e-Store User interface for customers (Store web view) along with some backend services to check products inventory, authorize and charge payments and shipping orders.

Despite having different components/modules/services, the application is built and deployed as one Application for all platforms (i.e. desktop, mobile, and tablet) using RDBMS as a data source. Benefits and Drawbacks of Monolithic Architecture.

Benefits:

Simple to develop➤At the beginning of a project, it is much easier to go with Monolithic Architecture.

Simple to test. For example, you can implement end-to-end testing by simply launching the application and testing the UI with Selenium.

Simple to deploy. You have to copy the packaged application to a server.

Simple to scale horizontally by running multiple copies behind a load balancer.

Drawbacks:

Maintenance ➼ If Application is too large and complex to understand entirely, it is challenging to make changes fast and correctly.

The size of the application can slow down start-up time.

You must redeploy the entire application on each update.

Monolithic applications can also be challenging to scale when different modules have conflicting resource requirements.

Reliability ➼ Bug in any module (e.g. memory leak) can potentially bring down the entire process. Moreover, since all instances of the application are identical, that bug impact the availability of the entire application

Regardless of how easy the initial stages may seem, Monolithic applications have difficulty in adopting new and advanced technologies. 

Since changes in languages or frameworks affect an entire application, it requires efforts to thoroughly work with the app details, hence it is costly considering both time and efforts.

Microservices Architecture

Microservices are an approach to application development in which a large application is built as a suite of modular services (i.e. loosely coupled modules/components). 

Each module supports a specific business goal and uses a simple, well-defined interface to communicate with other sets of services.

Instead of sharing a single database as in Monolithic application, each microservice has its own database.

 Having a database per service is essential if you want to benefit from microservices because it ensures loose coupling. 

Each of the services has its own database. Moreover, a service can use a type of database that is best suited to its needs.

Consider the same example of the e-commerce application, which consists of several components/modules. 

Define each component/module as a separate loosely coupled service depending on the requirement, which may collaborate with each other based on the scenario. 

We can have the following services for a complete application:

• Authorization Service⇰Responsible for authorizing customer.
• Order Service⇰takes an order and process it.
• Catalog Service⇰Manage products and check products inventory.
• Cart Service⇰Manage user cart, this service can utilize Catalog service as a data source.
• Payment Service⇰Manage and Authorize payments.
• Shipping Service⇰Ships ordered products.

Benefits:

Microservices Enables the continuous delivery and deployment of large, complex applications.

• Better testability➨services are smaller and faster to test.
• Better deployability➨services can be deployed independently.

It enables you to organize the development effort around multiple teams.

 Each team is responsible for one or more single service.

 Each team can develop, deploy and scale their services independently of all of the other teams.

Each microservice is relatively small

Comfortable for a developer to understand

The IDE is faster making developers more productive

The application starts faster, which makes developers more productive, and speeds up deployments

Improved fault isolation. For example, if there is a memory leak in one service then only that service is affected. 

The other services continue to handle requests. In comparison, one misbehaving component of a monolithic architecture can bring down the entire system.

Microservices Eliminates any long-term commitment to a technology stack. 

When developing a new service you can pick a new technology stack. Similarly, when making major changes to an existing service you can rewrite it using a new technology stack.

Drawbacks:

Developers must deal with the additional complexity of creating a distributed system.

Developer tools/IDEs are oriented on building monolithic applications and don’t provide explicit support for developing distributed applications.

Testing is more difficult as compared to Monolith applications.

Developers must implement the inter-service communication mechanism.

Implementinga use cases that span multiple services without using distributed transactions is difficult.

Implementing use cases that span multiple services requires careful coordination between the teams.

Deployment complexity. In production, there is also the operational complexity of deploying and managing a system comprised of many different service types.

Increased memory consumption. The microservice architecture replaces N monolithic application instances with NxM services instances. If each service runs in its Container, which is usually necessary to isolate the instances, then there is the overhead of M times as many Containers.

Microservices vs. Monolith Architecture

The evolution of technologies has changed the way we build the architecture of applications.

 Docker, Cloud services, and Container Orchestration services brought us ability to develop distributed, more scalable, and reliable solutions. 

In this article, we will compare microservices and monolith architecture, discuss what teams and projects should use what type of architecture, and explore their advantages and disadvantages.

At a glance, the difference between those types can be illustrated like this

It is not strictly true that monolith apps are always simple, but microservices are often 10 times larger and almost always requires more resources.

Let’s discuss the pros and cons of each, point by point.

Deployment

Monolith apps allow you to set your deployment once and then simply adjust it based on ongoing changes.

 At the same time, however, there is also only a single point of failure during deployment and, if everything goes wrong, you could break your entire project.

Microservices require much more work; you will need to deploy each microservice independently, worry about orchestration tools, and try to unify the format of your ci/cd pipelines to reduce the a amount of time required for doing it for each new microservice. 

There is a bright side, however; if something goes wrong, you will only break one small microservice, which is less problematic than the entire project. 

It’s also much easier to rollback one small microservices than and entire monolith app.

Maintenance

If you plan to use a microservices architecture, get a DevOps for your team and prepare yourself.

 Not every developer will be familiar with Docker or orchestration tools, such as Kubernetes, Docker Swarm, Mesosphere, or any similar tool that could help you to manage infrastructure with a lot of moving parts. 

Someone has to monitor and maintain the functioning state of your CI configuration for each microservice and the whole infrastructure.

Reliability

Microservices architecture is the obvious winner here. 

Breaking one microservice affects only one part and causes issues for the clients that use it, but no one else.

 If, for example, you’re building a banking app and the microservice responsible for money withdrawal is down, this is definitely less serious than the whole app being forced to stop.

Scalability

For scalability, microservices are again better suited. 

Monolith apps are hard to scale because, even if you run more workers, every worker will be on the single, whole project, an inefficient way of using resources. 

Worse, you may write your code in the way that would render it impossible to scale it horizontally, leaving only vertical scaling possible for your monolith app. 

With microservices, this is much easier. Resources can be used more carefully and allow you to scale only that parts that require more resources.

Cost

Cost is tricky to calculate because monolith architecture is cheaper in some scenarios, but not in others. 

For example, with the better scalability of microservices, you could set up an auto-scale and only pay for that when the volume of users really requires more resources. 

At the same time, to keep that infrastructure up and running you need a devops that needs to be paid. With a small monolith app, you could run on a $5-$20 host and turn on the snapshot. 

With a larger monolith app, you may host a very expensive instance because you can’t share it over multiple small, cheap hosts.

Development

In one of our projects, we have 16 microservices and I could tell you from experience that this can be tricky to deal with it. 

The best way to deal with microservices is to build your docker-compose file from the beginning and develop through Docker. 

This helps you reduce the time spent onboarding new people; simply run the system from scratch and launch all microservices as needed. 

Opening 10+ terminal windows and executing commands to start each individual service is a pain.

On the other hand. when you develop one microservice, you may have a case in which you don’t need to run other parts of the application at all. 

This results in fewer problems with git conflicts due to the better process of breaking down tasks and the ability to isolate developers across microservices.

Doing code review and QA is simpler with microservices; you may even be able to write microservices in different languages.

Releasing

Microservices that are smaller and with a proper architecture of microservices communication allow you to release new features faster by reducing QA time, build time, and tests execution time.

 Monolith apps have a lot of internal dependencies that could not be broken up. 

There is also a higher risk that something you are committed to could depend on unfinished changes from your team members, which could potentially postpone releases.

What’s architecture better to you?

Use monolith architecture if you:

• Have a small team.

• Build the MVP version of a new product.

• Did not get millions in investments to hire DevOps or spend extra time on complex architecture.

• Have experience of development on solid frameworks, such as Ruby on Rails, Laravel, etc.

• Don’t see performance bottlenecks for some key functionality.

• Think that microservices are cool and it’s a trend.

Keep in mind that if you find out that there is need of microservices in your project, monolith architecture always carries the risk of break down as a result of these small microservices.

Use microservices architecture if you:

• Don’t have a tight deadline; microservices require you to research and architecture planning to ensure it works.
• Have a team with knowledge of different languages.
• Worry a lot about the scalability and reliability of your product.
• Potentially have a few development departments(maybe even in different countries/time zones).
• Have an existing monolith app and see problems with parts of your application that could be split across multiple microservices.

MVC

MVC stands for Model–view–controller.

 It is a software architectural pattern for implementing user interfaces on computers.

 It divides a given software application into three interconnected parts, so as to separate internal representations of information from the ways that information is presented to or accepted from the user.

Components of MVC

1) Model: It specifies the logical structure of data in a software application and the high-level class associated with it. It is the domain-specific representation of the data which describes the working of an application. When a model changes its state, domain notifies its associated views so they can refresh.

2) View: View component is used for all the UI logic of the application and these are the components that display the application’s user interface (UI). It renders the model into a form suitable for interaction. Multiple views can exist for a single model for different purposes.

3) Controller: Controllers act as an interface between Model and View components. It processes all the business logic and incoming requests, manipulates data using the Model component, and interact with the Views to render the final output. It receives input and initiates a response by making calls on model objects.

Advantages of MVC

1) Faster development process: MVC supports rapid and parallel development. With MVC, one programmer can work on the view while others can work on the controller to create business logic of the web application. The application developed using MVC can be three times faster than an application developed using other development patterns.

2) Ability to provide multiple views: In the MVC Model, you can create multiple views for a model. Code duplication is very limited in MVC because it separates data and business logic from the display.

3) Support for asynchronous technique: MVC also supports asynchronous technique, which helps developers to develop an application that loads very fast.

4) The modification does not affect the entire model: Modification does not affect the entire model because the model part does not depend on the views part. Therefore, any changes in the Model will not affect the entire architecture.

5) MVC model returns the data without formatting: MVC pattern returns data without applying any formatting so the same components can be used and called for use with any interface.

6) SEO friendly Development platform: Using this platform, it is very easy to develop SEO-friendly URLs to generate more visits from a specific application.

Disadvantages of MVC

1) Increased complexity

2) The inefficiency of data access in view

3) The difficulty of using MVC with a modern user interface.

4) Need multiple programmers

5) Knowledge of multiple technologies is required.

6) Developer has knowledge of client-side code and HTML code.

Tools and technologies used with MVC

There are many tools and technologies which can be used to the developed web application with the help of MVC architecture.

 Depending upon the interest of developers, they can use any of the tools and technologies to develop a web application.

 Here are some tools and technologies which can be used to develop a web application using MVC architecture:

Tools

Visual Studio: Visual Studio is not just only a tool but a complete development environment which provide us facility to create different kinds of application. 

When we want to develop an application using ASP.NET MVC framework then the visual studio is very helpful for us.

1) MYSQL Server ↝ relational database management services to maintain the database.

2) SQL Server ↝ a database engine to maintain database just like MYSQL server 

3) MYSQL Workbench ↝a database design tool 

4) Net Beans ↝ ⇗IDE (integrated development Environment) provide complete environment to develop different applications 

5) Glassfish Server: Java EE application server  

Technologies

 A. HTML, CSS, JQUERY, AJAX for designing

B. Servlet and Java server pages (JSP) used with Net beans

C. EJB (Enterprise Java beans) technologies

D. JSTL (Java server pages standard tag libraries)

E. JPA (Java persistence API)

F. JDBC (Java database connectivity)

G. ASP.NET MVC used with Visual studio

Example of MVC architecture application

★In our research study we have tried to make an Ecommerce web application using MVC architecture which will help the developers to understand the features of model view and controller pattern. E-commerce refers to the online selling and purchasing of goods over the internet. For example, amazon.com is today’s most useful e-commerce website which provides different products of different categories. Customer can purchase those products online using internet. There are different types of e-commerce applications such consumer to consumer, Business to business, business to consumer.

★In our application we have developed a business to consumer application which normally accommodates a B2C scenario consists of two components: first component store front which enables the customers to view different products, the data about the products is maintained in the database and is displayed to the customers on the pages dynamically. Second component is admin console which is protected area. It cannot be accessed by the customers instead it is available to the administration who manages the customer transactions such as customer orders, shipping and payment methods, CRUD (create read update delete) access to the database store.

★The technology used in our application is Java. Java is a programming language which contains the fundamental concepts that can be grasped quickly. It sticks to an object-oriented technique which contained encapsulated objects that communicates with each other by passing information. Java include compile and run time checking to identify the errors. It also contains network security features. It is portable, application can easily be transferred from one platform to another platform with the need of a very little or no modification. Java interpreter is independent of run time environment, so we can run applications quickly. It also provides an automatic garbage collector to free unused memory.

★Java is not only a programming language it is a complete platform which suggests software-based platform consist of two components. JVM (java virtual machine), engine used to execute the instruction translated by the java complier. It is considered as an instance of JRE (java runtime environment) and inserted in different products such as operating system, browsers and web servers etc. Second component of java platform is java application program interface (API) which provides prewritten codes which are prearranged into packages. These packages include classes for creating user interfaces such as font, button, menus etc. There are several editions of java platform such as Java standard edition, Java micro edition and java enterprise edition. Here we are working with java enterprise edition.

★Java enterprise edition provides technologies used for developing and managing vigorous, consistent, scalable and secure server-side applications. These enterprise edition technologies are divided into two categories. These categories include web application technologies and enterprise application technologies. In our application as we must develop a web application so mostly we will be getting help from web application technologies. In our web application we are using Servlet, JSP, JSTL, EJB, and JPA enterprise technologies. Java EE technologies are mostly used technologies in the market as we have shown in a diagram taken from independent survey of European market perform in 2007 (Figure 1).

★★Figure 1:Survey findings about well-known IDEs.

★The tools which we have used for the development of our application are net beans IDE, MySQL server and MySQL workbench. NetBeans is a development environment provides the facility of creating professional, enterprise desktop, mobile and web applications. MySQL server is a database engine used to maintain our database. MySQL workbench is used to visually design database such as ERD (entity relationship diagram).

Designing the application

✦Designing the application demonstrates that how our application can be applied to real world business requirements. Before designing the application, we try to gather the customer requirements. The customer requirements should be clear. As per requirements of our application, our application should meet the following customer requirements.

a. Online representation of data which should be stored in our database. The information about our products which will be displayed to the customer will be (name, image and description).

b. Add products temporary selected by our customer to a shopping cart.

c. Customer can update the quantity of the selected products.

d. Customer can remove the selected product from shopping cart.

e. Customer can view summary of shopping cart i.e. which product he selected and in how much quantity.

f. Customer can place an order and can make payment through a secure checkout process.

g. Our application should provide server-side administration so that administrators can view customer orders, add new products for the customers.

✦After gathering the requirements, we should design application according to customer requirements. We will try to make a use case which will describe that how our application will work and encapsulate its behavior. In our application we are making an e-commerce web site, so our use case will describe the following actions to be performed by different actors.

1) Customer can browse different products of the selected category.

2) Customer will add his desired products of different categories into shopping cart so that later he can purchase it.

3) Customer can view his shopping cart to see which items he has selected.

4) Customer can verify the shopping cart information so that he can proceed to checkout process.

5) Customer will provide his personal information as well he will see his order details on checkout page.

6) After viewing the checkout process page customer will confirm his order.

7) Administrator will view the orders of different customers after successfully login to our application.

8) Administrator can add new products into different categories.

✦According to above given use-case we must identify and design web pages which will be used in our application. We can create the mockups using different techniques. The technique which we use to design our application is paper prototyping in which we try to cooperate with customers by sketching ideas on the paper. In our application we have design five web pages i.e. welcome page (home page entry point to our application where our main categories of products will be shown), Category page (which will show us the list of different products also it will show us shopping cart option and proceed to checkout option), cart page (which will show us the list of all the product items which we have selected for purchasing), checkout page (which will be used to collect the user personal information as well as it will provide the order summary) and confirmation page (which will show the information that his order has been successfully placed) (Figure 2).

✦✦Figure 2:Purchasing an item using a web-application.

Determining the architecture

✴Before we start the development of application we should decide that which type of architecture we should use to develop our application. We should examine the functional components of our application and determine the way through which they will communicate with each other. There are many design patterns are available which can be used to develop an application. Here we are going to use MVC architecture pattern.

✴✴Figure 3:Functionality of each layer in MVC architecture.

✴MVC pattern divides our application into three major components i.e. Model, View and Controller. Model is used to communicate with our database. View is used to get data from model and present it to the user. And finally, the controller is used to define the application behavior. It interacts with the inputs of the users. Normally in web-based application user’s inputs are HTTP GET and HTTP POST. Detail about the MVC architecture pattern is given earlier in this paper in section I, section II, section III and Section IV (Figure 3).

✴Here we will be working with JSP technologies, our business logic into JSP pages will be coded using script lets. The script lets are snippets in <% %> tags. JSP pages will be compiled into Servlet. JSP was firstly introduced in 1999 and it included a description of two model architectures. Model one involves implementing business logic directly with JSP pages and second model applies the MVC pattern architecture which we are using in our application (Figure 4).

✴✴Figure 4:Interaction and overview of the MVC layers.

Designing the data model

Development of application

MVC - Strengths and Weaknesses

• Rapid development
• Easy to learn and implement.

• Bizarre page life cycles, sometimes leaves you guessing where to put your code.
• Very often I had to fight with my code just to produce something simple, my workarounds included lots of javascript.
• False separation of concerns, business logic / data logic can easily be placed into your code behinds.
• Viewstate can grow enormously making your web pages even larger in size
• Little control over the HTML

• Complete separation of concerns over view, data, and business logic.
• Convention over configuration, ASP.NET MVC practically forces you to follow a naming convention
• Much improved control over your HTML
• No postbacks / viewstate
• Support for unit testing

• Takes some time to learn.  First couple of sessions with MVC will feel rough especially if you are coming from a Web Forms background.

 Technologies for Supporting Distributed Computing

 Understanding Distributed Systems Software Technologies via Patterns

Remote Procedure Call 

Definition 

• The client process calls the client stub with parameters, and its execution is suspended until the call is completed.
• The parameters are then translated into machine-independent form by marshalling through client stub. Then the message is prepared which contain the representation of the parameters.
• To find the identity of the site the client stub intercommunicate with name server at which remote procedure exists.
• Using blocking protocol the client stub sends the message to the site where remote procedure call exists. This step halt the client stub until it gets a reply.

• The server site receives the message sent from the client side and converts it into machine specific format.
• Now server stub executes a call on the server procedure along with the parameters, and the server stub is discontinued till the procedure gets completed.
• The server procedure returns the generated results to the server stub, and the results get converted into machine-independent format at server stub and create a message containing the results.
• The result message is sent to the client stub which is converted back into machine specific format suitable for the client stub.
• At last client, stub returns the results to the client process.

Remote Method Invocation 

Definition 

Key Differences Between RPC and RMI

• RPC supports procedural programming paradigms thus is C based, while RMI supports object-oriented programming paradigms and is java based.
• The parameters passed to remote procedures in RPC are the ordinary data structures. On the contrary, RMI transits objects as a parameter to the remote method.
• RPC can be considered as the older version of RMI, and it is used in the programming languages that support procedural programming, and it can only use pass by value method. As against, RMI facility is devised based on modern programming approach, which could use pass by value or reference. Another advantage of RMI is that the parameters passed by reference can be changed.
• RPC protocol generates more overheads than RMI.
• The parameters passed in RPC must be “in-out” which means that the value passed to the procedure and the output value must have the same datatypes. In contrast, there is no compulsion of passing “in-out” parameters in RMI.
• In RPC, references could not be probable because the two processes have the distinct address space, but it is possible in case of RMI.

Difference Between RPC and RMI

Comparison Chart

Common Object Request Broker Architecture (CORBA)

CORBA Features

• It specifies an interface description language (IDL) that allows you to specify the interfaces to objects. IDL object interfaces describe, among other things:
• The data that the object makes public.
• The operations that the object can respond to, including the complete signature of the operation. CORBA operations map to Java methods, and the IDL operation parameter types map to Java datatypes.
• Exceptions that the object can throw. IDL exceptions also map to Java exceptions, and the mapping is very direct.

• All CORBA implementations provide an object request broker (ORB), that handles the routing of object requests in a way that is largely transparent to the application developer. For example, requests (method invocations) on remote objects that appear in the client code look just like local method invocations. The remote call functionality, including marshalling of parameter and return data, is performed for the programmer by the ORB.
• CORBA specifies a network protocol, the Internet Inter-ORB Protocol (IIOP), that provides for transmission of ORB requests and data over a widely-available transport protocol: TCP/IP, the Internet standard.
• A set of fully-specified services eases the burden of application development by making it unnecessary for the developer to constantly reinvent the wheel. Among these services are:
• Naming. One or more services that let you resolve names that are bound to CORBA server objects.
• Transactions. Services that let you manage transaction control of data resources in a flexible and portable way.
• Events.

• the ORB--how to talk to remote objects
• IDL--how to write a portable interface
• the naming service (and JNDI)--how to locate a persistent object
• object adapters--how to register a transient object

ADVANTAGES 

• CORBA supports many existing languages. CORBA also supports mixing these languages within a single distributed application.
• CORBA supports both distribution and Object Orientation.
• CORBA is an industry standard. This creates competition among vendors and ensures that quality implementations exist. The use of the CORBA standard also provides the developer with a certain degree of portability between implementations. Note: application source is not 100% portable between different CORBA products.
• CORBA provides a high degree of interoperability. This insures that distributed objects built on top of different CORBA products can communicate. Large companies do not need to mandate a single CORBA product for all development.
• Over 600 companies back CORBA, including hardware companies, software companies, and cable companies, phone companies, banks, etc.

Benefits of CORBA

• The original version of the CORBA standard was defined in 1991. This first version of the specification was deliberately limited in scope. The OMG’s philosophy was to define a small standard, let implementors gain experience and then slowly expand the standard to incorporate more and more capabilities. This “slow but sure” approach has been remarkably successful. In particular, there have been few backwards-incompatible changes to the CORBA specification. Instead, new versions of the specification have tended to add new functionality rather than modify existing functionality. Today, CORBA is extremely feature-rich, supporting numerous programming languages, operating systems, and a diverse range of capabilities—such as transactions, security, Naming and Trading services, messaging and publish-subscribe services—that are essential for many enterprise-level applications. Many newer middleware technologies claim to be superior to CORBA but actually have to do a lot of “catching up” just to match some of the capabilities that CORBA has had for a long time.

• CORBA is an open standard rather than a proprietary technology. This is important for a variety of reasons.

• First, users can choose an implementation from a variety of CORBA vendors (or choose one of the freeware implementations). You might think that switching from one CORBA product to another would involve a lot of work. However, the amount of work involved is likely to be much less than you might think, particularly if you follow the practical advice in Chapter 25 about how to increase the portability of CORBA-based applications. In contrast, if you use a proprietary middleware system then switching to another proprietary middleware vendor is much more challenging.

• Second, the competition between different CORBA vendors helps to keep software prices down.

• Finally, many proprietary middleware technologies are designed with the assumption that developers will build all their applications using that particular middleware technology, and so they provide only limited support for integration with other technologies. In contrast, CORBA was designed with the goal of making it easy to integrate with other technologies. Indeed, the CORBA specification explicitly tackles integrations with TMN, SOAP, Microsoft’s (D)COM and DCE (a middleware standard that was popular before CORBA). Furthermore, many parts of J2EE borrow heavily from concepts in CORBA, which makes it relatively easy to integrate J2EE and CORBA. Some vendors sell gateways between CORBA and J2EE that make such integration even easier. Several CORBA vendors sell COM-to-CORBA and/or .NET-to-CORBA gateways. This provides a very pragmatic solution to organizations that wish to write GUI applications in, say, Visual Basic on Windows that act as clients to server applications on a different type of computer, such as UNIX or a mainframe. The Visual Basic GUI can be written as a COM/.NET client that thinks it is talking to a COM/.NET server, but in fact communicates with a gateway that forwards on requests to a CORBA server.

• CORBA implementations are available for a wide variety of computers, including IBM OS/390 and Fujitsu GlobalServer mainframes, numerous variants of UNIX (including Linux), Windows, AS/400, Open VMS, Apple’s OS X and several embedded operating systems. There are very few other middleware technologies that are available on such a wide range of computers.

• CORBA defines standardized language mappings for a wide variety of programming languages, such as C, C++, Java, Smalltalk, Ada, COBOL, PL/I, LISP, Python and IDLScript. Some small organizations might use a single programming language for all their projects, but as an organization increases in size, it becomes increasingly likely that the organization will make use of several programming languages. Likewise, the older an organization is, the higher the likelihood becomes that some of its “legacy” (older) applications are implemented in one programming language and newer applications are implemented in a different programming language. For these organizational reasons, it is important for a middleware system to support many programming languages; unfortunately, not all middleware systems do so. One extreme case of this is J2EE, which supports only Java. Another extreme case is the SOAP middleware standard. SOAP applications can be built with a variety of programming languages but, at the time of writing, the SOAP standard defines only one language mapping (for Java). There may be several vendors who support, say, C++ development of SOAP applications, but each of those vendors provides their own proprietary C++ APIs. This means that there is no source-code portability of non-Java SOAP applications across different vendor products.

• The on-the-wire protocol infrastructure of CORBA (discussed in Chapter 11) ensures that messages between clients and servers are transmitted in a compact representation. Also, most CORBA implementations marshal data (that is, convert data from programming-language types into a binary buffer that can be transmitted) efficiently. Many other middleware technologies also use a similarly compact format for transmitting data and have efficient marshaling infrastructure. However, there are some notable exceptions, as I now discuss.

• SOAP uses XML to represent data that is to be transmitted. The verbosity of XML results in SOAP using much more network bandwidth than CORBA.1 SOAP-based applications also incur considerable CPU overhead involved in formatting programming-language types into XML format and later parsing the XML to extract the embedded programming-languages types.

• Some other middleware technologies, such as IBM MQ Series, transmit only binary data, which is efficient. However, this requires that developers write the marshaling code that copies programming-language types into the binary buffers prior to transmission, and the unmarshaling code to extract the programming-language types from a binary buffer. In contrast, a CORBA IDL compiler generates the marshaling and unmarshaling code, so that developers do not need to write (and maintain) such low-level code.

• The flexible, server-side infrastructure of CORBA (Chapter 5) makes it feasible to develop servers that can scale from handling a small number of objects up to handling a virtually unlimited number of objects. Obviously, scalability varies from one CORBA implementation to another but, time and time again, real-world projects have demonstrated that a CORBA server can scale to handle not just a huge amount of server-side data, but also high communication loads from thousands of client applications. Most CORBA vendors will likely know of customers who have tried a different middleware technology, found that it could not scale sufficiently well and then switched to CORBA.

• With such an impressive list of benefits as those discussed in this chapter, it is little wonder that CORBA is being used successfully in many industries, including aerospace, consulting, education, e-commerce, finance, government, health-care, human resources, insurance, ISVs, manufacturing, military, petrochemical, publishing, real estate, research, retail, telecommunications, and utilities.

• CORBA is used in everything from billing systems and multi-media news delivery to airport runway illumination, aircraft radio control and the Hubble space telescope. Most of the world’s telephone systems, as well as the truly mission-critical systems operated by the worlds biggest banks, are built on CORBA.

• A discussion about real-world projects that have benefitted from the use of CORBA is outside the scope of this book. However, many CORBA success stories are available on various web sites. For example, you can find over 300 CORBA success stories on www.corba.org. The web sites of some CORBA vendors also contain more detailed success stories.

XML 

XML stands for Extensible Markup Language. It is a text-based markup language derived from Standard Generalized Markup Language (SGML).

XML tags identify the data and are used to store and organize the data, rather than specifying how to display it like HTML tags, which are used to display the data. XML is not going to replace HTML in the near future, but it introduces new possibilities by adopting many successful features of HTML.

There are three important characteristics of XML that make it useful in a variety of systems and solutions −

XML is extensible − XML allows you to create your own self-descriptive tags, or language, that suits your application.

XML carries the data, does not present it − XML allows you to store the data irrespective of how it will be presented.

XML is a public standard − XML was developed by an organization called the World Wide Web Consortium (W3C) and is available as an open standard.

XML Usage

A short list of XML usage says it all −

• XML can work behind the scene to simplify the creation of HTML documents for large web sites.
• XML can be used to exchange the information between organizations and systems.
• XML can be used for offloading and reloading of databases.
• XML can be used to store and arrange the data, which can customize your data handling needs.
• XML can easily be merged with style sheets to create almost any desired output.

Virtually, any type of data can be expressed as an XML document.

What is Markup?

XML is a markup language that defines set of rules for encoding documents in a format that is both human-readable and machine-readable. So what exactly is a markup language? Markup is information added to a document that enhances its meaning in certain ways, in that it identifies the parts and how they relate to each other. More specifically, a markup language is a set of symbols that can be placed in the text of a document to demarcate and label the parts of that document.

Following example shows how XML markup looks, when embedded in a piece of text −

<message>

   <text>Hello, world!</text>

</message>

This snippet includes the markup symbols, or the tags such as <message>...</message> and <text>... </text>. The tags <message> and </message> mark the start and the end of the XML code fragment. The tags <text> and </text> surround the text Hello, world!.

Is XML a Programming Language?

A programming language consists of grammar rules and its own vocabulary which is used to create computer programs. These programs instruct the computer to perform specific tasks. XML does not qualify to be a programming language as it does not perform any computation or algorithms. It is usually stored in a simple text file and is processed by special software that is capable of interpreting XML.

XML Elements

XML elements can be defined as building blocks of an XML. Elements can behave as containers to hold text, elements, attributes, media objects or all of these.

Each XML document contains one or more elements, the scope of which are either delimited by start and end tags, or for empty elements, by an empty-element tag.

Syntax

Following is the syntax to write an XML element −

<element-name attribute1 attribute2>

....content

</element-name>

where,

element-name is the name of the element. The name its case in the start and end tags must match.

attribute1, attribute2 are attributes of the element separated by white spaces. An attribute defines a property of the element. It associates a name with a value, which is a string of characters. An attribute is written as −

name = "value"

name is followed by an = sign and a string value inside double(" ") or single(' ') quotes.

Empty Element

An empty element (element with no content) has following syntax −

<name attribute1 attribute2.../>

Following is an example of an XML document using various XML element −

<?xml version = "1.0"?>

<contact-info>

   <address category = "residence">

      <name>Tanmay Patil</name>

      <company>TutorialsPoint</company>

      <phone>(011) 123-4567</phone>

   </address>

</contact-info>

XML Elements Rules

Following rules are required to be followed for XML elements −

• An element name can contain any alphanumeric characters. The only punctuation mark allowed in names are the hyphen (-), under-score (_) and period (.).

• Names are case sensitive. For example, Address, address, and ADDRESS are different names.

• Start and end tags of an element must be identical.

• An element, which is a container, can contain text or elements as seen in the above example.

XML
➥Pros

1. Open and extensible

The XML structure is adaptable and can be modified to match industry specific vocabulary. Users can add elements when needed.

2. Internationalization

Multilingual documents and Unicode standards are supported by XML. This is important for electronic business applications.

3. Future oriented technology 

The W3C has endorsed XML, which is supported by major software providers. It is also being used in an increasing number of industries.

4. Self-describing data

Business applications have tasks other than just presenting the content. XML is therefore used because there is complete data usability as well as proper presentation of data. XML is thus preferred over traditional database systems.

5. Integration of traditional databases and formats

XML documents support all types of data; classical (text, numbers), multimedia (sounds), active formats (java applets, active x components).

6. Data presentation modifications

XML style sheets can be used to modify documents or websites without modifying the actual data.

7. One Server view

Data from different databases and multiple servers can be a part of an XML document. That is, the whole WWW is converted into one database.

➥Cons

1. Requires more development resources and expertise to implement and maintain

2. You become responsible for the programming, logic, debugging and monitoring of your site and you will not be able to leverage the development

3. XML's biggest disadvantage is that its parsers tend to be very large, although the large memory footprint of XML parsers may be reduced to a reasonable size by eliminating unneeded features.

4. The larger size of XML data records may be an issue for some applications. This can be dealt with by compressing the data before transmitting it or writing it to disk.

JSON Pros and Cons

JSON is a simple object serialization approach based on the JavaScript object initializers syntax. The code for initializer (object literal) is put into a string and then interpreted using JavaScript eval() function or JSON parser (which is very lightweight):

 serializedObj='{firstName:"john", lastName:"doe"}';

...

// This is just an example, JSON parser should be used instead

// to avoid security vulnerabilities of "eval"

var obj = eval("(" + serializedObj + ")");

document.getElementById("firstName").innerHTML=person.firstName;

JSON is used extensively in various AJAX frameworks and toolkits to provide easy object serialization for remote calls. It is is supported by both GWT and DOJO. There is a growing realization that perhaps JSON should be considered as an option when implementing SOA, for example Dion Hinchcliffe recently published a blog entry suggesting that JSON (and other Web 2.0 technologies) must be seriously considered by SOA architects.

So what are the benefits of using JSON relative to XML (for this comparison I want to focus just on XML and stay away from SOAP)? Here is my brief take on that, there are also numerous other articles and posts on the subjects.

So the bottom line is that JSON and XML are, of course, two very different technologies; XML is much broader in scope so I'm not even sure if comparing them side by side is fair.

As an object serialization technology for AJAX (or should it now be called AJAJ since we've replaced XML with JSON?) JSON looks very appealing. Anybody who ever tried parsing SOAP directly in a browser (while having to support multiple browsers) can attest that this is not a straightforward task. JSON simplifies this task dramatically. So I think that ESB vendors should definitely start thinking about adding JSON to the list of formats they support.

One of the keys to SOA success is that it should be easy to consume a service, i.e., the entry barrier for service consumers must be low to support "grass root" SOA adoption. While a top-down SOA effort may succeed, it will certainly take longer than bottom-up ("grass-root") approach when developers are able to consume services as they see fit. AJAX/JSON fits this bill perfectly - it is easily understood by developers and it does not require any Web services -specific tools or infrastructure.

Data Encoding Techniques

Encoding is the process of converting the data or a given sequence of characters, symbols, alphabets etc., into a specified format, for the secured transmission of data. Decoding is the reverse process of encoding which is to extract the information from the converted format.

Data Encoding

Encoding is the process of using various patterns of voltage or current levels to represent 1s and 0s of the digital signals on the transmission link.

The common types of line encoding are Unipolar, Polar, Bipolar, and Manchester.

Encoding Techniques

The data encoding technique is divided into the following types, depending upon the type of data conversion.

Analog data to Analog signals − The modulation techniques such as Amplitude Modulation, Frequency Modulation and Phase Modulation of analog signals, fall under this category.

Analog data to Digital signals − This process can be termed as digitization, which is done by Pulse Code Modulation (PCM). Hence, it is nothing but digital modulation. As we have already discussed, sampling and quantization are the important factors in this. Delta Modulation gives a better output than PCM.

Digital data to Analog signals − The modulation techniques such as Amplitude Shift Keying (ASK), Frequency Shift Keying (FSK), Phase Shift Keying (PSK), etc., fall under this category. These will be discussed in subsequent chapters.

Digital data to Digital signals − These are in this section. There are several ways to map digital data to digital signals. Some of them are −

Non Return to Zero (NRZ)

NRZ Codes has 1 for High voltage level and 0 for Low voltage level. The main behavior of NRZ codes is that the voltage level remains constant during bit interval. The end or start of a bit will not be indicated and it will maintain the same voltage state, if the value of the previous bit and the value of the present bit are same.

The following figure explains the concept of NRZ coding.

If the above example is considered, as there is a long sequence of constant voltage level and the clock synchronization may be lost due to the absence of bit interval, it becomes difficult for the receiver to differentiate between 0 and 1.

There are two variations in NRZ namely −

NRZ - L (NRZ – LEVEL)

There is a change in the polarity of the signal, only when the incoming signal changes from 1 to 0 or from 0 to 1. It is the same as NRZ, however, the first bit of the input signal should have a change of polarity.

NRZ - I (NRZ – INVERTED)

If a 1 occurs at the incoming signal, then there occurs a transition at the beginning of the bit interval. For a 0 at the incoming signal, there is no transition at the beginning of the bit interval.

NRZ codes has a disadvantage that the synchronization of the transmitter clock with the receiver clock gets completely disturbed, when there is a string of 1s and 0s. Hence, a separate clock line needs to be provided.

Bi-phase Encoding

The signal level is checked twice for every bit time, both initially and in the middle. Hence, the clock rate is double the data transfer rate and thus the modulation rate is also doubled. The clock is taken from the signal itself. The bandwidth required for this coding is greater.

There are two types of Bi-phase Encoding.

• Bi-phase Manchester
• Differential Manchester

Bi-phase Manchester

In this type of coding, the transition is done at the middle of the bit-interval. The transition for the resultant pulse is from High to Low in the middle of the interval, for the input bit 1. While the transition is from Low to High for the input bit 0.

Differential Manchester

In this type of coding, there always occurs a transition in the middle of the bit interval. If there occurs a transition at the beginning of the bit interval, then the input bit is 0. If no transition occurs at the beginning of the bit interval, then the input bit is 1.

The following figure illustrates the waveforms of NRZ-L, NRZ-I, Bi-phase Manchester and Differential Manchester coding for different digital inputs.

Block Coding

Among the types of block coding, the famous ones are 4B/5B encoding and 8B/6T encoding. The number of bits are processed in different manners, in both of these processes.

4B/5B Encoding

In Manchester encoding, to send the data, the clocks with double speed is required rather than NRZ coding. Here, as the name implies, 4 bits of code is mapped with 5 bits, with a minimum number of 1 bits in the group.

The clock synchronization problem in NRZ-I encoding is avoided by assigning an equivalent word of 5 bits in the place of each block of 4 consecutive bits. These 5-bit words are predetermined in a dictionary.

The basic idea of selecting a 5-bit code is that, it should have one leading 0 and it should have no more than two trailing 0s. Hence, these words are chosen such that two transactions take place per block of bits.

8B/6T Encoding

We have used two voltage levels to send a single bit over a single signal. But if we use more than 3 voltage levels, we can send more bits per signal.

For example, if 6 voltage levels are used to represent 8 bits on a single signal, then such encoding is termed as 8B/6T encoding. Hence in this method, we have as many as 729 (3^6) combinations for signal and 256 (2^8) combinations for bits.

These are the techniques mostly used for converting digital data into digital signals by compressing or coding them for reliable transmission of data.

Data Structure - Sorting Techniques

Sorting refers to arranging data in a particular format. Sorting algorithm specifies the way to arrange data in a particular order. Most common orders are in numerical or lexicographical order.

The importance of sorting lies in the fact that data searching can be optimized to a very high level, if data is stored in a sorted manner. Sorting is also used to represent data in more readable formats. Following are some of the examples of sorting in real-life scenarios −

Telephone Directory − The telephone directory stores the telephone numbers of people sorted by their names, so that the names can be searched easily.

Dictionary − The dictionary stores words in an alphabetical order so that searching of any word becomes easy.

In-place Sorting and Not-in-place Sorting

Sorting algorithms may require some extra space for comparison and temporary storage of few data elements. These algorithms do not require any extra space and sorting is said to happen in-place, or for example, within the array itself. This is called in-place sorting. Bubble sort is an example of in-place sorting.

However, in some sorting algorithms, the program requires space which is more than or equal to the elements being sorted. Sorting which uses equal or more space is called not-in-place sorting. Merge-sort is an example of not-in-place sorting.

Stable and Not Stable Sorting

If a sorting algorithm, after sorting the contents, does not change the sequence of similar content in which they appear, it is called stable sorting.

If a sorting algorithm, after sorting the contents, changes the sequence of similar content in which they appear, it is called unstable sorting.

Stability of an algorithm matters when we wish to maintain the sequence of original elements, like in a tuple for example.

Adaptive and Non-Adaptive Sorting Algorithm

A sorting algorithm is said to be adaptive, if it takes advantage of already 'sorted' elements in the list that is to be sorted. That is, while sorting if the source list has some element already sorted, adaptive algorithms will take this into account and will try not to re-order them.

A non-adaptive algorithm is one which does not take into account the elements which are already sorted. They try to force every single element to be re-ordered to confirm their sortedness.

Important Terms

Some terms are generally coined while discussing sorting techniques, here is a brief introduction to them −

Increasing Order

A sequence of values is said to be in increasing order, if the successive element is greater than the previous one. For example, 1, 3, 4, 6, 8, 9 are in increasing order, as every next element is greater than the previous element.

Decreasing Order

A sequence of values is said to be in decreasing order, if the successive element is less than the current one. For example, 9, 8, 6, 4, 3, 1 are in decreasing order, as every next element is less than the previous element.

Non-Increasing Order

A sequence of values is said to be in non-increasing order, if the successive element is less than or equal to its previous element in the sequence. This order occurs when the sequence contains duplicate values. For example, 9, 8, 6, 3, 3, 1 are in non-increasing order, as every next element is less than or equal to (in case of 3) but not greater than any previous element.

Non-Decreasing Order

A sequence of values is said to be in non-decreasing order, if the successive element is greater than or equal to its previous element in the sequence. This order occurs when the sequence contains duplicate values. For example, 1, 3, 3, 6, 8, 9 are in non-decreasing order, as every next element is greater than or equal to (in case of 3) but not less than the previous one.