Yelp Product & Engineering Blog

Yelp re:Invents!

Last month, Yelp was asked to talk about our experiences with Amazon’s Web Services at their re:Invent conference in Las Vegas.  I was delighted to be able to attend, speak, and learn from other speakers.  All videos from the conference have been published, and below I’ve highlighted the sections specifically about Yelp.

Big Data with Elastic MapReduce

 

The majority of our AWS usage is Simple Storage Service (S3) and Elastic MapReduce (EMR).  We use these technologies because we want every engineer to be extremely effective, to be able to command a cluster of machines that would normally take another entire team just to manage.  We want our engineers asking and answering questions like:

• “What category did the customer want when she searched for ‘Pool’?”
• “When will our mobile traffic eclipse our web traffic?”
• “Was this review written by someone with firsthand experience?”

At Yelp, whether you’re a senior engineer or an intern, if you want to test the next great data driven product, you don’t have to cajole another team for resources, or sit around waiting for your job to be scheduled.  Deploying is the same way: no need to worry about interrupting someone else’s batch job, or filling out TPS reports estimating the time you need on the production cluster.  Just ship the code; the boxes will be available when you need them.

Yelp AWS Optimization 

Make no mistake: optimizing for developer time can mean trading-off potential cost savings.  While we believe the trade-off is worth it, that doesn’t mean we ignore our costs!  Two of the specific ways we save money on EMR are:

• Re-use of job flows
• Buying reserved instances

We try to find ways of saving money that are invisible to other developers, and base improvements on how developers want to use the resources available.  Contrast this with the philosophy of making every developer justify and micro-optimize their costs.  We build tools to multiply the effectiveness of fellow engineers, instead of having policies that divide their attention between business issues and implementation details.  By sharing tools such as mrjob and EMRio we’re not only letting Yelp developers better focus on business problems, hopefully we’re letting other companies do the same.

I hope you enjoy the videos, and Happy Holidays!

Building and Testing Yelp Mobile

In this post, Steven S. from Yelp's mobile team gives us the lowdown on what tools we use to make a rich, reliable mobile experience.

---

The mobile team at Yelp always strives to bring the best possible experience to your mobile device, but what does it take to accomplish this? For Yelp's iOS app, in addition to tools used by many iOS developers — Xcode for a development environment, Git for version control — we have found other useful tools and libraries to improve our development experience. If you've ever appreciated our app and wondered what goes into its development, we're happy to shed some light on what tools from the iOS development community we make use of, and we even have some of our own to share!

The foundation upon which the Yelp app is built is YelpKit. YelpKit is an Objective-C library that provides reusable controls and helpful extensions for Apple's UIKit framework. YelpKit can assist with tasks from making requests and caching images to using pull-to-refresh. In fact, we found YelpKit to be so useful that we open-sourced it so we could use it in our own personal projects. Check out YelpKit on GitHub for instructions on using YelpKit and to see what features would come in handy for you!

Of course, with all the work you put into building your app, you want to make sure it works! Automated testing is an important tool used by many developers, and the iOS developers at Yelp are no exception. We use GHUnit for unit testing and also make heavy use of its view testing capabilities; tests in GHUnit are run on an iOS device or emulator, and the resulting view of your app can be saved to an image file and compared against previous runs. GHUnit's view tests prove invaluable for catching inadvertent changes, and can even help detect minute changes that occur from updates to the iOS SDK.

As useful as automated testing is, getting your app into the hands of as many people as possible is still one of the surest ways to find bugs. This is where TestFlight comes in: TestFlight is a free service that makes it easy to distribute your app to testers. Testers must join TestFlight and be included in your app's ad hoc provisioning profile. When you want to release a new version of your app for testing, you just upload the compiled IPA file and TestFlight will notify your testers that it is available for download! Testers need only click a link in this email to begin installing the app. You can choose to which testers to distribute the file, and TestFlight provides analytics indicating, for example, which testers have opened the email or if any have had problems installing your app. With our sharp group of fellow iPhone-wielding engineers eager to try out new features, this convenience offered by TestFlight allows Yelp to rapidly distribute and receive feedback on beta builds of apps.

