Hash performance improvements in Ruby 2.4

Some corrections and clarifications from this week’s talk on hashes in Ruby 2.4.

On converting hashval to index:

I gave an example of using modulus on a hashval (which might be huge) to an index in an array (like `152`), so it can be inserted in a table. Ruby does not actually do modulus for performance reasons; it actually takes some of the lower bits of the hashval instead (discarding the other bits). This is generally not a good idea, but apparently the alternatives are worse.

On collision resolution:

In MRI 2.4, collisions result in a secondary hash operation to find a new index, but I was incorrect when I said that Ruby did the equivalent of:

new_index = Hash(index)

This would result in all collisions continuing to collide until a free index was found. All else equal, this would almost certainly still be better than closed addressing, but we can do better. The algorithm is more accurately summarized as:

new_index = Hash(index + lower_five_bits(hashval))

which is much better than the behavior I described. When two keys collide (in bucket 152, for example), the next index to be generated via double hashing is likely to be distinct, because the hashvals of the colliding keys are probably distinct (after all, the conversion from hash to index involves discarding bits).

On guaranteeing that empty entries are found:

The mathematical theorem I was looking for was “Hull-Dobell theorem”, which guarantees a cycle linear congruential generator. Ruby uses this theorem to guarantee that during a collision the secondary hash function will eventually find an empty index, if it exists in the table.

On load factor:

In ruby trunk the load factor is currently 0.5, so if half of the table fills up, it should trigger a rehash.

Changes to constant unloading in Ruby 2.4

We noticed some interesting behavior recently while upgrading to Rails 5.0.1 and Ruby 2.4. Between MRI 2.3x branch and 2.4.0, constant unloading no longer affects variable references to the unloaded class constant:

ref = Object.const_set(“ASD”, Class.new)
=> ASD
2.4.0 :014 > Object.send(:remove_const, “ASD”)
=> ASD
2.4.0 :015 > ref.name
=> “ASD”

In previous versions of Ruby, ref.name would return nil. In fact, in 2.4 the reference doesn’t appear to be unloaded in nearly any sense of the word – I can do ref.new and it will create a new instance of the ASD class, and calling instance.class on it will return ASD. The only change appears to be that directly trying to reference ASD now results in a NameError.

At first I thought this had something to do with threadsafety, but now I’m not so sure; Ruby lets you do all sorts of things that can silently affect behavior in other threads (like redefining methods and classes), so this reasoning would be inconsistent with that design.

Anyways, there are 3,392 commits between 2.3.0 and 2.4.0. Should be fun to track down.

We just raised a round led by Mike Volpe + Yoav Shapira

We just raised a round of funding led by the amazing guys at Operator.vc. Yoav Shapira (1st VPE, Hubspot) and Mike Volpe (founding CMO, Hubspot) are swell guys in addition to being towering figures in Boston, and I look up to them a lot more than they probably know.

The new financing also includes participation from Bill Cohen, Managing Partner and Todd Breeden, Principal at KiwiVenture Partners II. With this new round, Operator.vc and KiwiVenture Partners II join our existing investors (Hubspot, Accomplice, 500 Startups and more).

Around the interwebs:

On a related note, check out our job openings.

The two-man rule in engineering

In nuclear weapons design, there is a two-man rule that prevents any single individual from accidentally — or maliciously — launching nuclear weapons. Each step requires knowledge and consent from two individuals to proceed. Even when the President initiates a launch order, he must jointly authenticate with the Secretary of Defense (they’re given separate codes, even though the President has sole authority).

When the order reaches the launch control center, two people are required to authenticate and initiate the launch, for example by (vastly simplifying…) turning two keys simultaneously.

The benefits are at least twofold. First, it’s much harder to compromise or impersonate two people simultaneously than it is to compromise one. Second, it also provides error correction. When two people are involved in a process, it’s much more likely that if someone is about to make an oversight or error, it will be caught. This works better when the roles are asymmetric, because then they won’t both be on the same “wavelength.” Most good processes of this type seem to be asymmetric in some way.

There are many contexts where we want error correction and extra security: executing large financial transfers, preparing patients for surgery, performing space shuttle launch checks, or running nuclear reactors. It also comes up a lot in software development, which is what got me thinking about this. Let’s count the ways we implement the two man rule:

Code review: Everyone is either doing this or making bad excuses for why they shouldn’t. But it’s the clearest and most accessible example of a two-man rule in software engineering.

Spec review: An essential part of any sizable project is a review of the specification to make sure, in particular, that 1) the right thing is being built in the right way, and 2) the right people and teams are aware of any impact the work might have on them.

