Rapleaf is a San Francisco-based startup with an ambitious vision: we want every person to have a meaningful, personalized experience. We want you to see the right content at the right time, every time. However, delivering relevant, personalized content requires a deep understanding of individuals’ attributes. At times, our knowledge of individuals is incomplete or in an irregular, unusable form and we need a way to fill in the gaps. For cases like these, we’ve built internal tools for data deduction and sanitization.

When tools like these are very general-purpose in nature, we add them to an internal API accessible to our whole development team. Today, I’m happy to announce that we’re starting an initiative to open up these tools to the public via the Utilities API. We hope that this API will allow external developers to leverage our toolset to improve the quality of their own applications.

Here are the first tools that we’ve added to the Utilities API:

Name to Gender

This function takes a string as a person’s first name and deduces the likelihood that the person has either gender.

Example: “mike” => “Gender: Male, Likelihood: .9946”

Name Deducer

This function takes a string as a user name and attempts to parse it into its constituent components.

Example: “dolegbob42″ => “First: Bob, Middle: G, Last: Dole.”

Name Normalizer

This function takes a string as a name and attempts to parse it into its constituent components.

Example: “mr john g smith iv” => “Prefix: Mr., First: John, Middle: G, Last: Smith, Suffix: IV”

Often, you might find these functions useful in conjunction with one another. For instance, imagine that you have a sign up process that requires a user to provide their email, full name, and gender. Many email addresses contain information about the owner’s name, and a person’s name contains information about their gender. In order to save your users time and increase the likelihood that they follow through with the sign up process, you could eliminate the name and gender fields. In their stead, you could apply name deduction to their email to determine their name and apply gender inference to their first name to determine their gender.

Getting Started

Try out our demo: a simple UI that demonstrates the current offerings of the API. You can also check out the documentation for better information about how to get the API working for you.

We look forward to hearing back from you about ways that you’ve found the API useful and how we can make it better.

A bitset is a data structure designed to store a vector of boolean values very compactly – one bit per value. In practice, they’re a really handy way to save memory. However, we had a situation in one of our extremely memory-intensive applications where a simple bitset wouldn’t cut it. We have over 2500 variables to store bits on, meaning that our bitsets took up over 300 bytes each!

If most or all of the bits were usually set, this would be an unavoidable issue, but in our case, the set bits were very rare – usually no more than 20 or 30. This leads to a large amount of wasted space. The traditional approach to sparse sets like these is to just store the position number of the set variables directly in a collection. To allow for the full 2500 position numbers, we needed a short int, meaning that with this approach, the memory size of the collection is 2 bytes times the number of elements. A sparse set of 30 elements will take a lot less memory than the equivalent bitset (60 bytes versus 313), but in our application, it’s still too much.

What if we could combine the tight-packing benefits of a bitset with the low impact of the sparse set? It turns out that we can. In our application, some of the variables are set pretty frequently (1/4 records have it set) and some are set very rarely (1/10000), with a gradient of various frequencies between. We can exploit this gradient to make really efficient storage decisions. Here’s the graph of frequencies over our set:

It comes down to this: in a bitset, each possible variable in your set costs you one bit, whether or not it’s set. In a sparse set, with our example of 2500 variables, each variable costs 16 bits, but only when it’s set. Comparing these two costs gives a clear tradeoff point. When a given variable is set on at least one of every 16 records, you should store it in a bitset; when it is set on one out of every 17 or more records, then you should store it in the sparse set.

To build this type of set in practice, you just need to get your variables into a list ordered by frequency of occurrence and then apply the cutoff. Everything above should be managed through a bitset, and everything below should be managed by a collection. We found it handy to wrap both of these sets up in a single class so that the user can be indifferent to where the data is stored.

At Rapleaf, every employee is required to be entrepreneurial, and a big part of entrepreneurship is the willingness to invest enormous efforts in initiatives that might not succeed. It has thus always been an important part of our culture to celebrate both well-executed successes as well as well-executed failures.

