Evernote Tech Blog

The Care and Feeding of Elephants

Wearables Update: Evernote for Pebble Now with Cyrillic and Image Support (Really!)

pebble-story-232x232

The following is a behind the scenes walkthrough on our latest updates for Evernote for Pebble by our lead wearables engineer, Damian Mehers. For our announcement of Evernote for Pebble, click here.

Since the initial release of the Evernote app for the Pebble we’ve made several improvements.  I’m going to briefly talk about what’s changed, and then dive into technical details about how I implemented two of the more challenging changes: supporting custom fonts and generating bitmaps from JavaScript.

First we will review the straightforward improvements:

Preserving line-breaks in notes

If you used the initial release of Evernote for Pebble, you may have noticed that some of your notes looked a little garbled.  This was because the app was not preserving line-breaks in your notes:

Screen Shot 2014-04-16 at 18.23.53 pebble-screenshot_2014-04-16_18-18-39

With the latest release, we’ve address this and it should be much better now:

pebble-screenshot_2014-04-16_18-19-37

Note font size

Soon after we launched Evernote for Pebble, we received helpful feedback.  Thankfully, some people have much better eye-sight than I do.  We added a setting for those keen-eyed people that can read smaller fonts:

pebble-screenshot_2014-04-17_13-22-47 pebble-screenshot_2014-04-16_18-29-34 pebble-screenshot_2014-04-16_18-29-40 pebble-screenshot_2014-04-16_18-29-24 pebble-screenshot_2014-04-16_18-29-47 pebble-screenshot_2014-04-16_18-29-55

Reminder order

Some people use Evernote reminders to “pin” their most important notes to the top of a notebook, and some people use them as actual reminders.

For the “pinned important notes” use case, it makes sense to list the reminders in the order in which they are pinned on the desktop. For the “Notes as actual reminders” use case it makes more sense to list them in the order that each reminder is set to go off.

With the latest release, you choose the order, just like you can on Evernote for Mac.  The default is to order them based on the order in which they are pinned, but if you use reminders as actual reminders, you can see them by reminder date instead:

pebble-screenshot_2014-04-17_13-22-47 pebble-screenshot_2014-04-16_18-35-36 pebble-screenshot_2014-04-17_17-56-04

Custom fonts & Cyrillic Support

The Pebble doesn’t support fonts with accents on them, which is why the initial release of Evernote didn’t support such fonts either.   You’ll have noticed that when you receive a text message with an emoji in it, you just get little squares in the notification on your Pebble.  The same thing happens for notes with cyrillic characters.  Look what happens to the note’s title below:

Screen Shot 2014-04-16 at 18.39.58

pebble-screenshot_2014-04-16_18-40-26

Soon after the initial release we received a deluge of requests for support for PebbleBits which is an unofficial way in which the Pebble can be made to support additional fonts.  Essentially you generate, download and install custom firmware which includes additional fonts.

In order to add support for this in the Evernote JavaScript companion app that runs on the phone, so that it can send the correct strings over to Evernote app running on the Pebble, I needed to convert the UTF-16 strings containing note text over to the equivalent UTF-8 bytes to send over to the Pebble.

image_thumb27

This is the JavaScript code which pushes the UTF-8 bytes into a byte array buffer from a UTF-16 String:

// From http://stackoverflow.com/a/18729536/3390
function addUTF8StringToBuffer(buffer, text) {
  var utf8 = unescape(encodeURIComponent(text));
  for (var i = 0; i < utf8.length; i++) {
    buffer.push(utf8.charCodeAt(i));
  }

  buffer.push(0);
}

You’ll see that I am NUL terminating the string for consumption by the C code on the Pebble.

Once you’ve generated and installed custom firmware with the appropriate character set(s) you’ll see the note titles and content displayed properly:

pebble-screenshot_2014-04-16_18-51-37

Note bitmaps – Images on the Pebble!

Previously when you viewed a note in Evernote for Pebble, the app looked to see if there was any text in the note content, and if there was it displayed the text, otherwise it displayed this message:

pebble-screenshot_2014-04-17_12-30-08

Wouldn’t it be cool, I thought, if we could display an image on the Pebble if the note contains an image?  That way, when I’m shopping for yogurt, and I’m faced with an overwhelming array of dairy produce, I could glance at my watch to remind myself of what it was I was supposed to buy, assuming I’d previously captured a photo of the yoghurt in Evernote on my phone:

Screen Shot 2014-04-17 at 12.34.03

There were a couple of challenges to overcome.  The Pebble has a black-and-white display, and it requires its bitmaps to be in a specific format with a specific header.  On the other hand you can store all kinds of images in Evernote, including PNGs, JPGs, BMPs etc.  And they can have all kinds of color depths.

Using the Evernote Thumbnail API

Fortunately there is an Evernote Thumbnail API, which as a developer you can use to request a thumbnail for a specific note or resource.  What is more, you can request a specific thumbnail size, and the icing on the cake is that you can request that the thumbnail be in a specific format, such as a bitmap.

This was perfect.  In my JavaScript I request the thumbnail using code like this:

  var xmlhttp = new XMLHttpRequest();
  var url = pbnote.webUrl + '/thm/note/' + noteGuid + '.bmp?size='
            + pbnote.CONSTS.THUMBNAIL_SIZE;
  xmlhttp.open("GET", url, true);
  xmlhttp.setRequestHeader('Auth', pbnote.authTokenEvernote);
  xmlhttp.responseType = 'arraybuffer';
  xmlhttp.onload = function () {
    if (xmlhttp.readyState == 4 && xmlhttp.status == 200) {
      pbnote.sender.convertToPebbleBitmap(xmlhttp.response, onOk, onError);
    } else {
      pbnote.log.e('fetchBitmap xmlhttp.readyState=' + xmlhttp.readyState + 
                   ' and xmlhttp.status=' + xmlhttp.status);
      onError(xmlhttp.statusText);
    }
  };

The size constant is 140.  I’m requesting bitmaps by adding ‘.bmp’ to the URL.

