Apache Spark with MongoDB (using pymongo-spark)

Here is a follow up on previous post about using Apache Spark to work on MongoDB data.  Please refer to the old post for details on the setup.

This post is about using the "unstable" pymongo-spark library to create MongoDB backed RDD.

First, get the mongo-hadoop source tree from github:

git clone https://github.com/mongodb/mongo-hadoop.git


We need to build a jar and copy a Python script from the source.

For building the jar:

./gradlew jar

When done, the only jar we need is (version number depends on the source you checkout)

spark/build/libs/mongo-hadoop-spark-1.5.0-SNAPSHOT.jar


Copy it to the  lib directory under Spark.  Also need to add it to the classpath when using pySpark or spark-submit.

And the Python file we need from the source tree is located at:

mongo-hadoop/spark/src/main/python/pymongo_spark.py


Save it under the same folder as the application script and remember to use "--py-files" parameter to deploy it.

Also make sure you have pymongo installed.  e.g. for Debian machines

sudo apt-get install python-pymongo


Finally, the application script. The pymongo-spark needs to be activated before loading / writing RDDs.  Also, the structure of the loaded RDD is slightly different when compared with RDD using mongo-hadoop.

from operator import add
from pyspark import SparkContext, SparkConf
import pymongo_spark

if __name__ == "__main__":

    # initiate pymongo-spark
    pymongo_spark.activate()

    conf = SparkConf() \
        .setAppName("SparkMongoDB2") \
        .set('spark.executor.extraClassPath', '/home/spark/spark-1.4.1-bin-hadoop2.6/lib/mongo-hadoop-spark-1.5.0-SNAPSHOT.jar')
    sc = SparkContext(conf=conf)

    # we know the number of business is much less than reviews
    # create a dictionary of stars given to each business
    businessStar = sc.mongoRDD('mongodb://192.168.1.69:27017/test.yelp_business') \
        .map(lambda b: (b['business_id'], b['stars'])).collectAsMap()

    # create and process review RDD
    poorReview = sc.mongoRDD('mongodb://192.168.1.69:27017/test.yelp_review') \
        .filter(lambda r: r['stars'] < businessStar[r['business_id']]) \
        .map(lambda r: (r['business_id'], 1)) \
        .reduceByKey(add)

    # save output back to MongoDB
    poorReview.saveToMongoDB('mongodb://192.168.1.69:27017/test.poor_count')

    sc.stop()

Here is an example of submitting the application


bin/spark-submit  --master spark://192.168.1.10:7077 --conf "spark.eventLog.enabled=true" --py-files "/home/spark/test/spark_mongodb/pymongo_spark.py" --driver-class-path="/home/spark/spark-1.4.1-bin-hadoop2.6/lib/mongo-hadoop-spark-1.5.0-SNAPSHOT.jar" --executor-memory=256m ~/test/spark_mongodb/yelp_poor2.py

Apache Spark with MongoDB

Updates (2015-12-17): There are two ways for Apache Spark to access MongoDB data: mongo-hadoop or pymongo-spark.  This post is about using mongo-hadoop.  There is another post on using pymongo-spark.

Here is an example of running analytic tasks on Apache Spark using data from MongoDB.  Note that this is a trivial problem and it is much more efficient to solve it within MongoDB (or using PostgreSQL FDW).  But it is a good exercise to try out the mongo-hadoop solution.

My Apache Spark cluster consists of one UDOO and one Raspberry Pi with UDOO as both master and slave.  The CPU and memory resources on these devices are limited.

UDOO: 192.168.1.10. 1GB memory and 4x 1GHz cores
RPi: 192.168.1.7. 512MB memory and 1x 700MHz core

MongoDB is installed on a x86 machine (192.168.1.69).  Some Yelp sample data is loaded in the test database.  In particular, we are interested in the "business" and "review" collections:

> db.yelp_business.findOne()
{
        "_id" : ObjectId("566bb192563714b25d604a94"),
        "business_id" : "UsFtqoBl7naz8AVUBZMjQQ",
        "full_address" : "202 McClure St\nDravosburg, PA 15034",
        "hours" : {

        },
        "open" : true,
        "categories" : [
                "Nightlife"
        ],
        "city" : "Dravosburg",
        "review_count" : 4,
        "name" : "Clancy's Pub",
        "neighborhoods" : [ ],
        "longitude" : -79.88693,
        "state" : "PA",
        "stars" : 3.5,
        "latitude" : 40.350519,
        "attributes" : {
                "Happy Hour" : true,
                "Accepts Credit Cards" : true,
                "Good For Groups" : true,
                "Outdoor Seating" : false,
                "Price Range" : 1
        },
        "type" : "business"
}
> db.yelp_business.count()
61184
> db.yelp_review.findOne()
{
        "_id" : ObjectId("566bb1eb563714b25d61ea02"),
        "votes" : {
                "funny" : 0,
                "useful" : 2,
                "cool" : 0
        },
        "user_id" : "H1kH6QZV7Le4zqTRNxoZow",
        "review_id" : "RF6UnRTtG7tWMcrO2GEoAg",
        "stars" : 2,
        "date" : "2010-03-22",
        "text" : "Unfortunately, the frustration of being Dr. Goldberg's patient is a repeat of the experience I've had with so many other doctors in NYC -- good doctor, terrible staff.  It seems that his staff simply never answers the phone.  It usually takes 2 hours of repeated calling to get an answer.  Who has time for that or wants to deal with it?  I have run into this problem with many other doctors and I just don't get it.  You have office workers, you have patients with medical needs, why isn't anyone answering the phone?  It's incomprehensible and not work the aggravation.  It's with regret that I feel that I have to give Dr. Goldberg 2 stars.",
        "type" : "review",
        "business_id" : "vcNAWiLM4dR7D2nwwJ7nCA"
}
> db.yelp_review.count()

1569264


We are going to find, for each business, the number of reviews with rating lower than its rating.

First, on the Spark machines, we need to download the MongoDB Java driver and the mongo-hadoop software:

wget http://central.maven.org/maven2/org/mongodb/mongo-java-driver/3.0.4/mongo-java-driver-3.0.4.jar
wget https://github.com/mongodb/mongo-hadoop/releases/download/r1.4.0/mongo-hadoop-core-1.4.0.jar

I saved them under the lib directory of Spark.

The logic is written in Python:

from operator import add
from pyspark import SparkContext, SparkConf