With the help of GHUnit and TestFlight, we manage to keep the Yelp app in good shape! Inevitably, though, some bugs can slip through, so we use Crashlytics to help us get to the bottom of any crashes that crop up once the app is released to the App Store. Crashlytics is a crash reporting solution that supplements the crash logs available through iTunes Connect. After configuring Crashlytics, the debug symbols (dSYM) for your app are uploaded to Crashlytics during the build; if your app crashes, a crash log is sent to the Crashlytics servers and symbolicated. Crashes are ordered by their prevalence in Crashlytics' web interface, so at a glance you can tell what issues are most pressing and then start digging through the stack trace in order to keep your app functional and your users happy.

In the lively iOS development community, you don't have to look very far to find all sorts of useful tools and libraries. In showing you those that helped Yelp reach its success, we hope you're excited about these tools, and we can't wait to see what you can make using them!

Firefly: Illuminate Your Website's Performance

One of Yelp's core values is "play well with others."  So it's no surprise that Yelp thrives with open source projects written by others, and gives back by sharing projects of our own.  That's why I'm excited to share this post by the manager of our Infrastructure team, Oliver N. (or as he's known around the office, "BigO"), which adds to our library of open source projects.  

---

How do you know if your website slows down as a result of a code push?  How do you keep tabs on the performance of your most important endpoints?  How do you know if your error rates spike, or what their baselines are?  If you're not actively using it, how do you even know your website is serving traffic?  For Yelp's Infrastructure team, the answer is an emphatic "GRAPHS".  Tasked with keeping the site up and running smoothly, we rely heavily on graphing the data from a variety of real-time metric systems.  We keep these graphs open on our work computers as well as splashed across large LCDs in our office, and they communicate to us the heartbeat of a system that serves approximately 78 million uniques per month.  Today we are releasing the home-grown tool we use to navigate, explore, annotate and graph these time series metrics on github.  Meet Firefly:

 

Firefly is not a metric collection system itself.  It is a pluggable front-end for exploring time series metrics stored anywhere, combining these metrics into graphs, combining those graphs into dashboards, and sharing those dashboards with colleagues.  It's designed to scale across datacenters and to bring together data from disparate sources.  It supports automatic graph titles and legends, as well as highly configurable graph annotations (vertical bars to record particular events). It has a stateful UI based on HTML5 pushState to allow easy sharing of dashboards.  Its server is built in Python on top of the Tornado framework, and its front-end is built in JavaScript atop the fantastic D3 graphing engine.

Firefly consists of a Data Server and a UI Server.  The Data Server can run in multiple datacenters and provides the primary data interface - responding to requests that essentially translate as "give me the time series data for these particular metrics over this particular time window."  It is the abstraction between a unified UI and a potential myriad of backends, be they Ganglia RRDs, HyperTable, MySQL, Redis or any other data source.  Each distinct data source is described as a (surprise) DataSource subclass, which exposes the standard interface methods of list_path(path), data(sources, start, end), legend(sources), and title(sources).  The UI server configures and serves up the HTML and JavaScript base interface, and handles the URL minification/expansion that underlies the stateful pushState features.

Firefly has a ton of features, and has been super useful to us.  We're going to keep expanding those features and are also really interested in seeing what uses the community can find for this tool.  We're only shipping it with a DataSource configured for Ganglia right now, but adding new sources is designed to be easy and over time we'll be looking to release some more parts of this system.  Fork Firefly on github, give it and shot and let us know what you think!

GPS vs WiFi: The Battle for Location Accuracy Using Yelp Check-Ins

Our next post comes from Mason G., superstar intern on our IOS team.  While not assembling a 20-monitor wide version of Mario that displays the entire level at once, Mason has been cranking out features for our shiny iPhone and iPad apps.  Yelp thrives on data, so it is no suprise that one of Mason's projects was to evaluate the technologies we use for pinpointing users' geolocation.  Read on to get the full scoop!

---

“Checking in” to a business using Yelp’s mobile applications is a fun way for Yelpers to engage with businesses and others in the Yelp community, but we don’t allow users to check in from just anywhere -- they have to earn those badges! In order to make sure everyone’s playing fair, we compare a user’s reported location with the location of the business they’re trying to check in to figure out how far away they are. We thought it would be interesting to figure out how Wi-Fi positioning and accuracy compared to GPS and, in order to do this, we had to take a look at Yelp check-ins from different mobile devices.

First, a little background. A phone can figure out its location in several ways: by using GPS, cell tower triangulation or Wi-Fi positioning. GPS connects to satellites orbiting the Earth, and figures out where it is compared to the satellites. Cell tower triangulation connects to nearby cell towers, and performs a similar calculation. Wi-Fi positioning depends on companies like Skyhook, who record the locations of Wi-Fi networks. Your phone can then look at nearby Wi-Fi networks and figure out where it is. 

Using Yelp’s open-source map reduce framework, mrjob, we analyzed all Yelp check-in data from June 2012, breaking it out by device type. Android and iPhone can use GPS, cell tower triangulation and nearby Wi-Fi networks to get a precise fix. On the other hand, iPods can only use Wi-Fi positioning. By comparing iPods to Android and iPhones, we were able to see how accurate Wi-Fi positioning is in comparison to a mix of all three techniques.

After gathering all the data from June, we graphed a probability distribution function of Yelp check-ins versus distance in order to see the distance between users and the businesses they’re checking in to. This graph shows the percentage of check-ins attempted (y-axis) at a given reported distance from a business (x-axis). As you can see, check-ins from iPhones tend to be closest to the business, followed by Android phones and iPods.

For example, 40% of Android check-ins are less than 0.1 miles away from the business.

 

Next we converted this graph into a cumulative distribution function, in order to see how many Yelp check-ins occurred within a specific distance from the business. iPhone fared better than Android, likely due to lower-quality GPS chips in some Android devices. For example, 7.5% of Yelp check-ins from Android, the phone thought that the user was actually more than two miles away from the business, while only 4.5% of iPhone check-ins were that far away.

For example, 79% of iPod check-ins were less than one mile from the business.

 

When checking in, we also record the reported location inaccuracy. This number represents the phone’s best guess at the number of miles it might be off by. We account for this inaccuracy by subtracting the number from the distance to the business. This way users don’t miss out on the chance to check in.

The dot shows your reported location, and the larger circle represents the inaccuracy.

 

Android devices gain the most from this comparison, although iPhones still have better location services overall. However, the iPod line barely moves – the reported accuracy is always close to 0.

For example, 90% of Android check-ins were less than one mile from the business after adjusting for the accuracy radius.

 

By analyzing millions of data points, we can easily see how, on average, different platforms perform. iPhones consistently have the most accurate positioning, with a fairly small accuracy radius. Android phones are often inaccurate, but reliably reported that inaccuracy. And finally, iPods using Wi-Fi positioning proved the least accurate and usually reported incorrect accuracy radii. We can use this analysis to make sure that users have a great experience checking in, no matter their device.

 

Introducing EMRio: Optimize your AWS bills

This post comes to us from Sean, one of our Data Mining interns and a student at the University of Pittsburgh. Sean wrote production code his first week here, and hasn't slowed down since. I'm happy to see his main project released today: it's called EMRio (pronounced like the Italian plumber). Yelp has already started using EMRio to start saving money on our Elastic MapReduce bills. Take it away, Sean!

---

At Yelp, we like to use MapReduce a lot. We use it so much, in fact, that we made mrjob, a tool that allows easy creation of mapreduce jobs in Python. We use Amazon’s Elastic MapReduce (EMR) service that allows us to compute large amounts of data on their EC2 cluster. The service allows for anyone to buy different types of machines by the hour, depending on the needs of the business. Typically, you are billed by the hour with no upfront cost, but with a large enough demand the hourly rates can be reduced by switching to reserved instances. To save some money on our EMR bill next year, we developed a tool which runs a cost optimizer over our historical EMR usage and spits out the optimal reserved instance pool for our usage. It suggests how many reserved instances, of what type, and of what size we should buy to minimize our costs. 

For reserved instances, you pay a yearly upfront cost for a machine and in return you pay a lowered hourly rate. Here is a graph showing the three tiers of reserved instance types you can buy, and the cost associated with them over time.

 

At the extreme (Heavy Utility), you pay only the upfront cost. Heavy Utility is used for machines that are consistently running during the year.  For more intermitant usage, a smaller upfront cost makes more sense. This is where my project comes in: find the optimal number and type of instances to buy that would save Yelp the most amount of money in the long run. This is how EMR Instance Optimizer (EMRio) was born.

EMRio works by looking at your EC2 usage and calculating the optimal number and type of reserved instances you should have purchased during that period. Since Amazon only keeps 2 months of job flow history, it normalizes the history as if it was a single year’s worth of data. After normalizing, it then starts optimizing. This works by swapping between two modules: the optimizer and simulator.

The simulator is surprisingly simple. The main run method of it looks like this:

# event_queue is an ordered list of events that happened in your AWS job history.
for (time, event_type, job) in event_queue:
    if event_type is START:
        allocate_job(jobs_running, reserved_instance_pool_used, job)

    elif event_type is LOG:
        log_hours(logged_hours, jobs_running, job_id)
        rearrange_instances(jobs_running, reserved_instance_pool_used, job)

    elif event_type is END:
        log_hours(logged_hours, jobs_running, job_id)
        remove_job(jobs_running, reserved_instance_pool_used, job)

    return logged_hours

All it does is break down the jobs into a bunch of event tuples containing the time and type of a job event. These event types are START, END, or LOG. START and END are when the job starts to spin up on EC2 and when the job is finished, respectively. LOG is for logging an hour that the job runs. LOG is also useful since each hour Amazon can reallocate reserved instances to jobs if they become available. The simulator also reallocates the instances being used if there are any available reserved instances that can be used.

The Optimizer starts out with zero reserved instances for all types. It then simulates adding a single instance for each utilization type for a single instance type. It simulates all the utilization types, and then whichever one was best, it adds that instance to the "best pool." If at any point the cost for buying the next instance is more costly than the previous instance, we stop because we have found the optimal reserve instance pool that minimizes cost. This technique is called Hill Climbing and it is useful for this domain because each reserved instance added will only use as many hours as the reserved instance before it. This is because if the instance before it was free to be used, then it would have been scheduled for the hours used instead of the newly added machine. This means that each instance added will have lower or equal hour usage, but never higher which makes hill climbing applicable.

Once the Optimizer is done, EMRio runs two more simulations: one for the optimized pool and one for only on demand usage, so we can compare the costs of both. It then outputs the optimal instance pool and a cost analysis. The cost analysis describes how much money both are and the money saved if these instances were used for a year.

If you want to give EMRio a spin, just head on over to: https://github.com/Yelp/EMRio and give it a try!

Datamining and Visualization with the Academic Dataset

One of the qualities Yelp looks for in engineers is a passion for making sense of "big data."  But as a student or newbie in the field of data science, how are you supposed to demonstrate that passion? Enter the Yelp Academic Dataset, a snapshot of review, user, and business data from the communities around 30 universities.  Last semester, I had a chance to see some of the amazing things that UC Berkeley students could do with the dataset.

Visualizing Data

Unfortunately, the raw dataset is only exciting to those who can skim JSON serialized datastructures (OK, OK, I admit to being one of those people).  To make the data valuable to everyone else, it needs to be aggregated and displayed in an engaging, dynamic way.  Enter stufte, a project which displays aggregate information about businesses organized by campus.

stufte uses Bootstrap, leaflet, Typekit, and several other HTML5 technologies to build a compelling and informative view of Yelp's data.  Visually rich, the site conveys a lot of information without being overwhelming by allowing you to narrow your focus with intuitive mouse hover actions, click through modes, and widgets.

Data mining

stufte surfaces some interesting stats, like review distribution, featured restaurants, and most prolific users.  What is the best way to discover these nuggets given mountains of data to comb through?  Students used Yelp's open source library mrjob to discover patterns.

mrjob is a Python package that helps you write and run Hadoop Streaming jobs.  mrjob can use Amazon's Elastic MapReduce service to easily run huge data processing jobs.  Amazon AWS in Education provides several programs to let students use their services for free.  This makes the two a great combination for students learning to datamine on the cheap!

Hadoop and mrjob have extensive documentation. If you are new to these technologies, I recommend skimming these first to get an idea of what's possible.  Now, let's jump into some of the interesting questions that were asked and answered by students.

Measuring Originality

After an intro to mrjob, students tackled the question: which review or reviews have the most number of unique words (i.e., words not seen in any other review)? It turns out answering this question requires several steps:

• extracting words from their reviews
• finding which words were only used in one review
• recombining a particular review's unique words
• scoring the reviews by the count of their unique words
• finding the review with the highest score

After wrapping one's head around the MapReduce paradigm, the next big challenge one faces is what to do when your task can't be answered with one Job (MapReduce iteration).  Manually writing and connecting multiple jobs is a hassle. How do you handle dependencies, storage for the data between jobs, or cleanup after success?  Luckily, mrjob handles all of this for you, leaving a clean interface for specifying how data will flow through multiple steps:

def steps(self):
	return [self.mr(self.words_in_review, self.doc_frequency),
		self.mr(reducer=self.unique_words),
		self.mr(reducer=self.find_max_review)]

I'll leave the implementation as an exercise to the reader (and future students!), but give you the punchline: 6 year Yelp Elite Tom E. shows his nerdy side with his unique review of MIT's Middlesex Lounge. Second place goes to another Elite, Jonathan T. for his slang slingin' review of Matsuri near CalTech's campus.

Dangerous Patterns

For Apoorva Sashdev and Alex Chung's final project, the Yelp dataset was used to predict business closings.  Yelp doesn't want to send users to businesses that have closed, so how can we quickly catch businesses that appear to be closed but have not been caught yet?  If we could predict business closings, the tool could also be used by business owners to spot dangerous trends early on.

Using a Baysian classifier and features such as votes, review frequency, and category, they predicted which businesses were now closed, and used Yelp to check their findings.  As is frequently this case with datamining projects, sometimes the most important finding is that there's not much to find. Overall accuracy was high, but many truely closed businesses were not found; a classic "precision vs recall" problem with skewed datasets.  While the recall of their classifier for closed businesses wasn't quite accurate enough for production use, they did make some interesting discoveries along the way:

"We found that certain categories had a high percentage of closed businesses namely Moroccan, Wineries, Afghan, Hawaiian, Adult Education and Arcades whereas other categories like Health and Medical, Coffee & Tea, Bars, Beauty and Spas seem to remain open more often."

Jump In!

Set yourself apart from other candidates by trying your hand at datamining. It's never been easier with data sources like Yelp's and tools like mrjob.  If this sounds fun, take a look at the software engineering positions we have open (including fall interns!).  We're looking forward to hearing about your projects!

After Hours Project: Simulating Flight with Kinect

If you could have any superpower, what would it be? (You can't say the power to get more powers.) If you're like me, it'd be the power to fly. Unfortunately, I'm not a Superman, Neo, nor a bird. I'm a software engineer at Yelp; I make things happen by writing code. So I started to write code that tricks me into feeling like I'm flying. What I ended up with was a Mac app that allows you to control a quadcopter by flapping your arms like wings.

To do this I used the Microsoft Kinect, a Parrot ARDrone quadcopter, OpenNI, and the app I wrote, KinectWings.

How Does it Work?

KinectWings uses the Kinect and OpenNI to track your body position. It monitors your body for movements that look like flapping or tilting. When a flap or a tilt is recognized, KinectWings sends control messages over wifi to the ARDrone. Video from the quadcopter is transmitted over wifi back to KinectWings, where it's displayed for the user. When used in front of a large screen, it creates the illusion that you are flying by flapping and tilting your arms.

I Want to Fly!

If you've got some code know-how, you too can build software to control hardware using your body! I've opensourced an example project for using OpenNI in Cocoa applications for OSX. This provides a good starting point for doing skeletal tracking using a Mac and Kinect. I've also opensourced the changes I made to the ARDrone SDK so that it works on Mac. Check them out on GitHub!

• http://github.com/johnboiles/ARDroneSDK
• http://github.com/johnboiles/CocoaOpenNI

Newsflash R. Kelly! I no longer believe I can fly, I can fly.

After Hours Project: Kinect Hacking

Here at Yelp, we're passionate about building things; it's at the core of our engineering philosophy. In fact, we enjoy it so much that many of us keep on building after we finish work. I recently found some spare time to work on an interesting project with the Microsoft Kinect. I think it's a cool start and I've open sourced the code so that others can build something even cooler.

mrjob: Distributed Computing for Everybody

Ever wonder how we power the People Who Viewed this Also Viewed... feature? How does Yelp know that people viewing Coit Tower might also be interested in the Filbert Steps and the Parrots of Telegraph Hill?

It's pretty much what you'd expect: we look at a few months of access logs, find sessions where people viewed more than one business, and collect statistics about pairs of businesses that were viewed in the same session.

Now here's the kicker: we generate on the order of 100GB of log data every day. How do we deal with terabytes of data in a robust and efficient manner? Distributed computing!

Today we want to share that power with you.

As you may have guessed, we use MapReduce. MapReduce is about the simplest way you can break down a big job into little pieces. Basically, mappers read lines of input, and spit out tuples of (key, value). Each key and all of its corresponding values are sent to a reducer.

Here's a simple MapReduce job that does a word frequency count, written in our mrjob Python framework:

from mrjob.job import MRJob
import re

WORD_RE = re.compile(r"[\w']+")

class MRWordFreqCount(MRJob):

    def mapper(self, _, line):
        for word in WORD_RE.findall(line):
            yield (word.lower(), 1)

    def reducer(self, word, counts):
        yield (word, sum(counts))

if __name__ == '__main__':
    MRWordFreqCount().run()

In goes text, out come tuples of (word, count). You can give it your README file, or all of Project Gutenberg, and it'll scale gracefully.

(More complex examples: PageRank, Text Classifier)

We used to do what a lot of companies do, which is run a Hadoop cluster. We had a dozen or so machines that we otherwise would have gotten rid of, and whenever we pushed our code to our webservers, we'd push it to the Hadoop machines.

This was kind of cool, in that our jobs could reference any other code in our code base.

It was also not so cool. You couldn't really tell if a job was going to work at all until you pushed it to production. But the worst part was, most of the time our cluster would sit idle, and then every once in a while, a really beefy job would come along and tie up all of our nodes, and all the other jobs would have to wait.

About a year ago we noticed that Amazon had a service called Elastic MapReduce (EMR for short) where you could essentially spin up virtual Hadoop clusters with as few or as many machines as you needed, and pay for it by the hour.

I was tasked with migrating our code over to EMR. Not just getting Python scripts to run on EMR, but getting our code base to run more or less as-is, with all of its 40+ library dependencies, C and Cython code that compiles into Python modules, and files that are different from development to production.

It took me a while, but on May 18, 2010, we retired our Hadoop cluster for good, and switched all of our production jobs over to EMR. Our framework, mrjob, is finally mature enough that we're releasing it as an open source library.

• If you're new to MapReduce and want to learn about it, mrjob is for you.
• If you want to run a huge machine learning algorithm, or do some serious log processing, but don't want to set up a Hadoop cluster, mrjob is for you.
• If you have a Hadoop cluster already and want to run Python scripts on it, mrjob is for you.
• If you want to migrate your Python code base off your Hadoop cluster to EMR, mrjob is for you.
• (If you don't want to write Python, mrjob is not so much for you. But we can fix that.)

So try it out and let us know what you think! And send us cool examples so we can feature them on our blog. :)

• To install: sudo easy_install mrjob
• Documentation
• PyPI profile page
• GitHub

If you have questions or encounter issues, feel free to contact me through Yelp or through GitHub. I really want using mrjob to be a smooth and productive experience for everyone.

By the way, here are some other features on our site that are powered by mrjob:

• Review highlights
• Autocomplete as you type on search
• Search spelling suggestions
• Top searches
• Ads

tron - Centralized Scheduling

As Yelp has grown over the years, we've amassed huge collections of data - the collective output of the actions of tens of millions of users. Analyzing this data helps us improve the user experience across the site, from ranking businesses and extracting "review highlights" to fighting spam and keeping the site secure. These tasks involve long-running batch processes that analyze large logs and database tables, with workflows sometimes composed of five or more dependent processes. Managing these workflows with traditional scheduling tools - most notably the cron family - eventually caused us to breach the "complexity comfort zone" that surrounds any large engineering project. But then we had a vision, and it is that vision we are releasing today as tron.