Continuous integration: The branch built on your machine, but does it build on another one? This turns up countless “oh right I added this config variable/package and forgot to propagate the change” incidents before they become blocking.

Pair programming: I think of this as just real-time code review. It has all the same benefits and more, with the downside that it can’t be done asynchronously.

Deployments: I wish we did this closer to 100% of the time, but it has definitely been helpful to have a second person on hand for deployments in addition to the primary engineer. This is especially critical during complex deployments that happen in phases or involve many moving parts. Ideally the role is relegated to going through the checklist one last time (“says there are database migrations, are we expecting downtime or can we keep pre-boot on, and if so is the config correct?”), and in the event of an issue, helping to investigate or doing the checklist in reverse to roll back.

Mind the Gap

As we continue to grow, there are a few areas where I think a more consistent two-man rule will lead to high return on effort in the future:

  • manually rebooting servers, changing server counts or container types
  • adding/scaling services
  • running one-off commands against the production database

And yes, every once in a blue moon we deploy tiny changes to production without full code review, or force a failing build onto staging — something that is intentionally difficult and unwieldy to do. This has gone from rare to extremely rare, and I expect this trend to continue. But I like processes to be developed and enforced bottom-up if possible, and prefer values over inflexible rules. So far this tenet hasn’t failed us, and we still trust each other with good judgment above all else.

However, as the stakes get higher every day, the cost/benefit equation will eventually tip towards a standard operating procedure that can be summarized as “trust, but verify.” If that doesn’t sound like a good proverb to live by, maybe a second opinion is in order?

 

Don't tweak all the variables at once

I have been at Privy for a year. I’m proud of the team and product we’ve built, and I was excited to sit down and make a list of some of the new things I learned during my time here. Then I realized that most of these “lessons” would’ve been covered if I had just re-read everything ever written by Fred Brooks, Martin Fowler and Eric Ries…but that doesn’t make a good blog post.

So that got me thinking about the things I already sorta-knew that had been validated. Perhaps there was some pattern there. And so I made my first order list, which I present below.

I have learned virtually nothing about…

  1. Using a stack in the middle of the adoption curve: Ruby on Rails.
    • Ruby/MRI is between 2 and 50x slower than running a static language on the JVM, but even a slight increase in developer productivity more than makes up for the operations cost.
    • The advantage of using a really fancy stack (more cool factor for recruiting, etc) really doesn’t seem to compare favorably to the disadvantages (more uncertainty, smaller pool of technical talent).
    • The evidence that startups regularly die due to technology stack is vanishingly flimsy, so no need to dwell here.
  2. Building a local team.
    • Geographically distributed teams and getting on the bandwagon of “work anywhere cuz we have Slack lol” seems all the rage today, but the early team is more important than the early product, and the best teams are in the same place every day.
    • Resisting the urge to go remote has been something of a useful filtering mechanism: does this individual believe enough in our vision to consider moving here for the job?[1]
  3. Having some really solid cultural values (or aspirations, as they may be) that aren’t totally groundbreaking.
    • It’s more important that we live up to great values than come up with amazing ones. I’ll leave the latter to the management consultants.
  4. Using traditional engineering management.
    • We basically do agile: there are weekly-ish sprints; we do higher level planning on a monthly basis; a couple times a year we work on a strategic roadmap. We write software specifications before we code, and we ship daily with continuous integration and lower test coverage than I’d like to admit. Yawn.
    • We don’t use “flat” organizations or Holacracy or whatever trendy hipster management structure is in vogue. What the hell kind of problem is this trying to solve anyway? My theory is it’s got something to do with cool factor for recruiting, but I have a feeling the people trying this are no more certain than I am.

What’s the big meta lesson here?

If anything, it probably goes a little bit like this: the available levers to pull in a startup are numerous, but there are only a few that make a measurable difference. The things that are most likely to kill us are the things that kill most startups: having a subpar team, building a product that nobody wants, executing poorly on feedback loops, that kind of thing.

These are the things that, in Paul Graham terminology, make you “default dead” until you figure out how to get them right. And it’s critically important to realize that things like “what do we build?” and “who do we sell it to?” are the things that startups are doing “wrong by default” and need to diagnose and fix as quickly as possible.

But then there are the other things, like “how do we write a scalable system to respond to HTTP requests?” or “how should we manage engineering teams?” in which there are essentially no forced errors, and where (barring a well-articulated exception[2]) the correct answer is the default one. So almost all of the risks here seem to be to the downside, and any upside is probably insignificant compared to the scale and difficulty of the hard problem: building a novel product under uncertainty.

