Building Fault-tolerant Software

Creating a software system or an app that can fail-safe or even fault-tolerant is not an easy task, especially for cloud apps or services since they are often platform agnostic and may require network availability.

I often ask myself how to enhance the user experience even in the unexpected user scenarios. Though the answer varies case by case for different systems and scenarios, here are some simple questions I often deliberate on when designing for error handling and fault-tolerance:
 
1. What are the corner use cases the app or system might encounter? Can system handle it?
2. In case of internal or external error occurs, can system automatically recover from the error? Can it prevent the error happens again?
3. If not, can system continue its intentional operations by providing walk-around options for users?
4. If not, can system provide users with possible manual solutions to get rid of the error?
5. If not, can system fail gracefully with proper error message for users?
6. Then, does the error need to be logged or sent for further analysis?

A simple example would be how different JavaScript websites react when the hosting browser has JavaScript support disabled (in Dec, 2014):

1. My Facebook Personal Homepage: Neither shows any content nor error message, but only an app bar:
 

2. My Live.com Homepage: Shows the proper error messages with solution:

3. My Gmail Homepage after logon: Provide user with both proper error messages with solution, and excitingly, an html version mail walk-around:

 

 

It requires extensive software validations to uncover some of software failures, and then careful design for the error handling remedy. But this process will eventually benefit the users, ITs, and developers!
 
 

encodeURI() and encodeURIComponent() in JavaScript.

In JavaScript, we have two utilities for encoding an URI:

encodeURI():
1) normally for encoding a full URI (given that parameters are properly encoded already)
2) encodes everything except [a-A0-9] with ~!@#$&*()=:/,;?+'

encodeURIComponent():
1) normally for encoding URI's "component" such as parameters' value in the query part.
2) encodes everything except [a-A0-9] with ~!*()'
 
1. Reserved characters in URI: http://en.wikipedia.org/wiki/Percent-encoding#Types_of_URI_characters
2. Nice article on the comparison of the two functions: http://xkr.us/articles/javascript/encode-compare/
 

Retrieving Directory Name or File Name using Powershell

# File should exist> (Get-Item 'C:\Windows\test.txt').DirectoryName
C:\Windows

> (Get-Item 'C:\Windows\test.txt').Name
test.txt

# File does not have to exist> Split-Path 'C:\Windows\test.txt'
C:\Windows

> Split-Path -Parent 'C:\Windows\test.txt'
C:\Windows

> Split-Path -Leaf 'C:\Windows\test.txt'
test.txt

Windows batch script to lookup a value or key in Registry

Find... method in RegEdit is a little tedious to use on Windows platform cauze it is looking for one instance of a search key at a time (you have to hit "Next" to get the next search result).

We could instead do the global search by the following script (regrep.bat) in command line:

@echo off
for %%a in (HKLM HKCU HKCR HKU HKCC) do (
  echo [Regrep] Looking for reg value under path %%a
  reg query %%a /f %1 /s
)

 
which could find the search term under all path recursively.
 
e.g.
 
Find a single term:
  regrep system32
 
Find a word with space
  regrep "internet explorer"

Shining || Responsive?

Google recently previews its new Google Maps. The new interface looks more comprehensive and stunning:

However, the trade-offs are speed and memory comsumption.
 
At the time of writing this post, I still favor the classic Google Map which offers a much simpler UI but more responsive experience.

New Google Map 

Image Name                     PID Session Name        Session#    Mem Usage
========================= ======== ================ =========== ============
iexplore.exe                  1804 Console                    1    461,972 K 
firefox.exe                   4800 Console                    1    645,508 K

Classic Google Map

Image Name                     PID Session Name        Session#    Mem Usage
========================= ======== ================ =========== ============
iexplore.exe                  4148 Console                    1    160,116 K
firefox.exe                   1204 Console                    1    221,092 K

Software design needs to strike a balance between performance and functionality and UI in order to provide great user experience for customers. So,