This is all very well, and works flawlessly, but what I get back is a color bitmap as a byte array, and what I need to send to the Pebble is a black-and-white bitmap.

Generating the Pebble Bitmap Header (from JavaScript)

I needed to parse the bitmap, and for each pixel convert the Red/Green/Blue components to a black or white pixel, and add the corresponding header.  From JavaScript.

I went searching on the web to see if anyone else had already solved this problem.  No one had, but the good news was that someone had written a library in JavaScript that knew how to parse bitmaps and get the RGB values for each pixel.  The bad news was that they had written the library for Node.js, which uses a special Buffer type for binary data, rather than Typed Arrays that are used in web browsers and the Pebble.

No problem, I thought.  I’ll just write my own Buffer class which wraps a typed array and exposes all the methods that are needed by the library.  That worked, and I was able to parse the bitmap that I received back from the Evernote service, and get the RGB components for each pixel.

All that was left was to generate the appropriate header that the Pebble expects:

  // Buffer is a our own implementation of the bare minumim Node.js Buffer class' 
  // functionality since the bitmap class relies on it
  var buffer = new Buffer(bytes);
  var bitmap = new Bitmap(buffer);
  bitmap.init();

  var width = bitmap.getWidth();
  var height = bitmap.getHeight();

  var data = bitmap.getData(true); // true means it returns 'rgb' objects

  // Calculate the number of bytes per row, one bit per pixel, padded to 4 bytes
  var rowSizePaddedWords = Math.floor((width + 31) / 32);
  var widthBytes = rowSizePaddedWords * 4;

  var flags = 1 << 12; // The version number is at bit 12.  Version is 1
  var result = [];  // Array of bytes that we produce
  pushUInt16(result, widthBytes); // row_size_bytes
  pushUInt16(result, flags); // info_flags
  pushUInt16(result, 0); // bounds.origin.x
  pushUInt16(result, 0); // bounds.origin.y
  pushUInt16(result, width); // bounds.size.w
  pushUInt16(result, height); // bounds.size.h

Generating a Pebble black and white bitmap from a color bitmap (in JavaScript)

Now that I had the header generated (I stole some techniques from a Python tool in the Pebble SDK), I walked through the bitmap’s pixels, converting each pixel to black-and-white:

var currentInt = 0;
for (var i = 0; i < width; i++) {
  var bit = 0;
  var row = data[i];
  for (var b = 0; b < row.length; b++) {
    var rgb = row[b];
    // I'm using the lightness method per
    // http://www.johndcook.com/blog/2009/08/24/algorithms-convert-color-grayscale/
    var isBlack = (Math.max(rgb.r, rgb.g, rgb.b) + Math.min(rgb.r, rgb.g, rgb.b))/ 2 
                   < pbnote.CONSTS.BLACK_CUTOFF;

    // This is the luminosity method, which doesn't seem to give as good results
    //var isBlack = (0.21 * rgb.r + 0.71 * rgb.g + 0.07 * rgb.b) 
    //               < pbnote.CONSTS.BLACK_CUTOFF;
    if (!isBlack) {
      currentInt |= (1 << bit);
    }

    bit += 1;
    if (bit == 32) {
      bit = 0;
      pushUInt32(result, currentInt);
      currentInt = 0;
    }
  }
  if (bit > 0) {
    pushUInt32(result, currentInt);
  }
}

The code on the Pebble side does nothing more than load the bitmap using gbitmap_create_with_data and display it.

Amazingly enough, images rendered on Evernote for Pebble work:

pebble-screenshot_2014-04-17_12-37-10 pebble-screenshot_2014-04-17_12-37-06

I’m using the Evernote Thumbnail API to download a bitmap, converting it to a black-and-white bitmap, adding the appropriate Pebble bitmap header and sending it over to the Pebble for display.

pebble_image_conversion

It might be worth looking at compressing the bitmap prior to sending over to the Pebble, but I’d need to balance reduced battery consumption on the Pebble due to less Bluetooth messages being sent, against the increased battery consumption on the Pebble due to increased CPU usage to decompress the image.  It would also be smart to look at dithering the image to replicate grey-scale.  If anyone has a library to do that in JavaScript, let me know!

About Damian

DamianPortait10PercentDamian Mehers is a Senior Software Engineer at Evernote, currently focused on Evernote and wearable devices.  Damian created  Evernote for the Pebble and the Samsung Galaxy Gear.  He also worked on Evernote Food for Android, and created the initial release of Evernote for Windows Phone.

@Damian Mehers damian@evernote.com

Tagged , , , | Leave a comment

Indexing Handwritten Images: From Latin to CJK

With the recent addition of Chinese support, Evernote Recognition System (ENRS) indexes handwritten notes in 24 languages. Each time we add another language, we have to overcome new challenges specific to the particular alphabet and style of writing.

Yet another batch came once we approached the CJK group of languages — Chinese, Japanese and Korean. These languages require support for two orders of magnitude more symbols, each being vastly more complex. Writing does not require spaces between words. Fast scribbling shifts to cursive, making interpretation rely heavily on context.

Before going into specifics of CJK support, let’s first look at the challenges that need to be addressed for Latin script recognition. For our engine, the first step to parsing a handwritten page is finding lines of text. This already could be a non-trivial task. Let’s take a look at an example:

Screen Shot 2014-04-09 at 2.52.39 PM

Lines could be curved. Letters from different lines cross each other and the distance between lines varies randomly. The line segmentation algorithm has to follow the lines, untangling the accidental connections as it goes.

The next challenge comes once the lines are extracted — how to split them to words. This task is mostly simple for printed texts, where there is a clear difference in distance between letters and words. With handwriting, in many cases it is not possible to tell just by distance whether it is a symbol or a word break:

Screen Shot 2014-04-14 at 9.32.56 AM

What could be helpful here is understanding what is written. Then, by understanding the words, you can tell where each begins and ends. But, this requires the ability to recognize the line as a whole, not just reading word after word — the way most regular OCR engines operate. Even for European languages, the task of recognizing handwriting turns out to be not that different from the challenges of processing CJK texts. To illustrate, here is an example of a Korean handwriting:

