Preface

I have been working on Node.js related projects for quite a while, and have built apps with node both for the clients or personal projects, such as LiveHall, CiMonitor, etc. I have promised some one to share my experience on node. Today I’ll begin to work on this. This will be the first blog of the series.

Background

In this blog, I would like to talk about the configuration in node, which is common problem we need to solve in apps.

Problems related to configuration aren’t new, and there have been a dozens of mature solutions, but for Node.js apps, there is still something worth to be discussed.

Perhaps configuration could be treated as a kind of special data. Usually developers prefer to use data language to describe their configurations. Here are some examples:

• .net and Java developer usually uses Xml to describe their configuration
• Ruby developer prefers Yaml as the configuration language
• JavaScript developer tend to use Json

Data languages are convenient, because developers can easily build DSL on it, then they describe the configuration with the DSL. But is the data language the best option available? Is it really suitable to be used in all scnearios?

Before we answer the questions, I would like to say something about the problem we’re facing. There is one common requirement to all kinds of configuration solutions, which is default values and overriding.

For example, as a Web app default, we use port 80; but in development environment, we prefer to use a port number over 1024, 3000 is a popular choice. That means we need to provide 80 as the default value of the port, but we wish to override the value with 3000 in the development environment.

For the languages I mentioned above, except for Yaml, Xml and Json, doesn’t provide native support of inheritance and overriding. It means we need to implement the mechanism by our own. Take Json as example, we might write the configuration in this way:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

{
  "default": {
    "port": 80,
    "serveAssets": true
  },
  "development": {
    "port": 3000,
    "database": "mongodb://localhost/development"
  },
  "test": {
    "database": "mongodb://localhost/test"
  },
  "production": {
    "serveAssets": false,
    "database": "mongodb://ds0123456.mongolab.com:43487/my_sample_app"
  }
}

The previous Json snippet is a typical example of web app configuration; it has a default section to provide the default values for all environments. Three sections for specific environments. To apply it corecctly to our app, we need to load and parse the Json file to get all data first, then load the values of the default section, then override the value with the values from specific environment. In addition, we might wish to have the validation that yields error when the provided environment doesn’t exist.

This solution looks simple and seems to work, but when you try to apply this approach to your app in real life, you need to watch out some pitfalls.

Issue 1: Confidential Values

In the real world, values in configuration sometimes could be sensitive and need to be kept confidential. It could contain the credential to access your database, Or it could contain the key to decrypt the cookies. It may also contain private certificate that identifies and authenticates the app to other services. In these scenarios, you need to protect your configuration in order to avoid big trouble!

To solve the issue, you might think about adding new feature that enable you to to encrypt confidential values or to load it from a different safe source. To achieve it, you might need to add another layer of DSL which add more complexities to your app and make your code harder to debug or to maintain.

Issue 2: Dynamic Data

A solution to first issue, one could store the environment related but sensitive data in the environment variables. The solution is simple and works perfectly, so I highly recommend it. However, to do this means you need the capability to load the value not only from Json directly but also from the environment variables.

Sometimes, such as deploying your app to Heroku/Nojitsu, might give rise that make the case trickier. After deployed the app to Heroku/Nojitsu, the default values are provided in Json directly, and some of which need to be overrode with the values from environment variables or you need to do it vice versa. These tricky requirements might blow your mind and your code away easily. It causes complicated DSL design and hundreds lines of implementation, but just to load your configuration properly. Obviously it is not a good idea.

Issue 3: Complicated Inheritance Relationship

Scared about above cases? No, then how about complicated inheritance relationship between environments?

In some big and complicated web apps, there might be more than 3 basic environments, such as:

• Development: for developers to develop the app locally
• Test: for developers to run unit or function test locally, such as mocha tests
• Regression: for developers or QAs to run regression tests, such as cucumber tests
• Integration: for QAs or Ops to test the integration with other apps
• Staging: for ops and QAs to test the app in production like environment before it really goes live
• Production: the environment serves your real users
• …

When try to write configurations for these environments, one might find there are only a few differences between environments. To make life easier, to avoid the redundancy, introducing the inheritance between configurations might be a good idea.

As the consequence, the whole configuration becomes environments with complex inheritance relationship. And to support this kind of configuration inheritance, a more complex DSL and hundreds lines of codes are needed.

Some Comments

My assumption above seems to be a little too complex. From some people, it might be the “WORST CASE SCENERIO” and hard to come by. But according to my experience, it is very common when building real web app with node. So if to solve it isn’t too hard, it could be better to consider it seriously and solve it gracefully.

Ruby developer might think they’re lucky because Yaml supports inheritance natively. But confidential data and dynamic data still troubles.

My Solution

After learnt a number of painful lessons, I figured out a simple but working solution: Configuration as Code - describe the configuration with the same language that the business logic is described!

Configuration as code isn’t a new concept, but it is extremely handy when you use it in node applications! Let me explain why and how it works:

To protect the confidential configuration values, one should store them with environment variables, which are only accessible in the specific server.
Then one can load these values from the environment variables as dynamically values.

