It’s hard to tell what info is going to be useful and what is fluff

Classes in school (at all levels) lead to lots of wasted effort, because a lot of the stuff you’re supposed to learn is simply not useful knowledge. For example, for one college exam, I had to name about 30 different rocks and minerals by sight, and the names are very complicated. People say: “well just going through the process is teaching you how to think.” I don’t disagree, but I think that’s a fallacy; learing to think and useful knowledge are not mutually exclusive. Useless knowledge includes specific dates, long names, irrelevant historical events, and other things we might in everyday life dismiss as “trivia”.

In my experience, all academic disciplines have room to reduce the “trivia” overhead in their curricula.

In college computer science classes, there is not a whole lot of trivia. However, their is a “jump into abstraction” that often left me confused. I quite often didn’t understand why what I was learning was important. Edsger Dijkstra said we should teach the abstractions before rotting the students’ brains with modern programming realities and deficiencies. That’s a laudable mission, but problems still need to be better motivated.

Difficult material with no motivation is not rewarding

E.g. during my first Operating Systems course. Everything seemed way more complicated than anything I should ever be expected to know in real life. So I figured I would never end up needing to understand virtual memory, processes and threads, scheduling, networking, etc. In reality, I just had no idea what I was talking about, and that’s why it should have been motivated. For example, I have since learned that the Linux kernel has a very interesting open source development ecosystem. They are making upgrades to the thing all the time that affect everyone developing most kinds of modern software. In addition, a whole lot of the different features of computers are motivated by internal business tool usecases, rather than home consumer usecases. Being a college student without a computer nerd background, I had no idea about any of that. Being taught to appreciate how important this stuff would end up being for me would have made me learn drastically more during the course of the class.

What I wanted at that time was for the material to be motivated with an example, like, “let’s build a program for running a medical radiation machine.”Now we’re talking; we’re going to need to get all the different low-level components right and make them fit together so that we can save lives!

What actually happened was similar in content, but not in objective. We were expected to read a very long and dry paper on the Therac-25, a radiation machine with concurrency issues that killed a few people in the 1980s. I spent a few hours trying to read the paper. One could say I was spending that time “learning to think”, but I think I spent that time “getting nowhere”. The whole time I was reading the paper, I was thinking: it would take me so long to get to the point of this paper, and I’m not even going to get a whole lot out of it. No good. In the end I learned about the Therac-25 from Wikipedia, a source of information whose expected readership has a level of background knowledge more commensurate with my own. Then, a few years later, I had to read that paper again for a graduate operating systems class, and at that point I had sufficient background knowledge to simply read the paper and feel like I understood its content and learned important lessons about software engineering.

This example demonstrates the fundamental principle that the same content can lead to completely different learning outcomes for different people, and even for the same person at different points of time and (as we shall return to later) in different emotional moods.

Some keys to not wasting effort

• Have something in mind that you want to accomplish with your newly-obtained knowledge
  • E.g. “I want to build the software for a medical radiation device”
• Have someone (colleague) or some place (e.g. stack overflow) where you can ask questions when you get confused
  • Sometimes having another person just explain the whole thing in one shot face to face can lead you to simply just get it
• Learn the relevant vocabulary for the field on wikipedia
  • For example take at least half an hour digging through linked topics until you have a general grasp of the various concerns and their names, and ideally how they relate to one another
• Skim liberally but don’t expect to understand what you skim

Qualities of time

During college, I learned from an Aaron Swartz article about how one can’t just spend all day reading tough material because it’s too mentally strenuous. Instead, you have to choose the right activity for the mood you’re in, and there’s not a whole lot you can do if you’re just not in the mood to learn anything. Mr. Swartz says we should have a todo list that is aware of the fact that different tasks require different levels of mental effort. Maybe after reading my compilers textbook for an hour I’m mentally tired and physcally peppy, so I go for a jog. Then I’m relaxed and ready to work on writing code for a program. Then I’ll get overwhelmed so I step back and plan out some next steps for the program. By now I’m sick of the program so I meet some friends. Then I’m tired and take a nap. And so on. The point is each activity follows from the next according to my current mental and physical state. So many people don’t start the project until the night before, and have to do one strenuous activity all night, fighting exhaustion, and not really getting much out of it because it’s all slapped together. Granted, plenty of people are really proficient at getting that strategy to work out.

Find the right source of information for you right now

Some places to learn things include youtube, conversations, podcasts, wikipedia, books, tutorials, projects, and blogposts. In terms of enabling lots of deep and useful knowledge to be gained per minute, the most effective might be reading a great book, and doing a great project.

Try out a few different compiler books

Finding a great book can be pretty challenging, because you may spend some time reading the wrong books. But it is worth it, because the right book can make a big impact. After looking for some time, I have finally found a compilers book from which I am learning what I wanted to know. (It’s cover happens to be quite ugly compared to the other compiler books.) Before that I tried reading a hundred pages of each of a few more theoretical compiler books, but over time I decided that for now I’m more interested in learning to write the code, over understanding the theory. So the book I found is a tutorial for building a Pascal compiler from scratch in Java, with real executable code accompanying the text. The point is I found a book that is teaching me what I want to know more efficiently than several other popular books on the subject. And I know that from having tried out the other books. I think this is a useful strategy in general.

Try out a few different algorithms books

I went through a similar process for learning the fundamentals of algorithms. First I took the class in school and got an A. I can’t say that did me much good, as evidenced by failing many easy job interview questions. I didn’t like to go to class so someone else would hand in my homework. I studied for the exams directly from the book called “Algorithm Design”.

After failing at interviews, I started rotating through different algorithms books. I finally sat and (over a few months) read the whole explanatory section of “The Algorithm Design Manual,” but didn’t feel like was walking away with a good grasp of the material it covered.

So I tried to read the classic “CLRS”. After reading about two chapters then skimming around, I decided I wanted to focus on implementing algorithms instead of proving correctness and complexity bounds.

So I started “Algorithms” by Sedgewick and Wayne. It started off pretty slow, so I found that by skimming, I was able to read a few hundred pages in the first few hours, which wasn’t productive but motivated me to get into some more challenging material. So I skimmed up to a lot of material that I didn’t already know (I think chapter 2 or 3).

In addition to incredible explanations, the book has clean code, amazing diagrams, easy, medium, and hard code and theoretical exercises, a full sequence of lecture videos by Dr. Sedgewick himself, etc. With this mix, I was finally able to achieve a satisfying learning per minute score. In general, I was able to just “follow along” with the book and understand things as they came.

The whole time I was reading this book, whenever I found a concept hard to grasp, based on my bad experiences with other books and classes and tutorials, I could rest assured that it would be unlikely that I could find a better explanation elsewhere. This attitude strengthened my resolve, and I ended up reading and understanding almost everything in the book.

Maybe it’s just the tone

I have always been deeply affected by the tone in which information is presented to me in turms of being able to remember it. So have you, just ask your parents. I’ve had professors I couldn’t stand teach me subjects I love and walked away with nothing from that class. And vice versa. Everyone knows that. It’s the same with textbooks. I think the key is inspring the student about the potential of what they can do with the knowledge, and to actually convey the excitement of it!, instead of simply boring you to tears with facts.

One thing the Khan Academy (among others) has brought to teaching is excitement for the actual content. The end result is that people (e.g. me) can actually bear to spend hours watching and re-watching Mr. Khan explain differential equations. He’s doing a taylor series expansion, and he’s like “just check out how cool this is!” and I’m like “yeah, expand that shit!” Whereas otherwise I’d be sitting at class at 8:30 in the morning like, “FML I can’t believe I’m not sleeping right now”. Junior year of college, without Khan Academy’s help (and Paul’s Online Notes, a free math textbook), there’s no way I would have done so well in diff-eq, which gave me the confidence to transfer into a computer science degree later on.

When to skim

Most of the time, skimming material does not lead to understanding the material. Instead, it only leads to some kind of awareness of the material; that feeling later of “yeah I think I’ve seen this stuff before”. That said, skimming is often crucial, especially for reading blogposts.

Blogposts may be written with any of an assortment of aims.

For example, the author may be trying to assert her expertise in an area by providing a good explanation, in order to further her career. Those vary widely in quality, and can occassionally be read deeply for understanding. Data science has a huge number of those.

Or the author may be trying to clear up his own thoughts on some subject. That’s what I’m trying to do here. In that case, skim to find the parts that are relevant or entertaining, and read those.

Or it may be written for the author to remember something, like “how to get HDFS running locally on Mac”. Thank heavens for such blogposts.

Or it may be some sort of war story: “this is what we did, and this is how it worked out”. If you’re trying to build a complex system, you probably want to read some of those.

Lectures are generally only worth skimming. It takes me less effort to understand a lecturer than to understand a book. But even when it’s clearly stated, the lecturer is generally not divulging much information, and when they start to say something actually complicated, it becomes easy to zone out, get lost, and lose interest. They may also get lost on side-tracks or try to pull things in that they think are cool. A great lecturer can be a very entertaining way of learning, but it’s generally not time spent learning nearly as much substance as can be read from a page. Please note, hour long lectures are quite different from a super-helpful and targeted 5 minute youtube video.

One useful question to ask before reading something is “Can I just skim it?” The answer to this is yes if you don’t want to be able to actively use that knowledge in the future. Often, skimming is useful for verifying that you understand something that you learned about elsewhere. For example, if I were to skim a tutorial on parsing theory, I would be able to roughly guage how much of that stuff I actually understand based on how much I’m recognizing concepts and “agreeing with the author” as I skim.

A frustrating situation is to read something deeply when you could have just skimmed it because there was nothing really there. Maybe this can be avoided by skimming first to see whether it’s even worth really reading. But I never do that.