There are certainly going to be exceptions to this. There are going to be teams that have figured out how to deviate from orthodoxy and are reaping benefits from it. I’m OK with this, and my theory is that it either doesn’t matter (e.g., they were going to be a success anyway) or it won’t rescue them (they’re doomed and they didn’t differentiate in a way that mattered).

And so it must follow that the majority of our iterating and tweaking is on the thing that will make us a great company: what do we build? Who do we sell it to? There are enough variables in there that I don’t really have any brainpower left over to do anything except reach for Generic Ruby/Python/JavaScript framework and using engineering/recruiting/management techniques that were old 30 years ago.

 

[1] This isn’t all roses, since it biases us significantly towards younger folks who don’t have as many attachments, the net effect of which is…debatable, but obviously not lethal in a vibrant tech city like Boston.

[2] Example: One excuse I’ve used to provision real hardware in a real datacenter as opposed to just spinning up an EC2 instance is “I’ve done the math and TCO in AWS is literally 25X more expensive.”

How to uninstall the default Windows 10 apps and disable web search

If you’re like me, you’ve been enjoying Windows 10 for quite some time now. Couple things annoy me:

1. I accidentally changed all my file associations to the new default Windows apps, because the (intentionally) misleading firstrun experience presented fine print I glossed over.
2. I don’t like searching the web from the Windows Start menu, because I’d rather not transmit everything I type there over the network. Call me old fashioned.

Remove default apps

Open up a powershell prompt and run this to remove most of the default apps:

Get-AppxPackage *onenote* | Remove-AppxPackage
Get-AppxPackage *zunevideo* | Remove-AppxPackage
Get-AppxPackage *bingsports* | Remove-AppxPackage
Get-AppxPackage *windowsalarms* | Remove-AppxPackage
Get-AppxPackage *windowscommunicationsapps* | Remove-AppxPackage
Get-AppxPackage *windowscamera* | Remove-AppxPackage
Get-AppxPackage *skypeapp* | Remove-AppxPackage
Get-AppxPackage *getstarted* | Remove-AppxPackage
Get-AppxPackage *zunemusic* | Remove-AppxPackage
Get-AppxPackage *windowsmaps* | Remove-AppxPackage
Get-AppxPackage *soundrecorder* | Remove-AppxPackage

Turn off Web Search

Next, open up Group Policy Editor (gpedit.msc) and navigate to:

Computer Configuration -> Administrative Templates -> Windows Components -> Search. Enable the policies:

  • Do not allow web search
  • Don’t search the web or display web results in Search
  • Don’t search the web or display web results in Search over metered connections

Finally, open up “Cortana and Search Settings” and disable “Search online and enable web results”.

Heroku Pricing Changes

Couple of quick points on Heroku’s pricing changes which I’ve been meaning to get out:

  • Its not an across-the-board price cut. While the dyno pricing has decreased, they also got rid of the free $36ish/month in free dyno credits.
  • New free tier replaces the free dyno credit. Minimum 6 hours of sleep per day means no more abusing the free tier by pinging your app every few minutes to keep it from sleeping. Seems a lot of people were doing this to run production apps for free; good riddance.
  • New $7/month hobby tier is a great new option for people who were previously hosting production apps for free and need them live 24/7. This is a great deal since you can even have worker/background dynos for the same price. Makes sense for Heroku too – they’ll derive a good deal of long tail revenue from folks who would’ve previously just stuck with the free tier (maybe using the ping hack to prevent idling). Honestly I think the revenue is not the point – it’s more just preventing people from abusing the free tier while giving enough folks a no-excuses carrot to use the platform so it’ll be a no-brainer when they “go pro.”
  • Professional dyno pricing drop is great, but it’s going to be a wash for the majority of paying users because the free credit is going away. Basically there’s no more big cliff where you go from free->paid any more, but the steepness of the pricing increases is somewhat lower. My intuition is the winners are the 4-5 figure/month customers, makes sense since that’s around the time they start thinking about moving to AWS directly for cost savings. More of them will just consider staying.

Why Work at a Startup?