Screen Shot 2014-04-14 at 9.33.05 AM

Each line’s flow needs to be traced similarly, with possible overlaps untangled. After a line is singled out, there is no way to even attempt a space-based word segmentation. As with European handwriting, the solution would be to do recognition and segmentation in a single algorithm, using the understanding of recognized words to decide where the word boundaries are to be found.

Now, let’s look at the steps for the process of symbols interpretation. It first estimates where individual characters could begin. These would be smaller whitespaces between strokes and specific connecting elements, characteristic of cursive handwriting. We will have to ‘oversegment’ here, placing extra division points — at this point we have no clear idea if a segmentation point is correctly placed outside of symbol boundaries, or falls inside it:

Screen Shot 2014-04-14 at 4.49.58 PM

To assemble the actual symbols, we will try to combine these smaller parts into bigger blocks, estimating every combination. The next image illustrates an attempt to recognize the combination of the first two blocks:

Screen Shot 2014-04-14 at 4.51.28 PM

Of course, this means that we will have to recognize many more symbol variants than there are actual characters written. And for CJK languages, this in turn means that the recognition process becomes much slower than it is for Latin languages, as estimating different combinations is multiplied by so many more symbols to consider. The core of our symbol recognizer is a set of SVM (“Support Vector Machine”) decision engines, each solving the problem of recognizing its assigned symbol ‘against all the rest.’

If we need to have about 50 such engines for English (all Latin letters + symbols), in order to support the most common Chinese symbols, we would need 3,750 of them! This would’ve been 75 times slower, unless we devised a way to run only a fraction of all these decision engines each time.

Our solution here is to first employ a set of simpler and faster SVMs, which would pre-select a group of similarly written symbols for a given input. Such an approach usually allows us to net only five to six percent of the whole set of characters, thus speeding up the overall recognition process about 20 times.

To decide which variants of the multiple possible interpretation of the symbols of handwriting should be selected for the final answer, we now need to refer to different language models — context that would allow us to create the most sensible interpretation of all the possible symbol variants generated by the SVMs. Interpretation starts with simply weighing up the most common two-symbol combinations, then raising the context level to frequent three-symbol sequences, up to dictionary words and known structured patterns — like dates, phones, and emails. Next comes probable combinations of the proposed words and patterns set together. And at no point in the process before you weigh all the possibilities in depth, can you tell for sure what is the best way to interpret the writing of that line. Only evaluating millions and millions of possible combinations together, similar to how “Deep Blue“ was analyzing myriad of chess positions playing against Kasparov, is it possible to come up to the optimal interpretation.

Once the best interpretation for the line is established, it finally can define the word segmentation. Overlaid green frames on the images below show the best segmentation to words the system could devise:

Screen Shot 2014-04-14 at 5.01.31 PM

Screen Shot 2014-04-14 at 5.02.00 PM

And, as you can see, the process turned out to be mostly the same for both, European and CJK handwriting!

Leave a comment

In depth: Descriptive Search in Evernote

The following is a behind the scenes walkthrough of Descriptive Search within Evernote by our Augmented Intelligence Engineer, Adam Walz. For our public announcement of Descriptive Search, click here.

Search Box Evernote

Evernote has always had a great keyword search experience being able to surface notes that match not only in the body of the note but also within images and documents. However, when confronted with a blinking cursor in the search bar we often find ourselves struggling to remember what exactly we named that particular note. We realize that while keywords are an integral part of the search experience, we as humans have a natural tendency to relive our memories by the places we’ve been, the dates we created our notes or even the types of files the note contains. How often do you wish you could just search by typing San Francisco last week ? Now, with Descriptive Search for Mac you can!

Screen Shot 2014-04-08 at 1.43.44 PM

Realizing that search needs to evolve from keywords, Descriptive Search was our attempt to create a natural extension of your thought process. Because this is an ambitious attempt, we decided to start with support for the English language on the Mac client. In forthcoming releases, we will expand to additional languages and platforms.

 

Tearing Open The Seams

Evernote has always had an advanced Search Grammar which also allows you to search the metadata associated with your notes and resources. However, using it requires a syntax that is difficult to remember, and far from intuitive.

For example, a search for all your notes that contain all ‘office documents’ would entail typing the query:

any:
resource:application/msword
resource:application/vnd.openxmlformats-officedocument.wordprocessingml.document
resource:application/vnd.ms-excel
resource:application/vnd.openxmlformats-officedocument.spreadsheetml.sheet
resource:application/mspowerpoint
resource:application/vnd.openxmlformats-officedocument.presentationml.presentation

Now that’s a query that I wouldn’t expect anyone to remember or want to type! Descriptive Search allows you to do this by simply typing ‘office documents’.

Our implementation goal for the first version of Descriptive Search was to support a large subset of  what our Search Grammar supports by adding a natural language query interface so you can use everyday language to find notes the way you remember them.

At an implementation level, this comes down to a classic Parsing problem. Parsing is the process of analyzing the syntax of a piece of text to pull out the important parts and understand the meaning behind the text.  When we have to deal with the nuances of multiple languages, dialects, and an ever expanding dictionary things get interesting.

Natural languages are characterized by their lack of a strict grammar. You could write the same search many different ways, and Evernote should be able to understand that any number of queries could have the same meaning. In the world of natural language processing this is called a semantic grammar. Our semantic grammar is specifically created to pull out the meaning in your query, and throw away anything that is not helpful in finding your notes.

parse-tree.png

This all comes together in the following sequence of steps:

1.  Preprocessing Step

Like most natural language systems, our goal in the preprocessing step is to sanitize the users input query to remove irrelevant language nuances. This begins by detecting the words in the users input query.  While this might seem like a trivial task, finding what constitutes a word for languages like Chinese and Japanese gets into difficult areas of natural language processing. This becomes one of the most critical steps to get right. Since we did not want multiple conjugations of a phrase to cause parsing to fail, we then remove common words from the input language (stop word detection and removal) and condense the words down to their root word (stemming).