Another time skimming is useful is when you’re stuck. When I got stuck reading about computer architecture, I would go back to the table of contents. “How did I get to where I am?” “Where are we going with this stuff?” “What do I find interesting about this?” Then I would skip to some figures. Look at the figure. Is it cool looking? Wouldn’t it be fun to understand what it means? Let’s look at some of the keywords in the text near the figure. Oh there’s some words I’ve seen before but didn’t understand, I guess they were important. Now I can go back to their definitions and see if I can place them properly in the figure. And so on.

Is learning important

By getting better at seeking out the best sources of information, we build an improved ability to affix knowledge into the brain accessibly, without expecting the best educators to just to fall in our lap when we need them. Here, I have tried to explore and share some lessons about building the conditions for learning efficiently.

In short, they’re looking to build systems that will “one day” recommend more effective treatments for diseases including cancer and Alzheimer’s within an hour of receiving a patient’s DNA sample. They describe several components of what needs to be done to make [research toward] this possible.

ADAM according to YouTube

See the references at the bottom of this post.

They didn’t explain much of the actual genomics, though what they did explain of that, they did with laudable clarity. In essence, the first step is to assemble (“sequence”) a large number of small strips of DNA into a single massive (250 GB) chain (per sample per person), even in the presence of small errors in the small strips. Ok now the the second step is to take the data from multiple samples from multiple people, and find anomalies that correlate historically with the likelihood to end up being diagnosed with a particular disease. These anomalies may be on the scale of a few single-character changes scattered around the DNA, again in the presence of mistakes in the transcription of the DNA. So statistical techniques are used (from what I remember, Poisson random sampling methods and binomial Bayesian methods, and Chi-squared independence tests) to evaluate the confidence in the correlations.

According to the lecturers, currently, techniques for doing this sort of computation and analysis relies on code written by PhD students in genomics, who are not so interested in writing high quality code, as learning about genomics and finishing their dissertations. Therefore, there are many (compressed) file formats, and processing subsystems written in every programming language you can think of. These subsystems are assembled together by piping data through the filesystem between each compoenent. Many of these subsystems are inherent unscalable.

All these are issues the researchers at the Big Data Genomics project are trying to solve using ADAM. They reported in SIGMOD 2015 to have achieved a 28x speedup and 63% cost reduction over current genomics pipelines. The Big Data Genomics project is a collaboration between researchers at the AMPLab at UC Berkeley, and other genetics and cloud- computing research institutions and companies. They note that their ADAM pipeline infrustructure is able to accommodate analyses from other areas of scientific research as well, including astronomy and neuroscience.

Producing a high-quality human genome currently takes 120 hours using a “single, beefy node”. Their improvements involve using map-reduce (via Spark), and columnar storage (via Avro & Parquet) to distribute the workload across a scalable cluster, so their 28x speedup is probably something people are happy about.

A major issue faced by genomics researchers is the proprietary nature of the data. This means that researchers must collect and process their own data, which is heavily human and computer labor intensive. The humongous (I mean really…) nature of the datasets means that the only practical means of transferring them is by shipping boxes of hard drives. As data collection gets easier, and the amount of data available explodes, even shipping boxes will become impractical. So the vision is to keep the data in the Simple Storage Service (S3) hosted by Amazon Web Services (AWS) so that it can be operated on via Spark without being copied into an institution’s private data center. This is currently more dream than reality, but seems like the logical step because of how Big the Data is.

Another major issue faced by genomics researchers is the large number of (open and proprietary) genomics data formats, and the quirks/bugs in their implementations. The ADAM team’s solution to this is their large, fixed schema, created using Apache Avro. This schema is designed to be able to accommodate whatever genetics research you may want to do. To allow ADAM to ingest your format, you write a transformation from your format to their standard Avro schema. Then all the applications built-in to ADAM for analyzing the data are available to you.

ADAM, according to the paper

The software architecture is (explicitly) based to a large extent on the Internet’s OSI model. It also has 7 layers, starting with a few storage layers, going to a schema layer, going to compute and transform layers, then to an application layer. The point is, like the OSI model, to make it easier to implement on top of existing components, to make it portable in the important dimensions across scientific disciplines and execution environments; and also to allow the implementations of each layer to be swapped out over time as the hardware, compute software, and relevant scientific algorithm ecosystems evolve.

They proceed to discuss several pipelines (one genomics, the other astronomy) that they implemented (mainly) around the needs of Spark and their AWS (virtual) hardware. They note that their re-implementation provides several bug-fixes with respect to algorithm implementations in reference genetics software components. Plus, each of the reference components can only communicate through disk I/O, while the Spark data pipeline keeps data in memory until the end. This is reminiscent of the original insight of Spark: speedup over Hadoop MapReduce by keeping as much data in memory as possible throughout the job.

Datasets in genomics, astronomy, and many other scientific fields involve a coordinate system. In genomics, it is generally a 1-dimensional string of nucleotides (A, C, G, T), which serves as a convenient abstraction over what is really a collection of molecules, each containing a packaged collection of DNA polymers in a complex 3D shape, crammed into the nucleus of a cell (I think, pg. 8). There is an assumed independence of data between distant regions of the 1D string.

The Region Join Algorithm

To figure out which regions of the 1D space were acquired by this sample from this “non-reference” human being, it is matched up with a “reference” (a.k.a. “idealized”) human genome, generated by aggregating many people together. What they use Spark for is to figure out which regions of the reference genome were sequenced in this real DNA sample. They call it “convex hull” (see below for definition), because to generalize to multi-dimensional spaces that’s the right way to see it, but for 1-Dimension, you’re really just looking to line-up sub- lines along a big line, and that would have been a simpler way to explain it if I’m not mistaken.

This “region join” can be implemented by (a) shipping the reference genome to each node, and having them output which part was matched for each input data- strip, or (b) repartitioning and sorting the datasets in such a way that puts the joinable data from each dataset on the same machine in sorted order (which I believe is part of the Spark API), and then iterating through both, and “zipping” them together.

The output of that stage is a powerful primitive for higher-level algorithms that researchers will want to run.

Storage

Part of the Hadoop concept is that you get data locality because MapReduce (or Spark) schedules your computations on the HDFS nodes that already happen to be holding the relevant data. However, this conflicts with their goal of being able to store like 100s of petabytes of data. They can’t really maintain the cost of having enough (even virtual) machines up and storing their giant datasets. So they opted to store the data in Amazon S3 (distributed storage) “buckets”. This increases job start (and sometimes finish) duration, but lowers costs.

This reminds me of how the default method for using the “Databricks cloud platform” assumes that you are storing your dataset in S3 buckets, and the data will be loaded (remotely) into the relevant EMR (virtual machine) nodes when the user of an interactive Spark session (or scheduled script) asks for them.

They store the data as in Parquet files. They wrote their own Parquet “row chunk” index file, that Spark then uses to figure out how to intelligently paralellize file [system block] reads, and not read (too much) more of the files than is really necessary. This is done with the help of a query predicate pushdown mechanism. If I’m not mistaken, all this stuff is really cool, but now it’s built-in to Spark with the help of the Catalyst optimizer, which I think came out after this paper did.

Cost and Performance

In their experiments, ADAM is way faster and cheaper than existing implementations of each of its components in almost all genomic situations. Taking the whole pipeline as a single system, then it’s always way cheaper and faster. This is also true for the astronomy dataset and task. They achieve near linear performance scaling (i.e. when adding more machines to the cluster) in almost all components.

Diversion: Convex Hull

• Convex set/shape — for any two points in the shape, the line connecting them is also part of the shape
• Convex hull — the smallest convex set that contains a given subset of points in the space
• Convex hull in 1-Dimension
  • given a set of lines, the smallest range of the line that contains the start and end of every given line (right?)
  • given a set of points, just find the line connecting the smallest and largest point (right?)

References

• Nothaft, Frank Austin, et al. “Rethinking data-intensive science using scalable analytics systems.” Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. ACM, 2015.
• Youtube: Next-Generation Genomics Analysis Using Spark and ADAM- Timothy Danford (AMPLab, UC Berkeley)
• Youtube: ADAM: Fast, Scalable Genomic Analysis – Frank Austin Nothaft (UC Berkeley)
• Youtube: sfspark.org: Frank Nothaft, Scalable Genome Analysis With ADAM
• Github project

Linux file API

In the normal Linux file system API, there are various ways to “flush” a file. Here are a few of the ones I have seen.

We have fflush(3), which flushes all user-space buffers via the stream’s underlying write function. This data may still exist in the kernel (e.g. buffer cache and page cache [since 2.4, Linux buffer cache usually just points to an entry in the page cache see quora]).

We have fsync(2), which flushes modified pages of data from the operating system’s buffer cache to the actual disk device, and blocks until this has completed. Modified metadata (e.g. file size) is also written out to the file’s inode’s metadata section.

We have close(2), which closes a file descriptor, but does not cause flushing of any kernel buffers.

We have fclose(3), which closes the file descriptor, and flushes its user space buffers (like fflush(3)).

https://www.quora.com/What-is-the-major-difference-between-the-buffer-cache-and-the-page-cache/answer/Robert-Love-1?srid=zA4O

References

• man fflush(3)
• man fsync(2)
• wiki inode
• man close(2)
• man fclose(3)

Hadoop File System (HDFS) file Java API

In this API the names of the functions are similar, but the semantics are quite different.

In HDFS, a “file” is stored as a sequence of “blocks”, and each block is is globally-configured to be e.g. either 64MB or 128MB in size. Each block is separately stored on the configured number of machines, according to the chosen HDFS “replication factor”. For the instance of Linux running on a particular node in the HDFS cluster, a block is a file that Linux must track just like it would any other file: with a page/buffer cache (see above), inode, etc. Tracking and deciding which blocks belong to each HDFS file, and on which nodes each of those blocks are stored is the responsibility of the HDFS NameNode (i.e. the single master node).

But the whole block-level view of HDFS is not (directly) visible to the HDFS client API. Instead, a client simply opens an OutputStream to a file by telling the name node that it either wants to create a new file, or append to an existing file. The NameNode responds with nodes that should accept the first block of data. The client starts writing to the first DataNode willing to take its data. That DataNode, pipelines this incoming data to the other DataNodes responsible for replicating this block.