To do it in a data language such as Xml, Json or Yaml could be hard, but it will become as easy as taking a candy from a baby if it is done in the programming language that application applied/used, such as ruby or javascript.

To the configuration inheritance, OO languages have already provided very handy inheritance mechanism. Why do we need to invent one? Why not just use it? To the value overriding, OO programming tells us that it is called polymorphism. The only difference here from the typical scenario is that we override the values instead of the behaviors. But it isn’t an issue, because the value could be the result of the behavior, right?

Now I assume that everyone got a pretty good idea of what I am saying. If that is the case, then the below code should be able to be understood quite clearly, which is a standard Node.js file written in coffee script:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

process.env.NODE_ENV = process.env.NODE_ENV?.toLowerCase() ? 'development'
class Config
  port: 80
  cookieSecret: '!J@IOH$!BFBEI#KLjfelajf792fjdksi23989HKHD&&#^@'
class Config.development extends Config
  port: 3009
  redis:
    uri: 'redis://localhost:6379'
  mongo:
    uri: 'mongodb://localhost'
class Config.test extends Config.development
class Config.heroku extends Config
  cookieSecret: process.env.COOKIE_SECRET
  redis:
    uri: process.env.REDISCLOUD_URL
  mongo:
    uri: process.env.MONGOLAB_URI
module.exports = new Config[process.env.NODE_ENV]()

See, with the approach, one can describe the configuration easily and clearly in a few lines of code, but with built-in loading dynamical values capability and configuration inheritance and overriding capability.

In fact, with my suggestions, it might work better than expected! Here are the additional free benefits:

1. Only one configuration is needed when the app deployed to the cloud. Because all the host specific configurations are usually provided via the environment variables in Paas.
2. Have some simple and straightforward logic in the configuration, which could be very useful, especially if there is some naming convention in the configuration. But complicated or tricky logic should be strictly avoided, because it is hurts the readability and maintainability.
3. Easy to write tests for configurations, to ensure the values are properly set. It could be very handy when there are complicated inheritance relationships between configurations, or have some simple logic in your configuration.
4. Avoid to instantiate and execute the code that isn’t related to the current environment, which could be helpful to avoid overhead to instantiate unused expensive resources or to avoid errors caused because of incompatibility between environments.
5. Get runtime error when the configuration for the environment doesn’t exist.

Besides of the content, I want to say thank you to my English teacher Marina Sarg, who helped me on this series of blog a lot. Without her, there won’t be this series of blogs. Marina, thank you very much.

I was working on the YouTube video playback feature for LiveHall last night, and have it works successfully on my local devbox, which is running Mac OS X. Then I deployed the code to Heroku, without any regression.

But today morning, when I have the demonstrate the new features, I met server error! It says 1 of the 4 javascripts are missing, so the Jade template failed to render.

This is a very wield issue, then I try the same data on my local dev box once again, and it works perfect! But it does yield error on the production! Then I tried to use heroku toolbelt to run ls command on the production, and I found the there are 4 coffee scripts there.
Then I tried to enforce heroku to redeploy the app by using git push --force, but the issue remains!
Then I even tried to dive into the dependency pacakges connect-assets and snockets, but still found nothing useful.

Same code, same data, but different result! Very odd issue!

After half an hour fighting against the code, I suddenly noticed I the file name is RevealJSPresenter.coffee, whose “S” is capital S! And I reference the file with name #= require ./presenter/RevealJsPresenter, whose ‘s’ is a lowercase ‘s’!

And snockets depends on the OS feature to locate the file. On my local dev environment, I’m using Mac. Although OS X allow user to explicitly format the HFS+ into file name case sensitive mode, but it is case insensitive by default. So snockets can locate the file even the case is wrong.
But once I have deployed to heroku, which, I assume, runs Linux, whose file system is absolutely filename case sensitive. So the snockets won’t be able to locate the file due to the case issue.

To resolve the bug, I renamed my file in RubyMine, then try to commit in terminal.
But when I commit, I met another very interesting issue, that git says there is no file changed, so it refused to commit.
It is still the same issue, due to FS is case insensitive, git cannot detect the renaming.

This problem is more common when coding on Windows, but CI or production runs on Linux. And the very common solution is to pull the code in case sensitive environment, then rename the file and commit it.

But I found another more easier way to do it:

Using git mv in terminal to rename the file, which will enforce git to track the file renaming action.

Or

Most of Git GUIs are able to track file name case changing, so you can try to commit the change with the tool, such as RubyMine or SourceTree.

I usually uses \^\ and \$\ to verify user input, e.g:
I uses following regexp to verify whether a user input is valid gmail email address:

1

^[a-zA-Z_\.]+@gmail.com$

But in fact it is potentially vulnerable!
According to the RegExp document, ^ and $ is matching to line head and line end!
So I might rush into pitfall when user try to fool me with following input:

1

"hacker@gmail.com\n<script>alert('bang!')</script>"