1. Do you really prefer the Shining map to the Responsive one, when you are running out of time for catching a flight, but only eager to know the fastest route to the airport?
2. User-oriented is good, but not glod-plating

Evolution of a Programmer :)

http://www.ariel.com.au/jokes/The_Evolution_of_a_Programmer.html

Subset, Combination and Permutation (Recursion)

#define MAX_K 100 

void subset_rec(
    const char *cont, 
    const size_t start, 
    const size_t n,
    char *res, 
    const size_t last)  
{
    size_t i;

    // print (res, last);
    for (i = start; i < n; i++) {
        res[last] = cont[i];
        subset_rec(cont, i+1, n, res, last+1);
    }
}

void subset(const char *content, const size_t n) {
    char *result;
    result = (char*)malloc(MAX_K * sizeof(char));
    subset_rec(content, 0, n, result, 0);
    free(result);
    result = NULL;
}

void comb_rec(
    const char *cont,       // pointer to combination's content
    const size_t start,     // starting index of the content
    const size_t n,         // n of C(n,k)
    const size_t k,         // k of C(n,k)
    char *res,              // pointer to one combination generated so far
    const size_t last)      // length of the result
{
    size_t i;

    if (k == 0) {
        // print (res, last);
    } else {
        for (i = start; i < n; i++) {
            res[last] = cont[i];
            comb_rec(cont, i+1, n, k-1, res, last+1);
        }
    }
}

void combination(const char *content, const size_t n, const size_t k) 
{
    char *result;
    if (k > n || k == 0 || n == 0)  return;
    result = (char*)malloc(MAX_K * sizeof(char));
    comb_rec(content, 0, n, k, result, 0);
    free(result);
    result = NULL;
}

void perm_rec(
    char *cont, 
    const size_t n, 
    const size_t k, 
    char *res, 
    const size_t last)  
{
    size_t i;
    char t;

    if (k == 0) {
        // print (res, last);
    } else {
        for (i = 0; i < n; i++) {
            t = cont[i];
            res[last] = t;                          // A B C D
            memmove(cont+i, cont+i+1, n-i-1);       // A C D
            perm_rec(cont, n-1, k-1, res, last+1); 
            memmove(cont+i+1, cont+i, n-i-1);       // A A C D
            cont[i] = t;                            // A B C D
        }
    }
}

void permutation(const char *content, const size_t n, const size_t k) 
{
    char *result;
    if (k > n || k == 0 || n == 0)  return;
    result = (char*)malloc(MAX_K * sizeof(char));
    perm_rec((char*)content, n, k, result, 0);
    free(result);
    result = NULL;
} 

For the permutation of set that contains duplicates, the solution can be found here:
https://oj.leetcode.com/discuss/16264/a-simple-recursion-solution-c

Tail Call

// Non tail-call optimization
// Because the last statement is n+sum1() in the function call, 

// which triggers the saving of sum1()'s current context, then do the next call
int sum1(int n) {
 return (n <= 0) ? 0 : n+sum1(n-1);
}

// We can skip this step by passing the current sum as an argument in the function
int sum2(int n, int cur) {
 return (n <= 0) ? cur : sum2(n-1, cur+n);
}