Like everything else we do at evernote, we also wanted to make your job easier, so we expand your query using our Type-Ahead Search system. This means faster, more accurate searches for the user with less typing.

preprocessing.png

2. Honoring User Specified Contextual Hints

It is often the case where the meaning of a search can be ambiguous when seen only one word at a time. The word ‘cute’ in the previous example could be a tag, part of a notebook title, or simply a keyword in the text of your notes. However, if you instead specified ‘tagged cute’, we look at the neighboring words to determine if you specified a contextual hint for the word. In this case the hint would be ‘tag’. We then verify that this is a good suggestion by doing a quick cross reference against your tag list to make sure that you actually do have a tag named ‘cute’.

hints.png

3. Grammar Parsing

The next step is what makes Descriptive Search so powerful. A word such as ‘image’ may not appear as a keyword anywhere in your notes, and even if it did, when you type ‘image’ you are most likely not looking for a keyword in the text of your notes. You want to see notes with have attached image files. This is where parsing comes in.

What we have at the heart of this system is a Semantic Grammar that is very carefully handcrafted to meet the specifications of the particular user language, such as English. This grammar takes into account the nuances of the language with several very advanced parsing rules, even finding synonyms of the words we want to detect. This grammar is then cross compiled to the native platform which also gives us the benefit of maintainability and portability across platforms.

At runtime, we pass the preprocessed query through this semantic grammar parser which looks for character patterns that closely match one of the rules in our grammar. All matched character patterns are then replaced with an unambiguously formatted search token.

As seen in the example below, the pattern ‘image’ detected by the grammar parser is replaced by its equivalent evernote search grammar resource token.

parsing.png

4. Content Matching

While the Semantic Grammar can cover patterns that are common across all our Evernote users like the existence of date ranges or file types, there is another very important category of queries which is derived from the users own personal content, e.g. your own notebooks or tags or places you’ve been.  In this step we will close this gap by taking the unmatched words left in your query and checking them against your own user index.