Since there is a \n in the string, so $ won’t really match to the end of the string but actually matched to the \n, then the whole string become a valid input, but actually it isn’t!

To avoid such issue, we should stick to \A and \z, which is literally means the the beginning of the string and end of the string!

CCTray.xml is an RSS-like CI server build status xml feed, which is originally developed for CruiseControl.net.
ThoughtWorks declared it in a standard called “Multiple Project Summary Reporting Standard”, which now have become some kind of unofficial standard of CI server feed that is widely supported by all kind of popular CI servers.

You can find the feed as described below:

• GO - http://servername:8154/go/cctray.xml
• CruiseControl.rb - http://cc.rb.servername:3333/XmlStatusReport.aspx
• CruiseControl - http://cc.java.servername:8080/cctray.xml
• CruiseControl.NET - http://cc.net.servername/XmlStatusReport.aspx
• Jenkins - http://jenkins.servername:8080/cc.xml
• Hudson - http://hudson.servername:8080/cc.xml
• Travis CI - http://travis-ci.org/ownername/repositoryname/cc.xml
• tddium - - http://api.tddium.com/cc/long_uuid_string/cctray.xml

And according to cc_dashboard, there are some exceptions that are not included in the document.

• An additional “Pending” activity
• An additional “Unknown” status. I’ve seen Unknown reported by CruiseControl.rb when project builds are serialized (“Configuration.serialize_builds = true” set in .cruise/site_config.rb) and one build is waiting for another build to finish. I’ve seen Unknown reported by Hudson when a project is disabled.

The following is a patched version of Multiple Project Summary Reporting Standard.

Multiple Project Summary Reporting Standard

Introduction

Various Continuous Integration monitoring / reporting tools exist. Examples are:

• CruiseControl.NET’s CCTray
• CruiseControl Firefox Plugin
• CCMenu for Mac

These tools work by polling Continuous Integration servers for summary information and presenting it appropriately to users.

If a Continuous Integration server can offer a standard summary format, and a reporting tool can consume the same, then we get interoperability between reporting tools and CI Servers.

Description

Summary information will be available as a plain XML string retrievable through an http GET request.

The format of the XML will be as follows:

Summary

A single node, the document root, which contains 0 or many node.

Each may have the following attributes:

Clients that consume this XML should not rely on any optional attribute being present, and should degrade their functionality gracefully.

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

<Projects>
    <Project
        name="SvnTest"
        activity="Sleeping"
        lastBuildStatus="Exception"
        lastBuildLabel="8"
        lastBuildTime="2005-09-28T10:30:34.6362160+01:00"
        nextBuildTime="2005-10-04T14:31:52.4509248+01:00"
        webUrl="http://mrtickle/ccnet/"/>
    <Project
        name="HelloWorld"
        activity="Sleeping"
        lastBuildStatus="Success"
        lastBuildLabel="13"
        lastBuildTime="2005-09-15T17:33:07.6447696+01:00"
        nextBuildTime="2005-10-04T14:31:51.7799600+01:00"
        webUrl="http://mrtickle/ccnet/"/>
</Projects>

Schema

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

<?xml version="1.0" encoding="UTF-8" ?>
<xs:schema elementFormDefault="qualified" xmlns:xs="http://www.w3.org/2001/XMLSchema">
<xs:element name="Projects">
<xs:complexType>
<xs:sequence>
<xs:element name="Project" maxOccurs="unbounded">
<xs:complexType>
<xs:attribute name="name" type="xs:NMTOKEN" use="required" />
<xs:attribute name="activity" use="required">
<xs:simpleType>
<xs:restriction base="xs:NMTOKEN">
<xs:enumeration value="Sleeping" />
<xs:enumeration value="Building" />
<xs:enumeration value="CheckingModifications" />
</xs:restriction>
</xs:simpleType>
</xs:attribute>
<xs:attribute name="lastBuildStatus" use="required">
<xs:simpleType>
<xs:restriction base="xs:NMTOKEN">
<xs:enumeration value="pending"/>
<xs:enumeration value="Exception"/>
<xs:enumeration value="Success"/>
<xs:enumeration value="Failure"/>
<xs:enumeration value="Unknown"/>
</xs:restriction>
</xs:simpleType>
</xs:attribute>
<xs:attribute name="lastBuildLabel" type="xs:NMTOKEN" use="required" />
<xs:attribute name="lastBuildTime" type="xs:dateTime" use="required" />
<xs:attribute name="nextBuildTime" type="xs:dateTime" use="optional" />
<xs:attribute name="webUrl" type="xs:string" use="required" />
</xs:complexType>
</xs:element>
</xs:sequence>
</xs:complexType>
</xs:element>
</xs:schema>

JSONView is a very popular JSON formatter for Chrome, which automatically prettifies the JSON content.

JSONView provide a very sweety feature that allow user to customize the css used to format the JSON. And I love dark theme and the Consolas font so much, so I customized my dark own dark theme for JSONView.

Here is my theme css, and you can copy it to your JSONView theme editor to apply.
Also you can find code on gist: https://gist.github.com/timnew/5167241

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