The processor time it takes to execute these two functions are (N is the # of repetitions):

   N      sum1      sum2
 1000     1123      1061
10000    13213     12839

Ref.: http://c2.com/cgi/wiki?TailCallOptimization

Thoughts on Sorting

I compared the basic in-memory sorting algorithms against the standard sorting functions in C/C++ (qsort/sort) on my x86 machine today. Although the results were preliminary, it did confirm some ideas in sorting techniques:

       Sort Type    Sorted       Nearly Sorted              Random            Reversed           All Equal
       =========    ------       -------------              ------            --------           ---------
  Selection Sort    29.1090             29.2660             33.7420             28.9850             29.0480
  Insertion Sort    0.0000              0.0150             21.3410              0.0000              0.0000
      Merge Sort    0.0310              0.0160              0.0310              0.0310              0.0310
        Qck Sort    57.6120              1.5760              0.0460             57.7990             18.6420
   Rand Qck Sort    0.0150              0.0160              0.0150              0.0310             18.5490
  R.Qck+Ins Sort    0.0000              0.0160              0.0310              0.0000              0.0150
     C lib qsort    0.0000              0.0160              0.0160              0.0000              0.0000
    C++ lib sort    0.0000              0.0000              0.0150              0.0000              0.0160

• 100K integers are used to perform the test and the CPU time is recorded
• The 1st column lists the sorting methods.
• The 1st row is the arrangement of integers in the test array: already sorted, almost sorted (99.99% sorted), unsorted (random order), reversely sorted and all equal.

The comparison shows that:

1. The qsort/sort in standard library outperforms other user defined sorting functions in many cases. So use them when in doubt;
2. Insertion sort works fine if the input data is sorted or "mostly" sorted;
3. Merge sort performs nearly same under all cases, so does selection sort; but the former one is O(n*lgn) in time with O(n) in space;
4. Not randomized quick sort works OK only if the input data is in random order; it performs badly O(n^2) when data is sorted or nearly sorted (beware of the deep recursion! set the stack size accordingly); 
5. Quick sort works faster when partitioned from two sides, optimized by randomization and combined with insertion sort (Programming Pearls, Sorting);
6. Choose the "right" sorting strategy based on the data size, data order, memory/time req., ...

Test on gcc 4.6.2

Notes on memset

1. memset

  void * memset ( void *pMemoryBlock, int byte, size_t numOfByte );

2. Typical using senarios

• Bytewise memory initialization
• Zero a block of memory
• Zero a POD struct

3. Test

#include<vector>
#include<string>
#include<algorithm>
#include<cstring>

using namespace std;

struct C {
 char a;
 short *b;
 int c[10];
};

struct CPP {
 string a;
 CPP& operator=(const CPP &r);
};

CPP& CPP::operator=(const CPP &r) {
 if (this != &r) {
  (*this).a = r.a;
 }
 return *this;
}

char achar[3];
int aint[3];

C s;
C as[3];

CPP c;
CPP ac[3];

int main (){
 // 1. Initialize a block of memory using a given byte
 memset(achar, 'a', 3);
 
 // 2. Quickly zero a block of memory
 memset(achar, 0, 3);
 memset(achar, 0, sizeof achar);
 
 memset(aint, 0, 3 * sizeof(int));
 memset(aint, 0, sizeof aint);
 
 memset(as, 0, 3 * sizeof as[0]); 
 memset(as, 0, 3 * sizeof (struct C));
 
 // 3. Reset POD struct
 memset(&s, 0, sizeof(struct C));
 
 // Caution 1. memset works byte by byte only
 memset(aint, 1, 3 * sizeof(int)); // aint : 16843009, 16843009, 16843009
 
 // Caution 2. Be careful with pointer in struct
 s.b = new short;
 memset(&s, 0, sizeof s); // address of b : 0
 
 // Caution 3. POD only
 //memset(&c, 0, sizeof(CPP)); // crash!!!
 
 // Either define a reseting member function, or
 // use fill() and '=' overriding
 c.a = "N/A";
 fill(ac, ac+3, c);  // ac : "N/A", "N/A", "N/A"
 
 return 0;
}

 (code test on g++ 4.6.2)

Netbeans "Cannot locate java installation in specified jdkhome..."

If you change the jdk's dir path after Netbeans installation, the Netbeans will complains it cannot find the original jdk's path and ask if you'd like to use "default" jdk in a message box each time you start the program.

To disable the warning message box, just change the default jdk path to the new one Netbeans at "<netbeans_dir>/etc/netbeans.conf":

netbeans_jdkhome="E:\Java\jdk1.6"

Flashing Screen followed by Windows Hang or Crash

I switched to Windows 7 from XP two years ago and have never experienced one system crashing since then, but until recently I began to be haunted by a Windows 7 system crash, or precisely, a crash caused by the NVidia video card driver.

My Dell T3500 had its original video card replaced with NVidia Quadro NVS 295 not too long ago. Unluckily, I have never got a change to enjoy the performance that would have come with this video card. What I have experienced on the contrary has been continuous system hanging, then crashing, or even (at times) BOSD since the replacement!

Symptom: Initially, the screen suddenly becomes flashing (glowing colorful dots and lines) with blurring resolution for no reason (for 3~60 seconds); then the whole screen goes frozen (for 20 ~ 60 seconds); finally it is blacked out forever, but the CPU and power indicators are still on.

Attempt: 1. I have checked the event viewer each time it crashes but found no clue. And I also attempted to reinstall the video card driver using Windows device manager which still did not help at all;

2. Installed the Windows Debugger (link) and examined the system dump file at C:\Windows\MEMORY.DMP, which said:

Defaulted to export symbols for nvlddmkm.sys -
Probably caused by : nvlddmkm.sys ( nvlddmkm+7b73bc )

So the Windows kernel mode driver nvlddmkm.sys file may be the culprit.

The interim solution I have so far is to disable the nView and dual monitor to use a single screen. I have two DPI ports on the video card, and I guess the overhead when using both of the ports of the video card at the same time may cause the issue...

Same with other users experiecing this issue. No official solution found so far...

a. http://en.kioskea.net/faq/6210-handling-nvlddmkm-sys-crash
b. http://voices.yahoo.com/techtips-nvidia-blue-screen-death-nvlddmkmsys-5316783.html
c. http://en.community.dell.com/support-forums/desktop/f/3515/t/19436822.aspx

Ref.: 1. Handling "nvlddmkm.sys" Crash, http://en.kioskea.net/faq/6210-handling-nvlddmkm-sys-crash;
2. How to solve Windows 7 crashes in minutes, http://www.networkworld.com/supp/2011/041811-windows-7-crashes.html?page=1;

Using `awk` to Convert CSV Format Data

The awk utility provides a handy way to extract and transform data.

In many application scenarios, we wish to quickly convert a form of tabular data to another tabular form that 1) is separated using a different character, 2) contains a subset of all the fields, or 3) contains a reordered set of fields. The awk utility can be very helpful in these situations by calling only its print command.

