Coding tricks I learnt at Apple | Hacker News Reader

Coding tricks I learnt at Apple

blog.joemoreno.com

192 pointswhiskers95 comments

> These tests were run against a copy of the live database in a production environment.

This is pretty terrible from a security standpoint. A development environment is typically much less secure than the live environment, and for good reason. The development environment must be accessible to developers, typically both on-site and remote. All developers have access to test databases for the purpose of testing their changes. There are often many more software packages in a development environment, and development servers have a higher probability of running vulnerable services. Live environments typically have much better logging and auditing.

Every company should have a program that can be run to sanitize the live database for use in testing. I've seen too many situations where the production environment was appropriately locked down and audited, but the development environment was compromised. It's not unheard-of for a developer to lose possession of his laptop, and if it contains a copy of the live database it's no better than the site, itself, being compromised.

You raise a great point that I wished I had clarified. I worked on the product side of the store, not, say order fulfillment, order integration, etc.

Multiple databases made up the live environment. The developers did not have access to the live environment. As a matter of fact, we had developed it to the point that, except in special circumstances, the engineers didn't even know what products were about to be announced until Steve Jobs announced them to the public.

The dev database was a copy of the products database – most everything in the products database was either public information or it was obsolete data for EOL Apple and third party products. I don't recall ever seeing any sensitive data in our production environment. Unlike, say Walmart or Amazon, we didn't need to keep track of inventory since we build the products (the only exception that comes to mind were the refurbed products since there was a limited amount of inventory).

Dev systems would process dummy credit card numbers, etc, in dev (but I didn't work, in that area). The applications were smart enough to figure out which environment they were in when started up which is a big help.

Every company should have a program that can be run to sanitize the live database for use in testing.

+1.

However, modifying or sometimes even a dump/load on a SQL database can change its behavior dramatically.

But the harder part can be getting a hardware setup similar to production. Most places want their newest, best hardware in production for obvious reasons. Few places want to pay for mirror-image production systems just for testing to bang on.

There's the old saying: If you have two systems, 'production' and 'testing', the one with the more challenging load is 'testing'.

You make some very good and interesting points, though I think it's wrong to just presume Apple is lax on security based from that one sentence.

I have to second BrandomM's comments. Don't make a complete copy of your live database to use in dev. Sensitive data needs to be scrubbed, ideally by a bona fide DBA, before bringing it over. Best to avoid this if at all possible so you don't have to worry about overlooking something that was sensitive.

Also, I don't recall ever seeing any security issues with our environment or how we handled the code and data. There were some very smart engineers "minding the store."

I agree. My main intention was to inform would-be copy-cats that they shouldn't play fast and loose with copies of their live database. I'm sure (or at least, I hope) that Apple is smarter about sensitive data than that.

> These tests were run against a copy of the live database in a production environment.

Read above line twice. He is saying that test is done in 'production environment'. Do not assume there is 'development environment' for testing within 'production environment'

The "production environment" is obviously not a "live production environment"; it's some kind of development environment.

And mostly, I made my comment in the hopes that people here wouldn't go, "Oh, Apple tests against a copy of the live database. I should do that, too!" I'm sure Apple is smarter about it than my comment indicated.

My point was simply to be careful with the live database. Investing in state-of-the-art protection and auditing in your live environment can be trivially defeated by simply copying the live database to an insecure environment. So don't do it.

In my experience, large high tech organizations have many environments such as dev, build, QA, staging, demo, live, etc. The really good organization, with the smart engineers, have built this environments over the span of years and they've carefully thought through how each environment works.

Also, some organizations, especially ones that use cloud computing (EC2, Slicehost, etc) have the option of creating a staging environment for QA. testing, etc and, if everything checks out, the staging environment can be restarted as a live environment (there are ways to do this safely and securely) while leaving the previous live environment live. If, for some reason, you find problems with the new live environment, then you can simply shut it down and keep the old live environment humming along. Of course, this is easier said than done, but it'll keep the anxiety level down.

Another good idea is to have apps that know which environment they're in when they start up. So, if an app starts up in dev, it should only access the dev database. If it starts up in the live deployment environment, it should only access the live database. To enforce this security, the live database must only allow connections from clients in the live environment (IP address).

But, these "self aware" apps don't necessarily need (probably should not) have configuration files with the sensitive data used to access databases, credit card processors, etc. Rather, at app start up, these apps should know which environment they're in and then go over the network to fetch the sensitive data used for logging into databases, services, etc. (The apps should only store this sensitive data in memory.) The services, on the other end of that connection, should be checking the IP address of the app which is asking for the data to ensure that there isn't a mixup.

Its often called a staging environment. Everything is the same as production, except those things that simply cannot be the same, as you pointed out.

Hash tables are worst-case O(n) time.

B-trees are an external storage technique; he means balanced binary trees.

The answer to the interview question is another question: "what operations does the container need to support?". It's not "hash tables are O(1)".

He does say: "Perfect hash tables always win, hands down."

A perfect hash table does have O(1) look-ups in the worst case.

I saw that. From the context of the article, do you think he was really talking about a system using perfect hash tables? Be that as it may, "use a perfect hash table" is rarely a good answer to the job interview question, which is the only reason I commented on this.

A really perfect hash table is just an array ;)