Going back to our example query from the previous step (‘cat tag:cute resource:image/*’), the word cat is still unmatched. We cross reference the unmatched words in the query against the metadata in the search index to find that maybe you have a notebook named ‘cat pictures‘ and that you have a tag named ‘cats‘. In the case of multiple metadata matches like this, we use a probabilistic model to determine which of these suggestions closely matches your intent and query. Remember, if we happen to get this wrong, the Contextual Hint step can be used to provide more context about your meaning.

content match.png

5. Suggestion Creation

We have now found a match for all of the important words in your search. However pulling out the meaning of your query behind the scenes is only part of what we feel makes a search “Descriptive”. The user experience matters a great deal to us and we know you wouldn’t want to see a result in the form of “notebook:cats tag:cute resource:image/*”

The Suggestion Creation step formats the search grammar result into an an equivalent descriptive phrase in your language making the suggestions conversational and easy to read.

suggestions.png

What’s Next?

If you haven’t already used this feature on the Mac client I encourage all of you to give it a try. If you need a little help getting started you can refer to our knowledge base article. At the same time, our team is hard at work bringing this experience to all the other platforms and increasing our support for different languages and a broader range of queries.

Keep an eye out for these new features with coming releases.

About Adam

adam-walzAdam Walz is an Augmented Intelligence Engineer at Evernote where he is focused on taking the Search experience to the next level. The Augmented Intelligence team is on a mission to improve the search experience for Evernote and make memories more discoverable.

@adamwalz

[Opening] Join Adam and the ‘Augmented Intelligence’ Team – we are hiring! Software Engineer

Tagged , | Leave a comment

In depth: Pebble OAuth configuration using Node.js

 The following is a behind the scenes walkthrough on building apps for the Pebble Smart Watch by our lead wearables engineer, Damian Mehers. For our announcement of Evernote for Pebble, click here.

pebble-story-232x232

When Pebble released the new Pebble 2.0 SDK and app store, it suddenly became possible to do a whole lot more with Pebble apps than before, including setting up a configuration screen for your Pebble App.

In this post, I’ll take you through my journey of setting up the Pebble App configuration to use OAuth to authenticate to a web service (Evernote in this case), by way of Node.js.  I’ll also share my experience publishing the Node.js app to Amazon’s cloud services (AWS), and Microsoft’s cloud services (Azure).

How Pebble Configuration works

You might be wondering: how on earth can you do configuration on that tiny Pebble screen?  The answer: you can for some things, but for others, like authentication, you can’t.

What you can do though is configure your Pebble app via your phone’s nice, big screen, and then pass configuration data from the phone to the watch.

A typical Pebble app will have two components: a C app that runs on the Pebble watch and a companion app that runs on the phone.  The companion app communicates with the watch app and does the heavy-lifting of talking to the internet to access data, process it, and send it to the Pebble for display, interaction, and so on.

The phone-based companion apps can be written in Objective-C if they run on iOS, or in Java in they run on Android, or—my personal favorite—they can be written in JavaScript, in which case they run on both iOS and Android.

Your companion app’s JavaScript runs within a JavaScript engine contained within Pebble’s official Android and iOS management apps, which you can download from their respective app stores.

image_thumb27

Each Pebble app that you create has a configuration file, called appinfo.json. In this file you can indicate that your app supports configuration by modifying the capabilities item:

{
  "uuid": "e0898619-eccd-4370-9141-2ce19b91c432",
  "shortName": "DamianDemo",
  "longName": "DamianDemo",
  "capabilities": [ "location", "configurable" ],

Once you do this, when you open the Pebble iOS app you’ll see a “Settings” button under the app you’ve developed (in this case ‘DamianDemo’).  Below I’m opening the iOS Pebble app (in an iOS folder I’ve called “Connected”), and I’m showing the Settings button.

image_thumb14 image_thumb15

What happens when you tap the “Settings” button? In the companion app’s JavaScript code you must register a callback to be invoked when the user tries to configure your app:

Pebble.addEventListener("showConfiguration", function() {
  var url = '...';
  console.log("showing configuration at " + url);
  Pebble.openURL(url);
});

This will open up a browser within the Pebble iOS app to the URL you specify, and there you can display configuration options and eventually return data to your JavaScript companion app.  In this case, I want to display an OAuth authentication screen, authenticate the user, and return OAuth tokens back to my Pebble app.

I decided to use Evernote as an example.

Finding an OAuth example

I went searching for an Evernote OAuth example and quickly came across one that was based on Node.js at the Evernote GitHub repository:

image_thumb16

I’d never used Node before, but it was very easy to install, add dependencies, and run:

image_thumb31

Accessing the Node.JS Evenote OAuth example locally

I decided to make sure it was working properly by firing up a browser on my desktop, and, sure enough, it seemed to be working:

image_thumb19image_thumb20image_thumb21

image_thumb28

Invoking the OAuth example from the Pebble app

Next, I updated the Pebble’s JavaScript companion app, so that when the user clicked on the “Settings” button it navigated to the Node.js app on my desktop (my desktop’s IP address is 192.168.0.43):

Pebble.addEventListener("showConfiguration", function() {
  var url = 'http://192.168.0.43:3000';
  console.log("showing configuration at " + url);
  Pebble.openURL(url);
});

image_thumb29

Now when I tapped the “Settings” button I was indeed taken to the Node.js app running on my desktop:

image_thumb23image_thumb30image_thumb25

Works locally but not from the Pebble iOS App?

Unfortunately the “Re-authorize” button did not respond when I tapped it.  But it worked when I accessed it through the browser on my desktop (same machine as the Node.js app). I went through all kinds of scenarios in my mind: perhaps some kind of JavaScript was disabled?  Maybe some re-direct wasn’t working?

After an embarrassingly large amount of time I discovered the cause when browsing through the Evernote OAuth sample code I was running: the code was set to redirect to localhost.  That was why it worked on the desktop, but failed on the iOS device.  I needed to make it redirect to the Node.js app, so I changed the code to redirect to the Node app I was running on my desktop, and it worked:

var Evernote = require('evernote').Evernote;

var config = require('../config.json');
// var callbackUrl = "http://localhost:3000/oauth_callback";
var callbackUrl = "http://192.168.0.43:3000/oauth_callback";

// home page
exports.index = function(req, res) {

Changing the OAuth example to return values to the Pebble app

When I say it worked, I mean that it did what it was supposed to do, but I needed it to return the values to my JavaScript code.  This is the Node.js app code that gets invoked once the authentication is complete (in the redirect that wasn’t working initially):

// OAuth callback
exports.oauth_callback = function(req, res) {
  var client = new Evernote.Client({
    consumerKey: config.API_CONSUMER_KEY,
    consumerSecret: config.API_CONSUMER_SECRET,
    sandbox: config.SANDBOX
  });

  console.log("Calling getAccessToken");
  client.getAccessToken(
    req.session.oauthToken, 
    req.session.oauthTokenSecret, 
    req.param('oauth_verifier'), 
    function(error, oauthAccessToken, oauthAccessTokenSecret, results) {
      console.log("getAccessToken got " + oauthAccessTokenSecret);
      if(error) {
        console.log('error');
        console.log(error);
        res.redirect('/');
      } else {
        req.session.oauthAccessToken = oauthAccessToken;
        req.session.oauthAccessTtokenSecret = oauthAccessTokenSecret;
        req.session.edamShard = results.edam_shard;
        req.session.edamUserId = results.edam_userId;
        req.session.edamExpires = results.edam_expires;
        req.session.edamNoteStoreUrl = results.edam_noteStoreUrl;
        req.session.edamWebApiUrlPrefix = results.edam_webApiUrlPrefix;
        res.redirect('/');
      }
    });
};

You can see that it redirects back to the home page, but I want it to redirect back to the iOS Pebble app, so that it can hand the result back to my JavaScript companion app.  There is a standard way to do that, defined by Pebble.  You need to redirect to pebblejs://close passing any parameters you wish.

This is my updated code:

      } else {
        // store the access token in the session
        var result = { 
          oauthAccessToken : oauthAccessToken,
          oauthAccessTokenSecret : oauthAccessTokenSecret,
          edamShard : results.edam_shard,
          edamUserId : results.edam_userId,
          edamExpires : results.edam_expires,
          edamNoteStoreUrl : results.edam_noteStoreUrl,
          edamWebApiUrlPrefix : results.edam_webApiUrlPrefix
        };
        var location = "pebblejs://close#" + encodeURIComponent(JSON.stringify(result));
        console.log("Warping to: " + location);
        res.redirect(location);
      }

image_thumb26

Deploying to a server

I wanted to run my Node.js OAuth helper app on a server, rather than on my local desktop, so that it would work even when my desktop wasn’t running.

I started off with Amazon Web Services

Amazon Web Services

Of course I jumped in far too quickly, and went and created an Amazon EC2 instance, which is complete machine, into which you can SSH and then install and configure whatever software you wish.

Turns out there was a far simpler way of doing things. Amazon’s Elastic Beanstalk, which lets you easily deploy Node.js apps, takes care of all the infrastructure behind the scenes, without my needing to perform all the configuration I’d done manually when setting up the EC2 instance.

It was still a little fiddly, with lots of little steps.

But once I’d deployed it, it did work just fine.  I was uncomfortable using “http” for the the Node app, since theoretically someone could sniff the packets and see the OAuth tokens in plain text, so I tried shifting to “https”. Try as I could, I couldn’t get it to work.  After much browsing and reading I came to the conclusion that I’d need to install my own custom certificates and my own custom domain to get it working, which seemed like overkill.

(If you know of a way of accessing Elastic Beanstalk apps using https without using a custom domain, please do let me know in the comments.)

Microsoft Azure

I decided to try Azure instead since, from what I’ve read, it supports https when accessing Node.js apps via the standard Azure hosting domain.

I was happily surprised at how easy it was to deploy the Node.js app to Azure.  I followed their tutorial and within 10 minutes I was up and running, pushing updates using a simple “git push”.  Now my JavaScript configuration launch code and OAuth callback both use https://mydomain.azurewebsites.net/.

Conclusion

Using a Node.js server to handle Pebble configuration such as OAuth was remarkably easy, and since I’d been writing so much JavaScript code in my phone-based Pebble companion app, it seemed natural to continue in Node.js.

I was able to take the Evernote Node.js OAuth example and by changing less than 10 lines of code, get it up and running and passing values back to the Pebble.  The use of https, combined with the fact that the Node.js app stores nothing locally (it just acts as a relay), makes for an attractive solution.

About Damian

DamianPortait10PercentDamian Mehers is a Senior Software Engineer at Evernote, currently focused on Evernote and wearable devices.  Damian created  Evernote for the Pebble and the Samsung Galaxy Gear.  He also worked on Evernote Food for Android, and created the initial release of Evernote for Windows Phone.

@Damian Mehers damian@evernote.com

Tagged , , , , | 1 Comment

AirPair Launches Evernote Community Powered API Live Help

Our developer community is broad and full of solid engineers building ways to save and share content with Evernote. We want help companies find top level support for the Evernote API within a straightforward directory.

airpair

Today we launched our Evernote community expert channel on AirPair. We look forward to referring our top community developers for projects involving integrating the Evernote API into your products.

About AirPair

AirPair is a high quality network of software experts on the web that assists developers to quickly overcome any software challenge or learn a new technology. Their experts have a deep knowledge across many technology stacks and solutions (Hadoop, iOS, SAP integration, MongoDB sharding, etc). AirPair accelerates software development by “pairing” experts with customers in real-time via video and screen sharing – leading to better software, produced faster, and at lower costs.

Book hours with an Evernote API expert now »

Related stories:

Tagged , , , | Leave a comment

Evernote developers get 50% off for Box Dev conference!

logo

Join Evernote and over 1,000 developers and entrepreneurs for Box Dev — Box’s first annual developer conference on March 26, 2014 at Fort Mason in San Francisco.

boxdev

The day will feature platform product unveilings, deep-dive technical sessions on the Box API’s, thought-leadership sessions on building for the enterprise, and talks by:

  • Aaron Levie (co-founder and CEO of Box)
  • Phil Libin (CEO of Evernote)
  • Joe Lonsdale (co-founder of Palantir)
  • Ben Horowitz (co-founder and partner at Andresseen Horowitz)
  • and many more!

In addition to a full day of technical workshops and talks,  the day will end with an after party of epic proportions, including DJ and open bar.

RSVP now before spots fill up! Also, as an added bonus, all Evernote developers save 50% using the following promo code: evernotedev

Tagged , | Leave a comment

Join us at the Evernote Platform Night @ SXSW

sxsw-banner-updated

Join the Evernote crew in Austin during SXSW for a night dedicated to our community of users, developers, and apps that save and sync with our cloud platform. We’ll be kicking off our plans for the year along with inviting apps from the Evernote App Center to join us and show how their products work.

Where: Frank’s – 407 Colorado St Austin, TX 78701
When: Sunday, March 9th, 6pm – 8pm
RSVP: evernotesxsw2014.eventbrite.com

Thousands of apps sync and save content into Evernote. With over 30,000 developers and 85 million users, we aim to be your “second brain” where anything can be stored, searched, and remembered. During our SXSW event, we’ll have some announcements along with drinks, food — and especially our partners and developers currently building with the Evernote API!

If you are considering integrating the Evernote functionality into your product, learning more about the platform, or meeting the Evernote API and Partnerships teams this is a great opportunity to see examples and find the resources to get started.

We look forward to meeting our community in person,

RSVP: evernotesxsw2014.eventbrite.com

@evernote_dev
facebook.com/evernotedevelopers
dev.evernote.com
#evernoteplatform

Tagged , , , | Leave a comment

Evernote @ DeveloperWeek SF 2014

dwlogos-03

Join us this weekend as we help kick of DeveloperWeek 2014 in San Francisco! This Friday night is the kick-off party and we’ll be at Rackspace HQ for the BIG hackathon this weekend.

About DeveloperWeek 2014

devweek
DeveloperWeek is a massive full-stack Developer Conference + Festival where thousands of developers and entrepreneurs build new apps and add-ons and stay current on 100+ developer tools, technologies, and languages.

Register for DeveloperWeek 2014: http://developerweek.com/register/

About the DeveloperWeek 2014 Hackathon

hackathon-devweek-2014
The DeveloperWeek Hackathon is a 30-hour app-building contest in downtown San Francisco and the official kick-off for DeveloperWeek 2014! The purpose of the hackathon is to give developers, designers, and entrepreneurs the chance to pitch app ideas, form teams, build a prototype of their app, and present to our hackathon judges.

Get your hackathon tickets here: http://www.developerweek.com/hackathon/

Our team will be looking to meet developers, designers, and startups that are building great products. If you’re around, find us and say hello!

See you in a few days – RSVP using these links:

Leave a comment

Inside Evernote: Ed Roskos

Ed Roskos is a Senior Software Engineer on the Platform team. He has been with Evernote for 3 years and has been involved with major efforts in scaling and improving our infrastructure.

What does the Platform team work on at Evernote?

The Platform Team works behind the scenes on advanced service backend features, service scalability and stability, and with client teams in how they interact with the service.  Advanced features in the past have included enhancements to our sharing infrastructure, major updates to our caching subsystems, a rewrite of our synchronization engine, and a rewrite of our security access control subsystem.  Before handing them off to dedicated teams, the Platform Team also developed the original Evernote Business backend and related notes technology.  Keeping an eye on service scalability and stability involves instrumenting code and working with our Operations Team to understand current bottlenecks and issues.  These efforts often require us to devise clever ways to refactor code and improve the core infrastructure that supports our service.  Naive solutions often fail to scale adequately for servicing millions of users.  These efforts also lead to discussions with client teams to help them find defects and optimize their use of the Evernote Service.

What role do you play on the Platform team?

My role on the Platform team is as a developer, currently focused on sharing, synchronization, and access control.

What are the big challenges?

The biggest challenges for the Platform Team are to consider the maintainability and scalability of our solutions, manage the end-to-end rollout on live systems, and avoid breaking clients. Coding solutions to challenging problems can require additional care when accounting for live system upgrades, and we often have to write code that runs for a week or more to allow a transition between two solutions.  We also have to account for existing database schema and consider how to map newly added, persistent state into our business model objects.  Care must also be taken to instrument code sufficiently to know that features are working properly when deployed at full scale.  Evolution of, and additions to, the API and service model are ongoing as the Evernote Service continues to grow and seemingly safe changes in behavior or state can break deployed clients.  It is important to work with our QA Team to verify this doesn’t happen.

What is the most satisfying part of your job?

Knowing that by keeping the lights on while expanding and scaling the service, we make life better for millions of people.

What is your background?

I’m a software generalist.  I’ve worked in early stage startups as well as large companies in roles from management to development.  I previously worked on speech recognition application technology, networking systems and core routers, high performance storage systems, and web-scale search.  I look for jobs where I can work with smart people on tough challenges that result in products that make life better for our customers.

Who has been your biggest mentor?

I’m not sure I have a single “biggest” mentor.  There is no shortage of super-smart people in the world as long as your mind is open to new ideas, you are willing to admit you don’t have all the answers, and you immerse yourself in the right environments.  I have been fortunate to learn a lot from many people, some engineers and some not.  Sometimes, the most profound ideas come from people you might least expect to have them.

What’s your favorite Evernote feature?

It has to be the combination of the web clipper and related notes technology.  I love collecting articles on technology, science, history, and geopolitics.  Related notes technology brings up notes that help tie together the relationships between events over time.  And the web clipper’s auto-filer is also nice for helping tag my notes for topic search and perusal.

How do you use Evernote?

In addition to note clipping, I use Evernote to track my task lists and to communicate with friends and family by putting together images and text before e-mailing or sharing notes.

Leave a comment

Synchronization Speedupification

Memory Lane

When we designed our synchronization protocol way back in 2007, we wanted to make sure that a client could use a minimal number of network requests to find all of the content in the user’s account, or only of the relevant changes since the last sync. We chose a “non-locking object-state-based replication scheme based on an account-specific Update Sequence Number (USN) for every object in our heterogeneous, sometimes-cyclic data model”. A client can just say “Hey, what’s new?” and our servers will give back all of the relevant changes in the user’s Notes, Tags, Notebooks, Resources, etc., usually in a single HTTPS response.

This has worked well as a wire protocol, but our original service implementation had some scalability challenges in the last six years as we grew from two empty shards in February 2008 to more than four hundred shards containing billions of notes today. It can take a lot of IO operations to find the correct information to give the client just the right set of objects for its next SyncChunk.

In our original design, every shard stored the metadata for around 100,000 accounts within a MySQL database running on a RAID1 of 15krpm spinning disks. Each object type was stored in its own table, with a synthetic primary key and a secondary index to efficiently find entries by user, sorted by USN. For example, here are the relevant bits of our ‘notes’ table:

CREATE TABLE notes (
 id int UNSIGNED NOT NULL PRIMARY KEY,
 guid binary(16) NOT NULL,
 user_id int UNSIGNED NOT NULL,
 notebook_id int UNSIGNED NOT NULL,
 title varchar(255) NOT NULL,
 update_sequence_number int UNSIGNED NOT NULL,
...
 KEY user_id_usn_idx (user_id, update_sequence_number),
 UNIQUE guid_idx (guid)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

The three keys in this table all make it possible to find a single entry, or a range of entries, in efficient (logarithmic) time. But actual rows are clustered on disk, ordered by primary key. To find multiple rows by a secondary index (e.g. user_id, above), the database must first traverse the secondary index, and then follow those pointers to the actual disk pages where each separate row resides.

When a client asked the service “Give me up to 100 objects from my account with a USN higher than 8476”, the user’s shard would have to check up to 9 different tables for relevant entries and then merge those results together to return only the 100 entries with the lowest matching USNs. This was implemented as a single massive SQL UNION, which would crawl the user_id secondary index on each table and then load the primary pages for each matched row. In a worst-case scenario, this could potentially require thousands of non-sequential pages to be loaded from disk to satisfy one request.

That’s a ton of expensive I/O, which translated into slow replies for our clients. This problem was multiplied by the rapid growth in notebook sharing by individuals and businesses, which require separate client queries for each notebook. Our ops team bought us time by transitioning our database from spinning disks to SSDs, but the root problem required a software optimization.

Index to the Rescue

To make synchronization more efficient, we wanted to avoid hitting a dozen different tables to determine what to put into each sync chunk.  To support our growth in shared notebook and business usage, as well as implement new features such as contentClass sync, we wanted to place enough information in one table to minimize the unnecessary data brought back from MySQL into our Java middle layer.

Consider further that we had to query more rows from the entity tables (notes, tags, etc.) than we would return.  To return three entries from notes and tags, we would query three <note ID, USN> pairs and three <tag ID, USN> pairs and then sort by USN to find the entries to return.  Round trips to the database are expensive and so querying row by row in hopes of reading only the ones you need can increase the cost.  And when MySQL is asked to filter on values from the entity tables, additional table joins are often required.

So we embarked on our quest to design one table to index them all: the “sync index” table.  This one table would be queried to determine the primary keys of the candidate NoteStore entities to read for further consideration.  Many entities are efficiently filtered within MySQL by accessing a single table and treating each row independent of any other values in the database.

We chose a primary key of <user_id, USN> so that a user’s sync index rows would be clustered on disk in the order needed for synchronization.  A single database page read returns rows representing entities of various types of efficient filtering.  The rows are designed to be small to pack as many into a single I/O operation as possible.  The information needed per row includes:

  • Expunged status: Was the entity expunged from the service at the given USN?

  • Active status: Linked notebook synchronization hides inactive notes.  If a note becomes inactive, we send an “expunge”, or skip the note if not including expunged GUIDs in the chunk.

  • Entity type and object ID: We need to know the type (tag, note, etc.) and object identifier that the row refers to so we query the service entity.  An entity is either active, inactive, or expunged at any one time.  We therefore combine the entity type (note, tag, etc.) with a “modifier” (active, inactive, expunged, etc.) into a single 1-byte field for compactness.

  • Containing Notebook ID: Most permissions in Evernote are granted at the Notebook level.  For linked notebook and business synchronization, the notebook identifier allows us to filter most notes and resources without accessing those tables.

  • Content class: Applications such as Evernote Hello and Food define a contentClass on notes and can synchronize only those notes matching a common prefix.  To save space, we use a 32-bit hash to approximately match the first 32 characters rather than storing the entire content class.

The above covers the “current” state of an entity.  Some historical state is also needed.  When synchronizing in a context allowing access to a proper subset of notebooks in the account, the service will send an “expunge” event when a note is moved from a notebook to which you have access into one to which you do not.  We capture this state as “moved” records in the sync index, adding “moved” to our entry type modifier values mentioned above.  We also add a column to record the previous notebook ID.

There is also new state that was not previously captured.  Many of our clients currently synchronize a business account one linked notebook at a time.  This allowed them to re-use existing, proven linked notebook logic to sync and detect lost access to a notebook but increases the round-trips to the service proportional to the number of notebooks that a user has joined in the business.  The sync index now records historical records of “lost access” by a recipient to a notebook.  The service can now send an “expunge” informing the client that access has been lost.  We again use the entry type modifier to record “lost access” and add a field for the user ID of the recipient who lost access.  Evernote clients will switch to synchronizing all of their notebooks from a business in one pass.

The resulting table is thus defined as shown below.  Nullable fields use only a bit when the value is null.

CREATE TABLE IF NOT EXISTS sync_index (
 user_id int UNSIGNED NOT NULL,
 update_sequence_number int UNSIGNED NOT NULL,
 entry_type tinyint NOT NULL,
 notebook_id int UNSIGNED,
 grave_notebook_id int UNSIGNED,
 object_id int UNSIGNED,
 guid binary(16),
 content_class_hash int UNSIGNED,
 recipient_id int UNSIGNED DEFAULT NULL,
 service_updated TIMESTAMP DEFAULT CURRENT_TIMESTAMP NOT NULL,
 PRIMARY KEY (user_id, update_sequence_number),
 KEY objectid_entrytype_idx (object_id, entry_type)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 ;

For the programmers reading this, one obvious question might have come to mind: how is the sync_index state, which is replicated from various service entity tables, going to be kept up to date with those tables?  The answer was to use a Hibernate interceptor.  All of the changes to our service entities go through Hibernate.  The interceptor code that we wrote takes care of the denormalization and hashing.  If you change a note attribute, the interceptor will check to see if it was contentClass and update the note and resource rows of the sync index table accordingly.  If you move a note from one notebook to another, the interceptor verifies whether a new “moved” historical record should be created for the previous notebook, whether a prior historical record for the now-current notebook should be removed, and will update the notebook identifiers on all note and associated resource rows in the sync index to allow proper filtering on notebook ID for linked notebook and business synchronization.  Changes to shared notebook records result in creating or removing lost access rows.  All of this happens behind the scenes when our engineers work on the service API code.  They don’t need to think about what to do … it happens automatically.

Filling the Sync

Once we finished the code to properly store new and updated entries in the sync_index, we had to find a way to load the prior six years of history into the sync index to permit new clients to synchronize old accounts. It was harder than we expected to do this without affecting users or producing any incorrect entries. After a few weeks of trial-and-error, we came up with the following recipe:

  1. For each table (notes, notebooks, etc.), SELECT … INTO OUTFILE with the desired columns for the sync index.

  2. Use LOAD DATA INFILE to load that into the sync_index.

  3. Go back over every table to find inserted entries that were made obsolete by runtime changes between steps #1 and #2. Dump their primary keys to disk and then LOAD them into a (small) temp table.

  4. Use a MySQL multi-table DELETE to join that temp table against the sync_index and only remove matches.

Steps #1 and #2 were at least three times faster than the more obvious INSERT … SELECT statement, and they avoided locking any rows, which prevented ugly timeouts in the running application. Steps #3 and #4 cleaned up after the non-transactional insert, also avoiding painful locking on the big source tables from a more straightforward DELETE.

Did it Work?

Verification of our work took multiple forms.  A new unit test framework was developed and used to verify the correct values in the sync index table and results of synchronization.  This battery of tests runs for all of our continuous integration builds.  Our system test team performed repeated regression tests on staging platforms.  In the code, a number of sanity checks were added, such as verifying the state of a sync index row against the service entity when we add it to the sync chunk.  We also ran the previous and current sync algorithms side by side to verify the end results correctness.  Lastly, we built infrastructure and service configurations to control the introduction of the new technology into production use.

We tested the times for full synchronization of one of our accounts with 2456 personal notes and 2861 notes across 31 linked Business notebooks. In our tests, this synchronization was around 99% faster with the new sync index than before.

The user-visible improvements are reflected in the median processing times for individual sync functions. For example, this graph shows the change in median response times for calls to getLinkedNotebookSyncChunk on one shard before and after the sync_index changes:

MedianDuration_s12_getLinkedNotebookSyncChunk

In addition to improving the sync times for our users, these changes also significantly reduced the IO and CPU usages of our shards. This graph shows the load average on one of our eight-core shards over the last week (blue) and a random week in November (green):

Shard12_LoadAvgBeforeAfter

This will give our servers more head room to support future features and larger accounts as our users upload more data.

We have a few other optimizations in the pipeline that should improve the performance even further, but we’re pretty excited with the improvements so far. Thanks for your patience as we continue to scale Evernote to store all of your memories!

5 Comments