1.       To CSV

For example, the table1.txt contains data in tabular form of:

1    a1   b1

2    a2   b2

3    a3   b3

4    a4   b4

And the command below:

$ awk '{print $3","$1;}' table1.txt

will extract the 3rd and the 1st fields of table1.txt which are separated by tabs (or spaces), and generate the results in the comma separated format:

b1,1

b2,2

b3,3

b4,4

2.       From CSV

Or you can also specify the separator in the file by the `-F` argument. For example, the table2.txt contains comma separated data of:

1,a1,b1

2,a2,b2

3,a3,b3

4,a4,b4

And the command of:

$ awk -F, '{print $NF"\t"$2"\t"$1;}' table2.txt

states that the separator of the fields will be `,`. And it will convert the fields in table2.txt into the tab separated form (NF means the number of last field):

b1 a1 1

b2 a2 2

b3 a3 3

b4 a4 4

Ref.: http://www.grymoire.com/Unix/Awk.html

Notes on Gson (when converting a Json string to a Java Object)

Google's Gson library provides a handy way to convert Java Class from/to Json strings using fromJson() and toJson() function.

When converting a Json string to Java object, it is important that the fields' names in the Java Class must be exactly the same as the keys' names in the Json String. The visibility of the fields' name does not matter. E.g.:

  String json = "{'key1':'1', 'key2':2}";
  class Object {
   public String key1;
   private int key2;
  }
  Object objs = new Gson().fromJson(json, Object.class);