if __name__ == "__main__":

    conf = SparkConf() \
        .setAppName("SparkMongoDB") \
        .set('spark.executor.extraClassPath', '/home/spark/spark-1.4.1-bin-hadoop2.6/lib/mongo-hadoop-core-1.4.0.jar:/home/spark/spark-1.4.1-bin-hadoop2.6/lib/mongo-java-driver-3.0.4.jar')
    sc = SparkContext(conf=conf)

    keyClassName = 'org.apache.hadoop.io.Text'
    valueClassName = 'org.apache.hadoop.io.MapWritable'

    # two collections from MongoDB
    configReview = {'mongo.input.uri': 'mongodb://192.168.1.69:27017/test.yelp_review'}
    configBusiness = {'mongo.input.uri': 'mongodb://192.168.1.69:27017/test.yelp_business'}

    # we know the number of business is much less than reviews
    # create a dictionary of stars given to each business
    businessStar = sc.newAPIHadoopRDD(
            inputFormatClass='com.mongodb.hadoop.MongoInputFormat',
            keyClass=keyClassName,
            valueClass=valueClassName,
            conf=configBusiness) \
        .map(lambda b: (b[1]['business_id'], b[1]['stars'])).collectAsMap()

    # create and process review RDD
    poorReview = sc.newAPIHadoopRDD(
            inputFormatClass='com.mongodb.hadoop.MongoInputFormat',
            keyClass=keyClassName,
            valueClass=valueClassName,
            conf=configReview) \
        .filter(lambda r: r[1]['stars'] < businessStar[r[1]['business_id']]) \
        .map(lambda r: (r[1]['business_id'], 1)) \
        .reduceByKey(add)

    ''' This alternative is more elegant but require more memory
    businessStar = sc.newAPIHadoopRDD(
            inputFormatClass='com.mongodb.hadoop.MongoInputFormat',
            keyClass=keyClassName,
            valueClass=valueClassName,
            conf=configBusiness) \
        .map(lambda b: (b[1]['business_id'], b[1]['stars']))

    poorReview = sc.newAPIHadoopRDD(
            inputFormatClass='com.mongodb.hadoop.MongoInputFormat',
            keyClass=keyClassName,
            valueClass=valueClassName,
            conf=configReview) \
        .map(lambda r: (r[1]['business_id'], r[1]['stars'])) \
        .join(businessStar) \
        .filter(lambda (business_id, (rStar, bStar)): bStar > rStar) \
        .map(lambda (business_id, (rStar, bStar)): (business_id, 1)) \
        .reduceByKey(add)
    '''

    # save output back to MongoDB
    outConfig = {'mongo.output.uri': 'mongodb://192.168.1.69:27017/test.poor_count'}
    poorReview.saveAsNewAPIHadoopFile(
            path='file:///not-used',
            outputFormatClass='com.mongodb.hadoop.MongoOutputFormat',
            keyClass=keyClassName,
            valueClass=valueClassName,
            conf=outConfig)

    sc.stop()

Start the cluster ("sbin/start-all.sh") and submit the job, e.g.:

bin/spark-submit  --master spark://192.168.1.10:7077 --conf "spark.eventLog.enabled=true" --driver-class-path="/home/spark/spark-1.4.1-bin-hadoop2.6/lib/mongo-hadoop-core-1.4.0.jar:/home/spark/spark-1.4.1-bin-hadoop2.6/lib/mongo-java-driver-3.0.4.jar" --executor-memory=256m ~/test/spark_mongodb/yelp_poor.py

It took 20 minutes to complete.  Swapping was a big issue due to lack of memory on the ARM devices.

Next, will try pymongo-spark to see if skipping the Hadoop layer will improve the performance (however, as of version 0.1, pymongo-spark used mongo-hadoop as the underlying logic).

Playing with PostgreSQL FDW for MongoDB

While it was interesting to read articles on people bashing MongoDB's latest BI connector is based on PostgreSQL, I wonder how the (alleged) Python implemented Foreign Data Wrapper (FDW) performs.

First I got PostgreSQL 9.4 and Python dev installed on my openSUSE Tumbleweed machine:

postgresql94 postgresql94-server postgresql94-devel postgresql94-contrib python-devel python-setuptools


Then build and install Multicorn, which is a Postgresql extension that the (alleged) MongoDB FDW is based on:

git clone git://github.com/Kozea/Multicorn.git
cd Multicorn
sudo make
sudo make install


Also install the FDW:

git clone https://github.com/asya999/yam_fdw.git
cd yam_fdw
sudo python setup.py install


Start the PostgreSQL server  if it is not running:

sudo systemctl start postgresql.service


To test the performance, I got some sample Yelp data loaded into MongoDB 3.0.7.  Here is what the format of "business" data:

> db.yelp_business.findOne()
{
        "_id" : ObjectId("566bb192563714b25d604a94"),
        "business_id" : "UsFtqoBl7naz8AVUBZMjQQ",
        "full_address" : "202 McClure St\nDravosburg, PA 15034",
        "hours" : {

        },
        "open" : true,
        "categories" : [
                "Nightlife"
        ],
        "city" : "Dravosburg",
        "review_count" : 4,
        "name" : "Clancy's Pub",
        "neighborhoods" : [ ],
        "longitude" : -79.88693,
        "state" : "PA",
        "stars" : 3.5,
        "latitude" : 40.350519,
        "attributes" : {
                "Happy Hour" : true,
                "Accepts Credit Cards" : true,
                "Good For Groups" : true,
                "Outdoor Seating" : false,
                "Price Range" : 1
        },
        "type" : "business"
}
> db.yelp_business.count()
61184


And here is sample of the review data:

> db.yelp_review.findOne()
{
        "_id" : ObjectId("566bb1eb563714b25d61ea02"),
        "votes" : {
                "funny" : 0,
                "useful" : 2,
                "cool" : 0
        },
        "user_id" : "H1kH6QZV7Le4zqTRNxoZow",
        "review_id" : "RF6UnRTtG7tWMcrO2GEoAg",
        "stars" : 2,
        "date" : "2010-03-22",
        "text" : "Unfortunately, the frustration of being Dr. Goldberg's patient is a repeat of the experience I've had with so many other doctors in NYC -- good doctor, terrible staff.  It seems that his staff simply never answers the phone.  It usually takes 2 hours of repeated calling to get an answer.  Who has time for that or wants to deal with it?  I have run into this problem with many other doctors and I just don't get it.  You have office workers, you have patients with medical needs, why isn't anyone answering the phone?  It's incomprehensible and not work the aggravation.  It's with regret that I feel that I have to give Dr. Goldberg 2 stars.",
        "type" : "review",
        "business_id" : "vcNAWiLM4dR7D2nwwJ7nCA"
}
> db.yelp_review.count()
1569264

So, say I want to do a join of the two collections in PostgreSQL to find out, for each business, how many reviews give lower rating than its existing rating.  Here are the sample SQL scripts execute in psql:

-- create the Multicorn extension
CREATE EXTENSION multicorn;

-- define the mongodb FDW
create server mongodb_yelp foreign data wrapper multicorn options (wrapper 'yam_fdw.Yamfdw');
-- turn on debug if necessary
--create server mongodb_yelp foreign data wrapper multicorn options (wrapper 'yam_fdw.Yamfdw', debug 'True');