body {
  white-space: pre;
  font-family: consolas;
  color: white;
  background: black;
}
.property {
  color: orange;
  font-weight: bold;
}
.type-null {
  color: gray;
}
.type-boolean {
  color: orangered;
}
.type-number {
  color: lightblue;
}
.type-string {
  color: lightgreen;
}
a {
  color: dodgerBlue;
}
.callback-function {
  color: gray;
}
.collapser:after {
  content: "-";
}
.collapsed > .collapser:after {
  content: "+";
}
.ellipsis:after {
  content: "...";
}
.collapsible {
  margin-left: 2em;
}
.hoverable {
  padding: 1px 2px 1px 2px;
  border-radius: 3px;
}
.hovered {
  background-color: rgba(255, 255, 255, .3);  
}
.collapser {
  padding-right: 6px;
  padding-left: 6px;
}

Just watched a demo of Google Glass, which provides a close view of the experience of using Google Glass in daily life.
Check out the video here:
http://youtu.be/V6Tsrg_EQMw

After watching the video, I found glass behaves a little bit different to my previously understanding, it is could be a disadvantage of Google Glass, and will hurt the experience a lot!

Current design of the display on the Glass is to project the digital image on your right eye from a very close distance, which works like you have a transparent display near you right eye.
Since the display it so close to you eye, so the digital image will fall out of focus when you are looking around. When you really want to read something from the Glass, you need to ask your eye to focus on the image, on that time, the world around falls out of your focus!

According to the video, what Google is purchasing is a technology that can interact with user without any distraction, reads, bring the user out of the world. In this point of view, Google Glass is huge improvement comparing to classic digital devices, but is still not perfect!

From the distraction view, this little disadvantage isn’t really hurt the experience of Google Glass, if you feel happy that moving your eyeball on the top right of your view very often. But form enhanced reality point of view, it is a breaking blocker!

The most basic requirement of Enhanced Reality is to overlap the digital image contains descriptive information on the optical view of real world. But for Google Glass, it doesn’t provide a way for people to see the digital view and real world, but it is not simultaneously! Because you cannot see the digital view and surrounding world clearly simultaneously, then it is impossible for Google Glass to overlap the digital image over the optical image.

That’s what I means that Google Glass isn’t really an Enhanced Reality Device as a lot of people imagined and expected!

Here are 2 images that explain the idea:

View when you look around
The view around is clear, but the map is blur

View when you read Glass
The map become clear, but the view around is blur

To solve this problem, it requires device to detect the focus point of human eye, then adjust the image accordingly in real time. But still now, we don’t have mature technology that can detect the eye focus point and compact enough to built into a wearable device.

But any way, I still believe that Google Glass is an exciting milestone of purchasing real Enhanced Reality technology in human history! It must evolve and incubate a lot of future technologies!

Javascript is famous for its lack of preciseness, so it always surprises and make joke with the developers by breaking the common sense or instinct.

Javascript doesn’t provide integer type, but in daily life, integer sometimes is necessary, then how can we convert a trim a float number into integer in Javascript?
Some very common answers might be Math.floor, Math.round or even parseInt. But besides calling Math functions, is there any other answer?

The answer is bitwise operations. Amazing? Yes. Because bitwise operations are usually only applied to integers, so Javascript will try to convert the number into "integer" internally when a bitwise operation is applied, even it is still represented in type of number

Suppose value = 3.1415926, and we want integer is the trimmed value of value, then we can have:

1
2
3
4
5
6
7
8
9
10
11
12

var value = 3.1415926;
var integer = Math.floor(value);
integer = Math.round(value);
integer = parseInt(value);
integer = ~~value; // Bitwise NOT
integer = value | 0; // Bitwise OR
integer = value << 0; // Left Shift
integer = value >> 0; // Sign-propagating Right Shift
integer = value >>> 0; // Zero-fill Right Shift

For more detail information about bitwise operation in javascript, please check out the MDN document

All approaches listed before are working, but with different performance. And according to the result from JsPerf, I sort the algorithms by performance from good to bad:

1. integer = ~~value;
2. integer = value >>> 0; and integer = value << 0;
3. integer = Math.floor(value);
4. integer = value >> 0;
5. integer = value | 0;
6. integer = Math.round(value);
7. integer = parseInt(value);

NOTE: The test cases are running in Chrome 24.0.1312.57 on Mac OS X 10.8.2

Application is usually required to run in different environments. To manage the differences between the environments, we usually introduce the concept of Environment Specific Configuration.
In Rails application, by default, Rails have provided 3 different environments, they are the well known, development, test and production.
And we can use the environment variable RAILS_ENV to tell Rails which environment to be loaded, if the RAILS_ENV is not provided, Rails will load the app in development env by default.

This approach is very convenient, so we want to apply it to anywhere. But in node.js, Express doesn’t provide any configuration management. So we need to built the feature by ourselves.

The environment management usually provide the following functionalities:

