Understanding Graphs and Their Application on Software Systems

Lately, I wanted to spend a little bit time on going back to fundamental computer science concepts. I am going to start with Graphs, specifically Depth First Traversal (a.k.a. Depth First Search or DFS) and Breadth First Traversal (a.k.a Breadth First Search or BFS). However, this post is only about the definition of Graph and its application in software systems.
2017-09-19 17:21
Tugberk Ugurlu


Lately, I wanted to spend a little bit time on going back to fundamental computer science concepts. Hopefully, I will be able to write about these while I am looking into them in order to offload the knowledge from my brain to the magic hands of the Web :) I am going to start with Graphs, specifically Depth First Traversal (a.k.a. Depth First Search or DFS) and Breadth First Traversal (a.k.a Breadth First Search or BFS). However, this post is only about the definition of Graph and its application in software systems.

What is a Graph?

I am sure you are capable of Googling what a Graph is and ironically maybe that’s why you are reading this sentence now. However, I am not going to put the fancy explanation of a Graph here. Wikipedia already has a great definition on a Graph which can be useful to start with.

Let’s start with a picture:

Picture1

This is a graph and there are some unique characteristics of this which makes it a graph.

  • Vertices (a.k.a. Nodes): Each circle with a label inside the above picture is called a vertex or node. They are fundamental building blocks of a graph.
  • Edges (a.k.a. Arc, Line, Link, Branch): A line that joins two vertices together is called as edge. An edge could be in three forms: undirected and directed. We will get to what these actually mean.

At this point you might be asking what is the difference between a graph and a tree? A tree is actually a graph with some special constraints applied to. A few of these that I know:

  • A tree cannot contain a cycle but a graph can (see the A, B and E nodes and their edges inside the above picture).
  • A tree always has a specific root node, whereas you don’t have this concept with a graph.
  • A tree can only has one edge between its two nodes whereas we can have unidirectional and bidirectional edges between nodes within a graph

I am sure there are more but I believe these are the ones that matter the most.

As we can see with the tree example, graphs comes in many forms. There are many types of graphs and each type has its own unique characteristics and real world use cases. Undirected and directed graphs are two of these types as I briefly mentioned while explaining the edges. I believe the best example to describe the difference between them is to have a look at the fundamental concept of Facebook and Twitter.

Application of Graphs

Graphs are amazing, I absolutely love the concept of a graph! Everyone interacts with a system everyday which somehow makes use of graphs. Facebook, Google Maps, Foursquare, the fraud check system that your bank applies are all making use of a graph and there are many, many more. One application of graph concept which I love is a recommendation engine. There are many forms of this but a very basis one is called Collaborative Filtering. At its basis, it works under a notion of “Steve and Mark liked BMW, Mercedes and Toyota, you like BMW and Toyota, and you may like Mercedes, too?”.

There are some really good graph databases with their own query languages as well. One that I love about is Neo4j which uses Cypher query language to make its data available to be consumed. On their web site, there are a few key applications of Neo4j listed and they are fundamentally real world applications of the graph concept.

You can also come across some interesting problems in the space of mathematics which has solutions based on a type of graph like Seven Bridges of Königsberg problem (and I think this problem is the cornerstone in the history of graph theory).

Here is My Proudest Achievement, What is Yours?

It's very common that you get asked about your proudest achievement. I wanted to put mine here publicly so that I would have a place to direct people to. So, here it is :)
2017-09-18 16:59
Tugberk Ugurlu


It's very common that you get asked about your proudest achievement. I wanted to put mine here publicly so that I would have a place to direct people to. So, here it is :)

My proudest achievement to this day dates back to 2010. I was working at a local Travel Agency in Turkey while still studying Travel Management at the university and we had a Web site for our customers to book their airport transfers from/to their hotels by paying online. However, the application didn't allow our customers to book additional services with extra cost such as baby booster seat. In addition to this, we were unable to reflect our pricing accurately for particular conditions due to the limitations on the system. At the time, I was working at the reservations and booking department but I had a huge interest on software development, especially on web applications.