Because I’m tired of explaining to everyone, I’m going to make this list to refer to anyone who asks. While I don’t think any of these are particularly original, it makes a handy checklist for anyone considering a similar jump[1].

  •  Faster time to market. At Privy, we routinely ship code that was written earlier in the day or week. Seems petty, but as an engineer, it’s frustrating to improve something and then not have it in the hands of customers for weeks or months.
  • More hats to wear. The diversity of work at a startup appeals to me. I can work on product, recruiting, and engineering. Before lunch. The pace and scope of work is both faster and longer term, and I like being involved in multiple parts of the business.
  • Be judged by customers, not managers. A startup makes each person less insulated from the market. Therefore the correlation between performance and rewards tends to be much closer.
  • Less politics. As a consequence of the last point, politics becomes less important. It’s much harder to bullshit accomplishments in a startup when the entire company fits into a small room or two. Tired of carrying teammates who aren’t pulling their own weight? Join a startup.
  • Incredible learning. As another corollary to being closer to market forces, I’ve learned a lot about how to run a business that provides value to customers in exchange for money. I’ve in turn been able to apply experience I’ve learned elsewhere that I never would’ve been able to use at a larger company, because my job title would’ve prevented me from doing anything other than engineering.
  • Challenging the status quo, not defending it. Name recognition is cool, but I never got the sense that my role at Office was about reshaping how people work – probably because our market share had nowhere to go but down. But I’ve found I don’t mind playing the underdog as long as I have a thesis about how the future should change for the better.

 

1. In a necessary but not sufficient way (i.e. if these don’t apply to you, a startup is probably a bad idea; but if they do apply to you, a startup could still be a bad idea).

How we sped up our background processing 150x

Performance has always been an obsession of mine. I enjoy the challenge of understanding why things take as long as they do. In the process, I often discover that there’s a way to make things faster by removing bottlenecks. Today I will go over some changes we recently made to Privy that resulted in our production application sending emails 150x faster per node!

Understanding the problem

When we starting exploring performance in our email queueing system, all our nodes were near their maximum memory limit. It was clear that we were running as many workers as we could per machine, but the CPU utilization was extremely low, even when all workers were busy.

Anyone with experience will immediately recognize that this means these systems were almost certainly I/O bound. There’s a couple obvious ways to fix this. One is to perform I/O asynchronously. Since these were already supposed to be asynchronous workers, this didn’t seem intuitively like the right answer.

The other option is to run more workers. But how do you run more workers on a machine already running as many workers as can fit in memory?

Adding more workers

We added more workers per node by moving from Resque to Sidekiq. For those who don’t know, Resque is a process-based background queuing system. Sidekiq, on the other hand, is thread-based. This is important, because Resque’s design means a copy of the application code is duplicated across every one of its worker processes. If we wanted two Resque workers, we would use double the memory of a single worker (because of the copy-on-write nature of forked process memory in linux, this isn’t strictly true, but it was quite close in our production systems due to the memory access patterns of our application and the ruby runtime).

Making this switch to Sidekiq allowed us to immediately increase the number of workers per node by a factor of roughly 6x. All the Sidekiq workers are able to more tightly share operating system resources like memory, network connections, and database access handles.

How did we do?

This one change resulted in a performance change of nearly 30x (as in, 3000% as fast).

Wait, what?

Plot twist!

How did running more workers also result in a performance increase of 500% per worker? I had to do some digging. As it turns out, there’s a number of things that make Resque workers slower:

  • Each worker process forks a child process before starting each job. This takes time, even on a copy-on-write system like linux.
  • Then, since there are now two processes sharing the same connection to redis, the child has to reopen the connection.
  • Now, the parent will have to wait on the child process to exit before it can check the queue for the next job to do.

When we compounded all of these across every worker, it turns out these were, on average, adding a multiple-seconds-long penalty to every job. There is almost certainly something wrong here (and no, it wasn’t paging). I’m sure this could’ve been tuned and improved, but I didn’t explore since it was moot at this point anyway.

Let’s do better – with Computer ScienceTM

In the course of rewriting this system, we noticed some operations were just taking longer than felt right. One of these was the scheduling system: we schedule reminder emails to be sent out in redis itself, inserting jobs into a set that is sorted by time. Sometimes things happen that require removing scheduled emails (for example, if the user performs the action we were trying to nudge them to do).

While profiling the performance of these email reminders, I noticed an odd design: whenever the state of a claimed offer changes (including an email being sent), all related scheduled emails are removed and re-inserted (based on what makes sense for this new state). Obviously, this is a good way to make sure that anything unnecessary is removed without having to know what those things are. I had a hunch: If the scheduled jobs are sorted by time, how long would it take to find jobs that aren’t keyed on time?

O(n). Whoops!

It turns out that the time it took to send an email depended linearly on how many emails were waiting to be sent. This is not a recipe for high scalability.

We did some work to never remove scheduled jobs out of order – instead, scheduled jobs check their validity during runtime and no-op if there is nothing to do. Since no operations depend linearly on the size of the queue any more, its a much more scalable design.

By making this change, we saw an increase in performance of more than 5x in production.