The cultural recognition of “constructive failure” is identified by Dan Senor and Saul Singer in their book Start-Up Nation as one of the ingredients of Israel’s entrepreneurial “miracle”:

Israeli attitude and informality flow also from a cultural tolerance for what some Israelies call “constructive failures” or “intelligent failures.” Most local investors believe that without tolerating a large number of these failures, it is impossible to achieve true innovation. In the Israeli military, there is a tendency to treat all performance — both successful and unsuccessful — in training and simulations, and sometimes even in battle, as value-neutral. So long as the risk was taken intelligently, and not recklessly, there is something to be learned.

In this spirit, we took a few moments last week to celebrate the memory of a handful of the wonderful projects that were terminated this past year. We derived inspiration from the Mexican holiday Día de los Muertos, also occurring last week, in which dead friends and loved ones are remembered and celebrated, sometimes in “a humorous tone, as celebrants remember funny events and anecdotes about the departed.”

Our event was designated Día de los Proyectos Muertos (Day of the Dead Projects), and each departed project received a poignant (read: spectacularly funny) eulogy given by one of our engineers. There were multiple highlights, but the top crowd-pleaser was a eulogy given for a reporting system that was put to rest after three productive years. The eulogy recalled the conception, birth, high-points and low-points of the system’s “full and meaningful life”, and featured a filtered selection of colorful svn commit comments.

“Zero copies” is a common optimization principle used in high-performance applications. The gist of the technique is to have the smallest number of byte array copies necessary for the server to perform its task. Byte array copies are one of those insidious time-wasters that are hard to understand or even detect until you start looking for them. It seems intuitive to use a perfectly-sized byte array for everything you do: it’s straightforward, reduces the number of arguments you have to pass to each method, but most of all, it’s just simple. However, you actually pay a steep price every time you copy a byte array – the CPU is spinning away shuffling bytes from one memory location to another. It’s actually even worse in Java: every time you create a new byte[], you’re both allocating memory and looping over it to zero each position out. This means you pay a price now as you iterate over every position and a price later when you ultimately have to garbage collect the new byte[] you threw away. An ideal server would never copy a byte[] unnecessarily, preferring to reuse the one over and over again.

Before Thrift 0.4, no matter how much you might want to, there was no way to avoid doing an extra byte[] copy for each binary field that you deserialized, despite the fact that virtually all deserialization happens directly from an in-memory byte[] buffer. Thrift 0.4 changed that by switching the underlying type of binary fields from byte[] to the Java NIO construct ByteBuffer; Thrift 0.5 elaborated on this theme by making it easier to get the byte[]s that everyone expected while still offering access to the ByteBuffer for more advanced operations.

So how do you actually use this feature to speed up your servers? Let’s take a look at a pair of examples. In both examples, we’ll use the following Thrift file as our base:


struct A {
1: required binary foo;
}

service SomeService {
A read();
void logFoo(1: A a);
}


The logFoo method

Let’s pretend that your objective is to log the contents of the foo field to some stream. Here’s how you might do it naively:


private DataOutputStream out;

public void logFoo(A a) throws TException {
byte[] value = a.getFoo();
out.writeInt(value.length);
out.write(value);
}


Seems simple enough. So what’s wrong here? The problem is that calling getFoo() causes a byte[] copy. It’s hidden from you by the method, but it’s happening nonetheless. The copy you create is only used for an instant, becoming garbage after you pass it to write(), and then the entire A object becomes garbage.

Here’s the right way to do it:


private DataOutputStream out;

public void logFoo(A a) throws TException {
ByteBuffer value = a.bufferForFoo();
out.writeInt(value.remaining());
out.write(value.array(), value.arrayOffset() + value.position(), value.remaining());
}


There’s a lot here, so let’s break it down. First, notice that we called “bufferForFoo” instead of “getFoo”. This returns a ByteBuffer instead of a byte[]. Then, we use the remaining() method to get the number of bytes in the buffer that belong to this value. Finally, we go to the write() call, but this time using the “array, offset, length” version of write. This allows us to reference a subarray directly from the array that backs value without any intermediate copying. There’s some trickiness that goes into understanding why the first element in the backing byte array is arrayOffset() + position(), but for right now, trust me that it’s the case.