Similar to the Linux file system API above, just because bytes are being “written” by the client, does not mean they’ll necessarily:

1. be visible to someone who now tries to the read the file
2. be reflected in the current metadata available about the file (which lives in the NameNode)
3. survive crashes of
4. the client or
5. the DataNode(s)

Similar to the Linux file system API above, we have a few methods we can use to decide the buffering semantics we want of our pending writes.

We have hflush(), which flushes data in the client’s user buffer all the way out to the nodes which are responsible for storing the relevant “blocks” of this file. The metadata in the NameNode is not updated. Data is not necessily flushed from the DataNodes’ buffer caches to the actual disk device.

We have hsync(), which is just an alias for hflush.

We have close(), which closes the stream, makes sure all the data has arrived at all the relevant nodes, and updates the metadata in the NameNode (e.g. updates the file-length as seen from the hadoop fs -ls myFile.txt command line interface).

In my experience, it is not safe to be opening and closing the same files from the same instance of the Hadoop client on different threads. Maybe I was naive in thinking this would be OK, as the Linux man pages given above seem to suggest that this would be problematic even with the direct Linux file system API.

References

• HDFS output stream API

Even though I have a clearer conception of how to go forward than I did when first writing the program. I still find it hard to think through the whole problem without just trying it. But if I just try it then I don’t know what I’m doing. Then, after I learn what the pieces I need are, I can start from the top-level design and then go down.

I don’t know if there’s a particular moment when I am ready to see the problem more fully. In this case, it seemed to happen because I had to find a better way. The program was going to be a lot of trouble to keep dealing with if I didn’t figure out a better way to name and organize the different concerns it actually addresses. By naming and organizing things better, we get a little “registry” of package, class, method, and value names that reveal the solution’s structure.

Refactoring can get a bit tedious. But maybe the most tedious bits are often not really worth doing. I hope to build up a better intuition for it. But for now, it’s one of those things where I don’t know the words to describe what I’m really making. I can see how knowing a bunch of “patterns” would make this easier. Especially considering that the crux of the pipeline I implemented is the “observer” pattern, one of the only patterns I know. But I think the main thing is to just try things out, see what works, and what doesn’t, then go back and learn the “patterns” after I’ve read and written a bunch of different designs in the code.

Since I’m using Scala, the new design makes the “main” function look more like a Unix program:

1
2
3
4
5
6
7
8
9
10

val src1: DataSource[Type1] = Type1Source()
val src2: DataSource[Type2] = Type2Source()
val merger: Merger[Type1, Type2, Type3] = OneAndTwoMerger()
val output1: DataSink[Type3] = Dest1Sink()
val output2: DataSink[Type3] = Dest2Sink()

Merge(src1, src2) | merger tee (output1, output2)

// desugared to show there is no magic
Merge(src1, src2).|(merger).tee(output1, output2)

Ok, so data streams emanating from source-1 and source-2 are merged together by a type-compatible “merger” class, who writes its output stream into both output-1 and output-2.

There’s not a lot of code required to create those interfaces and methods. Basically any number of DataSink[T]s can be “observers” of a DataSource[T]. Whenever a DataSource finds itself with data to publish, it calls the receiveMsgs(msgs: Seq[T]) method of all the observing DataSinks. So now we have a “reactive” (sources produce data whenever it is available to them), and typesafe pipeline where components can be swapped in an out. Communication between sources and sinks by default is just function calls (i.e. synchronous), but their calls could be wrapped with Futures or Akka actors. Using function-calls makes coding, testing, debugging easier, has better type-checking, and doesn’t need backpressure. Increased asynchrony would allow for higher speeds, but is not needed yet, and will be hooked-in as-needed.

The biggest influences on this design are the Unix shell, and the Akka Streaming library, which I saw some presentations about. I think both were inspired by electrical engineering (e.g. circuits and signal processing).

With this approach, each component has a single responsibility: to ingest, filter, transform, aggregate, or output streams of data. Then in the “main” function we just assemble the data flow of the program by hooking components together. This means to test the program, we just need to test that each component produces or consumes the data that it says it does properly.

Before, almost all of my tests involved at least three separate major program components. I think I will start by re-writing those, and wherever things don’t work, write lower-level tests of one thing, and keep zooming in like that. That way, testing effort is spent on the parts that are hard to get right. I’m not writing the tests first because most of the code for the program is simple hooking things into each other. Testing that would be an unecessary duplication of effort. If the main logic is so plain to see and understand and will not undergo heavy modification, it does not need to be written twice. Then there are a few bits that use some pretty difficult external APIs that can be used well and can be used badly. I want to make sure that I’m using those at least as well as is necessary for the program to function properly. Most of the issues I’ve had in the past are with the HDFS API. With HDFS, it takes to take a little while sometimes for opens, writes, and closes to propagate properly to all the replicas. Before I knew that, I was using the API sub-optimally, and the program would crash every twelve hours or so. That problem itself would not be simple to test against, but it gives the impression that interaction ith these external APIs is where the main complexity in my program lives.

In this new “source-to-sink” program model, a single Kafka “topic” can be implemented as an object (i.e. Singleton) that has two ends (fields): a Producer (which is a DataSink[T], since it writes data out of the program), and a corresponding Consumer (a DataSource[T] for the program).

So if the program has two “main” functions, one connects to the Producer side of a Kafka topic, and the other connects to the Consumer side, all using this Unix-like Scala DSL, then we have integrated Kafka as a resilient buffer connecting two stages of the pipeline. This means the computation subgraph connected within-JVM to the Consumer side can be taken offline for fixing or augmentation without losing ephemeral data being collected by the Producer side.

I don’t know a whole lot about Uncle Bob, but he seems to be very experienced with designing, writing, maintaining, refactoring, etc. large Java projects. He also is very well-read on modern software engineering, but for the first quarter of the book, manages to stay away from the over-use of terminology I’m not familiar with. After that it goes into things like agile, test driven development, behavior driven development, cohesion, object oriented programming patterns (e.g. Gang of Four), plain old Java objects, data access objects, etc. that I don’t have much familiarity with. He also talks about his conversations with (the only) guys in this arena that I have heard of, including Fred Brooks and Martin Fowler.

His writing tone can be characterized as follows

• I have read and written sooo much more code than you
• Over time, I have taken the time to think about the best way to make the code ‘clean’
• Herein, I shall share with you what I have learned
• I’ll use the best didactic methods I can think of
• I hope you benefit as much as possible from my wisdom

His main didactic method can be characterized as

• Here is an example of some bad code
• This is how it goes wrong
• This is why that is bad
• Let’s improve it in these areas
• Here is the improved code
• Note how this new code doesn’t have the flaws of the previous

So far I have read perhaps ½ of the book, and I have already come up with and partially implemented a design for my problematic program that is so much better than the old design, and a rough prototype implementation is already running, and I have much more “direction/vision” for how it is going to progress. That shows me that the Clean Code book has produced an incredible return on investment.

The main thing I have understood from the book is that parts of programs should do what they say they do. Put most briefly, there are two parts of making that possible

1. Components should be simple enough to be described by just a few words
2. The name of a component should be the few words that describe it

It is embarrassing to say that I never thought of that myself, but the truth is I didn’t, and that is reflected all-too-obviously in the program that I wrote. I can come up with countless excuses for why I wrote the program that way, but that doesn’t fix the problem. The only way to fix the problem is to reorganize the program to conform to the above two rules.

What problem are we solving?

Bigtable provides an API for storing and retrieving data.

It is most useful if

• there is a lot of data coming in at a high rate over time
• there is no need to join each data table with another
• data might need to be updated
• range queries are common

Bigtable is a distributed database. It is a database management system which allows you to define tables, write and update data, and run queries against the stored data. It is similar to a relational database, except that it is not “relational” in the sense denoted by the term “relational database”. Instead, it brings its own type of data model, where instead of storing data in normal two-dimensional table cells, you store it according to a new set of rules that allows for flexibility in the shape of each record, while still enabling overall efficiency.

Go on…

In the Bigtable data model, data is grouped in tables. Each record in one table must have a string identifier unique in that table. Each table is defined to have a set of “column families”. This is where the data goes. A record has values, that is the point of having a record. Each of those values is associated with a timestamp when it was created. This can either be defined by Bigtable or by the user inserting the data. Having two versions of a record means it was updated. Each value has its own key (a string) pointing to it. That key has two components, a “family” and a “qualifier”. Each table has a finite set of families with known names. However, the qualifier segment of a value’s key may be an arbitrary string. There may be any number of anchors for each family in each record. You can hint whether you want Bigtable to prefer disk locality when writing many values in the same column family.

Rows are stored on disk in alphabetically by row key, and for each value, in descending order of timestamps (i.e. most recent first). All reads and writes over a single key are atomic with respect to each other, but not with respect to changes in other rows. (This is something the client must be careful about.) All the rows for a given table are chopped up (dynamically) into “tablets” which each are stored in by exactly one “tablet server” node in the cluster. One can specify garbage collection to either only keep the last n versions, or to only keep everything for a specified duration.

When reading the data, one might e.g. just fetch the data for one column family within a particular range of row names, but get all currently known versions of that data. This type of query is what was optimized by the creators of Bigtable. One might for example want to execute this type of query to feed as input to a MapReduce job. One could do that, and then also be able to enjoy the intentionally efficient writing of MapReduce results into a different Bigtable table.

Bigtable data is stored in the SSTable file format. In this format, each file represents what in Scala would be called a immutable.Map[String, String]. A file is made of blocks, each containing a continuous interval of the keys that is listed in the file’s “block index”. Each SSTable file is stored in Google File System (GFS), which I will not describe in detail here, and is similar to the Hadoop File System (HDFS).

Bigtable relies on Chubby (similar to Apache Zookeeper) to ensure there is “at most one active aster at any time” and for bootstrapping.