• Allow us to provide some configuration values as the default, which will be loaded in all environments, usually we call it common.
• Specific configuration will be loaded according to the environment variable, and will override some values in the common if necessary.

Rails uses YAML to hold these configurations, which is concise but powerful enough for this purpose. And YAML provided inheritance mechanism by default, so you can reduce the duplication by using inheritance.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

development: &defaults
  adapter: mysql
  encoding: utf8
  database: sample_app_development
  username: root
test:
  <<: *defaults
  database: sample_app_test
cucumber:
  <<: *defaults
  database: sample_app_cucumber
production:
  <<: *defaults
  database: sample_app_production
  username: sample_app
  password: secret_word
  host: ec2-10-18-1-115.us-west-2.compute.amazonaws.com

In express and node.js, if we follow the same approach, comparing to YAML, we prefer JSON, which is supported natively by Javascript.
But to me, JSON isn’t the best option, there are some disadvantages of JSON:

• JSON Syntax is not concise enough
• Matching the brackets and appending commas to the line end are distractions
• Lack of flexility

As an answer to these issues, I chose coffee-script instead of JSON.
Coffee is concise. And similar to YAML, coffee uses indention to indicate the nested level. And coffee is executable, which provides a lot of flexibilities to the configuration. So we can implement a Domain Specific Language form

To do it, we need to solve 4 problems:

1. Allow dev to declare default configuration.
2. Load specific configuration besides of default one.
3. Specific configuration can overrides the values in the default one.
4. Code is concise, clean and reading-friendly.

Inspired by the YAML solution, I work out my first solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

_ = require('underscore')
config = {}
config['common'] =
  adapter: "mysql"
  encoding: "utf8"
  database: "sample_app_development"
  username: "root"