-- create the foreign tables
create foreign table yelp_review ("_id" varchar, "review_id" varchar, "user_id" varchar, "business_id" varchar, "stars" numeric, "date" date, "text" varchar) server mongodb_yelp options (db 'test', collection 'yelp_review');
create foreign table yelp_business ("_id" varchar, "business_id" varchar, "name" varchar, "stars" numeric, "longitude" float8, "latitude" float8, "full_address" varchar, "type" varchar) server mongodb_yelp options (db 'test', collection 'yelp_business');

-- use SQL to join the collections
select b.name, count(1)
from yelp_business b
left outer join yelp_review r
  on r.business_id = b.business_id
  and r.stars < b.stars
group by b.name
fetch first 100 rows only;


The performance is nothing to write home about, but is better than I expected.  It is hard to do push-down to foreign data source.

Anyway, I did fork the FDW and made some minor changes.

PS.  Not sure if the bashing (here, here) of MongoDB's BI connector was caused by conflict of interest (after all, Slam Data is an analytic tool for NoSQL).  But I am no fanboy of any particular software.

I just use whatever software that suits my needs.  The more choices I have, the better off I will be.

Building MongoDB 3.0.x for ARM (armv7l) platforms

MongoDB does not officially support the 32-bit ARM platform. See the MongoDB Jira discussions for details.

Also note that for some Linux distributions of ARM, you can install MongoDB directly with their package managers, e.g. on Arch Linux: "pacman -Sy mongodb".  (But the latest build on Arch Linux ARM seems to be having issues.)

Updates (2016-01-18): Please note that the latest Arch Linux ARM package of MongoDB 3.2 seems to be working fine again.

Here are steps to compile MongoDB on 32-bit ARM.  I did it on my UDOO board with Arch Linux ARM.  But the procedure should be similar for other armv7l boards (e.g. Beaglebone Black).

While there are tutorials on how to compile MongoDB on ARM machines, most of them are based on fork such as this or this.  But these forks are pretty old (version 1.x or 2.x only).  Since I wanted to setup an ARM replica of my x86 primary running MongoDB 3.0.7, I decided to try to compile directly from the MongoDB git source.


Preparation

I will be compiling the source directly on the ARM board instead of cross-compiling.

Depending on your hardware and available RAM, you may need to add a swap file in order to build MongoDB successfully.  For reference, with the UDOO setup of 1GB of RAM, 1GB of swap space and swappiness equals to 1, the compilation process could hit 500MB of swap usage.

Make sure we have the latest software and compilers etc.  On the Arch Linux ARM, that means running:

sudo pacman -Syu

sudo pacman -Sy base-devel scons git-core openssl boost boost-libs

If you are using other Linux distributions, you may need other packages instead.  e.g. for Debian / Ubuntu with apt-get, you probably need "build-essential" instead of "base-devel":

sudo apt-get update

sudo apt-get upgrade

sudo apt-get install build-essential libssl-dev git scons libboost-filesystem-dev libboost-program-options-dev libboost-system-dev libboost-thread-dev

Get the MongoDB source

Get the MongoDB source from github and checkout the appropriate version.  I will be compiling version 3.0.7:

mkdir ~/test

cd ~/test

git clone git://github.com/mongodb/mongo.git

cd mongo

git checkout r3.0.7

Configure the V8 build for ARM

MongoDB depends on the V8 Javascript engine.  There are two versions of V8 in the source tree:  "mongo/src/third_party/v8" and "mongo/src/third_party/v8-3.25".  While the 3.25 version of V8 supports both ARM and ARM64, the SConscript is missing definitions for the 32-bit ARM.

(Note that 3.25 is not the default version.  There are problems with some of the memory tests.  And it seems that MongoDB will move to use SpiderMonkey soon)

Edit the file mongo/src/third_party/v8-3.25/SConscript to add definitions for "armv7l" accordingly (or you may get the patched file here):