When our web developer left the company, I prototyped the algorithm to calculate the airport transfer pricing on SQL Server based on the number of passengers, arrival and departure dates. I presented this to my manager who was also in charge of the company's online sales, and asked for a budget and time for developing a new airport transfer booking system for the company. I explained that this system would have the same features as the old system along with the additional features we have always wanted. This was going to allow us to provide better service to our customers and reflect cheaper prices by having a maintainable system to build upon. My manger believed in me, and gave me time and budget to invest on this. I spent a month to develop the system and its content management system by coding the business logic in C# (while learning it at the same time), developing the user interface as a web application using HTML, CSS and JavaScript, and integrating it with an online payment system. I had to deal with lots of things I hadn't known about but having a good support from my manager made me always trust myself and keep pushing to come through all the obstacles. We rolled out the system under a different domain name first and advertised it through Google AdWords‎ (you could see that version see here even if the styles and functionality don't quite work on web.archive.org). Within the first 5 hours, we sold a Private Minibus Transfer through the system Over the weeks, we directed all our transfer booking channels to this new system and kept evolving it. After two years, the system sold 32% more transfers than the old system and yielded 26% more revenue. The final look of the system is still running here and maintained by the company (I should point out that I am not entirely responsible for the new look of the site , especially for those red primary action buttons!). Proving myself with this achievement also gave me a chance to take more responsibility on software engineering at the company and I was able to get a budget for an accommodation booking system (it can been found on web.archive.org) which yielded extra revenue for the company for a few years.

Lots of things happened after this and I achieved so much more such as being part of several successful teams to create valuable software products, being published, having the Microsoft MVP award for 5 years in a row, speaking at lots of international conferences, maintaining a successful blog for 7+ years and many more. However, nothing was able to beat that because it was a unique opportunity to be able to fight for something I truly believed in. Besides that, having a true leader as your manager is a unique opportunity. He trusted me and my skills, and when looking back at this now, it's very clear to see that I would never have become a good software developer without this trust and my confident in myself.

What's Your Proudest Achievement?

Well, it's your turn. Hopefully I encouraged you to share yours publicly as well. Please share yours as a comment here, preferably by linking to your blog post which you are about to write :)

Defining What Good Looks Like for a Software Engineer

What does good look like for a software engineer? This is a question you might be asking frequently to yourself and I tried to share my thoughts on the topic with this blog post.
2017-03-18 15:00
Tugberk Ugurlu


If you are a software engineer, this is a very common question you will get to ask yourself a lot. This is going to be especially very frequent if you are being part of the recruitment process in your company. As you may know, I work at Redgate, and we have a good culture for development teams. Besides that, common characteristics of a good engineer with examples and counter examples for each engineering role are defined, too. This is a really good guidance for the employer to reflect their culture for a particular role. It’s also good for the employees to understand where they are on being an effective employee.

(Image is from https://commons.wikimedia.org/wiki/File:Coding_Shots_Annual_Plan_high_res-5.jpg)

I got inspired by this and I wanted to share the list of principals I value and look for within a software engineer. Obvious disclaimer: this is not the list of principals that my employer values even if the most of them are pretty similar. As we got the disclaimer out of our way, let's see these principals:

  • Knows the fundamental concepts, data structures and common algorithms rather than only being too good with a programming language or a specific framework w/o understanding the basics. In other words, know the basics and be polyglot.
  • Has good communication skills - both verbal and written. Without this, it's impossible to be a good software engineer.
  • Being pragmatic - Works incrementally and balances delivering value frequently with delivering high quality.
  • Iterates fast - Values Continuous Integration (CI) and Continuous Delivery (CD), makes their code fail fast, enforce consistency and keep master branch releasable. Your release process should as easy as adding a git tag as a valid semantic version.
  • Cares for sustainability - Strives for producing code which will sustain for years, even decades. Not one-off, works-now-who-knows-when-it-will-stop-working ones.
  • Knows the business - Cares to understand the business domain and strives for establishing an ubiquitous language between the software product team and stakeholders.
  • Strives for THE BEST UX - Makes user experience the part of the product completeness.
  • Being a team player - Works with their peers, gets/gives code review from/to them. Develops their skills while they are developing their own. Should strive for being transparent to the team all the time.
  • Knows the metrics but also has a vision - Should know the metrics and how to get them to make decisions. However, they should have a vision at the same time, too. They should not have the "Let’s ask the users” mindset as the default approach for product feature decisions. Remember, good artists copy; great artists steal! The problem you are trying to solve has been probably solved within the same or a different context. Find that, bend it and apply differently.
  • Disagrees and commits when needed - Should not be shy about getting their opinions out and pursue them. However, they should also know that a decision has to be made, and when that’s the case, they should commit fully and try to get the best out of it even if it’s not the decision they wanted to see.
  • Values open source and contributing back to software community - Has a blog, gives talks at conferences or user groups, contributes back to open source projects. Simply shares what they are proud of with others openly.

There are probably more but these are the most important ones that I care about and value at a very high level. However, I wonder what yours are, too. Therefore, please share them with me here by send me a comment.

ASP.NET Core Authentication in a Load Balanced Environment with HAProxy and Redis

Token based authentication is a fairly common way of authenticating a user for an HTTP application. However, handling this in a load balanced environment has always involved extra caring. In this post, I will show you how this is handled in ASP.NET Core by demonstrating it with HAProxy and Redis through the help of Docker.
2016-11-28 23:31
Tugberk Ugurlu


Token based authentication is a fairly common way of authenticating a user for an HTTP application. ASP.NET and its frameworks had support for implementing this out of the box without much effort with different type of authentication approaches such as cookie based authentication, bearer token authentication, etc. ASP.NET Core is a no exception to this and it got even better (which we will see in a while).

However, handling this in a load balanced environment has always involved extra caring as all of the nodes should be able to read the valid authentication token even if that token has been written by another node. Old-school ASP.NET solution to this is to keep the Machine Key in sync with all the nodes. Machine key, for those who are not familiar with it, is used to encrypt and decrypt the authentication tokens under ASP.NET and each machine by default has its own unique one. However, you can override this and put your own one in place per application through a setting inside the Web.config file. This approach had its own problems and with ASP.NET Core, all data protection APIs have been revamped which cleared a room for big improvements in this area such as key expiration and rolling, key encryption at rest, etc. One of those improvements is the ability to store keys in different storage systems, which is what I am going to touch on in this post.

The Problem

Imagine a case where we have an ASP.NET Core application which uses cookie based authentication and stores their user data in MongoDB, which has been implemented using ASP.NET Core Identity and its MongoDB provider.

1-ok-wo-lb

This setup is all fine and our application should function perfectly. However, if we put this application behind HAProxy and scale it up to two nodes, we will start seeing problems like below:

System.Security.Cryptography.CryptographicException: The key {3470d9c3-e59d-4cd8-8668-56ba709e759d} was not found in the key ring.
   at Microsoft.AspNetCore.DataProtection.KeyManagement.KeyRingBasedDataProtector.UnprotectCore(Byte[] protectedData, Boolean allowOperationsOnRevokedKeys, UnprotectStatus& status)
   at Microsoft.AspNetCore.DataProtection.KeyManagement.KeyRingBasedDataProtector.DangerousUnprotect(Byte[] protectedData, Boolean ignoreRevocationErrors, Boolean& requiresMigration, Boolean& wasRevoked)
   at Microsoft.AspNetCore.DataProtection.KeyManagement.KeyRingBasedDataProtector.Unprotect(Byte[] protectedData)
   at Microsoft.AspNetCore.Antiforgery.Internal.DefaultAntiforgeryTokenSerializer.Deserialize(String serializedToken)

Let’s look at the below diagram to understand why we are having this problem:

2-not-ok-w-lb

By default, ASP.NET Core Data Protection is wired up to store its keys under the file system. If you have your application running under multiple nodes as shown in above diagram, each node will have its own keys to protect and unprotect the sensitive information like authentication cookie data. As you can guess, this behaviour is problematic with the above structure since one node cannot read the protected data which the other node protected.

The Solution

As I mentioned before, one of the extensibility points of ASP.NET Core Data Protection stack is the storage of the data protection keys. This place can be a central place where all the nodes of our web application can reach out to. Let’s look at the below diagram to understand what we mean by this:

4-ok-w-lb

Here, we have Redis as our Data Protection key storage. Redis is a good choice here as it’s a well-suited for key-value storage and that’s what we need. With this setup, it will be possible for both nodes of our application to read protected data regardless of which node has written it.

Wiring up Redis Data Protection Key Storage

With ASP.NET Core 1.0.0, we had to write the implementation by ourselves to make ASP.NET Core to store Data Protection keys on Redis but with 1.1.0 release, the team has simultaneously shipped a NuGet package which makes it really easy to wire this up: Microsoft.AspNetCore.DataProtection.Redis. This package easily allows us to swap the data protection storage destination to be Redis. We can do this while we are configuring services as part of ConfigureServices:

public void ConfigureServices(IServiceCollection services)
{
    // sad but a giant hack :(
    // https://github.com/StackExchange/StackExchange.Redis/issues/410#issuecomment-220829614
    var redisHost = Configuration.GetValue<string>("Redis:Host");
    var redisPort = Configuration.GetValue<int>("Redis:Port");
    var redisIpAddress = Dns.GetHostEntryAsync(redisHost).Result.AddressList.Last();
    var redis = ConnectionMultiplexer.Connect($"{redisIpAddress}:{redisPort}");

    services.AddDataProtection().PersistKeysToRedis(redis, "DataProtection-Keys");
    services.AddOptions();

    // ...
}

I have wired it up exactly like this in my sample application in order to show you a working example. It’s an example taken from ASP.NET Identity repository but slightly changed to make it work with MongoDB Identity store provider.

Note here that configuration values above are specific to my implementation and it doesn’t have to be that way. See these lines inside my Docker Compose file and these inside my Startup class to understand how it’s being passed and hooked up.

The sample application can be run on Docker through Docker Compose and it will get a few things up and running:

  • Two nodes of the application
  • A MongoDB instance
  • A Redis instance

Image

You can see my docker-compose.yml file to understand how I hooked things together:

mongo:
    build: .
    dockerfile: mongo.dockerfile
    container_name: haproxy_redis_auth_mongodb
    ports:
      - "27017:27017"

redis:
    build: .
    dockerfile: redis.dockerfile
    container_name: haproxy_redis_auth_redis
    ports:
      - "6379:6379"

webapp1:
    build: .
    dockerfile: app.dockerfile
    container_name: haproxy_redis_auth_webapp1
    environment:
      - ASPNETCORE_ENVIRONMENT=Development
      - ASPNETCORE_server.urls=http://0.0.0.0:6000
      - WebApp_MongoDb__ConnectionString=mongodb://mongo:27017
      - WebApp_Redis__Host=redis
      - WebApp_Redis__Port=6379
    links:
      - mongo
      - redis

webapp2:
    build: .
    dockerfile: app.dockerfile
    container_name: haproxy_redis_auth_webapp2
    environment:
      - ASPNETCORE_ENVIRONMENT=Development
      - ASPNETCORE_server.urls=http://0.0.0.0:6000
      - WebApp_MongoDb__ConnectionString=mongodb://mongo:27017
      - WebApp_Redis__Host=redis
      - WebApp_Redis__Port=6379
    links:
      - mongo
      - redis

app_lb:
    build: .
    dockerfile: haproxy.dockerfile
    container_name: app_lb
    ports:
      - "5000:80"
    links:
      - webapp1
      - webapp2

HAProxy is also configured to balance the load between two application nodes as you can see inside the haproxy.cfg file, which we copy under the relevant path inside our dockerfile:

global
  log 127.0.0.1 local0
  log 127.0.0.1 local1 notice

defaults
  log global
  mode http
  option httplog
  option dontlognull
  timeout connect 5000
  timeout client 10000
  timeout server 10000

frontend balancer
  bind 0.0.0.0:80
  mode http
  default_backend app_nodes

backend app_nodes
  mode http
  balance roundrobin
  option forwardfor
  http-request set-header X-Forwarded-Port %[dst_port]
  http-request set-header Connection keep-alive
  http-request add-header X-Forwarded-Proto https if { ssl_fc }
  option httpchk GET / HTTP/1.1\r\nHost:localhost
  server webapp1 webapp1:6000 check
  server webapp2 webapp2:6000 check

All of these are some details on how I wired up the sample to work. If we now look closely at the header of the web page, you should see the server name written inside the parenthesis. If you refresh enough, you will see that part alternating between two server names:

Image

Image

This confirms that our load is balanced between the two application nodes. The rest of the demo is actually very boring. It should just work as you expect it to work. Go to “Register” page and register for an account, log out and log back in. All of those interactions should just work. If we look inside the Redis instance, we should also see that Data Protection key has been written there:

docker run -it --link haproxy_redis_auth_redis:redis --rm redis redis-cli -h redis -p 6379
LRANGE DataProtection-Keys 0 10

Image

Conclusion and Going Further

I believe that I was able to show you what you need to care about in terms of authentication when you scale our your application nodes to multiple servers. However, do not take my sample as is and apply to your production application :) There are a few important things that suck on my sample, like the fact that my application nodes talk to Redis in an unencrypted fashion. You may want to consider exposing Redis over a proxy which supports encryption.

The other important bit with my implementation is that all of the nodes of my application act as Data Protection key generators. Even if I haven’t seen much problems with this in practice so far, you may want to restrict only one node to be responsible for key generation. You can achieve this by calling DisableAutomaticKeyGeneration like below during the configuration stage on your secondary nodes:

public void ConfigureServices(IServiceCollection services)
{
     services.AddDataProtection().DisableAutomaticKeyGeneration();
}

I would suggest determining whether a node is primary or not through a configuration value so that you can override this through an environment variable for example.

React with Redux: A Stable, Powerful and Scalable Combination - Part 1

React and Redux has been my go-to UI tools for a while now and I wanted share the fundemental benefits of adopting this type of architecture on your web applications. This is the first part of the blog post series I will publish on this.
2016-10-22 14:25
Tugberk Ugurlu


For the last a few months, I have been using React and Redux. I successfully converted a small application from Aurelia to React + Redux combination. Actually, it's a lie that that application is small. I told you it's small because it was less than halfway done at the time I started converting. That Web application is meant to be complex and has complicated data needs. Besides that application, we started building a completely new web application on top of React and Redux: SQL Clone Web Client. We haven’t shıpped ıt yet but we are approaching there.

This is an interesting move from someone like me who hated and thought React was bad.

However, I must admit that it was a premature thinking. I had my reasons but those reasons blocked me to look further to see the actual benefıt and power of React. In this post, I am going to hopefully answers the "why" question behind React and I will take it further to mix it with Redux.

I also suggest you to have a look at the short video of Cory House answering the "Why React" question.

React

If you don't know already, React is a library from Facebook to help you create user interfaces. It's important to make the distinction here that React is not a framework like Angular or Aurelia. You can see React as the V in MVC. However, this doesn't mean that you cannot create full-blown applications with React. There are a few other tiny libraries which you can plug into React like react-router, react-redux and they close the React's gap to build scalable Web applications.

React takes a declarative and component based approach on creating user interfaces. For example, the below is the well-known "Hello World" example of React:

var HelloMessage = React.createClass({
  render: function() {
      return <div>Hello {this.props.name}</div>;
  }
});

ReactDOM.render(<HelloMessage name="John" />, mountNode);

mountNode is just an element here which you can get a hold of through document.getElementById or similar APIs to that.

This will print "Hello John" inside the mountNode. At this point, it's OK to be puzzled with all the buzz about React because this is not something which blows your mind and if you are seeing this for the first, it's also OK to go "WTAF" here because you have something HTML{ish} inside your JavaScript code. This is neither HTML nor part of Javascript. That is JSX and it needs transpiling. As stated, you go "WTF" over this (well, at least I did) because it might go against the "separation of concerns" thinking you have been holding onto. I have been there and done this. I stopped looking at React at that point and convinced myself that it's not something that would scale in terms of maintenance.

Do you have the same reaction? If so, let me tell something which I wish someone would told me when I had this reaction and I think deserves to be emphasized over and over again. The above "Hello World" example is not the place where you should start learning React. It should be "Thinking in React" documentation that you should start with. It's such a good documentation explaining what the mindset you should be in while you are working with React. However, you might be dealing with another challenge in our mind now while this direction can put you into a different situation:

This kind of has a point. I believe the amount of boilerplate code which you write with React to get your application running is higher than any of its opponents. However, small applications is probably not going to highlight the value of React that well. You see the value it brings when you think in terms of the whole application. Let me tell you a few things about this.

To me, most valuable thing about an evolvable application (doesn't have to be a web application, any sort of it) is to be able to reason about its behaviour at any point during its evolution. Whenever, you see some unexpected behaviour, you should able to say "this is happening because this part in my application is doing something wrong". This is also valid for expected behaviours as well as you will be contributing to its evaluation by adding new features to it and you should know exactly where you need to apply the changes to add those features.

The other point I want to make here is based on amazing Brian Holt's talk at Dev Day: "React: Learn Once Write Anywhere". If my memory is not failing me, he stated a very important fact about a React application: its constant complexity level. I accept that a typical React application starts complex but that complexity mostly stays the same during the entire evolution of the web application unless you go outside the boundaries of the structure. However, if you go with a simple approach at the begging, your complexity will grow as you grow your web application codebase. I have witnessed this several times and I will tell you that it’s not fun to apply changes after a certain point.

If you are struggling with the React getting started process, there is an approach which I see very efficient that will ease your process. You can start working without thinking about the separation of your application into smaller components. With this way, you can write your components as big, fat components. Once you have two or three like that, you will start seeing patterns which will make you think about isolations. That's where you can start drawing mockups like this one. I went this way at the start where I was really fuzzy about React but now, it's a set mindset for me that I start with a mockup.

Final point I want to touch on is about stability and problem solving, I think one of the biggest values of React is its stability and adoption. I can assure you that the most of your Web UI problems have an answer in React and it is also highly likely that someone has already written up a blog post, put a sample somewhere or answered a Stackoverflow question on that. Also, Facebook and some other big companies rely on React. So, the evolution of React is a fairly safe progress in this fast evolving JavaScript ecosystem.

Conclusion

In this post, I just wanted cover the React part of the story and I should admit that it's not much. However, my aim here is to convince you to give React a chance. I can understand that you may have questions about how to handle the data at this stage (e.g. how to react to the changes that happens behind the background, etc.). This is probably a good time for you to look at what Flux application architecture is all about and have a go with one of the state management libraries like Redux. This is the exact topic that I will touch on the second part of this blog post series, which will also highlight the practical strength of React along with Redux.

Further Resources

Tags