It’s a small difference with a bit more code, but depending on the size of foo, you could see a substantial boost in performance.

The read method

Now let’s look at things from the other side of the equation. Let’s say that the objective of the read() method is to read the bytes of foo from an input stream and return them wrapped in an instance of A. Here’s what the naive approach might look like:


public A read() throws TException {
// assume that "in" is a DataInputStream
int fooLength = in.readInt();
byte[] value = new byte[fooLength];
in.readFully(value);
A result = new A();
result.setFoo(value);
return result;
}


The problem with this method is that every call leads to a new short-lived instance of A and a brand new perfect-sized byte[]. Both of these will become garbage very soon, and allocating the new byte[] every time is a drag on your CPU.

Let’s focus on how we can reuse the byte[] for now and think about the A instance some other time. There are many possible strategies for caching your buffers, but here’s a simple one:


private final ThreadLocal bufferCache;

public A read() throws TException {
int fooLength = in.readInt();
byte[] value = bufferCache.get();
if (value.length < fooLength) {
value = new byte[fooLength];
bufferCache.set(value);
}
in.readFully(value, 0, fooLength);
A result = new A();
result.setFoo(ByteBuffer.wrap(value, 0, fooLength);
return result;
}


There’s a good bit more to this version. First, note that we’re using Java’s ThreadLocal capability to support us keeping a single byte[] per active thread. This makes sure that each thread servicing a client won’t interfere with any other, and there’s no contention (synchronization) for the thread-local buffer. Next, after we figure out how much we need to read, we make a point of checking if we have enough buffer space to complete the read. If not, we replace our buffer with a new, bigger one. Then we complete the read into the buffer – this time specifying the length we want to read, rather than letting the length of the buffer imply the size of the read. This ensures that on subsequent reads, when fooLength is less than value.length, we don’t try to read more than we wanted to. Finally, instead of passing the entire buffer into the foo field, we pass in a ByteBuffer that wraps just the portion that contains the value we read this time.

By using this technique, we’ve avoided one copy per call plus an unknown number of byte[] allocations – if your record sizes vary a lot, then it will take some time before the buffer has to expand to accommodate the biggest one, but after that, you won’t need any more allocations. If your records are fixed size, then you should reach that point immediately.

One of Rapleaf’s key services is helping marketing companies bring data they have traditionally used in offline contexts to the online world in a privacy-centric way. We have an internal name for this: “safe onlining”.

Safe Onlining: What Is it?

Many companies have marketing databases that have been gathered offline—for example, from customer surveys or questionnaires, or from purchasing histories. These have been used in previous decades to help companies sort the marketing messages they send, mostly by direct mail and sometimes by email or phone. Today, however, people spend much of their time online, and those previous delivery mechanisms are becoming outmoded.

Safe onlining helps businesses make their databases useful in online contexts, in a way that protects people’s online anonymity and privacy. It’s meant to benefit both people and businesses by enabling companies to personalize the online banner ads and content that people see without interrupting their daily activities (unlike direct mail).

Here’s how safe onlining works:

Step 1: Importing and Mapping

The process begins when a customer comes to Rapleaf with a marketing database that they would like to bring online for advertising, analytics, or personalization. Our first step is to import this database into our system. This isn’t trivial—data arrives in a surprising (and occasionally bewildering) array of formats, and we need to normalize things to match what’s in our existing database.

Moreover, data tends to come in high volume, which makes storage and processing a daunting task. We don’t use a traditional relational database for this purpose, so this import process involves converting our customer’s data into dataunits. If you’re interested in learning a bit more about our data storage schema, check out Bryan’s earlier post on Thrift and pseudo-RDF schemas.

We then need to match the marketing database to our Rapleaf system. Using a corpus of matching data, plus some high-confidence inference algorithms, we are able to map our customers’ input files to entities in the Rapleaf system. This process is a large part of our technology and will be the subject of a future post.

Step 2: Summing

Once the mapping process is complete, we need to package it into a more usable, consumable format. We call this process summing (“summarizing” was too long a word). The workflow that performs summing is called the summer, and the objects that are the end result of this process are called summs. Very creative nomenclature, I know.

The summer creates a summ for each entity. A summ is basically just a package of little tidbits of information, which we call segments. Here are a few examples of segments:

• Demographic, Age 18-24
• Demographic, Age 25-34
• Demographic, Age 35-44
• Interests, Sports
• Interests, Sports > Baseball
• Shopping, In-Market for new SUV

And so on. As you can see, it’s often pretty straightforward to translate an entity’s data into a segment. But you can also imagine how multiple pieces of data might contribute towards a single segment. For example, we might place an Interest, Media segment in a summ based on the fact that a person is interested in music, books, and movies.

In reality, summs and segments are even more complicated than this. For many reasons, we need to keep track of which data partners contributed data for a given segment. We also may need to create different packages of data depending on how it will be applied.

Step 3: Anonymization

Once we have our summs, we need to anonymize them in order to ensure that the data we eventually publish respects consumers’ privacy.

The idea behind anonymization is to ensure that every summ in our datastore looks like some number of other summs. For example, let’s say a person’s summ looks like the following:

• Demographic, Age 25-34
• Interests, Pets
• Interests, Travel

Now let’s imagine that this person is the only individual in our entire datastore who has these three particular attributes. This is a privacy problem, because the segments in this summ are uniquely identifying. If these segments were to make their way into a browser cookie, it would be possible to trace that cookie back to this particular summ, and therefore, the person.

But let’s say we drop that last segment, Interests, Travel. As it turns out, there are several other people in our datastore with the Demographic, Age 25-34 and Interests, Pets segments. Therefore, the summ is no longer uniquely identifying; those two segments could apply to several thousand different entities in our system, not just one person. Based solely on those two segments, there is no longer any way to trace a browser cookie back to the person’s entity. The person is anonymous.

The number of other summs that any given summ is identical to is usually referred to as k, and we often speak of k-anonymization. This means that it is impossible to trace a given set of segments back to any fewer than k individuals. k = 2 is the most basic level of anonymization; we’re striving for k = 1000.

Anonymization is an incredibly tricky and interesting problem, especially when you’re dealing with datasets as huge as Rapleaf’s. I could go on for pages about it, but this is already quite a lengthy post, so I’ll leave it at that for now. If you want a more in-depth discussion, be sure to check out our previous post on anonymization.

Step 4: Publishing Cookies

After we’ve generated and anonymized the summs for all our entities, it’s time to actually bring them online.

The first step is to load the anonymized summs into a distributed hash table. The system we use for this is an internally developed read-only hashmap that we’ve optimized for extremely fast lookups. Using this hash table, we can quickly look up a summ from an online identifier.

To bring the summs online, we partner with a variety publishers—web sites and services that support logged-in users. When a user logs into a publisher’s site, they make that user’s identifier available to Rapleaf for matching purposes only. This request can come via javascript, an HTML <iframe> element, or a small pixel embedded onto the publisher’s page. For security purposes, we typically ask that the publisher send us a hashed version of the identifier in their request so that no new data is passed to us by the publishers—just the hashed identifier.

Now we’re at the home-stretch! From the hashed identifier that the publisher sends us, we query our distributed hash table to get the user’s summ. Our response to the publisher’s request is to drop a cookie based entirely on the information in the anonymized summ. The cookie we drop only contains a plain-vanilla set of non-identifying segments: there’s no personally identifiable information, and nothing about the user’s browsing behavior.

Step 5: Safe Onlining: Success!

Finally, our customer’s offline data has been safely “onlined” into a cookie on people’s browser. This allows them to participate in the online world where most people are today. And this ultimately makes for a more tailored, personalized experience for people on the web—while protecting their privacy.