Summing up

  • Moving from process-based to thread-based workers: ~6x more workers per node.
  • Moving from forking workers to non-forking workers: 5x faster.
  • Removing O(n) operations from the actual email send job: 5x faster.
  • Total speedup: Roughly 150x performance improvement.

Compounding Advantages

The biggest myth about successful people is the “overnight success.” There’s basically no such thing. This is a great platitude, which happens to be true, but how can we deconstruct it down to its quintessential lesson?

The first point of order is to understand where advantages that lead to success come from. They might come from raw talent – which I won’t focus on, because it isn’t something you can control for (and experience is often confused with raw talent, because they look the same to outsiders). Or they might come from external sources – such as growing up with good financial security, in a two-parent household, in a well-off neighborhood with good schools. Those types of advantages are mostly out of your control as well, so that’s out too. Finally, there is experience.

Experience is the advantage most under your control. When most people ask me for advice about careers in computer science, they often know they are at a disadvantage (often because they are switching career tracks), but aren’t sure of the most efficient way to erase that deficit. But what appears to be an insurmountable disadvantage is usually the result of years of hard work, or a lack thereof.

So how does one gain experience without any experience? Isn’t that like the some sort of catch-22?

Not really. If it were, then by definition the industry couldn’t possibly exist, now could it?

(Normally, when people claim that it’s a catch-22, they’re just being unrealistic about what types of jobs are actually entry-level, or, more likely, they aren’t willing to do what it takes to become qualified for entry level jobs. In fact, software engineering is one of the easiest jobs to gain experience in, because all you need is a keyboard and monitor that eventually connects to the internet, and some free time. So whining about it is just immature.)

This isn’t really an essay on how to get into software engineering, since I’ve already written a bit on that topic. But there is a recurring theme, which is that it takes consistent application of conscious effort to build and maintain the credentials to become an engineer. And most importantly, all experience advantages start small, and compound over time. So the best way to become the best engineer is to start coding, a lot. Today.

Why coding?

Because while software engineering is about much, much more than just coding, coding is the most important part. It’s the only part you can’t skip. It’s also one of the easiest skills to show off and test for.

OK. So what should you code?

There’s no one-size-fits-all answer, but here’s a few starting points:

1) Go to Codecademy and start one of the courses. It almost doesn't matter which one, since they're all pretty solid.
Pros: Structured learning with helpful hints and explanations, sense of progression.
Cons: Toy problems that don't require reading existing code as much as the other options, an extremely useful skill.
2) Take a Coursera course (core concepts with programming involved -- data structures, algorithms, operating systems).
Pros: Online-classroom environment, instructor-led with a focus on fundamentals.
Cons: Academic in nature, which is actually sort of a plus, but it won't maximize lines/code per day.
3) Download a release of Ruby on Rails and start a web app.
Pros: Good documentation and explicit best-practices, more "realistic" than some guided courses.
Cons: Undirected learning. Requires product management to design things to code, which is a distraction. Too much Ruby/Rails "magic" abstracts away important concepts.
4) Browse Github (etc) and find an open source project to contribute to.
Pros: Working on released software, chance to interact with other coders. Most "realistic" experience.
Cons: Reading code is significantly harder than writing code.
5) Download the iOS / Android SDK and create a mobile app.
Pros: Everyone loves mobile.
Cons: Learning programming, a programming language, how to read documentation, and a complex API at the same time can be extremely overwhelming.

So…About that degree thing

I’m of the opinion that most software engineers should get a Bachelor’s in Computer Science. I’ve hammered on this point before. There are exceptions though. Like, do you know your computer science fundamentals (data structures, algorithms, operating systems, programming paradigms, software lifecycles)? Do you have practical software engineering experience (e.g., measured in years), doing work that shipped?

If not, I still recommend a CS degree, because it’s an excellent signaling mechanism, and you can complete one full-time in less than the traditional 4 years. However, coding boot camps have been all the rage lately, and I wanted to touch on them briefly.

Basically, coding boot camps are an excellent option for many people (and I know of many who have successfully gone this route), but I don’t recommend them in general because the best engineers aren’t minted in 12 weeks. It’s a different story if you already have some experience under your belt, but don’t want to get a full-on BSCS. But in that case, a coding boot camp generally isn’t really tailored for you anyway, since most programs don’t require existing experience by design. And that means you lose the benefits of a compounding advantage by not building on existing experience.

This is the main advantage of following a degree-granting program. It starts with the fundamentals, and then builds on that foundation with programming experience and core theory, leveraging your existing knowledge.

Boom.

You gain a small advantage, compounding itself.