@@ -77,6 +77,9 @@ LIBRARY_FLAGS = { 
    'arch:arm64': { 
      'CPPDEFINES':   ['V8_TARGET_ARCH_ARM64'], 
    }, 
+    'arch:arm': { 
+      'CPPDEFINES':   ['V8_TARGET_ARCH_ARM'], 
+    }, 
  }, 
  'msvc': { 
    'all': { 
@@ -308,6 +311,27 @@ SOURCES = { 
    arm64/stub-cache-arm64.cc 
    arm64/utils-arm64.cc 
    """), 
+  'arch:arm': Split(""" 
+    arm/assembler-arm.cc 
+    arm/builtins-arm.cc 
+    arm/code-stubs-arm.cc 
+    arm/codegen-arm.cc
+    arm/constants-arm.cc 
+    arm/cpu-arm.cc 
+    arm/debug-arm.cc 
+    arm/deoptimizer-arm.cc 
+    arm/disasm-arm.cc 
+    arm/frames-arm.cc 
+    arm/full-codegen-arm.cc 
+    arm/ic-arm.cc 
+    arm/lithium-arm.cc 
+    arm/lithium-codegen-arm.cc 
+    arm/lithium-gap-resolver-arm.cc 
+    arm/macro-assembler-arm.cc 
+    arm/regexp-macro-assembler-arm.cc 
+    arm/simulator-arm.cc 
+    arm/stub-cache-arm.cc 
+    """), 
  'os:freebsd': ['platform-freebsd.cc', 'platform-posix.cc'], 
  'os:openbsd': ['platform-openbsd.cc', 'platform-posix.cc'],
   'os:linux':   ['platform-linux.cc', 'platform-posix.cc'], 
@@ -362,6 +386,8 @@ def get_options(): 
        arch_string = 'arch:x64' 
    elif processor == 'aarch64': 
        arch_string = 'arch:arm64' 
+    elif processor == 'armv7l': 
+        arch_string = 'arch:arm' 
    else: 
        assert False, "Unsupported architecture: " + processor

Also, depending on your environment, you may want to patch the code otherwise the compiled mongod and mongo will cause segmentation fault.


Compile and install

Next we can compile and install MongoDB:

cd ~/test/mongo/

scons -j 2 --ssl --wiredtiger=off --js-engine=v8-3.25 --c++11=off --disable-warnings-as-errors CXXFLAGS="-std=gnu++11" all

scons --ssl --wiredtiger=off --js-engine=v8-3.25 --c++11=off --disable-warnings-as-errors CXXFLAGS="-std=gnu++11" --prefix=/home/cho/apps/mongo install

Although the i.MX6Q CPU on my UDOO has 4 cores, I used "-j 2" instead of "-j 4" due to stability reason.  Adjust according to your CPU power / memory usage.

The WiredTiger storage engine does not support 32-bit platforms.  So we are disabling it here with "--wiredtiger=off".

The "--js-engine" parameter is to select the non-default V8 engine to use.

Standard c++11 is disabled with "--c++11=off" and the "-std=gnu++11" flag is used instead.  The Google Performance Tools (gperftools) has problem with the "-std=c++11" flag when compiled for ARM.  This could be a problem if you tried to compile latest MongoDB source as "--c++11=on" has been made as mandatory.  You probably still can disable it by editing SConstruct if necessary. Or use the system allocator ("--allocator=system") instead of tcmalloc.

The "--prefix" parameter specifies where to install MongoDB.  You probably want to specify another location.

If you only want to build the database, no need to specify "all".  Or specify "core" to build mongo, mongod, and mongos.

Depends on the toolchain you are using, during compilation, the assembler will give warnings about SWP/SWPB instructions being deprecated:

Warning: swp{b} use is deprecated for ARMv6 and ARMv7

The generated code should be fine as Linux kernel can emulate these instructions (you may run "dmesg | grep -i swp" to check).  Not sure how to avoid it (tried specifying various gcc parameters such as -mcpu and -march but seems not effective) and whether it will affect the performance or not. Anyone? (See updates below)

And you can run "cat /proc/cpu/swp_emulation" and see the emulated count.


Build the tools (optional)

You may also want to build the tools. Install Go first:

sudo pacman -Sy go

Then get the source and build:

cd ~/test

git clone https://github.com/mongodb/mongo-tools
cd mongo-tools
git checkout r3.0.7

./build.sh

(Update 2015-12-08): It turns out that the boost library included in MongoDB is pretty old and it contains inline assembly with SWP instruction. You can apply the patch to the file src/third_party/boost/boost/smart_ptr/detail/spinlock_gcc_arm.hpp

Or, use the system boost library by specifying the "--user-system-boost" parameter when building.

References

http://gravitronic.com/compiling-mongodb-with-ssl-support-on-ubuntu-12-04-lts/

https://github.com/linux-on-ibm-z/docs/wiki/Building-MongoDB-3.0-on-RHEL-7-and-SLES-12

MongoDB 3.0.7 segmentation fault on ARM

Updates (2015-12-28): mongodb-3.2.0-3-armv7h of Arch Linux ARM ssems to be working fine.


The latest stable version (3.0.7) of MongoDB is having problem on Arch Linux ARM platforms.

Out of curiosity, I checked out the code from github and tried to compile and reproduce it. The segmentation fault seems to be caused by std::map.  Here is the gdb backtrace:

#0  std::basic_string<char, std::char_traits<char>, std::allocator<char> >::basic_string (this=0xad3e28, 
    __str=<error reading variable: Cannot access memory at address 0x0>)
    at /build/gcc/src/gcc-build/armv7l-unknown-linux-gnueabihf/libstdc++-v3/include/bits/basic_string.tcc:617
#1  0x00459b08 in std::pair<std::string const, mongo::optionenvironment::Value>::pair<std::string const&, 0u>(std::tuple<std::string const&>&, std::tuple<>&, std::_Index_tuple<0u>, std::_Index_tuple<>) (__tuple2=<synthetic pointer>, 
    __tuple1=..., this=0x0) at /usr/include/c++/5.2.0/tuple:1172
#2  std::pair<std::string const, mongo::optionenvironment::Value>::pair<std::string const&>(std::piecewise_construct_t, std::tuple<std::string const&>, std::tuple<>) (__second=..., __first=..., this=0x0)
    at /usr/include/c++/5.2.0/tuple:1161
#3  __gnu_cxx::new_allocator<std::_Rb_tree_node<std::pair<std::string const, mongo::optionenvironment::Value> > >::construct<std::pair<std::string const, mongo::optionenvironment::Value>, std::piecewise_construct_t const&, std::tuple<std::string const&>, std::tuple<> >(std::pair<std::string const, mongo::optionenvironment::Value>*, std::piecewise_construct_t const&, std::tuple<std::string const&>&&, std::tuple<>&&) (__p=0x0, this=0xbefff558)
    at /usr/include/c++/5.2.0/ext/new_allocator.h:120
#4  std::allocator_traits<std::allocator<std::_Rb_tree_node<std::pair<std::string const, mongo::optionenvironment::Value> > > >::_S_construct<std::pair<std::string const, mongo::optionenvironment::Value>, std::piecewise_construct_t const&, std::tuple<std::string const&>, std::tuple<> >(std::allocator<std::_Rb_tree_node<std::pair<std::string const, mongo::optionenvironment::Value> > >&, std::pair<std::string const, mongo::optionenvironment::Value>*, std::piecewise_construct_t const&, std::tuple<std::string const&>&&, std::tuple<>&&) (
    __p=<optimized out>, __a=...)
    at /usr/include/c++/5.2.0/bits/alloc_traits.h:256
#5  std::allocator_traits<std::allocator<std::_Rb_tree_node<std::pair<std::string const, mongo::optionenvironment::Value> > > >::construct<std::pair<std::string const, mongo::optionenvironment::Value>, std::piecewise_construct_t const&, std::tuple<std::string const&>, std::tuple<> >(std::allocator<std::_Rb_tree_node<std::pair<std::string const, mongo::optionenvironment::Value> > >&, std::pair<std::string const, mongo::optionenvironment::Value>*, std::piecewise_construct_t const&, std::tuple<std::string const&>&&, std::tuple<>&&) (__p=<optimized out>, 
    __a=...) at /usr/include/c++/5.2.0/bits/alloc_traits.h:402
#6  std::_Rb_tree<std::string, std::pair<std::string const, mongo::optionenvironment::Value>, std::_Select1st<std::pair<std::string const, mongo::optionenvironment::Value> >, std::less<std::string>, std::allocator<std::pair<std::string const, mongo::optionenvironment::Value> > >::_M_construct_node<std::piecewise_construct_t const&, std::tuple<std::string const&>, std::tuple<> >(std::_Rb_tree_node<std::pair<std::string const, mongo::optionenvironment::Value> >*, std::piecewise_construct_t const&, std::tuple<std::string const&>&&, std::tuple<>&&) (
    __node=0xad3e18, this=0xbefff558)
    at /usr/include/c++/5.2.0/bits/stl_tree.h:529
#7  std::_Rb_tree<std::string, std::pair<std::string const, mongo::optionenvironment::Value>, std::_Select1st<std::pair<std::string const, mongo::optionenvironment::Value> >, std::less<std::string>, std::allocator<std::pair<std::string const, mongo::optionenvironment::Value> > >::_M_create_node<std::piecewise_construct_t const&, std::tuple<std::string const&>, std::tuple<> >(std::piecewise_construct_t const&, std::tuple<std::string const&>&&, std::tuple<>&&) (
    this=0xbefff558) at /usr/include/c++/5.2.0/bits/stl_tree.h:546
#8  std::_Rb_tree<std::string, std::pair<std::string const, mongo::optionenvironment::Value>, std::_Select1st<std::pair<std::string const, mongo::optionenvironment::Value> >, std::less<std::string>, std::allocator<std::pair<std::string const, mongo::optionenvironment::Value> > >::_M_emplace_hint_unique<std::piecewise_construct_t const&, std::tuple<std::string const&>, std::tuple<> >(std::_Rb_tree_const_iterator<std::pair<std::string const, mongo::optionenvironment::Value> >, std::piecewise_construct_t const&, std::tuple<std::string const&>&&, std::tuple<>&&) (this=0xbefff558, __pos=...)
    at /usr/include/c++/5.2.0/bits/stl_tree.h:2170
#9  0x0046225c in std::map<std::string, mongo::optionenvironment::Value, std::less<std::string>, std::allocator<std::pair<std::string const, mongo::optionenvironment::Value> > >::operator[] (__k="authenticationDatabase", this=0xbefff4c4)
    at /usr/include/c++/5.2.0/bits/stl_map.h:483
#10 mongo::optionenvironment::OptionSection::getDefaults (this=0xbefff51c, 
    this@entry=0xad4038, values=0xbefff4c4, values@entry=0xbefff558)
    at src/mongo/util/options_parser/option_section.cpp:508
#11 0x00462134 in mongo::optionenvironment::OptionSection::getDefaults (
    this=0xbefff550, this@entry=0xbefff68c, values=0x4, 
    values@entry=0xbefff558)
    at src/mongo/util/options_parser/option_section.cpp:514
#12 0x0046984c in mongo::optionenvironment::OptionsParser::addDefaultValues (
    this=this@entry=0xab5750 <mongo::optionenvironment::startupOptions>, 
    options=..., 
    environment=0xab5704 <mongo::optionenvironment::startupOptionsParsed>, 
    environment@entry=0x474934 <mongo::optionenvironment::_mongoInitializerFunction_StartupOptions_Parse(mongo::InitializerContext*)+84>)
    at src/mongo/util/options_parser/options_parser.cpp:845
#13 0x0046edf8 in mongo::optionenvironment::OptionsParser::run (
    this=0xab5750 <mongo::optionenvironment::startupOptions>, 
    this@entry=0xbefff79c, options=..., 
Python Exception <class 'ValueError'> Cannot find type const std::map<std::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::less<std::basic_string<char, std::char_traits<char>, std::allocator<char> > >, std::allocator<std::pair<std::basic_string<char, std::char_traits<char>, std::allocator<char> > const, std::basic_string<char, std::char_traits<char>, std::allocator<char> > > > >::_Rep_type: 
    argv=std::vector of length 2, capacity 2 = {...}, 
    env=std::map with 21 elements, 
    environment=0xab5704 <mongo::optionenvironment::startupOptionsParsed>)
    at src/mongo/util/options_parser/options_parser.cpp:1012
#14 0x00474934 in mongo::optionenvironment::_mongoInitializerFunction_StartupOptions_Parse (context=0xbefff81c)
    at src/mongo/util/options_parser/options_parser_init.cpp:46
#15 0x0025eed4 in std::_Function_handler<mongo::Status (mongo::InitializerContext*), mongo::Status (*)(mongo::InitializerContext*)>::_M_invoke(std::_Any_data const&, mongo::InitializerContext*&&) (__functor=..., __args#0=<optimized out>)
    at /usr/include/c++/5.2.0/functional:1857
#16 0x0025f330 in std::function<mongo::Status (mongo::InitializerContext*)>::operator()(mongo::InitializerContext*) const (
    __args#0=<error reading variable: Cannot access memory at address 0x0>, 
    this=0xbefff80c) at /usr/include/c++/5.2.0/functional:2271
#17 mongo::Initializer::execute (this=0xab3dc0 <mongo::getGlobalInitializer()::theGlobalInitializer>, 
    Python Exception <class 'ValueError'> Cannot find type const mongo::InitializerContext::EnvironmentMap::_Rep_type: args=std::vector of length 2, capacity 2 = {...}, env=std::map with 21 elements) at src/mongo/base/initializer.cpp:58
#18 0x0025f8cc in mongo::runGlobalInitializers (
    Python Exception <class 'ValueError'> Cannot find type const mongo::InitializerContext::EnvironmentMap::_Rep_type: 
    args=std::vector of length 2, capacity 2 = {...}, 
    env=std::map with 21 elements) at src/mongo/base/initializer.cpp:71
#19 0x0025fb30 in mongo::runGlobalInitializers (argc=argc@entry=2, 
    argv=argv@entry=0xbefffc64, envp=<optimized out>, envp@entry=0xbefffc70)
    at src/mongo/base/initializer.cpp:90
#20 0x002600a0 in mongo::runGlobalInitializersOrDie (argc=argc@entry=2, 
    argv=argv@entry=0xbefffc64, envp=envp@entry=0xbefffc70)
    at src/mongo/base/initializer.cpp:94
#21 0x0025332c in _main (argc=argc@entry=2, argv=argv@entry=0xbefffc64, 
    envp=envp@entry=0xbefffc70) at src/mongo/shell/dbshell.cpp:601
#22 0x0023aeac in main (argc=2, argv=0xbefffc64, envp=0xbefffc70)
    at src/mongo/shell/dbshell.cpp:924

From the getDefaults function in src/mongo/util/options_parser/option_section.cpp, the operator[] of std::map seems caused the failure when allocating new node:



    Status OptionSection::getDefaults(std::map<Key, Value>* values) const {

        std::list<OptionDescription>::const_iterator oditerator;
        for (oditerator = _options.begin(); oditerator != _options.end(); oditerator++) {
            if (!oditerator->_default.isEmpty()) {
                (*values)[oditerator->_dottedName] = oditerator->_default;
            }
        }

        std::list<OptionSection>::const_iterator ositerator;
        for (ositerator = _subSections.begin(); ositerator != _subSections.end(); ositerator++) {
            ositerator->getDefaults(values);
        }

        return Status::OK();
    }

Haven't figured out why.  But using the equivalent insert seems to be able to get around the issue.

-            (*values)[oditerator->_dottedName] = oditerator->_default;
+            //(*values)[oditerator->_dottedName] = oditerator->_default;
+            (*((values->insert(make_pair(oditerator->_dottedName, std::map<Key, Value>::mapped_type()))).first)).second = oditerator->_default;


Updates (2015-12-06): Building MongoDb with "--opt=off" (i.e. using -O0 instead of -O3") also works. Using g++ 5.2.0

Choosing cipher suites for Java SSL connections

Implemented a simple SSL socket factory for Java to allow specification of cipher suites to use.  Code available on github: https://github.com/kitsook/PrefSSLSocketFactory/

Compiling Nvidia driver 340.xx for latest kernels

Updates (2015-11-30): Nvidia driver 340.96 seems to fixed the issue.  Also, it now works with xserver ABI 20 (x-server 1.18)


One of my PCs has openSUSE Tumbleweed installed.  The machine has a Nvidia 9300 graphic chip on the motherboard and so I was using the legacy driver NVIDIA-Linux-x86_64-340.93.

After upgrading the kernel to 4.3.x, the Nvidia driver failed to compile.  The error is something like this:

error: void value not ignored as it ought to be
return seq_printf(s, "Binary: \"%s\"\n", registry_keys);

After some digging, seems that the Linux kernel has changed and seq_* family now return void instead of an integer.

Here is a quick fix.  First extract the Nvidia driver by running

./NVIDIA-Linux-x86_64-340.93.run  -x

Then modify the file NVIDIA-Linux-x86_64-340.93/kernel/nv-procfs.c:

359c359,360
<     return seq_printf(s, "Binary: \"%s\"\n", registry_keys);
---
>     seq_printf(s, "Binary: \"%s\"\n", registry_keys);
>     return 0;
555c556,557
<     return seq_puts(s, s->private);
---
>     seq_puts(s, s->private);
>     return 0;

Then run the installer to compile and install the driver:

sudo NVIDIA-Linux-x86_64-340.93/nvidia-installer

Easy to maintain logic(?) vs speed

Read this blog post about the FizzBuzz problem:

Write a program which return "fizz" if number is multiplier of 3, return "buzz" if its multiplier of 5 and return "fizzbuzz" if number is divisible by both 3 and 5. If number is not divisible by either 3 or 5 then it should just return the number itself


Here are some implementations and test codes:


I personally prefer the implementation of doFizzBuzz1: the logic captures the sense of "if the number is dividable by x, append y to the result".  It makes future modification of adding similar logic easier without understanding the existing code. (e.g. say adding "print 'buzzbazz' if the number is divisible by 10 and 'fizzbuzzbazz' if divisible by 30" etc).

But of course, it is going to be slower as it involves creation of additional objects.  But by how much?  Here are some test results of running the three implementations against the whole range of integer:


Time taken to run net.clarenceho.test.TestFizzBuzz$$Lambda$1/1212899836@75a1cd57 is 175.717783485s
Time taken to run net.clarenceho.test.TestFizzBuzz$$Lambda$2/1285044316@3d012ddd is 141.0544738s
Time taken to run net.clarenceho.test.TestFizzBuzz$$Lambda$3/1607460018@6f2b958e is 140.644691232s


So it is about 25% slower.  Is it worth it? Probably not in this trivial case.  But worth to consider if the logic is complicated and expected to change / enhance in the future.

doFizzBuzz3 is cleaner without nested conditions and runs slightly faster possibly due to fewer branching.

JUnit code used to test the implementations.  Also a good exercise to practice Java lambda and parallel streams.  Tests done on AMD X4 925.

UDOO Quad network driver issue

My UDOO board is running Arch Linux.  Since kernl 4.2.0, it failed to load the network driver.  Found similar issue being discussed and seems that it is related to the Micrel PHY module.

Issue posted to Arch Linux forum.  Kernel output of 4.2.3:

 [  14.797299] Unable to handle kernel NULL pointer dereference at virtual address 000001f5  
 [  14.805442] pgd = ed460000  
 [  14.808196] [000001f5] *pgd=00000000  
 [  14.811821] Internal error: Oops: 5 [#1] SMP ARM  
 [  14.816445] Modules linked in: ppp_async arc4 rt2800usb rt2x00usb rt2800lib rt2x00lib mac80211 cfg80211 crc_ccitt rfkill imx_ipuv3_crtc imx_ipu_v3 dw_hdmi_imx dw_hdmi uio_pdrv_genirq uio imxdrm drm_kms_helper sch_fq_codel ppp_generic slhc ip_tables x_tables  
 [  14.839599] CPU: 2 PID: 240 Comm: systemd-network Not tainted 4.2.3-1-ARCH #1  
 [  14.846732] Hardware name: Freescale i.MX6 Quad/DualLite (Device Tree)  
 [  14.853268] task: ed3c2080 ti: ed3e6000 task.ti: ed3e6000  
 [  14.858686] PC is at fec_enet_open+0x3d4/0x518  
 [  14.863140] LR is at genphy_suspend+0x54/0x5c  
 [  14.867499] pc : [<c0644f00>]  lr : [<c063ca24>]  psr: 00070013  
 [  14.867499] sp : ed3e7b78 ip : ed3e7ab0 fp : ed3e7bdc  
 [  14.878981] r10: 00000200 r9 : ee366800 r8 : c1136770  
 [  14.884211] r7 : 00000001 r6 : ee5e9d44 r5 : 00000001 r4 : ee5e9800  
 [  14.890744] r3 : 000010f9 r2 : c1036a24 r1 : c103696c r0 : ee5e9800  
 [  14.897272] Flags: nzcv IRQs on FIQs on Mode SVC_32 ISA ARM Segment user  
 [  14.904425] Control: 10c5387d Table: 3d46004a DAC: 00000015  
 [  14.910181] Process systemd-network (pid: 240, stack limit = 0xed3e6220)  
 [  14.916897] Stack: (0xed3e7b78 to 0xed3e8000)  
 [  14.921285] 7b60:                            00000006 00000008  
 [  14.929487] 7b80: ed3e7ba4 ee367000 3206e31c 30383831 652e3030 72656874 0074656e 38383132  
 [  14.937683] 7ba0: 2e303030 65687465 74656e72 0036303a c09fc628 c0644b2c ee5e9800 c09fc628  
 [  14.945880] 7bc0: ee5e9830 00000000 00000008 ed424180 ed3e7bfc ed3e7be0 c0817258 c0644b38  
 [  14.954071] 7be0: ee5e9800 00000001 00001003 00001002 ed3e7c24 ed3e7c00 c0817500 c08171ac  
 [  14.962267] 7c00: ee5e9800 00001002 ee5e9940 c09fc628 00000000 00000008 ed3e7c4c ed3e7c28  
 [  14.970471] 7c20: c08175cc c0817470 ee5e9800 00000000 ed3e7cd4 c09fc628 ed1f7310 00000008  
 [  14.978665] 7c40: ed3e7cb4 ed3e7c50 c0825e50 c08175b0 c08b56a8 c04431a0 c0a6a288 ef7b1990  
 [  14.986860] 7c60: ed3e7c84 00000000 00000000 00000000 00000000 00000000 00000000 00000000  
 [  14.995052] 7c80: 00000000 ed1f7328 ed3e7cb4 ee5e9800 ed1f7300 ed424180 ed424180 00000000  
 [  15.003238] 7ca0: 00000008 00000030 ed3e7d8c ed3e7cb8 c0826d58 c0825b58 ed3e7cc4 00000000  
 [  15.011434] 7cc0: 0000000e ee036800 ed3e7cec ed3e7cd8 c01529b0 00000000 00000000 00000000  
 [  15.019628] 7ce0: 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000  
 [  15.027822] 7d00: 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000  
 [  15.036012] 7d20: 00000000 00000000 00000000 00000000 00000000 00000000 00000000 ed1f7320  
 [  15.044211] 7d40: 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000  
 [  15.052407] 7d60: 00000000 00000000 00000000 00000000 ed3e7d8c 00000024 ed1f7300 00000000  
 [  15.060603] 7d80: ed3e7dcc ed3e7d90 c0827770 c0826c70 ed3e7ddc ed3e7da0 c0174060 c092a00c  
 [  15.068793] 7da0: 00000001 ee001cc0 00000000 ed1f7300 ed424180 c08275c8 ee2e9800 00000000  
 [  15.076988] 7dc0: ed3e7dec ed3e7dd0 c08425c8 c08275d4 ed424180 00000030 ed424180 ee2e9800  
 [  15.085176] 7de0: ed3e7e04 ed3e7df0 c08254c4 c084256c ee251400 00000030 ed3e7e34 ed3e7e08  
 [  15.093369] 7e00: c0841d78 c08254a8 ed3e7ed4 7fffffff 00000008 00000000 ee2e9800 ed424180  
 [  15.101558] 7e20: ed3e7ed4 00000000 ed3e7e9c ed3e7e38 c0842440 c0841c90 ee754630 b6ef7000  
 [  15.109751] 7e40: eeef8000 c0134480 ed3e7e8c ed3e7e58 c0134480 00000000 ed265f00 00000000  
 [  15.117943] 7e60: 000000f0 000000c1 000000c1 00000000 ee754630 ed3e7ed4 ed847340 ed847340  
 [  15.126151] 7e80: 00000010 beeefa64 ed3e6000 00000000 ed3e7eb4 ed3e7ea0 c07fafa0 c0841f04  
 [  15.134346] 7ea0: ed3e7f00 00000000 ed3e7fa4 ed3e7eb8 c07fc20c c07faf68 ed3e7edc 00000000  
 [  15.142540] 7ec0: ed791ec8 00000000 00000000 808ca0e8 00000030 ed3e7f00 00000010 00000001  
 [  15.150735] 7ee0: 00000000 00000000 ed3e7ed4 00000000 00000000 00000000 00000000 c00b7d00  
 [  15.158931] 7f00: 00000010 00000000 00000000 00000000 ed087c00 00000000 40b2ae30 0006422c  
 [  15.167132] 7f20: ffffffff 00000000 03c293d3 00000000 000000f9 ed3e7f88 00000001 808ca080  
 [  15.175339] 7f40: 00000107 c000f664 ed3e6000 00000000 ed3e7f84 ed3e7f60 c00b4474 c00b7c9c  
 [  15.183532] 7f60: 0000000e 00000001 808ca080 00000107 c000f664 beeefa90 00000008 00000000  
 [  15.191713] 7f80: beeefa90 beeefa64 00000010 000000f0 00000122 c000f664 00000000 ed3e7fa8  
 [  15.199907] 7fa0: c000f4c0 c07fc150 beeefa64 00000010 00000003 808ca0e8 00000030 00000000  
 [  15.208096] 7fc0: beeefa64 00000010 000000f0 00000122 017d7840 00000000 808d7198 000000f0  
 [  15.216294] 7fe0: beeefa58 beeefa4c 7f6a0d00 b6e61a18 60030010 00000003 00000000 00000000  
 [  15.224511] [<c0644f00>] (fec_enet_open) from [<c0817258>] (__dev_open+0xb8/0x114)  
 [  15.232100] [<c0817258>] (__dev_open) from [<c0817500>] (__dev_change_flags+0x9c/0x140)  
 [  15.240116] [<c0817500>] (__dev_change_flags) from [<c08175cc>] (dev_change_flags+0x28/0x58)  
 [  15.248572] [<c08175cc>] (dev_change_flags) from [<c0825e50>] (do_setlink+0x304/0x720)  
 [  15.256505] [<c0825e50>] (do_setlink) from [<c0826d58>] (rtnl_setlink+0xf4/0x100)  
 [  15.264005] [<c0826d58>] (rtnl_setlink) from [<c0827770>] (rtnetlink_rcv_msg+0x1a8/0x1bc)  
 [  15.272235] [<c0827770>] (rtnetlink_rcv_msg) from [<c08425c8>] (netlink_rcv_skb+0x68/0xc4)  
 [  15.280537] [<c08425c8>] (netlink_rcv_skb) from [<c08254c4>] (rtnetlink_rcv+0x28/0x34)  
 [  15.288474] [<c08254c4>] (rtnetlink_rcv) from [<c0841d78>] (netlink_unicast+0xf4/0x1a8)  
 [  15.296492] [<c0841d78>] (netlink_unicast) from [<c0842440>] (netlink_sendmsg+0x548/0x560)  
 [  15.304769] [<c0842440>] (netlink_sendmsg) from [<c07fafa0>] (sock_sendmsg+0x44/0x54)  
 [  15.312615] [<c07fafa0>] (sock_sendmsg) from [<c07fc20c>] (SyS_sendto+0xc8/0xec)  
 [  15.320023] [<c07fc20c>] (SyS_sendto) from [<c000f4c0>] (ret_fast_syscall+0x0/0x3c)  
 [  15.327698] Code: 0a00001c ea000038 e59435c8 e1a00004 (e59521f4)  
 [  15.333860] ---[ end trace 194130c04452a6bb ]---  

Loophole in Google Cloud Messaging (GCM) topic

When implementing an Android app that uses GCM topic messaging, I found that there is a risk of DoS attack on it.  And seems that Google engineers are aware of it.

A potential attack could render the app not able to receive broadcast messages from servers. The only solution will require developers to release a new version of the app using a new GCM sender ID.

Technical details of the Android app Weather Alert Canada

EDIT: Google has since demised GCM and now Environment Canada has its own app to push notification to mobile devices. This app has been unpublished from the Play store.

In late August 2015, there was a massive wind storm in Metro Vancouver that knocked out power to many people.  I relied on radio and Twitter to get updates but I thought it would be better if I could get notifications directly from Environment Canada.  A quick search on Google Play store turned up void.  And hence I spent some time to implement an Android app.

These are the technical details behind the app.

Getting the data

Meteorological data can be retrieved easily from Environment Canada.  The question is, what data to use?  My initial thought was to parse the forecast files and extract alert messages from there.  However, the forecast data is broken down into many files, each for specific area.  And these files are generated frequently.  As I planned to host the logic on Google App Engine (more on that later), I would like to minimize the network traffic.

Luckily, Environment Canada also provides public weather alerts in CAP format.  The CAP files are categorized by issuing offices.  Inside the file, the affected area is described by polygons and geocodes that are intended to overlap directly on a map.  However, what I needed was to somehow link each affected area to provinces / territories. Good thing is Environment Canada has geo data that can map the area description in CAP to specific provinces.

Push mechanism

A few years ago when I first played with push notification, I tried Amazon SNS.  The advantage is that it supports Google Cloud Messaging (GCM), Apple Push Notification (APN) and many more.  But it turns out that since Oct 2013, GCM also supports iOS devices.  So, to keep it simple this time, the backend utilized GCM to push out notifications.

To be specific, GCM Topic is used as the downstream mechanism to broadcast messages.  It is much simpler than keeping registration id of each device and sending out targeted GCM messages.  The downside is, users cannot request to receive notification on certain areas only (well, technically it can be done with topic subscription too, but that means I need to create lots of GCM topics for different areas...)

Backend logic

Before implementing the server side with App Engine, a quick prototype  was created using Python.  urllib2 is used to fetch CAP files from Environment Canada site. After processing the xml file, GCM messages are pushed out with urllib2 in JSON format.

A script was also created to load mapping between areas and provinces into a database.  DBM was used as the API is simple and made it easy to port to Google Datastore.

Another DBM file was also used to keep track of processed CAP files.

Once the prototype is working, porting it to App Engine was easy.  Cron jobs were defined to pull CAP data periodically.  There are also cron jobs to clean datastore of processed files.

Datastore and memcached

When moving the Python scripts to Google App Engine, the DBM databases were ported to  Datastore. As I intended to use the App Engine free tier, there was a need to keep the I/O low.  Luckily App Engine provides memcache as a free service.  With proper caching (over 98% hit rate), I could keep the datastore utilization as low as 2%  of the daily quota.

Android app

The android app was a shameless clone of the GCM sample application.  On the navigator bar, users can choose to show notifications for specific provinces only.  The main window is a WebView.  A HTML file and some JavaScript are included in the app to fetch Environment Canada WeatherLink.

Do you feel lucky today? (aka random Android notification ID)

Recently created an Android app that receives Google Cloud Messaging (GCM) messages.  Upon receiving certain messages, notifications will be shown on devices. Due to nature of the data, it is expected that a device will receive short bursts of multiple messages from time to time.

Now, to show a notification on Android, we need to assign an ID that is unique within the app. The "right way" to do it is to keep a counter as ID for each notification.

Well, I am too lazy to store that ID in the app. I have seen on stacktrace that some people tried to use the current timestamp in millisecond (long int)  as ID. But since the ID is an int, they divide the long by 1000 (ie reduce the resolution to second instead of millisecond) and cast the number to int. That is going to fail in my case as my app will receive multiple messages within a second.

There is an easy (and risky?) way to generate a "random" ID on the fly without keeping track of it: get system nano second in long and hash it.

Long.valueOf(System.nanoTime()).hashCode()

The (potential) downside is:
- nanoTime in signed long will repeat every 292 years (roughly). But that is ok for my app
- hashing long into int may result in collision, but the chance should be small if I only need a few numbers in each burst of incoming notifications

So, do I feel lucky today?

Integral Perfect Square

Here is a C implementation of calculating integral square root.  Algorithm based on "long division" logic.  Test cases done with OpenMP and should be compiled as

g++ --std=c++0x -fopenmp -Wall IntegralPerfectSquare.cpp -o IntegralPerfectSquare

Reference:
http://www.math-only-math.com/square-root-of-a-perfect-square-by-using-the-long-division-method.html

Gihub:
https://github.com/kitsook/CPerfectSquare

Project Euler: Integral median

From Project Euler:

ABC is an integral sided triangle with sides a≤b≤c.
mc is the median connecting C and the midpoint of AB. 
F(n) is the number of such triangles with c≤n for which mc has integral length as well.
F(10)=3 and F(50)=165.

Find F(100000).


Let d be the median.  Then d can be calculated by (1):

d = sqrt(2 * a^2 + 2 * b^2 - c^2) / 2

A brute-force solution is to loop through the range of a, b, and c. There are some conditions / optimization to reduce the scope and improve performance:

• a, b, c can form a proper triangle (triangle inequality. i.e. sum of any two sides is bigger than the remaining side)

a+b>c && b+c>a && c+a>b

• since a<=b<=c, the checking above can be rewritten as

a+b>c

• c must be even (otherwise, the square root result will be odd and d wont be an integer)
• if c is even, a and b must have the same parity.  Because (1) can be rewritten as:

2(d^2 + (c/2)^2) = a^2 + b^2

• pre-calculate even perfect sqaures instead of doing square root and check if dividable by 2

Tried to implement it with Scala.  The code is concise and under 30 lines (with comments!).  However, running it on my i5 4120 will probably take weeks to complete. And that is with parallelism and all CPU cores at 100%.

Time to re-install OpenCL SDK and do some coding in C/C++.

Android Safe is no more... Long live AndSafe

Back in 2009, I got my first Android phone - the HTC Magic which ran Android 1.5.  There were only handful of apps available on Android Market (now Google Play).  I wanted something to replace my Palm Pilot MemoAES but couldn't find something that was simple to use and secure (e.g. no network permission).  So I decided to write my own and later I released the Android Safe as freeware.

Fast forward to 2014.  In Sep I received an email from Google saying that "The use of 'Android' in your title is not compliant with Android branding guidelines" and they would suspend my app unless I rename my app.

To be honest, I developed the app for my own use.  I put it on Android Market / Google Play just to share it in case someone out there wanted similar things.  I wasn't making any money out of it.  So I didn't do anything and eventually Google removed my app from Market.

In 2015, I finally got some time to sit down to see how I can improve Android Safe:

- it used 256-bit AES with ECB mode.  I picked ECB because I was lazy to implement a secure way to generate the IV.  Also, most of my memos are short (e.g. password, PIN etc) and without pattern.  So ECB was fine.  But if I am going to re-do it again, maybe I will use CBC instead

- 1024-round of PBKDF2 was used to generate the encryption key.  It was OK back then, but now I prefer to use something that is more CPU intensive and can stand against ASIC attacks.  After comparing bcrypt and scrypt, I decided to go with scrypt.  Theoretically scrypt is better than bcrypt, but scrypt is newer and this is usually a bad thing in cryptography as there are not enough cryptoanalysis done against it.  But anyway, I am using it as a key generator rather than cipher, so it is good enough for me.

- JNI library was used to accelerate the PBKDF2 key generation.  Back then, the Android NDK only supported ARM platform.  Now the app should compile for x86 and MIPS too

And so, AndSafe was born.  Besides changes on the encryption logic, the UI was redo to remove the outdated Gallery UI component.