Since they did load testing to optimize performance, I think his argument stands. If they didn't bother to optimize I would agree with you.

Yes. So?

There are lots of other constraints that come to mind. Do we do frequent insertions/deletions?

What are the memory constraints?

What is the size of the unhashed key?

And many more... No data structure always wins.

Only if you neglect hashing time (significant with perfect hashes) and comparison-time. That makes them O(k), not O(1). It is helpful to me to think of hashing as expensive as copying.

Radix tries on the other hand don't hash. They're always at least O(k), and you can find the next and previous values (lexicographically) in O(k) as well. They're also more compact and you never have to resize your tables.

Hash tables are worst-case O(n) time.

That's important to keep in mind, particularly for DoS resistance. But isn't it really as much of an oversimplification as saying they're O(1)?

In practice, there are inexpensive ways to consistently avoid that worst case. But you do have to know to do it.

Hmm reminds me of some code I should probably go double check...

But isn't it really as much of an oversimplification as saying they're O(1)?

No, because big-oh notation implies worst case. It's an asymptotic upper-bound. If you want to talk about average case, then you need to qualify what your assumptions are. So insertion into a hash-table is O(n), but if we assume an even distribution of keys with a sufficiently large table, then insertion is O(1).

Big-O doesn't imply anything, it talks about functions, not algorithms. There are no laws of the English language that say a big-O bound implicitly refers to the function f(n) = max { T(input) : input is of size n }. Or with hash table insertion it's more like f(n) = max { T(h, input) : h is a hash table of size n, input is of size g(n) } where g is some Theta(log(n)) function. The proof that there's no guarantee that big-O notation refers to some worst-of-worst-case running time function is that people are using it in a way that makes you angry.

Yes, it talks about functions, and when used in the context of algorithms it describes the asymptotic growth of the function that describes the runtime behavior of an algorithm. There are no laws of English but there conventions of Computer Science that say when you say an algorithm is O(n), that implies that in the worst case, it will be linear.

For any given algorithm, the worst-case runtime behavior of an algorithm and the average-case runtime behavior are described by totally different functions, each of which has its own big-O.

There are no such conventions, you have just implanted in your mind this idea that there should be such conventions. People say that quicksort is O(n log n) all the time. They say that hash tables are O(1). It is normal for O notation to refer to average case or a set of cases with probability 1 of occurring.

Sure, but they should not say that hash tables are "O(1)", (perhaps "average case O(1)" is better). Unlike qsort's n^2 worst case, the conditions that degrade hash tables are very common: all you have to do is specify a crappy hash function for your load, or size the table poorly.

