Little-known, useful, charming and beautiful algorithms - part 1

Please find the updated version of this post here: https://piotr.westfalewicz.com/blog/2016/02/little-known-useful-charming-and-beautiful-algorithms---part-1/

Image source: https://goo.gl/mJjN4S

Warning: this post won't be about "boring" or "typical" algorithms from Computer Science which we all have learned on studies (like quick sort, merge sort, xxx sort, A*, FFT). Instead, this will be about other little-known, especially USEFUL algorithms, which people working as professional developers should know or heard of.

Little-known

ID generation problems are usually overlooked. Database ID's I mean. Ask someone to name ID "types". Well, GUID, newsequentialid(), int/long (increased one by one, as in IDENTITY), NHibernate's Hi/Lo will be the answers. The first will make your SQL Server cry, when used as clustering key. Two next requires SQL database as a part of the generation process. That limits the performance as well as can be problematic in occasionally connected client scenarios. The last one is quite interesting - solves the problems related to database usage in the generation process, doesn't have the problem as the GUID has... however, it's not quite suitable for distributed (cloud) environment. Many servers can generate the same ID's, if they begin from the same initial ID.

To address those and other issues, listen guys from Twitter:

As we at Twitter move away from Mysql towards Cassandra, we've needed a new way to generate id numbers. There is no sequential id generation facility in Cassandra, nor should there be.

they designed a system for generating ID's with following requirements (source):

Performance
 - minimum 10k ids per second per process
 - response rate 2ms (plus network latency)

Uncoordinated
   For high availability within and across data centers, machines generating ids should not have to coordinate with each other.