Otherwise, the null values will returned for each field.

Identify Functions Definition within a C Source File

1. Use the ctags tools, on a console, typing in "ctags -x --c-kinds=f " with the file name(s) (e.g. "flex.c"):

ctags -x --c-kinds=f flex.c

will generate the list of C functions defined in "flex.c" file:

FlexParser       function   2228 flex.c           extern parserDefinition* FlexParser (void)
addContext       function    786 flex.c           static void addContext (tokenInfo* const parent, const tokenInfo* const child)
addToScope       function    796 flex.c           static void addToScope (tokenInfo* const token, vString* const extra)
buildFlexKeywordHash function    207 flex.c           static void buildFlexKeywordHash (void)
copyToken        function    705 flex.c           static void copyToken (tokenInfo *const dest, tokenInfo *const src)
...

Ref.: http://ctags.sourceforge.net/ctags.html

MinGW Simple Installation Guide

MinGW is a minimal GNU development environment for MS Windows (http://www.mingw.org/Welcome_to_MinGW_org). On MinGW, MSYS provides a collection of GNU tools, which provides some of the GNU utilities and enables the use of autotools build system (http://www.mingw.org/wiki/MSYS).

Installation:

1. Main program: Install the MinGW from: http://sourceforge.net/projects/mingw/files/
2. Set system variable PATH to include the X:\MinGW\bin; where X is the root drive
3. mingw-get: Install the mingw-get-inst from http://sourceforge.net/projects/mingw/files/Installer/mingw-get-inst/mingw-get-inst-20111118/
4. Open a CMD console on Windows:
  1) gmake, gcc, g++, gdb: Install the make, compiler and debuger
  2) msys: Install the GNU utilities collection tool - msys.bat 
 > mingw-get install gcc g++ gmake gdb msys
 > cd X:\MinGW\msys\1.0\postinstall
 > pi.bat
 > X:\MinGW\msys\1.0\msys.bat

Done!

Simulating a Queue using two Stacks

// Simulating a queue by two stacks, one for enqueue, another for dequeue
#include <iostream>
#include <stack>
#include <queue>

using std::stack;
using std::queue;
using std::cin;
using std::cout;
using std::endl;
using std::boolalpha;

template<class T>
class squeue {
public:
 T& back()
 {
  assert (!empty());
  while (!_s2.empty())
  {
   _s1.push(_s2.top());
   _s2.pop();
  }
  return _s1.top();
 }
 
 T& front()
 {
  assert (!empty());
  while (!_s1.empty())
  {
   _s2.push(_s1.top());
   _s1.pop();
  }
  return _s2.top();
 }

 void push(const T& e) //enqueue
 {
  while (!_s2.empty())
  {
   _s1.push(_s2.top());
   _s2.pop();
  }
  _s1.push(e);
 }

 void pop() //dequeue
 {
  assert (!empty());
  while (!_s1.empty())
  {
   _s2.push(_s1.top());
   _s1.pop();
  }
  _s2.pop();
 }

 size_t size() const
 {
  return _s1.size() + _s2.size();
 }
 
 bool empty() const
 {
  return size() == 0;
 }
private:
 stack<T> _s1, _s2;
};

int main()
{ 
 squeue<int> sq;
 queue<int> q; // the control
 
 // push, back
 for (size_t i=0; i<5; i++)
 {
  sq.push(i); q.push(i);
  cout << sq.back() << " " << q.back() << "\n";
 }
 
 // size
 cout << "\n" << sq.size() << " " << q.size() << "\n\n";
 
 // front, pop
 for (size_t i=0; i<5; i++)
 {
  cout << sq.front() << " " << q.front() << "\n";
  sq.pop(); q.pop();
 }
 
 // empty
 cout << boolalpha << "\n" << sq.empty() << " " << q.empty() << endl;
 
 return 0;
}