This is kind of a silly semantics argument... but, if you interview for a job and look like a deer in the headlights when I said hash tables aren't O(1), NO HIRE.

Unlike qsort's n^2 worst case, the conditions that degrade hash tables are very common: all you have to do is specify a crappy hash function for your load, or size the table poorly.

(I'll assume you're talking about the quicksort algorithm rather than the qsort() function because you're comparing it to hash table accesses in general rather than a specific implementation of them.)

But I'm not sure I agree. The worst case for quicksort is an already-sorted list. I run into this scenario all the time, though usually in a slightly different form. When I iterate through the elements of one of the tree-based containers std::set and std::map they emerge in sorted order. If, inside my loop, I then insert them into a similar container I end up with worst-case performance. The other day I replaced std::set with std::unordered_set and saw a dramatic increase in performance, although it may not have been entirely due to this effect.

On the other hand, a non-crappy hash function should be available to everyone at this point. Personally I like FNV-1a, but haven't found an issue with whatever my C++ standard library is supplying. I have spoken with other programmers though who didn't realize hash tables needed some empty space to perform well or had stumbled into a pathological case with their oversimplified hash function.

This is kind of a silly semantics argument... but, if you interview for a job and look like a deer in the headlights when I said hash tables aren't O(1), NO HIRE.

Gee Ptacek, what do you have against deer? I can just imagine some poor interviewee with a bright desk lamp shining into his eyes...

There are such conventions. Take a look at an algorithms textbook, or a theory paper. That some people are semantically lazy does not change these terms have established definitions within computer science.

Well, the idea of conventions is that people agree to use them. I see a lot of variation in the degree to which people know about or are attached to this one.

While there may be a set of textbooks and papers for which the editors would have flagged "worst cast O(..)" as redundant, I think it's relevant to point out that the use of big-oh notation in mathematics predates computer science. So to the extent algorithm analysis is a branch of mathematics, those who use big-oh in this more general way are in fact consistent with the larger body of work.

Those are the conventions in Computer Science, but the conventions in Software Engineering are different. Words having different meanings in the jargons of related fields is a really old problem, and one which has bitten me from time to time. At least we aren't arguing over whether a factor of 10 increase in something is a 10 dB or a 20 dB change.

Knuth TAOCP 1.2.11.2 People often abuse O-notation by assuming that it gives an exact order of growth; they use it as if it specifies a lower bound as well as an upper bound. [It looks to me like Knuth does this on page 389 2.3.4.4 right after equation 14.] For example, an algorithm to sort n numbers might be called inefficient "because its running time is O(n^2)." But a running time of O(n^2) dos not necessarily imply that the running time is not also O(n). There's another notation, Big Omega, for lower bounds

I find this a bit confusing because it's unclear to me what Knuth actually endorses for use in average case description.

Wikipedia: Although developed as a part of pure mathematics, this notation is now frequently also used in the analysis of algorithms to describe an algorithm's usage of computational resources: the worst case or average case running time or memory usage of an algorithm is often expressed as a function of the length of its input using big O notation. Wikipedia and the web in general have many examples of "worst case O(...)" which would be redundant under your convention.

So clearly one needs to be vigilant about assumptions when discussing average case, but common usage does not agree that big-oh notation implies worst case.

I agree that the article was wrong, but...is there really never a case in which a B-tree is a useful in-memory index, rather than a storage technique?

I'm only commenting because of the "job interview" comment, but when someone compares hash tables to B-trees, I usually assume (fairly or not) that they don't really know what a B-tree is.

So what you are saying is that the whole database research community does not really know what a B-Tree is [1]?

[1] Every database implementation techniques lecture compares the two. See, e.g., http://infolab.stanford.edu/~hyunjung/cs346/.

You know that's not what I'm saying. You're just trying to assert nerd dominance.

Ah, thanks for clarifying. I had to implement a B+-tree using only a 2D byte array as a sophomore, so I don't think I'll ever be able to forget how they work.

It's possible. There are parallels between main memory and disks. A disk seek gets you hundreds or thousands of bytes and requires (blocking for) millions of cpu cycles; a cache line fill gets you 64 (sometimes) bytes and requires (spinning for) hundreds of cpu cycles. You want to minimize both of those, but with memory, the difference is much less dramatic.

Well, you can walk spatial partitions with trees in ways that become clunky with hashes (taking a branch means all children are 'near' each other). Also, B-trees might work better in cached architectures -- this is certainly true with respect to disk accesses but I'm not sure if that carries over to L3/L2/L1 cache.

B-Trees actually have superior cache performance compared to other types of trees (such as T-Trees or BST Trees). In part, this is because B-Trees have a higher density of actual data to pointers.

There is a tradeoff of computation (doing binary search inside the node) and amount of storage (keeping less pointers). In environments where memory access is much more expensive than a CPU instruction, it is preferable to perform these computations than to have to read all the extra pointer data to jump to the right places.

In fact, a breed of cache-friendly data structures are precisely based on the B+Trees but with even less pointers, having the algorithm compute these pointers instead (CSS-, CSB-Trees)

It does carry over to L3/L2/L1 cache, but only if the tree is designed to benefit from that. See http://blogs.msdn.com/b/devdev/archive/2007/06/12/cache-obli... for one strategy to do that. (With that structure lookups become faster, but walking the tree in order becomes difficult.)

This is a really great article and I wish I could give you some more points to make this appear higher. I once used a cache-oblivious matrix transpose algorithm that was startlingly simple and effective but I didn't know the approach had been so widely applied. Thanks!

Sorry about my typo. I really meant binary trees, not b-trees.

Thanks for that catch. Yes, I meant binary trees.

For some reason, binary trees look real cool when you learn about them from a textbook that people sometimes forget about hash tables. But, that might just be my personal experience from candidate interviews.

no real tricks here, this guy just seems happy he worked on a team with professional standards. thorough testing like that is, while not the norm, pretty commonplace at most of the better places i've worked.

Yeah, I would have liked to see specific things he learnt at apple. Load testing tools, algorithms for caching, how and which metrics they measured etc.

I am trying to figure out who would find this article useful without any details.

Those who would find this useful are those who have not figured out that following these basic principles WORKS. Too many teams think bypassing mundane correct process will somehow buy them time. There is no magic or secret to great success, only doing things right all the time.

Yup, I have to agree with you that I was very happy to work on a team with professional standards. While commonplace at high tech organizations, there are many non-tech organizations with their own tech teams which aren't aware of good practices since it's something that you have to experience, rather than be taught from a text book. That non-tech group is the one I'm really hoping to reach.

We had one, highly specialized piece of software code which could only be checked out, worked on, and checked in by a single engineer at a time. You were only allowed to touch this piece of code if you possessed a physical token.

Ahh, the all powerful Source Control Shingle: http://thedailywtf.com/Articles/The-Source-Control-Shingle.a...

This is really interesting and I would love to know what the code in question was responsible for.

Requiring that work on it be done single-threaded like this suggests that some other part of the overall process broke down somewhere - the developers/automated tests/continuous integration server couldn't catch merge conflicts? Code reviews weren't done and made visible to everyone else on changes to this special code?

Not necessarily. It could be a particularly tricky and critical piece of code that they want to ensure nobody is "auto-merging" into oblivion.

By putting a mutex on it, you are forced to re-evaluate the state when you obtain the lock. You can't sneak in a change in front of somebody else's change, requiring them to re-evaluate (or, worse, merge and hope).

If it was required for modules all over, it would be broken process. For a single module, I can understand it.

Good question - though I don't think it's a problem of broken process, but an absence of processes like you listed above. That's when these types of "solutions" are devised/used.

Two things I've learned in my years as a developer:

1. Sometimes the best process is old fashioned communication between people with common sense.

2. Never underestimate the power of a rubber chicken.

>1. Sometimes the best process is old fashioned communication between people with common sense.

I most wholeheartedly agree. Git, or a Source Control Shingle cannot replace effective communication. In fact, a solving a merge conflict is much more painful than a quick discussion.

VSS did this with all files by default. Does that put VSS way ahead of its time? :)