(Roughly) Time Ordered
   We have a number of API resources that assume an ordering (they let you look things up "since this id").
   However, as a result of a large number of asynchronous operations, we already don't guarantee in-order delivery.
   We can guarantee, however, that the id numbers will be k-sorted (references: http://portal.acm.org/citation.cfm?id=70413.70419 and http://portal.acm.org/citation.cfm?id=110778.110783) within a reasonable bound (we're promising 1s, but shooting for 10's of ms).

Directly Sortable
   The ids should be sortable without loading the full objects that the represent. This sorting should be the above ordering.

Compact
   There are many otherwise reasonable solutions to this problem that require 128bit numbers. For various reasons, we need to keep our ids under 64bits.

Highly Available
   The id generation scheme should be at least as available as our related services (like our storage services).

Note this is a system for generating ID's. However, this system can be easily detached from the whole infrastructure and put into a nice algorithm or a program for generating uncoordinated, time ordered, k-sortable, compact IDs. In fact, there is already a .NET project for that: IdGen. I recommend you looking into the internals of the generation algorithm because the idea is very simple and sleek. I can't stress enough the usefulness of this algorithm in distributed systems. A must have!

Concealed algorithm, which .NET developers use every day

Whenever you use TCP protocol (by WebClient or HttpWebRequest), this algorithm kicks in. Normally it's good and useful (source):

   Nagle's document, Congestion Control in IP/TCP Internetworks (RFC 896) describes what he called the "small packet problem", where an application repeatedly emits data in small chunks, frequently only 1 byte in size. Since TCP packets have a 40 byte header (20 bytes for TCP, 20 bytes for IPv4), this results in a 41 byte packet for 1 byte of useful information, a huge overhead. (...)
   Nagle's algorithm works by combining a number of small outgoing messages, and sending them all at once. Specifically, as long as there is a sent packet for which the sender has received no acknowledgment, the sender should keep buffering its output until it has a full packet's worth of output, so that output can be sent all at once.

However, sometimes it's not and it is good to know that such a thing even exists. Here is a performance test, which showed speed increase in Azure Queue PUT operations from ~210ms to ~28ms: Nagle’s Algorithm is Not Friendly towards Small Requests

Little algorithms

There are two "short" algorithms which I personally like. They aren't a big deal and by googling the problem, you probably will use one.

• Box–Muller transform which you probably want to use, when you want to turn standard C# Random class to Gaussian distributed random generator. C# code here: Random Gaussian Variables
• Fisher–Yates shuffle which is a solution for randomly shuffling an array. C# code here: Best way to randomize an array with .NET

What is your favorite algorithm/solution?

In part two there will be one, special "algorithm".

Checking "Star Wars - The Force Awakens" tickets availability with Azure WebJobs, scriptcs and SendGrid

This user story is quite simple: there is a guy (me) who likes Star Wars. This guy wants to buy the best tickets available in an IMAX Cinema. The premiere was not so long ago, so a day after the showtimes are updated, the best seats are booked. This guy (also me) is quite lazy, so he doesn't like to check the showtimes manually.

Hm... let's do it like pro developers using cutting-edge technologies!

How the booking system works?

There is this whole UI for selecting seats and so on, however there is one interesting request which I can use to check showtimes. It look like this:

POST http://www.cinema-city.pl/scheduleInfoRows HTTP/1.1
Host: www.cinema-city.pl
Connection: keep-alive
Content-Length: 52
Accept: */*
Origin: http://www.cinema-city.pl
X-Requested-With: XMLHttpRequest
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/47.0.2526.106 Safari/537.36
Content-Type: application/x-www-form-urlencoded
Referer: http://www.cinema-city.pl/imax
Accept-Encoding: gzip, deflate
Accept-Language: en-US,en;q=0.8
Cookie: bla bla bla

locationId=1010304&date=09%2F01%2F2016&venueTypeId=2

When there is a picture show on that date it returns an HTML table with links for booking, otherwise an empty HTML table.

scriptcs to make the job done

I've written a simple scriptcs which will make a POST with appropriate headers and check if a HTML link opening tag is in the response. If that's the case, I send an email using fresh, free SendGrid account.

using System.Net;
using System.Net.Mail;
using SendGrid;

public void SendMeEmail()
{
 var myMail = new SendGridMessage();
 myMail.From = new MailAddress("Yoda@gmail.com");
 myMail.AddTo("me@gmail.com");
 myMail.Subject = "StarWars tickets are available!!";
 myMail.Text = "Go to CinemaCity IMAX to book them.";

 var credentials = new NetworkCredential("user-sendgrid@azure.com", "sendgrid-password");
 var transportWeb = new Web(credentials);
 transportWeb.DeliverAsync(myMail).Wait();
}

var httpClient = new HttpClient();
httpClient.DefaultRequestHeaders.Add("Host", "www.cinema-city.pl");
httpClient.DefaultRequestHeaders.Add("X-Requested-With", "XMLHttpRequest");
httpClient.DefaultRequestHeaders.Add("Referer", "http://www.cinema-city.pl/imax");
httpClient.DefaultRequestHeaders.Add("User-Agent", "Mozilla/5.0 (Windows NT 10.0; WOW64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/47.0.2526.106 Safari/537.36");

var content = new StringContent(@"locationId=1010304&date=09%2F01%2F2016&venueTypeId=2", Encoding.UTF8, @"application/x-www-form-urlencoded");
var response = httpClient.PostAsync("http://www.cinema-city.pl/scheduleInfoRows", content).Result;
var responseAsString = response.Content.ReadAsStringAsync().Result;

var isMovieAvailable = responseAsString.Contains("<a");
if(isMovieAvailable)
{
 Console.WriteLine("Movie is available, sending email");
 SendMeEmail();
 Console.WriteLine("Movie is available, email sent");
}
else
{
 Console.WriteLine("Movie is not available.");
}

Evironment setup is quite simple:

• create a new SendGrid account
• download scriptcs as zip (link) and unzip it to a folder StarWarsCheck
• save the code as checkmovie.csx to folder StarWarsCheck
• update checkmovie.csx with your SendGrid credentials
• add reference to Sendgrid dll's by invoking scriptcs.exe -Install Sendgrid
• now you can run the script locally. In a console write: scriptcs.exe checkmovie.csx

If you are interested on other options how one can prepare a standalone, portable scriptcs scripts - check my question on StackOverflow: How to run scriptcs without installation? Make portable/standalone scriptcs (csx)

Note: of course, once showtimes are updated, I will get email every hour. But that's good, isn't it? There is a chance I won't miss it.

Create an Azure WebJob to run scriptcs file every hour

You can use Azure WebJobs by simply uploading a .zip file with the job and configuring how it should be scheduled in Azure. The job entry point is based on naming convention. According to the documentation, the recommended script file to have in your job directory is: run.cmd. Therefore, my run.cmd look like this:

call scriptcs.exe checkmovie.csx

Next, pack whole StarWarsCheck folder as a zip file and upload it as Azure WebJob. Instructions are here.

Effects

It started with...

But then...

The email arrived without problems:

However, most importantly, I've booked the best seats for my friends & me:

Summary

It was fun, easy and profitable to play with Azure WebJobs and scriptcs. I liked the scriptcs sleekness and Azure WebJobs simplicity. For sure I'll use them for something else in the future.

Merging multiple git repositories into one and purging sensitive data

Git is a very powerful, distributed version control system. It's based on simple concept - directed graph without cycles (a tree) pointing four types of objects in it's database. I love git and it's brilliant design. Therefore, when I saw how misused it was in a company which I joined, I've had to fix it.

The state before

Due to multiple factors, there were around 4 repositories, which had to be cloned in one directory. Each repository was using or was being used by another repository. In other words, projects in VisualStudio were having dependencies on another projects, or worse - on compiled dlls in another repositories. Therefore, sometimes, one change required 4 commits (including projects rebuild and adding compiled dlls to the commit). During one month, around 2 man-days were lost for checking in/out changes from multiple repositories and for false (or true...) alarms that somebody forgot to check in/out something from the repositories. What's more, this was only for one branch - master - because only one existed back then. However, in future, to support multiple environments or development on fine-grained features/stories, multiply those problems by the number of branches and the number of new developers, at least. As always in IT, there wasn't much time, so setting up internal company NuGet Server wasn't the best thing to do. It isn't that it takes a long time to setup NuGet Server, but training all developers requires a great amount of time. Instead, I've decided to create one repository.
The state before was like this:

\Repo1
  \src
    \project1
      project1.csproj with dll reference to project 2
    \ExternalDlls
      project2.dll
    Solution1.sln
\Repo2
  \project2
    project2.csproj with project reference to project 3
  \project3
    project3.csproj with project reference to project 4
  Solution2.sln
\Repo3
  \project4
    project4.csproj
  Solution3.sln

One to rule them all

In those 4 repositories passwords or MachineKey's to production environment were stored in plain text. Therefore I've decided to create a new repository. Side note: remember, passwords pushed to git repository always there will be, Yoda said. Therefore the new repository will have entirely rewritten history (removed passwords). Naturally, all branches (masters in this case) from all repositories with their's history must be included in the new repository. It will look like this:

new repo HEAD
|
M
|  \
M    \
| \    \
x' \     \
|   y'    z'
x'  |     |
|   y'    z'
x'  |     |
.   y'    z'
.   .     .
.   .     .
    .     .
 
Legend:
x' - commits from repository 1 with removed sensitive data
y' - commits from repository 2 with removed sensitive data
z' - commits from repository 3 with removed sensitive data
M  - merges in the new repository
new repo HEAD - the brand new, future repo HEAD (master)

Migration scripts

Migration must be done in "atomic" way, well at least it must be seen from developers perspective as atomic operation - they commit to the old repos and from some point in time they commit to the new repo (note: stashes will have to be discarded). Therefore, I've decided to run the migration during the weekend, when repositories are inactive. However, I don't like to work during weekends, so I wrote a script or two to automate the majority of the work. The git filter-branch command which I will be using is painfully slow, so additionally I've used powerful Amazon EC2 instance to make things a little faster.

Step 1 - fetch all repos and form a nice repository structure

Look that in the state before not all repos have had the code in src folder. To fix it, I'll use git filter-branch command to entirely rewrite the history. Each commit in history, blame etc. will look like it was committed to the right, src folder. Additionally, I've seen that someone was committing Packages folder to the git (possibly due to poor .gitignore file), so now it's a chance to remove that bloat permanently. Here is the bash script. Save it as mergerepos.sh and run it from git bash console like normal linux script (./mergerepos.sh):

#!/bin/bash 
FinalRepo="main" 
echo $FinalRepo

mkdir $FinalRepo
cd $FinalRepo
git init

touch tmp
git add -A
git commit -m 'merge all repositories'


declare -a reponames=("repo1" "repo2" "repo3")
declare -a repourls=("https://user@bitbucket.org/Company/repo1.git" "https://user@bitbucket.org/Company/repo2.git" "https://user@bitbucket.org/Company/repo3.git")
numberofrepos=${#reponames[@]}

function rewriterepo {
 git checkout $1/master
 git checkout -b "$1master"
 git filter-branch -f --tree-filter 'rm -rf packages
 mkdir "src"
 rm -rf src/packages
 ls -A | grep -v ^[Ss]rc | grep -v \.git | while read filename
 do
 mv "$filename" "src/"
 done' HEAD
}

for (( i=0; i<${numberofrepos}; i++ ));
do
  echo $i " -> " ${reponames[$i]} $(date) "-" ${repourls[$i]} " STARTED"
  git remote add ${reponames[$i]} ${repourls[$i]}
  git fetch ${reponames[$i]}
  rewriterepo ${reponames[$i]}
  git remote rm ${reponames[$i]}
  echo $i " -> " ${reponames[$i]} $(date) "-" ${repourls[$i]} " FINISHED"
done

The script will:

• set up a new repository
• make a dummy commit
• go through the list of given repositories and for each do
• add it as remote, fetch it, checkout it to repoXmaster branch
• clean each commit as follows
• create src folder, remove src/packages folder
• move each file/directory from the root, except of src and git folder to src folder
• remove added remote

So far so good.

Step 2 - merge all branches (repositores)

As I have all repositories in the right structure and in our one "chosen" repository, merging them is just a normal merge operation.

Step 3 - delete sensitive data (passwords etc)

This can be done by painfully slow git filter-branch or... fast and easy to use BFG Repo Cleaner. 1Check the project website, it's self explanatory. 

Step 4 - add a nice, root .gitignore

All my work of removing redundant Packages folder can be destroyed by a single commit. Therefore I've merged all existing .gitignore files and added those rules to well known github/gitignore for VS file.

Further steps

I have now one repository with the right structure and good history. Further steps?

Taking the chance, I've introduced one solution for all projects in the new VS 2015, migrated to Automatic NuGet package restore (check all those scripts - one also fixes project hint paths), changed all dll references to project references and upgraded projects to the new VS version. This is how I've done the csproj update:

$listOfBadStuff = @(
 "<Project DefaultTargets=""Build"" xmlns=""http://schemas.microsoft.com/developer/msbuild/2003"" ToolsVersion=""4.0"">",
 "<OldToolsVersion>[0-9]\.0</OldToolsVersion>",
 "<Project ToolsVersion=""12.0"""
)
$listOfGoodStuff = @(
 "<Project DefaultTargets=""Build"" xmlns=""http://schemas.microsoft.com/developer/msbuild/2003"" ToolsVersion=""14.0"">",
 "<OldToolsVersion>14.0</OldToolsVersion>",
 "<Project ToolsVersion=""14.0"""
)

ls -Recurse -include *.csproj, *.sln, *.fsproj, *.vbproj, *.wixproj |
  foreach {
    $content = cat $_.FullName | Out-String
    $origContent = $content
 For ($i=0; $i -lt $listOfBadStuff.Length; $i++) {
  $content = $content -replace $listOfBadStuff[$i], $listOfGoodStuff[$i]
    }
    if ($origContent -ne $content)
    { 
        $content | out-file -encoding "UTF8" $_.FullName
        write-host messed with $_.Name
    }      
}

Summary

It was relatively easy to get from nightmare to a reasonable repository environment. Those one or two days of merging repositories will pay off very quickly. Not mentioning the removal of sensitive data from the repository - this can be priceless.

Presentation recommendation - LinkedIn's Active/Active Evolution

I like to watch a IT related presentations. Those give you a lazy way of grasping the idea of "what's up" in particular subject. It's grasping because by watching you won't learn actual skills, but you will know what exists, where are the dragons hidden and where to look deeper. What's more, if you are bored, you can always skip some parts or go to next presentation - which is extremely important in our fast-paced business. And most importantly - always learn from the bests.

Today I recommend you following presentation: LinkedIn's Active/Active Evolution - Erran Berger
Why? Active/active architecture is probably one of the most popular solutions for scaling existing monolith. Check out where you can expect problems and how LinkedIn team solved them.

Cassandra - problems, issues, worries

Normally I "live" in .NET environment. That is, my work is usually related to .NET environment and most popular libraries associated with it. Some time ago, I started to work with Cassandra. Google it. Popular. Superb. Advanced. Supreme. Design for speed and resilience. Used by some big players. That sort of impression you will get. Therefore, just few days after meeting Cassandra I've had an eye opener. From my perspective, when I switched from .NET and start to develop solution based on Cassandra, it hit me. Cassandra is very rare specie. Developers who knows it - are more like extinct developers. Therefore online materials or help which you can get is way more limited than it is for .NET.

The most popular website for asking for help or advice is StackOverflow, for programmers. Just to give you a feeling, how .NET tag is more popular than Cassandra tag look at this:

What does it mean?

Back then when I was learning about Cassandra I've read every question tagged with Cassandra tag. I've even been able to answer some of them - it was much easier for me, as a beginner in Cassandra than to answer questions about .NET - where my knowledge and experience is way more broad. This is mostly because for answering .NET question you have around one minute, before somebody else's answer pops up, while for Cassandra question you have around one day or sometimes even more.

That also means when you have a problem - either with the client or Cassandra node itself - it may be hard to find help. Consider my question on StackOverflow: Cassandra routing key not set due to ArgumentException: Column column_aliases not found

This time I was lucky. I've received an answer quickly and the problem was easily fixable. However, the question was viewed only 73 times during 3 months!

Unfortunately, I have other example, which I will describe some other time... Stay tuned.

Use "Lato Font" in Google Blogger

As you can see in Google Blog Designer, there is no Font Lato to choose:

Happily, you can edit Template HTML and apply that font manually.

• Go to Draft Blogger -> Template -> Edit HTML
• Locate </head> closing tag
• Before that line, add line:
• <link href='https://fonts.googleapis.com/css?family=Lato' rel='stylesheet' type='text/css'/>
• Locate tag <b:skin> and <b:skin> tag. Replace every occurrence of "Arial, " with "Lato, Arial, "

That's pretty much it. However, I noticed that the post became a little less readable than it was before (but it looks a lot more Flat/Material/Cool/Cutting-Edge though). To fix that, I've increased the font size for posts just by one pixel.

• Locate element <Group description="Post Background" selector=".post"> and add following element as a child (change according to the rest of your font rules):
• <Variable name="post.body.font" description="Font" type="font" default="normal normal 14px Lato, Arial, Tahoma, Helvetica, FreeSans, sans-serif" value="normal normal 14px Lato, Arial, Tahoma, Helvetica, FreeSans, sans-serif"/>
• Find .post-body CSS selector and add property font: $(post.body.font);

That's all. Unfortunately, you still won't be able to see font Lato in Google Blog Designer, however the font should be applied on your blog.

Is it the right way of adding custom font to Google Blogger?

After writing my first post ever it made me think... It is really the right way of adding Font Lato or any custom font to Google Blogger? After googling it turns out.. YES! It is: Upload And Use Custom Fonts In-Blogger

PS. After all, I've decided to go with font Roboto, as on My Account Google Page and adjust the style of the blog to mimic that minimalistic design. Hope you like it.

This is it, here I write

I've planned to start blogging for a quite long time. Now, after seeing Microsoft Live Writer going Open Source I've decided to start blogging. Just now. Just like that. Therefore here is my first post ever. I'm planning to publish minimum 1 post per month. Let's see how that will work.