config['development'] = {}
config['test] =
  database:"sample_app_test"
config['cucumber'] =
  database:"sample_app_cucumber"
config['production'] =
  database:"sample_app_production"
  username:"sample_app"
  password:"secret_word"
  host:"ec2-10-18-1-115.us-west-2.compute.amazonaws.com"
_.extend exports, config.common
specificConfig = config[process.env.NODE_ENV ?'development']
if specificConfig?
  _.extend exports, specificConfig

YAML is data centric language, so its inheritance is more like “mixin” another piece of data. So I uses underscore to help me to mixin the specific configuration over the default one, which overrides the overlapped values.

But if we jump out of the YAML’s box, let us think about the Javascript itself, Javascript is a prototype language, which means it had already provide an overriding mechanism natively. Each object inherits and overrides the value from its prototype.
So I worked out the 2nd solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

config = {}
config['common'] =
  adapter: "mysql"
  encoding: "utf8"
  database: "sample_app_development"
  username: "root"
config['development'] = {}
config['development'].__proto__ = config['common']
config['test] =
  __proto__: config['common']
  database:"sample_app_test"
config['cucumber'] =
  __proto__: config['test']
  database:"sample_app_cucumber"
config['production'] =
  __proto__: config['common']
  database:"sample_app_production"
  username:"sample_app"
  password:"secret_word"
  host:"ec2-10-18-1-115.us-west-2.compute.amazonaws.com"
process.env.NODE_ENV = process.env.NODE_ENV?.toLowerCase() ?'development'
module.exports = config[process.env.NODE_ENV]

This approach works, but looks kind of ugly. Since we’re using coffee, which provides the syntax sugar for class and class inheritance.
So we have the 3rd version:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

process.env.NODE_ENV = process.env.NODE_ENV?.toLowerCase() ? 'development'
class Config
  adapter: "mysql"
  encoding: "utf8"
  database: "sample_app_development"
  username: "root"
class Config.development extends Config
class Config.test extends Config
  database: "sample_app_test"
class Config.cucumber extends Config
  database: "sample_app_cucumber"
class Config.common extends Config
  database: "sample_app_production"
  username: "sample_app"
  password: "secret_word"
  host: "ec2-10-18-1-115.us-west-2.compute.amazonaws.com"
module.exports = new Config[process.env.NODE_ENV]()

Now the code looks clean, and we can improve it a step further if necessary. We can try to separate the configurations into files, and required by the file name:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

# config/config.coffee
configName = process.env.NODE_ENV = process.env.NODE_ENV?.toLowerCase() ? 'development'
SpecificConfig  = requrie("./envs/#{configName}")
module.exports = new SpecificConfig()
# config/envs/commmon.coffee
class Common
  adapter: "mysql"
  encoding: "utf8"
  database: "sample_app_development"
  username: "root"
module.exports = Common
# config/envs/development.coffee
Common = require('./common')
class Development extends Common
module.exports = Development
# config/envs/test.coffee
Common = require('./common')  
class Test extends Common
  database: "sample_app_test"
module.exports = Test
# config/envs/cucumber.coffee
Test = require('./common')
class Cucumber extends Test
  database: "sample_app_cucumber"
module.exports = Cucumber
# config/envs/production.coffee
Common = require('./common')  
class Production extends Common
  database: "sample_app_production"
  username: "sample_app"
  password: "secret_word"
  host: "ec2-10-18-1-115.us-west-2.compute.amazonaws.com"
module.exports = Production

It is a very basic question, but to solve it in a time limited environment, require solid knowledge about algorithm, and could use these knowledges flexibly.
I found the problem of myself is that I know it, but I cannot use it as flexible as my hand.

The problem description:

Calculate the square root of a given number N
The N could be a decimal, such as 6.25 or 0.01
The implementation only allow to use basic algebra operators like +, -, *, /, <, >, etc.
Advanced functions like Math.sqrt is not allowed

As a TDDer, I’m used to write a simple test structure that is gonna used to express the test cases:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

def assert(expected, actual)
  if expected == actual
    puts "Passed"
  else
    puts "Failed"
    p expected
    p actual
  end
end
def sqrt(n)
end

After this, we can begin to write our 1st test case, which is the simplest scenario that I can imagine:
We assume:

1. n must be an integer
2. n must have a integer square root

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

def assert(expected, actual)
  if expected == actual
    puts "Passed"
  else
    puts "Failed"
    p expected
    p actual
  end
end
def sqrt(n)
end
# Start from the easiest case, the integer square root.
assert 3, sqrt(9)

Run the code, if everything goes right, we will get a failed message as expected. Then we gonna introduce our first implementation to fix the failed test case:

With the 2 additional assumptions in 1st test case, we can easily figure out a simple solution: Simply linear search the integers between the root between 1 and n.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

def assert(expected, actual)
  if expected == actual
    puts "Passed"
  else
    puts "Failed"
    p expected
    p actual
  end
end
def sqrt(n)
  (1..n).each do |x|
    return x if x * x == n
  end
end
# Start from the easiest case, the integer square root.
assert 3, sqrt(9)

So far so good. But there are 2 magic integers that related to the sqrt, one is 1 and another is 0.
And it seems our function cannot handle all of them correctly, so I wanna improve my algorithm to enable it deals with special numbers: 0, 1.
So I added 2 test cases, and improved the implementation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

def assert(expected, actual)
  if expected == actual
    puts "Passed"
  else
    puts "Failed"
    p expected
    p actual
  end
end
def sqrt(n)
  return 0 if n == 0
  (1..n).each do |x|
    return x if x * x == n
  end
end
# Start from the easiest case, the integer square root.
assert 3, sqrt(9)
# 2 corner cases
assert 1, sqrt(1)
assert 0, sqrt(0)

Now everything looks good, except the performance.
The time complexity of this algorithm is O(n), which is bad. I expected the algorithm complexity could close to O(1). At least it should be O(log n)

How could we improve the performance?
I had ever thought that it is safe to shrink the range to (1..2/n), but in fact it doesn’t really help to improve the performance of this algorithm, it is still O(n) after the update.
And it causes problems when dealing with the number 1, so I prefers to keep it as is.

So what we did in the sqrt function now it kind of a search, we search the number match the condition between 1 and n.
Obviously that 1..n is a ascending series, and mapping x -> x*x has positive differential coefficient.
So it is possible for use to use variant binary search replace the linear search, which reduce the time complexity from O(n) to O(log n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

def assert(expected, actual)
  if expected == actual
    puts "Passed"
  else
    puts "Failed"
    p expected
    p actual
  end
end
def binary_search(goal, start, stop)
  mid = (stop - start) / 2 + start
  mid_square = mid * mid
  if mid_square == goal
    return mid
  elsif mid_square > goal
    return binary_search(goal, start, mid)
  else
    return binary_search(goal, mid, stop)
  end
end
def sqrt(n)
  return 0 if n == 0
  binary_search(n, 1, n)
end
# Start from the easiest case, the integer square root.
assert 3, sqrt(9)
# 2 corner cases
assert 1, sqrt(1)
assert 0, sqrt(0)
# 2 normal cases
assert 5, sqrt(25)
assert 9, sqrt(81)

After implemented the binary search algorithm, we found a very interesting phenomenon: We didn’t restrict n to integer, and it seems it get some capability to dealing with float number?!
So I tried to add 2 float number test cases:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

def assert(expected, actual)
  if expected == actual
    puts "Passed"
  else
    puts "Failed"
    p expected
    p actual
  end
end
def binary_search(goal, start, stop)
  mid = (stop - start) / 2 + start
  mid_square = mid * mid
  if mid_square == goal
    return mid
  elsif mid_square > goal
    return binary_search(goal, start, mid)
  else
    return binary_search(goal, mid, stop)
  end
end
def sqrt(n)
  return 0 if n == 0
  binary_search(n, 1, n)
end
# Start from the easiest case, the integer square root.
assert 3, sqrt(9)
# 2 corner cases
assert 1, sqrt(1)
assert 0, sqrt(0)
# 2 normal cases
assert 5, sqrt(25)
assert 9, sqrt(81)
# float number
assert 2.5, sqrt(6.25)
assert 1.5, sqrt(2.25)

Amazing, our code works fine!
But I believe it is tricky, since both 2.5 and 1.5 is the number stand on the right center between 2 near-by integers. And it fails dealing with generic float number.
The problem we met is call stack overflow. Binary search algorithm failed to hit the exactly accurate number that we expected.
To solve the problem, we can use a small enough range to replace the accurate equality comparison.
We introduce a const EPSILON to describe the accuracy of the calculation.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

EPSILON = 100 * Float.const_get(:EPSILON)
def assert(expected, actual)
  if (expected - actual) < EPSILON
    puts "Passed"
  else
    puts "Failed"
    p expected
    p actual
  end
end
def binary_search(goal, start, stop)
  mid = (stop - start) / 2 + start
  mid_square = mid * mid
  if (mid_square - goal).abs < EPSILON
    return mid
  elsif mid_square > goal
    return binary_search(goal, start, mid)
  else
    return binary_search(goal, mid, stop)
  end
end
def sqrt(n)
  return 0 if n == 0
  binary_search(n, 1, n)
end
# Start from the easiest case, the integer square root.
assert 3, sqrt(9)
# 2 corner cases
assert 1, sqrt(1)
assert 0, sqrt(0)
# 2 normal cases
assert 5, sqrt(25)
assert 9, sqrt(81)
# float number
assert 2.5, sqrt(6.25)
assert 1.5, sqrt(2.25)
# float numbers not at 2^n
assert 3.3, sqrt(10.89)
assert 7.7, sqrt(59.29)

Now it looks our code can calculate the square root of most of the numbers that larger than 1. But it fails to calculate the square root of number less than 1.
The reason of the failure is because x x < x when x < 1 but x x > 1 when x > 1, which means we should search in different range for the numbers > 1 and numbers < 1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

EPSILON = 100 * Float.const_get(:EPSILON)
def assert(expected, actual)
  if (expected - actual).abs < (EPSILON * 10)
    puts "Passed"
  else
    puts "Failed"
    p expected
    p actual
  end
end
def binary_search(goal, start, stop)
  mid = (stop - start) / 2 + start
  mid_square = mid * mid
  if (mid_square - goal).abs < EPSILON
    return mid
  elsif mid_square > goal
    return binary_search(goal, start, mid)
  else
    return binary_search(goal, mid, stop)
  end
end
def sqrt(n)
  return 0 if n == 0
  if n == 1
    return 1
  elsif n > 1
    return binary_search(n, 1, n)
  else
    return binary_search(n, n, 1)
  end
end
puts "Start from the easiest case, the integer square root."
assert 3, sqrt(9)
puts "2 corner cases"
assert 1, sqrt(1)
assert 0, sqrt(0)
puts "2 normal cases"
assert 5, sqrt(25)
assert 9, sqrt(81)
puts "float number"
assert 2.5, sqrt(6.25)
assert 1.5, sqrt(2.25)
puts "float numbers not at 2^n"
assert 3.3, sqrt(10.89)
assert 7.7, sqrt(59.29)
puts "float number < 1"
assert 0.1, sqrt(0.01)
assert 0.02, sqrt(0.0004)

So now the algorithm is pretty much as what we want, but we still found it raise call stack overflow exception sometimes. And it wastes too much iterations on unnecessary precision.
So I think maybe we can make the algorithm unlimitedly close to O(1) by sacrificing some precision of the result.
So we set up a limit for the maximum iterations that we can take during the calculation. When the limit is reached, we break out the iteration, and return a less accurate number.

It is really useful when calculating the irrational square root, which is has unlimited digits, and there is no accurate solution to it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

EPSILON = 10 * Float.const_get(:EPSILON)
DEPTH_LIMIT = 100
def assert(expected, actual)
  if (expected - actual).abs < (EPSILON * 10)
    puts "Passed"
  else
    puts "Failed"
    p expected
    p actual
  end
end
def binary_search(goal, start, stop, depth)
  mid = (stop - start) / 2 + start
  mid_square = mid * mid
  if (mid_square - goal).abs < EPSILON
    return mid
  else
    return mid if depth >= DEPTH_LIMIT
    if mid_square > goal
      return binary_search(goal, start, mid, depth + 1)
    else
      return binary_search(goal, mid, stop, depth + 1)
    end
  end
end
def sqrt(n)
  return 0 if n == 0
  n = n.to_f
  if n == 1
    return 1
  elsif n > 1
    return binary_search(n, 1, n, 0)
  else
    return binary_search(n, n, 1, 0)
  end
end
puts "Start from the easiest case, the integer square root."
assert 3, sqrt(9)
puts "2 corner cases"
assert 1, sqrt(1)
assert 0, sqrt(0)
puts "2 normal cases"
assert 5, sqrt(25)
assert 9, sqrt(81)
puts "float number"
assert 2.5, sqrt(6.25)
assert 1.5, sqrt(2.25)
puts "float numbers not at 2^n"
assert 3.3, sqrt(10.89)
assert 7.7, sqrt(59.29)
puts "float number < 1"
assert 0.1, sqrt(0.01)
assert 0.02, sqrt(0.0004)
puts "irrational root"
assert 1.414213562373095, sqrt(2)
assert 1.732050807568877, sqrt(3)

So besides of the binary search approach, we can calculate the square root with Newton’s method, which calculates the result with a iterative equation.
Newton’s method has the limitation in precision, but has a good performance. It is said that one of the ancestors of FPS game Quake uses it in the game engine to get a good performance with limited computing power.
Here is a easy-understood document explain how it works.

Today, we found there is a huge pitfall in node.js crypto module! Decipher has potential problem when processing Base64 encoding.

We’re building RESTful web service based on Node.js, which talks to some other services implemented with Ruby.

Ruby

In ruby, we use the default Base64 class to handle Base64 encoding.

Base64#encode64 has a very interesting feature:
It add line break (\n) to output every 60 characters. This format make the output look pretty and be friendly for human reading:

1
2
3
4
5
6
7

MSwyLDMsNCw1LDYsNyw4LDksMTAsMTEsMTIsMTMsMTQsMTUsMTYsMTcsMTgs
MTksMjAsMjEsMjIsMjMsMjQsMjUsMjYsMjcsMjgsMjksMzAsMzEsMzIsMzMs
MzQsMzUsMzYsMzcsMzgsMzksNDAsNDEsNDIsNDMsNDQsNDUsNDYsNDcsNDgs
NDksNTAsNTEsNTIsNTMsNTQsNTUsNTYsNTcsNTgsNTksNjAsNjEsNjIsNjMs
NjQsNjUsNjYsNjcsNjgsNjksNzAsNzEsNzIsNzMsNzQsNzUsNzYsNzcsNzgs
NzksODAsODEsODIsODMsODQsODUsODYsODcsODgsODksOTAsOTEsOTIsOTMs
OTQsOTUsOTYsOTcsOTgsOTksMTAw

The Base64#decode64 class ignores the line break (\n) when parsing the base64 encoded data, so the line break won’t pollute the data.

Node.js

Node.js take Base64 as one of the 5 standard encodings (ascii, utf8, base64, binary, hex). Ideally the data or string can be transcoded between these 4 encodings without data loss.

The Buffer class is the simplest way to transcode the data:

1
2
3
4
5
6
7
8

Base64 =
  encode64: (text) ->
    new Buffer(text, 'utf8').toString('base64')
  decode64: (base64) ->
    new Buffer(base64. 'base64').toString('utf8')

Although encode64 function in node.js won’t add line break to the output, but the decode64 function does ignore the line break when parsing the data. It keeps the consistent behavior with ruby Base64 class, so we can use this decode64 function to decode the data from ruby.

Since base64 is one of the standard encodings, and some of the node.js API does allow set encoding for input and output. So ideally, we can complete the base64 encoding and decoding during processing the data.
It seems Node.js is more convenient comparing to Ruby when dealing with Base64.

e.g. We can combine reading file and base64 encoding the content into one operation by setting the encoding to readFileSync API.

1
2
3
4
5
6

fs = require('fs')
fileName = './binary.dat' # this file contains binary data
base64 = fs.readFileSync(fileName, 'base64') # file content has been base64 encoded

It looks like we can always use this trick to avoid manually base64 encoding and decoding when the API has encoding parameter! But actually it is not true! There is a BIG pitfall here!

In our real case, we uses crypto module to decrypt the the JSON document that encrypted and base64 encoded by Ruby:

1
2
3
4
5
6
7
8
9
10
11

crypto = require('crypto')
parse = (data, algorithm, key, iv) ->
  decipher = crypto.createDecipheriv(algorithm, key, iv)
  decrypted = decipher.update(data, 'base64', 'utf8') # Set input encoding to 'base64' to ask API to base64 decode the input before decryption
  decrypted += dechiper.final('utf8')
  JSON.parse(decrypted)

1
2
3
4
5
6
7
8
9
10
11
12
13

crypto = require('crypto')
parse = (data, algorithm, key, iv) ->
  decipher = crypto.createDecipheriv(algorithm, key, iv)
  binary = new Buffer(data,'base64') # Manually Base64 Decode
  decrypted = decipher.update(binary, 'binary', 'utf8') # Set input encoding to 'binary'
  decrypted += dechiper.final('utf8')
  JSON.parse(decrypted)

The previous 2 implementations are very similar except the second one base64 decoded the data manually by using Buffer. Ideally they should be equivalent in behavior. But in fact, they are NOT equivalent!

The previous implementation throws “TypeError: DecipherFinal fail”.
And the reason is that the shortcut way doesn’t ignore the line break, but Buffer does!!! So in the previous implementation, the data is polluted by the line break!

Conclusion

Be careful, when you try to ask the API to base64 decode the data by setting the encoding argument to ‘base64’. It has inconsistent behavior comparing to Buffer class.

I’m not sure whether it is a node.js bug, or it is as is by design. But it is indeed a pitfall that hides so deep. And usually is extremely hard to figure out. Since encrypted binary is hard to human to read, and debugging between 2 languages are also kind of hard!