I'd actually take a Shingle over VSS. At least a shingle can't crash and corrupt all your revision metadata.

No. God no.

Perhaps I'm too attuned to NDA issues after having listened to the most recent episode of Gruber's Talk Show (http://5by5.tv/talkshow/46), but I am guessing that this guy is coming dangerously close to — and is perhaps crossing — the line with respect to disclosing details about Apple's technology and software development practices.

When in doubt, STFU. Not just for legal reasons, but also because you don't want future collaborators and employers thinking you're a Chatty Cathy who's going to tell everyone about your secret sauce.

I agree. He should remove the picture of that Darth Vader token immediately, it's clearly a very important Apple trade secret.

s/Vader/Tater/

I wouldn't want to work for any company that'd take issue with an article similar to this one.

"Take issue with" is vague. Is someone at a company allowed to think, "Dude, you don't talk about Fight Club"? Is that too extreme a reaction? Or are you talking about the legal department filing a lawsuit. Or something in between?

I don't think it's fair to expect Steve Jobs to hop in his helicopter and track down Joe Moreno so that he can high-five the guy for writing something that got on the front page of Hacker News.

It was in part a response to your suggestion that the author might be toeing the line of an NDA violation. The idea that a company would make you sign an NDA prohibiting you from discussing the development methodologies in use is a bit ridiculous to me. (Not that I don't believe that it could happen, but it's not a company I'd want to work for.)

Also, the "because you don't want future collaborators and employers thinking you're a Chatty Cathy who's going to tell everyone about your secret sauce" bit rubbed me the wrong way. I mean... really? I feel like that rates high on the unwarranted paranoia scale.

It's not unwarranted paranoia, it's treating people — and employers are people, by the way — with consideration, respect, and discretion.

Just what crept up my mind when I read the article. But then I realized: If American culture allows this kind of insight publicized, what boon that is to freedom of thought and freedom of expression!

All around us we see civilians cuffed and murdered for their opinions (for example, in countries with dictatorial regimes), but apparently this is not the 'status quo' in the USA.

Just imagine what MS and Google could do with knowledge of Darth Tater.

edw, you raise a good point. Keep in mind that Apple has hundreds of development teams. Each one is different. I don't think I disclosed any secrets and I was very careful to not say anything that might embarrass Apple.

I think Guy Kawasaki's first book, The Macintosh Way, goes much further than my comments here – and he was even rehired back at Apple several years after his book was published.

My hope is two fold. 1. That someone reading this would pick up some good practices; and 2. That someone reading this would say, "I want to be a part of that!"

Apple's a great company to work at on so many different levels.

So this is all well and good if you work with a team like this. But I have two questions:

(a) How do you find out, before going to work somewhere, whether they actually work like this? Are there questions you can ask? Word of mouth? ... ?

(b) If you don't work somewhere like this, how do you start putting professional processes in place? Assuming in particular that you have never actually worked somewhere like this, so you can't speak from experience, only from instinct about what seems to be a good way of working.

> We had one, highly specialized piece of software code which could only be checked out, worked on, and checked in by a single engineer at a time.

Why? Also, is this common these days?

Wait a sec - "it was always an interesting experience to turn the store back on after Steve Jobs walked off stage following one of his keynote presentations"

Does Apple seriously turn off their store while Jobs talks? Or is he talking about pushing new content out based on announcements?

The former just sounds... Odd.

They turn the store off when they introduce new products, I suspect more as a tradition than anything.

You wouldn't want an uninformed person buying an iPhone 3GS after Steve has already introduced the iPhone 4, but you don't want to put it up for sale yet because the media should be paying attention to Steve, not the store. If they just launched the item with all the specs on the store as soon as it was introduced in the keynote or media event or whatever, then it would ruin the suspense. Jobs is a salesman.

Yep. During keynotes, the web store is usually "down for maintenance". For simple reasons - they don't want to pre-announce before "The Steve(tm)", but they want to have all the new products immediately available after the keynote.

Ok, but that sure sounds like a design flaw. I would have expected that they would still have an option to push the new products live at the time of their choosing vs. disabling online purchases of their existing products.

I would think an appropriate separation of content from the site itself would allow them to reach their same business goals without deliberately giving themselves an outage.

It's not so much a technical issue as it is a marketing decision. The store being down creates a sizable amount of suspense. Of course they could leave it up if they wanted to, but it's as much part of Apple folklore now as Steve's turtleneck.

Yup, we turn off the online Apple store during the Steve Jobs keynote. Next time he speaks, check out store.apple.com and you'll see the yellow "We'll be back soon" sticky. If my memory serves, it's been like that for at least ten years.

Apple generally turns off the store for keynotes related to new product launches (new iPhone, sometimes MacBook/etc refreshes).

I suspect he means both. Apple turns off their store (i.e. puts up the "We'll be right back" post it) and prevents orders when there is a major product announcement. They turn it back on (with new products) after the announcement is over. I bet there's one hell of a traffic spike after those keynotes.

It seems to me that the author was very proud of the O(1) sophisticated caching algorithms invented at Apple.

I was thinking the physical token would have had a USB connector that you actually had to plugin to use it.

"Before writing any production code, we'd write our unit tests." With XCode? Somehow I have my doubts.

He mentions they're using Eclipse. The store is written with Java/WebObjects.

Xcode 4 offers to create unit test files when you create new project and it can run them. But there are other approaches: http://www.raywenderlich.com/3716/unit-testing-in-xcode-4-qu...

How can I learn how to test like Apple does? I feel like I don't know where to look for good resources on thorough website testing.

I'm afraid the methodology described has little to do with Steve Jobs.

When you're asked, during a job interview, which is the fasted lookup function, don't, as is very common, say, "a B-tree." Perfect hash tables always win, hands down.

Wait, saying a B-tree is the common answer?

Furthermore, B-trees are designed for storing things that don't fit into primary memory. They are the right answer for things like file systems, I think almost every file system uses some variant of them.

Surprisingly not: https://ext4.wiki.kernel.org/index.php/Frequently_Asked_Ques...

http://www.geeksofpune.in/drupal/files/8058778-ext34talk.pdf

ext2,3 used an indirect-block tree structure. Ext4 uses an extents system which is nicer, but still not (AFAIK, I've only skimmed this part) a B tree.

>"Coding tricks I learnt at Apple"

I'd wager "learning how to properly use 'learned'" wasn't one of them.

http://www.urch.com/forums/english/9214-learned-vs-learnt.ht... "The descriptive answer in American English is: There is no such word as "learnt". Use "learned" always."

Hate to break it to you, but not everyone on the Internets speaks American English.

You don't sound like you hate it one bit.

Ignoring that the submission title doesn't accurately reflect the original title, and even though you might be right, I'm having trouble understanding your decision to cite a 2004 post by user "Rommie" of the Urch forums as an authority on American English.

The article's title is "Tricks I Learned At Apple: Steve Jobs Load Testing"; the use of "learnt" must have been from whiskers who posted it.

I'm from the UK - learnt is perfectly valid here!

<nod> I wasn't asserting that you were wrong, only that the user to whom I replied that implied the author of the article used it incorrectly was wrong in his assertion.

With that sentence construction, you could be a lawyer :)

With that sentence construction, he must be a Perl programmer.

Thanks... I think? I'm a programmer by trade, and perl is but one of many languages I use with regular frequency.

Yeah, but so is 'kilt'.

In the US, we consider that poor grammar, as in: "I done did kilt three of 'em skeeters on me yesterday."

OK, maybe yours is a noun, but still!

Reply on news.ycombinator.com