A Bigtable instance has a single master node, and a potentially dynamic number of tablet servers. A tablet is a complete alphabetical interval of all the data in a table. The master manages tablet assignment, server cluster membership changes (with help from Chubby), load-balancing of tablets among servers, garbage collection, and schema changes. The tablet server handles read and write requests to its tablets, and splits tablets when they get too big.

Clients only need to communicate with the master to find the relevant tablet servers. The relative amount of this sort of communication compared to the actual data transfers is such that this practice is not a system-wide bottleneck. Clients also cache this data until a server says the information is stale.

Tablet location information (across all tables being managed by a single Bigtable instance) is stored in one big 3-level hierarchical B+-tree type thing (i.e. it’s a sorted n-way tree, where you go down the appropriate pointer from an internal node based on what it says about the interval of row IDs contained in its leaves. The root is stored in Chubby. At the third level I think you have the locations of all the tablets and what keys are owned by each.

As previously mentioned, persistent tablet state is stored in GFS, but what is that “tablet state”. Each write or update is appended a commit log (with a unique mutation identifier to resolve duplication caused by tricky crash scenarios). It also modifies the (copy-on-write) in-memory representation of the current state of this chunk of the table. One can always reconstruct the in-memory representation by playing back the commit log, but ideally most reads are serviced from memory. Every once in a while the in-memory state gets too big, and it is written out as an SSTable into GFS. Every once in a while, multiple SSTables are read back into, and since some might be updates to others, they are merged together, and the sources deleted.

In practice, the authors found that applying a very computationally efficient compression algorithm (rather than one with a top-notch compression ratio) increased overall system efficiency in many cases. They also added bloom filters to the SSTables to reduce the number of unecessary disk reads of non- existent data.

The paper says Google has used Bigtable as a backend for its Google Analytics product, Google Earth, Personalized Search, and storing websites for retrieving results for its Search Engine.

As future work they want to be able to provide better (but not full) support for transactions (I think this is addressed in the Spanner paper released a few years later).

Their lessons learned include

• “delay adding new features until it is clear how the new features will be used”
• “the importance of proper system-level monitoring”
• “the value of simple designs…code and design clarity are of immennse help in code maintenance and debugging”

They conclude by noting that this system bears some resemblance to the C-Store column-oriented database system, for which there is another good paper that I ought to finish reading at some point. They also note that people who are used to “traditional” relational databases find the Bigtable interface awkward, but that it works so much better than the alternatives that people end up using it anyway.

References

• Chang, Fay, et al. “Bigtable: A distributed storage system for structured data.” ACM Transactions on Computer Systems (TOCS) 26.2 (2008): 4.

I learned the basics of Ruby on Rails web application development a few years ago. At that time, my understanding how that system works was as follows

1. Find articles describing things Rails allows you to do easily
2. Decide on an app that requires only those things
3. Follow the instructions in those articles to implement your app idea
4. Push the app to Heroku
5. Now the app is accessible to anyone on the World Wide Web

The fact that it is so easy to do such a thing is nothing short of magical. Especially while you have no idea how any of it works. Now that I am slightly more knowledgeable about how software systems are put together and deployed, I’d like to take a slightly more nuanced stab at what really was going on when the above 5 steps were executed.

How Rails makes things so easy

Ruby on Rails was created out of frustration with “heavyweight” web application development frameworks, such as ones from the late 90’s that use Java. It gives you base-classes for all the important parts of your program so that you only need to write (and even see) code for the pieces that are unique to your system. It generates a base project with everything you need already included in a well-structured layout that helps you make sense of what is going on. Through some clever usage of the Ruby programming language, it creates methods named after the components you implemented, and makes them available in the places you may need them. This has led to a culture of natural-language inspired community-built APIs that enable you to easily do things only the most modern websites have.

How does traffic get into and out of Rails?

Maybe there is another way to do it, but at least by default Rails uses Rack. Rack is a “webserver interface”. A Rack application has a Ruby object that has a method that receives parsed HTTP requests in a well-specified format, and then calls a method (called call) which receives the parsed HTTP request as a Ruby object, and returns a parsed HTTP response in a well-specified format (specifically a Ruby array structured like [response_code, {headers_map}, [body_lines]]).

A Rails application implements Rack’s call method. What that call method actually returns for any given HTTP request argument is defined by all your Rails code, e.g. your router, controllers, models, views, etc.

What about Rack then?

Fine, now we understand that Rack passes the HTTP request to Rails, and Rails returns the HTTP response to Rack. But how did Rack get the HTTP request in the first place? Answer: from a Web Server.

A web server suitable for Rack would be a program that

• listens on a TCP port
• connects to clients on that port
• receives the HTTP requests from those clients
• parses them into the format that Rack expects
• Calls the Rack method call using that format
• Receives the HTTP response from Rack
• Converts that into the raw HTTP response format
• Sends the response to the client

There are many such suitable web servers, such as Unicorn and Thin.

So what is nginx?

It seems to me that one does not typically use nginx to call Rack’s call method (though this might be possible to do). One typically uses nginx as a waypoint of traffic bound for the application, but in need of some sort of pre-processing. That pre-processing could take multiple forms. Maybe there is a cache sitting outside of Rails itself, and nginx can be setup to return results from the cache instead of proxying requests into the server which interacts with Rails itself. This will improve performance for each client who hits such a cache, and will increase the load the system is capable of supporting overall. Nginx might know of multiple servers connected to different instances of the Rails app running concurrently, and will choose which server to send each request to in such a way as to distribute load across the Rails applications (“load balancing”). Nginx might “terminate SSL”, meaning that clients connect to the address on which nginx is listening, and will send their request to nginx over the TLS protocol, but nginx will decrypt that request before passing it wherever it will go next; then nginx will encrypt the response according to the TLS state and the client will know how to decrypt the response (and ideally no one else will know how to decrypt it).

What Heroku does

Using the simple git push heroku workflow, Heroku takes care of all the aspects of managing the deployment of your Rails server. It will provide a virtual server to run your Rails code. It will provide a server which speaks Rack to receive requests, invoke your Rails code, and return the response to the client. It has DNS entries installed in the relevant places on the internet so that you can choose a name for your app to be accessed by your friends in their homes using their browsers. It will do a whole lot more, such as autoscaling, caching, and other things beyond the scope of this post because I don’t know about them.

The system itself uses many APIs with which I was previously unfamiliar; Kafka, Elasticsearch, HDFS, ZooKeeper, Spray, CouchDB, etc.; but I have glued together unfamiliar APIs on many previous occasions. The system is “distributed” and has in-built fault-tolerance in various ways; but I have included that feature in previous projects. The thing that is new for me about this project is that it was written with maintainability as a goal, and “released” in such a way that it runs continuously as a service, and its output can serve as input for the daily work of other human beings. This is my first project for my first job, and it is finally working.

There were many times during the development of this project when I figured it would probably be deployed within the next few days. At those points, I told my manager to begin finding me something interesting to work on next. He always sounded more skeptical than I expected about the project actually being nearly done. On each of those occasions, I realized within the next few hours after announcing my near-completion, that there was still, in fact, a slew of components still needing to be worked out before the software could be deployed, and that I had no idea how to craft any of these components.

There are too many guides out there about how to develop and deploy software systems. For me, the most important ended up being a Medium article by Jesper L. Andersen (no idea who that is). I think I found the article on Hacker News a month and a half ago. I will summarize my takaways from it

• The developer is responsible for every aspect of the software
• Make sure the project makes sense to tackle
• Choose the right libraries, frameworks etc. to use
  • This requires a small amount of experimentation which should be done up front in a separated/extracted code-base
• Limit scope
  • E.g. create a list of problems you’re not solving
• Limit external dependencies
• Create a transition plan from the previous system to the new one
• Design for future extension
• Prefer correctness and elegance to efficiency of execution
  • This is especially true for my project because it is network bound anyway
  • But still, understand which parts must be more correct than others
• Collect metrics about system performance
• Write automated tests of whether
  • The components that need to do something correctly are
  • The different components of the system can communicate with each other effectively

There are still aspects of my system that are not perfect. For example, I occasionaly see errors about a timeout in some library used by a library I am using. I don’t know whether those errors are corrupting my data, or killing JVM threads, or whatever else. The system is already a vast improvement over what was in place before in terms of correctness and latency of the data produced, so having the occasional issue was not a good enough reason to delay deployment any further.

The system was deployed in a manner one might describe as “by hand”. I rsync the code onto a server, build the code on the server, open up two tmux windows, run one JVM which produces to Kafka, run another JVM which consumes from Kafka, make sure everything that is supposed to be happening is happening, and detach from tmux. According to the blog post I linked above, it is desirable to be able to hit a button and see it deploy itself automatically. In my case this conflicts with the other suggestion in that article, which is to stick to limit the number of things you have to learn in order to get the first version of your software working, which I believe the author meant to be more important than a one-click deployment scheme.

The system is not exactly “done” in the sense that it doesn’t have all the features it is supposed to have. But at least I know now that the system works in its production environment and is able to interact successfully and (demonstrably) correctly with all the external infrastructure that it relies upon. But to be sure, many corners were cut, many pieces are kind of there but not really, the metrics are not collected well, and configurations (e.g. of Kafka, ZooKeeper, and Elasticsearch) were chosen on a “that’ll probably get us running” basis. As it turns out, there have already been issues with Elasticsearch not being able to handle the load of multiple of my colleagues querying it at once.

A problem with having deployed it without a larger share of the issues worked- out is that I now need to be more careful to make my changes behave as transitions from “working state” to “working state”. There are pieces of the system that if they are left not-working for more than 24 hours, data will be irretrievably lost, and people will be sad. But by design of the software, the piece that must be left running properly is mostly disentangled from the rest of the system, so that it can run while the rest of the system is offline, and none of the data will be lost. This is accomplished by buffering data in Kafka.

Since I have no previous experience deploying a software system like this, I did not have a good basis to evaluate which libraries to build my system upon, except for the buzz that I see on Hacker News, and my own intuition and background. I like the Scala programming language best, and because of Spark, some people I work with already use Scala, so I chose Scala. Is Go a better tool for the job? According to the relative buzzes of the two ecosystems on Hacker News, maybe it is. Would Docker have provided a better mechanism for deployment? Most-likely it would have, but that can be added at any time if it turns out that deployment is a problem which needs to be solved, which at this simple stage, it is not.

It is exciting to final have real people relying on code that I wrote. I am excited to continue making this system better-meet the needs of its users. I am even more excited by the shift in the way I look at writing software now that I have seen more of the lifecycle of a single project.

“Tunnelling”, with two ells, is the British spelling.

A few months ago, I downloaded a tool (an ELK stack) that didn’t work right off the bat due to some sort of misconfiguration. It was running in a Vagrant- made virtual machine (VM) on my laptop. The Vagrant setup script had forwarded a local port on my laptop into the VM. So in order to debug it, my coworker configured a chain of tunnels that enabled him to SSH into the VM on my laptop.

In the back of my mind, I spent the next few weeks trying to figure out what SSH port-forwarding is and how its syntax works, then another few weeks to figure out what reverse port-forwarding is, and another few weeks to find practical use-cases for each.

Here is my executive summary

ssh -L [<localhost>:]<localport>:<remotehost>:<remoteport> <gateway>

By default, <localhost> will be localhost.

What this does is, start a serversocket listening to local address localhost:localport using the “SSH client”. When a client establishes a connection to that address, traffic received from that client will be encrypted, and forwarded to the sshd[aemon] listening on port 22 of gateway. (Only) after the gateway receives this traffic, the sshd will establish a (normal, unencrypted) connection to remote address remotehost:remoteport, and forward the data originally received by the SSH client there. Response traffic originating from remotehost:remoteport will go back to the sshd, back through the encrypted tunnel to the SSH client, and back to the originating client.

Reverse tunneling by contrast, means that traffic originating on the remote end will be forwarded to the local end.

What’s SSH

One thing that confused me about SSH forwarding, is that if I don’t use some extra flags to disable it, when I set up port forwarding to a another machine, I also end up with a shell ready executing commands remotely. What is going on here? It turns out it is doing what is called “remote command execution”.

Here’s what’s happening: SSH is capable of multiplexing multiple communication “channels” over a single encrypted TCP connection. If you just execute the normal tunneling command given above, it will create two channels, one for forwarding the tcp traffic, and another for executing commands visually in your pseudo-terminal but physically in a remote shell.

When you ssh onto a remote machine, a particular sequence of things happen that I think really clarify what the heck’s going on. You can see it happening if you turn on verbose mode (-v).

1. You connect via TCP to the standard SSH-daemon port (22) on the remote machine
2. You authenticate it via its public key
   • That’s why the first time you connect is says “do you want to trust this server’s fingerprint?” or something like that (I think saying “yes I trust it” implies you have verified that the fingerprint does not belong to a man-in-the-middle attacker)
3. It authenticates you, either by you supplying a password, or by it finding your username in its ~/.ssh/authorized_keys file, and [using what protocol?] you match it with your private key
4. Y’all negotiate an encryption for the session, over which future communications will take place
   • [Maybe you have to choose a specific cryptographic algorithm like in TLS?]
5. Now that communications are encrypted, control and channel data are transferred using a binary packet format that contains
   • Encrypted packet length — answers: when does this packet end?
   • Various random paddings — to fool the bad guys
   • The encrypted (and possibly compressed) payload — here’s the good stuff
   • A message authentication code (MAC) — find evidence of corruption/tampering
   • Recipient’s integer identifier for this channel — answers: what channel did this data come in from?
6. To setup a remote shell, your SSH client requests permission to create a special channel specifically designed for the purpose of remote shells
   • At this point you tell the server which ID you’re allocating to this channel, so that it knows how to fill the last item in the format specified above
   • Since each channel performs its own flow-control, you also state your “window size” (similar to TCP)
     • Both sides maintain a receive window, and once the sender has sent enough bytes to fill it, they will not send more data until you say that your window now has more room
7. If the server supports “shell” channels, it will tell you which ID it allocates for the new shell channel
   • so that you can put the correct ID in SSH packets in this channel
8. Then you tell the server your psuedo-terminal’s display specifics
   • characters horizontally and vertically, as well as pixels horizontally and vertically
   • If you were using X11, you would tell the server your screen’s specifics
   • If your dimensions change, you can send an update message to the server
9. Now you can send the server the values of environment variables to use
10. Then you request that the server initiate a shell in which to execute the commands you’re going to give it. You can specify the path to the specific shell to use.
11. Then you start sending commands to execute, which the server will pass to the shell it created
12. The server will send you back output received from the shell, formatted for your terminal
13. You can also send signals for the server to pass to its shell
14. When the remote shell command terminates, the server will send you its “exit-status”, or if there was a violent termination, it will send an “exit-signal”

Note this communication only used one channel, and there can be however many channels open over the same SSH connection. This is implemented using the framing layer that puts the data into the higher-level datagram format described in list item 5 above. Datagrams are then demultiplexed by the receiver according to the the channel identifiers in the datagram. So one channel might be used for forwarding packets received on a port registered with SSH for forwarding, while another is used for the normal SSH remote shell execution terminals. So that’s how we see the effects of the “-L” feature of SSH described in the beginning.

It’s like HTTP/2

I don’t know many protocols, so a lot of this stuff is new territory for me. When I got curious, to find out more, I started by reading the Wikipedia page, because in addition to having its explanation, it often has good references and links to related topics. From there I followed the reference to the IETF RFC. Maybe it was because I read the Wikipedia page first, but I found the RFC much easier to follow, and with a better enunciation of what is going on than the Wikipedia page. I didn’t read the RFC word for word except for the first few sections, but then, based on its structure and formatting, was able to find the pieces I was interested in surprisingly fast. The reason for that is the RFC’s authors are familiar with explaning such concepts, and spent months working as a team to increase the document’s utter clarity to reduce the possibility of miscommunication.

In a previous post I looked at the new HTTP/2 IETF RFC. That protocol contains a similar framing layer over TCP that allows it to multiplex multiple channels concurrently over a single underlying TCP socket. IIRC, the reason for that was to ease issues with “head-of-line blocking”, which is where one channel’s being slow ends up slowing down all the other channels because of TCP unecessarily guaranteeing maintaining FIFO order of packets across multiplexed channels that have no globally-defined order. At the same time opening up many TCP connections per client is undesirable for the server. So after having seen this framing-layer thing in two protocols, now I understand it to be some sort of “pattern” for allowing multiplexing communications over a single TCP link. One big advantage is less connections per client on the server side. Also, the TCP algorithm has a “ramp up” time, i.e. the congestion control starts out with a rather pessimistic window size. By using only one socket, that ramp up only must be done once. Surely, better knowledge of TCP would lead to more insight here.

I like to get at least a basic idea of what my favorite tools are actually doing. This sort of investigation can only go so far because the modern stack of technologies is so vast and the “lyfe so shorte”. My first computer science professor encouraged us to press the “I believe” button when something seemed like magic. Still, lifting some of the veil on one tool I use everyday is satisfying, and hopefully the time taken for others to get to my (still minimal) level of understanding is reduced by the explanations above.

Overview

• The only transport-layer protocols Java supports are TCP & UDP; for anything else, you must link to native code via the Java Native Interface
• TCP uses stream sockets, through which one generally just writes to an OutputStream and reads from an InputStream of bytes that remain in-order and uncorrupted and are (practically) guaranteed delivery by the implementation of the protocol by the operating system.
  • Unless you’re using NIO; see below for more on that
• UDP uses datagram sockets, through which you send and receive objects called DatagramPackets, which are just a length, a destination, and data
• Unless you’re using NIO, everything blocks: e.g. connecting to servers, listening for clients, reads, writes, and disconnecting (for TCP)
  • By default most of these actions may block indefinitely
  • For reading and connecting, you can configure a timeout, after which you will receive an InterruptedIOException
  • For writing to a TCP stream, you cannot configure a timeout

Handling multiple clients

• Deal with one at a time, which is simplest, especially if there’s some state that is shared by all potential clients. Speed may become problematic quickly.

1
2
3
4
5
6
7
8
9
10
11

void mainLoop() {
    while (true) {
        Socket s = serverSocket.accept();
        handle(s);
    }
}
void handle(Socket s) {
    InputStream in = s.getInputStream();
    // process request, etc.
    s.close();
}

• Create a new thread to handle each incoming client. This is still pretty simple, but will lead to massive overhead if you have many concurrent clients, and therefore you’re context-switching all the time.

1
2
3
4
5
6
7
8
9
10
11
12

void mainLoop() {
    while (true) {
        Socket s = serverSocket.accept();
        new Thread() {
            @Override public void run() {
                InputStream in = s.getInputStream();
                // process request, etc.
                s.close();
            }
        }.start()
    }
}

• Use a thread pool to handle requests. Java has abstracted the thread pool concept into the Executors factory class. There are a multitude of executors to choose from. This newCachedThreadPool() one will execute each task on an existing thread if one is idle, and will create a thread otherwise. Threads sitting idle in the cache for over one minute are terminated.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

ExecutorService executor = Executors.newCachedThreadPool()

void mainLoop() {
    while (true) {
        Socket s = serverSocket.accept();
        executor.execute(new TheHandler(s));
    }
}
static class TheHandler implements Runnable {
    Socket s;
    public TheHandler(Socket s) { this.s = s; }
    @Override public void run() {
        InputStream in = s.getInputStream();
        // process request, etc.
        s.close();
    }
}

• Use NIO (rather complicated) to allow N threads to service M clients, where N is small and M is huge. This uses event-based programming. We can set all network operations to be non-blocking, and only wait as long as we want to for them. An extensive example can be found below.
• Use a framework like Netty, Akka, etc. that wraps the NIO stuff up in a ribbon and a tie

10K feet above NIO

• If you’re using NIO, you create Channels of bytes into and out of sockets (or file handles)
• You register a Selector to be notified when the Channel is ready to be read from or written to
• You query the Selector to tell you which Channel are ready, and may then take action on those that are
• You get data in and out by passing a Buffer to the Channel

Here’s an example based on TCP/IP Sockets in Java, a highly recommended book about this stuff by Calvert and Donahoo.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

Selector slctr = Selector.open(); // factory
ServerSocketChannel chnl = ServerSocketChannel.open(); // factory
chnl.socket().bind(inetAddr); // set address to listen on

// For some reason Channels block by default. If we want to
// register with the Selector for notifications, we must turn
// that off.
chnl.configureBlocking(false);

// Notify Selector whenever this Channel has a new connection
// ready to be "accepted". Such a notification still does
// *not* guarantee it will work immediately.
chnl.register(slctr, SelectionKey.OP_ACCEPT);

while (true) {
    // wait configurable period of time to be notified
    // by any registered channel
    int numNotifications = slctr.select(timeoutMS);
    if (numNotifications == 0) {
        // We timed out without any notification.
        // We could do whatever we want here because we're
        // no longer blocked.
    } else {
        // numNotifications different channels have notified us of
        // being available for Connect, Read, Accept, or Write.
        // It is OK to use these keys in concurrent threads.
        for (SelectionKey key : slctr.selectedKeys()) {
            // We're not sure which channel this key belonged to.
            // Also, notification was just a "hint" and we need to
            // check again whether the Channel is available.
            if (key.isAcceptable()) {
                // here's the actual call to accept()
                SocketChannel clientChnl =
                    ((ServerSocketChannel) key.channel()).accept();

                // similar to the ServerSocketChannel
                clientChnl.configureBlocking(false);
                // Except that here we register to notify Selector
                // about being "readable", and
                clientChnl.register(
                    key.selector(),
                    SelectionKey.OP_READ,
                    // We must associate an "attachment" with this
                    // channel. This is the buffer that will be
                    // filled with the incoming bytes rcvd via TCP.
                    ByteBuffer.allocate(NUM_BYTES) // eg 256?
                );
            }
            if (key.isReadable()) {
                // retrieve the readable client socket's channel
                SocketChannel client =
                    (SocketChannel) key.channel();

                // retrieve the ByteBuffer we associated with
                // that channel
                ByteBuffer buf = (ByteBuffer) key.attachment();

                // Attempt to read `buf.remaining()` bytes _from_
                // the Channel _into_ the ByteBuffer.
                int bytesRead = client.read(buf);

                // -1 from read() means end-of-stream, which in
                // this case means the client closed their output
                // side of the TCP connection. We may still be
                // able to send data if that side of the connection
                // has not been closed yet.
                if (bytesRead == -1) client.close();

                else if (bytesRead > 0) {
                    // if our application has data to write back
                    // to the client, we must tell the selector
                    // that we've now become interested in writing
                    key.interestOps(SelectionKey.OP_READ
                                    | SelectionKey.OP_WRITE);
                }
            }
            // socket not closed, and is writable
            if (key.isValid() && key.isWritable()) {
                // beyond the scope of this post.
            }
        }
    }
}

Tips for Traps

• Don’t write to the network through a PrintStream
  • It chooses end-of-line chars based on your platform, not the protocol (HTTP uses \r\n)
  • It uses the default char encoding of your platform (likely UTF-8), not whatever the server expects (likely UTF-8)
  • It eats all exceptions into this boolean checkError() method, when you’re better off just using the normal exception hubbub

In giving advice, everyone has a different approach. I generally try to follow a line I heard in a rap song by The Streets, “If you never tell a lie to her, you don’t have to remember anything.” In other words, lying will only complicate your life because you have to remember the lies you made up. (Caveat: this may not always the best way to go for emotionally complex issues.) I also enjoy helping people rationally and realistically evaluate their options for significant decisions, and surely if someone recalls that your input was helpful in the past, they will be more likely to ask you in the future.

Most people I know don’t seem to like giving useful advice. It seems they either are (1) too afraid that their honesty will lead you to dislike them, or (2) they feel so stressed with their own issues that taking on yours for a few minutes would be overwhelming, or (3) they find your problem uninteresting and simply have better things to do.

But some people are the opposite. They will patiently listen to your question and give what they feel to be an honest evaluation of where you stand and what you should do. The advice of people in this category will often be heavily and obviously biased by their own experience and ideology. This is simply a symptom of “being honest”.

So if you want good advice, it would be ideal to find someone who is honest, not stressed about a similar problem to yours, as well as interested in and knowledgeable of the subject; they should generally also be disinterested in your particular problem. However, this ideal candidate is not always available.

In that case one can obviously try the timeless “pros vs cons” list, which doesn’t necessarily rely on external sources of wisdom, but often external sources of wisdom are critical. One can ask unideal candidates for advice, and maybe they’ll at least have some curt nugget that has some use. That’s what I usually do, and it is generally not effective at all, but occasionaly that curt nugget is exactly the required pithy jewel.

One can consult the Internet, but I kind of assumed that if you needed advice, you already checked the Internet for answers. But to go one step further you can ask the Internet, treating it like this all knowing Oracle. This will work to varying degrees depending on your problem. If your problem is one that everyone and their mother has an opinion on, you will end up sifting through junk answers, and may or may not get anything useful. In that case, the more details you can reveal, the more benefit you will obtain. Of course where you ask matters: for example Quora will be more effective than Yahoo Answers. If your problem is esoteric, find the people who are into that thing.

For example, I have noticed to my surprise that StackOverflow/StackExchange is not always the best place for all programming-related questions, because if your question is esoteric to one technological ecosystem, the question- answering population on StackOverflow won’t necessarily have the flag-bearers of the cause of that particular ecosystem. But if it really is an ecosystem, it will have a place where the flag-bearers dwell, so find it and they will probably help. In my experience, IRC channels tend to be empty; Gitter channels may be well-attended; Github issues get a lot of flak for being a mess, but are often effective if you’re sure your question isn’t stupid; mailing lists can be high-latency but that’s often where the true experts of super-technical projects converse. Following good forum-question-asking practices is crucial in any of these environments, and it can be trickier to do that than it sounds. The better you phrase your question, the more appealing it is to answer in the eyes of a high-quality potential source of advice.

Sometimes the advice you receive from multiple sources will be in direct conflict with each other. I have been having this issue a lot lately. Let’s say one person suggested I do A, and another suggested I do not A. I have decided this pair of suggestions implies that either decision is just fine, which is basically the ideal outcome; viz. my so-called “significant decision” was not so significant after all and doesn’t not need to be balanced carefully.

Just some biased thoughts from my experience; take some, leave some, etc.

My point here is not so much to discuss the piece, as the tone of the piece. This piece was written with a tone that raises the hair on the back of the necks of liberals. This may have been unintentional on the part of Graham, …although considering the follow-up discussions of his previous piece on females in tech, may he just likes raising those particular hairs (they’re called “hackles”).

I will now summarize what I took from the essay. Technology increases the potential productivity of people at an exponential rate. Since some people do not become more productive, this correspondingly increases the variability of productivity within the population. Those who are more productive in producing innovative goods are benefitting society. They mainly only are interested in being more productive because of the possibility of getting rich off of it. If we want to help the poor, the problem is not that there are rich people; the problem is that there are poor people. To help the poor, instead of taking away the ability for the productive to get rich, we should help the poor become more productive. This is because economic inequality per se is not the issue, poverty is.

For me, this is, as I’ve mentioned, both convincing and enlightening. But there are two concerns any left-winger is almost certainly going to bring up. First, a lot of people’s wealth is not made by being productive in a way that benefits society; shouldn’t we wage class-war against them? Second, even people who became rich by benefitting society, are likely to abuse their wealth via some form of corruption, so that’s why we should prevent them from getting rich in the first place. After those two arguments, there are a few other popular rebuttals. (E.g.) Third, why should we allow some people to be that much richer than everyone else; something about it seems creepy, therefore it should be prevented.

These are legitimate concerns, they just don’t actually rebut anything Graham was saying. That’s why, if Graham wants to have a legitimate conversation with people who are going to make the above rebuttals, his argument should start by saying that those rebuttals are correct, and then go into how it is still the case that his original arguments are correct. In this way, the hackles are down, and the legitimate points can be heard.

However, maybe Graham wasn’t writing the essay for left-wing people to be convinced. Maybe he was trying to convince right-wing people. If that is true, the essay was pointless, because right-wing people already agree with the opinions he stated. Or maybe he was writing the essay for maximum “virality” to increase his fame and international mindshare. In that case, I’m not a good judge of effective argument technique.

What I have noticed of myself is that gamification works for me. I love the satisfaction of (in descending order of [perceived] satisfaction)

• earning a badge
• getting to the next level
• beating other humans (directly, or via “percentile” calculation)
• beating robots (similar to “beating a boss” in a video game)
• getting points

Missing from the list below is Coursera, Udacity, etc. After 6 years of school, I’m really of sick of sitting in a lecture hall, even if it’s a virtual one. As a testament to this sentiment, so far I’ve read ~150 pages of the Compilers textbook, which is the book I would be reading were I to take the class at University. Sometimes I miss having a teacher whose personality I can associate with the material. This is a bizarre notion, but it is really important. For me, having a “great teacher” means someone I want to please by doing well on the test. Having a “bad teacher” means I don’t care what the teacher thinks of me, and frankly I want to do badly to make them feel bad. This is a mean way of looking at the world, and I don’t do it consciously, but looking back at how I approached my classes, this is what I did a lot of the time. Having a “great teacher” is an amazing feeling, and an excellent motivator to really dig into the subject. But I certainly don’t miss all the other crap that comes from having a teacher (even a “great” one). The main problem with teachers is that you need to be respectful of their time and the time of the other students in the class. This leads to a huge amount of wasted time on the part of each student, because his or her particular questions aren’t being answered. I could go on about that but I won’t. The point is, that I really feel like I understand everything that has happened so far in the 150 pages of the Compilers book, and it didn’t require and physical hand-holding. It is exceptionally easy to read a book and think you understand it, and actually not be understanding it. So who knows.

Here on out

My first “real” day of my first “real” job is tomorrow. So I probably won’t be spending much time just randomly learning whatever I want in the future. But in general, these are things that I like to learn about, and methods of learning them that I enjoy doing; so as I find time, I will come back to these things.

The List

This list contains bullets for each thing I have tried to learn over the past few weeks. The sub-bullets contain methods I have used to actually do the learning. Many of them are gamified methods of learning (e.g. HackerRank). Others, I have tried to gamify on my own (e.g. using test-driven development).

• Learn about compilers
  • read Compilers “Dragon Book” textbook
    • avg 8 pages per day for 20 days
  • do the exercises (on paper)
• Review AI & machine learning
  • earn an AI “badge” on HackerRank by
    • doing statistics problems (e.g. “find the z-score”)
    • writing a few programs (e.g. “do a multiple linear regression on the given data”)
• Become more familiar with algorithms and their application
  • do practice problems on Hackerrank
  • Read [from] the algorithms textbook “CLRS”
• Become a “good programmer”
  • write the programs suggested in “Programming Pearls” by Jon Bentley
  • Beat bots and people at debugging code on codefights.com
• Learn via observation
  • Livecoding.tv (haven’t actually looked into this one yet)
  • Annotate the code of small open source projects with comments explaining how it is working
    • substack — creator of popular modules for Node.js
    • Li Haoyi — Scala projects using concepts from compilers
• Understand P2P networking
  • Create a personal “open source” programming project that is a P2P networking application
    • To a large extent using test-driven development
• Learn to use NodeJS
  • do the learnyounode interactive tutorial
• Learn about functional programming
  • read from Learn you a Haskell
  • write some simple haskell programs as part of a “learn to code in 30 days” competition on HackerRank

The most fundamental thing I have learned so far is the overall pipeline for understanding the modular components forming the way a compiler is typically constructed. It goes

1. Lexical analyzer
2. Syntax analyzer
3. Semantic analyzer
4. Intermediate code generator
5. Machine-independent code optimizer (optional)
6. Code generator
7. Machine-dependent code optimizer (optional)

The input to the compiler pipeline is a “character stream” of the program. However I don’t recall the book ever dealing with specifications of that stream, except that it supports a generic getchar() operation. I can understand that if the entire source consists of one file, you just read character-by-character from the file into the compiler. Maybe the language designer decides how multiple-file projects are to be read by the compiler, i.e. it is beyond the scope of this book; or maybe they’ll go more in-depth on this later-on.

The Lexical Analyzer

The character stream is read into first component in the compilation pipeline: the lexical analyzer, which maps the character stream into a “token” stream. It seems like a token knows its tag, and its value. The tag is basically the type of this token in the eyes of the compiler. Possible tags in their example include NUM, ID, [keyword]s, and I added COMMENT as part of an exercise. The value for a token might be the literal value of a literal; or it might be the name of a variable. More about that below.

Symbol Tables

In addition to creating the token stream, the lexical analyzer builds the symbol table. It seems to that the symbol table maps names to places in memory. A symbol table also ‘by default’ implements the language’s preferred form of block scoping. Upon entering a new scope, a new symbol table is created that points to its “parent”, the one it is nested inside of. If a variable is declared, it is added to the symbol table to this scope. Later, when a variable is referenced (i.e. init’d, read, or updated), we will consult the table for the current innermost scope. If the variable’s data is not found there, we will continue to check ancestors until we find it.

From my experience talking with some of my colleagues so far, their collective attitude might be summed up with, “Google it, then copy-paste it, but don’t worry about what it does.” In my life, I have worked with and met many people having that attitude. Partially because of my experience working with those people, it happens to decidedly not be my attitude. My attitude is more like “google it, learn what to do, learn why that is the right approach, take notes, and then copy-paste and modify the best solution to make the final solution as clean as possible.” This strategy got me through many tough situations, so I have built up faith in it.

So, after seeing me spend days learning about ssh tunnelling, ansible, and vagrant — and not finishing my simple project — they finally said something along the lines of

At this rate it will take you weeks to learn how to automate deployment of a virtual machine. Why don’t you just deploy one copy and then learn about how to automate it on your own time?

Now, “weeks” is probably an overstatement, but they pointed out to me that I had sort of assumed out of nowhere that I was hired as some sort of devops role for the company, even though what I’m actually interested in is what one might call “big data engineering”. They said, “If you find yourself repeating the same tasks over and over, then you should learn to automate them.” It is now obvious that they are in the right.

At the time, I was startled by the way they approached me about what I consider to be largely a difference in personalities. But I can see that they are concerned that someone who reads too much never gets anything done, and so far I have fit that stereotype. At the same time, I am concerned that a person who doesn’t read will do their work quickly and incorrectly and will then spend the next few weeks rejiggering a broken project, and so far they have fit that stereotype. In short, it seems that we are all prejudiced and have plenty to learn from each other.

Going forward I shall take their advice and do the more mundane tasks as fast as possible and only learn things that come up more than once. If that doesn’t work out for me because I’m just cranking out shitty work, I will revert back to understanding what I am doing.

For my Wireless Networking project, I’m going to compare HTTP/1.1 and HTTP/2 with respect to performance metrics when talking to a mobile phone over the cellular network. There are not so many implementations of HTTP/2 right now, and some of them seem a bit shaky. At the end of the day, it seems to me that the easiest way to run this sort of experiment in a reliable fashion is to use Java’s Jetty project. It has well-tested HTTP/1.1 support, many heavyweight framework users, implements HTTP/2’s server push and all sorts of HTTP/2 negotation mechanisms, and I like static types.

Jetty is hard to find tutorials for

So I need to learn the basics of Jetty; and there’s a lot to learn, and I haven’t found a stellar resource, so I’ve been reading the embedded examples, which are decent. I’m usng “embedded” Jetty because that means I can write type-safe Java rather than XML. Perhaps XML would be a good choice for a long-standing app, but I’m making a prototype and it’s easier to just write code.

Here’s a brief overview of what I’ve learned so far, which may come in handy for someone else wanting to understand the very basics of Jetty (version 9). This is not a detailed overview because I don’t know what I’m talking about. I’m just explaining the things I have learned from the tutorial linked above and some mucking around.

Jetty has a few large architectural components

The main things you need to deal with in Jetty are Servers, Handlers, and Connectors.

The Server manages your entire web site. It does this by connecting Connectors to Handlers. The default Connector, ServerConnector responds to vanilla HTTP/1.1 requests. If you try to make a request via https to a ServerConnector without https support, in Chrome you will see the following error message

1
2
3
4
5

ERR_SSL_PROTOCOL_ERROR

Unable to make a secure connection to the server. This may be a problem with
the server, or it may be requiring a client authentication certificate that you
don't have.

Handler

You may want a chain of Handlers that will be tried one after another until one is found to be appropriate for handling the current request

1
2

HandlerList handlers = new HandlerList();
handlers.setHandlers(new Handler[] { resource_handler, new DefaultHandler() });

The DefaultHandler will simply return 404s for everything. Jetty will keep trying Handlers in the list until one of them performs

1

baseRequest.setHandled(true);

Looking at the DefaultHandler’s source, we can see that indeed, in the handle method, this is the first thing it does.

Connector

Each Connector instance can respond to a particular protocol at a particular host on a particular port. So if you want to respond to https requests as well as vanilla http, you’re going to need another Connector.

Routing

A ContextHandler is used to do what in Rails would be called “routing”. This is where you associate path’s in the HTTP request header to the right controller. After you’ve created your ContextHandlers and set their contextPaths, you need to do the following

1
2
3
4
5

Server server = new Server(8080);
//...
ContextHandlerCollection contexts = new ContextHandlerCollection();
contexts.setHandlers(new Handler[] { context0, context1, ... });
server.setHandler(contexts);

This means the server is going to ask the ContextHandlerCollection for the first ContextHandler that matches the path specified on the incoming request.

Conclusion: Jetty feels dated compared to Ruby on Rails

So far, I find Jetty surprisingly nice. I’m starting to appreciate the fact that it is written in Java and it is open source. It’s so different from Ruby on Rails and Node.js because there is not a lot of magical mystery code running in the background whose source is difficult to find. The advantage of those other frameworks is that they have much higher level APIs. I find myself wrapping Jetty methods into my own methods that do what in Rails would have been done automatically. Now I understand the draw of Rails’s “convention over configuration” and “don’t repeat yourself”. I didn’t realize how much configuration and repeating yourself was necessary back in the Java days. And that leads me to my next point, that writing Jetty feels like writing 10 year old code. I wasn’t coding 10 years ago, but I imagine you had to explicitly wire every last thing together by hand over and over again, as you do in Jetty.

Unlike Rails or iOS, basic Jetty is not a Model View Controller framework. It’s just handlers on a server, more like Node.js. Personally, I like MVC out of ignorance because I assume people who came up with it thought the “application framework” way of doing thigs was ‘bad’, and I tend to trust people who don’t like the ‘old’ way of doing things. That said, I am not making a database based application here so I will not evaluate this difference any further.

HTTP/1.1 is from an earlier Web

For the past several years, Google, Mozilla, Akamai, the IETF, the academic research community, and others have been engaged in efforts to reduce PLTs experienced by users of the WWW. One bottleneck in apparent need of an update is the now-“ancient” HTTP/1.1 (H1) protocol, published in 1999.

From the beginning, one of the major design goals of the original HTTP protocol was simplicity to implement and adopt, to encourage growth of the WWW. Evidently, this technique worked. However, over the past 16 years, the way people create, distribute, and view pages on the WWW has changed drastically. Pages today have far more Javascript, CSS, images, and other content to go along with the vanilla HTML. In the course of this evolution, numerous issues with H1 have come up, mostly pertaining to the number of sequential round-trips it requires to fully download the data for each web page. These round-trips introduce unnecessary latency.

Over the past 16 years, countermeasures, “optional” protocol alterations, and application level workarounds have been suggested and implemented to reduce the round-trip count and therefore latency of pages retrieved using H1.

HTTP/1.1 PLT Optimizations

Some optimizations servers and browsers use to lower PLTs seen by clients are the following:

1. Opening multiple TCP connections to request the download of multiple required web page resources in parallel.
2. Inlining and concatenating scripts and stylesheets to reduce the number of requests.
3. HTTP pipelining, in which multiple requests are sent by the browser over a single TCP connection before waiting for responses to any, then the server sends all of the responses back in the same order.

HTTP pipelining was an idea that did not work out. It seemed like a logical approach to improve HTTP performance by reducing latency. However, in reality, HOL blocking became an even greater issue then it already had been, and it also led to issues with older proxies that are difficult to update. Nowadays, modern browsers do not enable pipelining.

HTTP/2 aims to address these issues

The main reason multiple resources can’t be multiplexed (downloaded in parallel) over a single TCP connection in H1 is because it is an ASCII protocol. Being an ASCII protocol means that there is no easy way to specify how to demultiplex those responses with a parser.

To address this, HTTP/2 (H2) is a binary protocol that can easily multiplex multiple requests and responses through a single TCP connection. It does this using a new binary framing layer, in which responses are broken into separate frames and interleaved through the TCP socket.

Web designers have discovered that to yield the best user experience, the server should transmit certain most-important resources first, as soon as they are available to send (e.g. loaded from disk). H2 frames (and streams) have an (optional) priority field to allow the application developer (and server writer) to bias the ordering of frames sent through the socket. For example, one may want to ensure that .html files have a higher priority than .jpeg files because .jpegs contain a lot of data and are not as crucial for showing the user a barebones version of the page they requested.

Brief History

The current H2 specification (RFC 7540) is based primarily on the SPDY protocol invented and first used at Google. Google is in a rather unique position to conduct research on this topic because they write the code running large proportion of both user’s browsers, as well as the servers for a large portion of the web pages those people visit. This allows them to run real controlled experimental studies on web traffic, to try to guage the best way to speed up the Web.

Many have voiced concerns that Google’s ideas are welcomed to quickly by the standards committee. However, supporters are eager to get the ball rolling on any good ideas, and point to the fact that Google already has results.

Note that some of the experimental results below were actually obtained using SPDY rather than H2, but we will not concern ourselves with that because they are the same in essence. Google Chrome still supports SPDY, but has claimed it will remove support in 2016 so that there are not two competing standardizations of basically the same protocol.

In reality, in my Chrome browser, using the “HTTP/2 and SPDY indicator” extension, I can see that Google’s search results and YouTube videos are served over SPDY/3 running on top of their still-in-research QUIC protocol which is meant to replace TCP as the transport layer protocol underneath HTTP. The “indicator” reveals that many websites are in fact already being served over H2, including Twitter. I hope to explore what exactly QUIC does, promises, and delivers further in my research if there is time and space for it.

Experimental Results

Experiments investigating relative performance differences between H1 and H2 have yielded contradictory results (Wang et al.). In (Wang et al.), they found that H2 generally outperforms H1, except when the task is to transmit large objects over a high-loss connection. One of the goals in defining H2 is that it is supposed to be easy to swap-in in-place of H1. This finding indicates that especially with respect to mobile phones, the H1 optimization techniques of inlining and concatenating web page resources is the wrong way to improve performance for H2.

HTTP for Mobile

With respect to mobile devices, there are multiple problems with HTTP that are not addressed by H2 (Erman et al.).

First of all, TCP congestion window part of congestion avoidance (cwnd and ssthresh) makes it so that dropping a single TCP datagram leads to a drastically reduced throughput. This is because TCP assumes the packet was dropped due to network congestion, when in reality, it could have been for any of the wireless-specific issues (multipath propagation, etc.)

Secondly, bad interactions between the 3G & LTE MAC state machine timeouts and modern default TCP timeouts and mechanisms lead to datagram retransmissions with further resets on congestion window state variables, resulting in a drastically negative impact on throughput.

Research is needed

From the system administrators’ perspective, it is still difficult to decide whether enabling H2 on one’s servers is going to have a positive impact on performance at all (Varvello et al.). The following questions still do not have good enough answers to make answering that decision easy.

1. What changes to the infrastructure and optimization pipeline are needed to provide a significant benefit over H1?
2. What are the best algorithms for leveraging H2’s new capabilities for server push and prioritization?
3. Why do experiments by different research groups yield such a wide disparity in results?
4. Are we unlikely to see any real PLT improvements until we improve the underlying transport layer protocol?
5. In what ways is the problem different for mobile?
   • What changes need to be made in the mobile-specific scenario, viz. where interference, low bandwidth, high latency, and battery life considerations are major concerns?

Glossary

• IETF (Internet Engineering Task Force) — a standards organization for the Internet, which produces “RFC”s (requests for comment) specifying some of the crucial internet protocols, such as HTTP, TCP, and TLS.
• PLT (Page Load Time) — the duration between the time at which a user submits a request for a web page, and the time at which she receives the last byte of data needed to represent that web page correctly
• WWW (World Wide Web) — a decentralized collection of resources, requested and transmitted using HTTP
• HTTP (HyperText Transfer Protocol) — a protocol specifying the way an HTTP client may upload, download, update, etc. documents on an HTTP server. Often used for downloading HTML in particular.
• TCP (Transmission Control Protocol) — a protocol which provides an application the abstraction of having a reliable pipe across the Internet into/from which it may send/receive ordered sequences of bytes
• HOL blocking (head-of-line blocking) — when multiple messages are being sent, but due to imposed FIFO ordering, messages ready to be sent must wait for an earlier message which is taking a long time

References

• Erman, Jeffrey, et al. “Towards a SPDY’ier mobile web?.” Proceedings of the ninth ACM conference on Emerging networking experiments and technologies. ACM, 2013.
• Grigorik, Ilya. High Performance Browser Networking: What every web developer should know about networking and web performance. O’Reilly Media, Inc., 2013.
• Roth, Gregor. “HTTP/2 for Java Developers”. Retrieved from http://www.javaworld.com/article/2916548/java-web-development/http-2-for- java-developers.html on October 8, 2015.
• Stenberg, Daniel aka. bagder. http2 explained, retrieved October 8, 2015; downloaded as MOBI.
• Varvello, Matteo, et al. “To HTTP/2, or Not To HTTP/2, That Is The Question” arXiv preprint arXiv:1507.06562 (2015).
• Wang, Xiao Sophia, et al. “How speedy is SPDY.” Proc. of the 11th USENIX Symposium on Networked Systems Design and Implementation (NSDI). 2014.

The problem at my house is that WiFi connectivity is generally fine inside the house, but while sitting on the porch it is nearly impossible for anyone to browse the Hinternets. I think a lesson of my Wireless Networking course explains this observation.

In Wireless networking we have the situation called the Hidden Terminal Problem, which is the following. Node A is too far from node C to hear its transmissions, but both are in range of node B which sits between A and C. Suppose C is currently transmitting data to B. Now A checks whether any transmissions are currently happening, and finds that there are none (because it is out of range of C). So A goes ahead and sends data to B. Now B can’t understand either data packet because they collided and interfered with each other in an unrecoverable way because they were both sent in the same channel.

I think the porch scenario is simply an example of the Hidden Terminal Problem above. In my room, my laptop can hear many of my neighbors’ WiFi LAN networks, but it’s the same set that my WiFi router sitting in the closet can hear. However outside, where there’s less cause for signal attenuation, my laptop can hear many more WiFi LAN networks than the router inside. So the router checks whether there is congestion, doesn’t hear any, and sends the data. But there is, in fact, congestion, and my computer doesn’t receive the data properly. The data is therefore not ACKd, the router times out on the ACK, and has to retransmit, and so on. This makes for a far slower Hinterconnectivity outside on the porch than in my room.

Maybe the lesson learnt is that the WiFi router should be situated in a place where it can hear more of the outside noise so that it can compensate better for that noise.

First Thoughts

First of all

1

if (N > X) return N;

Otherwise, we have two cases

First Case

N: 00100
X: 01100
--------
=> 01100

This example indicates the following:

1

if (!(X & (N-1))) return X;

Second Case

N: 00100       
X: 01101       
--------       
=> 10000       

Which can be accomplished by

1

return (X | (N-1)) + 1;

So we have the first-take program of

1
2
3

if (N > X) return N;
if (!(X & (N-1))) return X;
return (X | (N-1)) + 1;

Engineering Wisdom

The above solution is in fact correct (takes a quick bow).

When I looked up a better answer on StackOverflow, I found a program that does not use conditionals, and is therefore much faster

1

return (X + N - 1) & ~(N - 1);

However, it was not obvious to me that this program works! Let’s peer inside and see how similar it is to my solution.

First we’re going to compute something, and then we’re going to “and” it with ~(N-1). Well, “and”ing anything against ~(N-1) is going to round it down to a multiple of N. So that part is taken care of.

Now we need to get the right multiple of N. if X < N, then then adding X to N and rounding down to a multiple N is just going to give us N. That’s the first line of my answer, taken care of.

So if X > N, we either do or don’t have bits in place values below N. This is what my last two lines are taking care of. However, we can deal with this by noting that after we add X to N, if there are bits in place values below N, when we subtract 1, it will not change any bits that will survive the “and” stage. But if there are no bits in place values below N, then subtracting one will decrement our answer wrt bits N and higher.

Hmm, not the best explanation of all time. But that’s what’s going on in there.