From 8c1c42913deb6a14f060c05e8a230c6aef23d948 Mon Sep 17 00:00:00 2001 From: Brian Picciano Date: Thu, 6 Sep 2018 11:59:01 -0400 Subject: rename post files to have padded 0 in month and day --- .../2013-04-09-erlang-tcp-socket-pull-pattern.md | 256 +++++++++++ _posts/2013-07-11-goplus.md | 77 ++++ _posts/2013-10-08-generations.md | 100 +++++ _posts/2013-10-8-generations.md | 100 ----- _posts/2013-4-9-erlang-tcp-socket-pull-pattern.md | 256 ----------- _posts/2013-7-11-goplus.md | 77 ---- _posts/2014-01-11-clojure-diamond-square.md | 493 +++++++++++++++++++++ _posts/2014-1-11-clojure-diamond-square.md | 493 --------------------- _posts/2015-03-11-rabbit-hole.md | 165 +++++++ _posts/2015-3-11-rabbit-hole.md | 165 ------- _posts/2017-09-06-brian-bars.md | 105 +++++ _posts/2017-9-6-brian-bars.md | 105 ----- 12 files changed, 1196 insertions(+), 1196 deletions(-) create mode 100644 _posts/2013-04-09-erlang-tcp-socket-pull-pattern.md create mode 100644 _posts/2013-07-11-goplus.md create mode 100644 _posts/2013-10-08-generations.md delete mode 100644 _posts/2013-10-8-generations.md delete mode 100644 _posts/2013-4-9-erlang-tcp-socket-pull-pattern.md delete mode 100644 _posts/2013-7-11-goplus.md create mode 100644 _posts/2014-01-11-clojure-diamond-square.md delete mode 100644 _posts/2014-1-11-clojure-diamond-square.md create mode 100644 _posts/2015-03-11-rabbit-hole.md delete mode 100644 _posts/2015-3-11-rabbit-hole.md create mode 100644 _posts/2017-09-06-brian-bars.md delete mode 100644 _posts/2017-9-6-brian-bars.md (limited to '_posts') diff --git a/_posts/2013-04-09-erlang-tcp-socket-pull-pattern.md b/_posts/2013-04-09-erlang-tcp-socket-pull-pattern.md new file mode 100644 index 0000000..3e5f0af --- /dev/null +++ b/_posts/2013-04-09-erlang-tcp-socket-pull-pattern.md @@ -0,0 +1,256 @@ +--- +title: "Erlang, tcp sockets, and active true" +description: >- + Using `{active:once}` isn't always the best way to handle connections. +--- + +If you don't know erlang then [you're missing out][0]. If you do know erlang, +you've probably at some point done something with tcp sockets. Erlang's highly +concurrent model of execution lends itself well to server programs where a high +number of active connections is desired. Each thread can autonomously handle its +single client, greatly simplifying the logic of the whole application while +still retaining [great performance characteristics][1]. + +## Background + +For an erlang thread which owns a single socket there are three different ways +to receive data off of that socket. These all revolve around the `active` +[setopts][2] flag. A socket can be set to one of: + +* `{active,false}` - All data must be obtained through [recv/2][3] calls. This + amounts to syncronous socket reading. + +* `{active,true}` - All data on the socket gets sent to the controlling thread + as a normal erlang message. It is the thread's + responsibility to keep up with the buffered data in the + message queue. This amounts to asyncronous socket reading. + +* `{active,once}` - When set the socket is placed in `{active,true}` for a + single packet. That is, once set the thread can expect a + single message to be sent to when data comes in. To receive + any more data off of the socket the socket must either be + read from using [recv/2][3] or be put in `{active,once}` or + `{active,true}`. + +## Which to use? + +Many (most?) tutorials advocate using `{active,once}` in your application +\[0]\[1]\[2]. This has to do with usability and security. When in `{active,true}` +it's possible for a client to flood the connection faster than the receiving +process will process those messages, potentially eating up a lot of memory in +the VM. However, if you want to be able to receive both tcp data messages as +well as other messages from other erlang processes at the same time you can't +use `{active,false}`. So `{active,once}` is generally preferred because it +deals with both of these problems quite well. + +## Why not to use `{active,once}` + +Here's what your classic `{active,once}` enabled tcp socket implementation will +probably look like: + +```erlang +-module(tcp_test). +-compile(export_all). + +-define(TCP_OPTS, [ + binary, + {packet, raw}, + {nodelay,true}, + {active, false}, + {reuseaddr, true}, + {keepalive,true}, + {backlog,500} +]). + +%Start listening +listen(Port) -> + {ok, L} = gen_tcp:listen(Port, ?TCP_OPTS), + ?MODULE:accept(L). + +%Accept a connection +accept(L) -> + {ok, Socket} = gen_tcp:accept(L), + ?MODULE:read_loop(Socket), + io:fwrite("Done reading, connection was closed\n"), + ?MODULE:accept(L). + +%Read everything it sends us +read_loop(Socket) -> + inet:setopts(Socket, [{active, once}]), + receive + {tcp, _, _} -> + do_stuff_here, + ?MODULE:read_loop(Socket); + {tcp_closed, _}-> donezo; + {tcp_error, _, _} -> donezo + end. +``` + +This code isn't actually usable for a production system; it doesn't even spawn a +new process for the new socket. But that's not the point I'm making. If I run it +with `tcp_test:listen(8000)`, and in other window do: + +```bash +while [ 1 ]; do echo "aloha"; done | nc localhost 8000 +``` + +We'll be flooding the the server with data pretty well. Using [eprof][4] we can +get an idea of how our code performs, and where the hang-ups are: + +```erlang +1> eprof:start(). +{ok,<0.34.0>} + +2> P = spawn(tcp_test,listen,[8000]). +<0.36.0> + +3> eprof:start_profiling([P]). +profiling + +4> running_the_while_loop. +running_the_while_loop + +5> eprof:stop_profiling(). +profiling_stopped + +6> eprof:analyze(procs,[{sort,time}]). + +****** Process <0.36.0> -- 100.00 % of profiled time *** +FUNCTION CALLS % TIME [uS / CALLS] +-------- ----- --- ---- [----------] +prim_inet:type_value_2/2 6 0.00 0 [ 0.00] + +....snip.... + +prim_inet:enc_opts/2 6 0.00 8 [ 1.33] +prim_inet:setopts/2 12303599 1.85 1466319 [ 0.12] +tcp_test:read_loop/1 12303598 2.22 1761775 [ 0.14] +prim_inet:encode_opt_val/1 12303599 3.50 2769285 [ 0.23] +prim_inet:ctl_cmd/3 12303600 4.29 3399333 [ 0.28] +prim_inet:enc_opt_val/2 24607203 5.28 4184818 [ 0.17] +inet:setopts/2 12303598 5.72 4533863 [ 0.37] +erlang:port_control/3 12303600 77.13 61085040 [ 4.96] +``` + +eprof shows us where our process is spending the majority of its time. The `%` +column indicates percentage of time the process spent during profiling inside +any function. We can pretty clearly see that the vast majority of time was spent +inside `erlang:port_control/3`, the BIF that `inet:setopts/2` uses to switch the +socket to `{active,once}` mode. Amongst the calls which were called on every +loop, it takes up by far the most amount of time. In addition all of those other +calls are also related to `inet:setopts/2`. + +I'm gonna rewrite our little listen server to use `{active,true}`, and we'll do +it all again: + +```erlang +-module(tcp_test). +-compile(export_all). + +-define(TCP_OPTS, [ + binary, + {packet, raw}, + {nodelay,true}, + {active, false}, + {reuseaddr, true}, + {keepalive,true}, + {backlog,500} +]). + +%Start listening +listen(Port) -> + {ok, L} = gen_tcp:listen(Port, ?TCP_OPTS), + ?MODULE:accept(L). + +%Accept a connection +accept(L) -> + {ok, Socket} = gen_tcp:accept(L), + inet:setopts(Socket, [{active, true}]), %Well this is new + ?MODULE:read_loop(Socket), + io:fwrite("Done reading, connection was closed\n"), + ?MODULE:accept(L). + +%Read everything it sends us +read_loop(Socket) -> + %inet:setopts(Socket, [{active, once}]), + receive + {tcp, _, _} -> + do_stuff_here, + ?MODULE:read_loop(Socket); + {tcp_closed, _}-> donezo; + {tcp_error, _, _} -> donezo + end. +``` + +And the profiling results: + +```erlang +1> eprof:start(). +{ok,<0.34.0>} + +2> P = spawn(tcp_test,listen,[8000]). +<0.36.0> + +3> eprof:start_profiling([P]). +profiling + +4> running_the_while_loop. +running_the_while_loop + +5> eprof:stop_profiling(). +profiling_stopped + +6> eprof:analyze(procs,[{sort,time}]). + +****** Process <0.36.0> -- 100.00 % of profiled time *** +FUNCTION CALLS % TIME [uS / CALLS] +-------- ----- --- ---- [----------] +prim_inet:enc_value_1/3 7 0.00 1 [ 0.14] +prim_inet:decode_opt_val/1 1 0.00 1 [ 1.00] +inet:setopts/2 1 0.00 2 [ 2.00] +prim_inet:setopts/2 2 0.00 2 [ 1.00] +prim_inet:enum_name/2 1 0.00 2 [ 2.00] +erlang:port_set_data/2 1 0.00 2 [ 2.00] +inet_db:register_socket/2 1 0.00 3 [ 3.00] +prim_inet:type_value_1/3 7 0.00 3 [ 0.43] + +.... snip .... + +prim_inet:type_opt_1/1 19 0.00 7 [ 0.37] +prim_inet:enc_value/3 7 0.00 7 [ 1.00] +prim_inet:enum_val/2 6 0.00 7 [ 1.17] +prim_inet:dec_opt_val/1 7 0.00 7 [ 1.00] +prim_inet:dec_value/2 6 0.00 10 [ 1.67] +prim_inet:enc_opt/1 13 0.00 12 [ 0.92] +prim_inet:type_opt/2 19 0.00 33 [ 1.74] +erlang:port_control/3 3 0.00 59 [ 19.67] +tcp_test:read_loop/1 20716370 100.00 12187488 [ 0.59] +``` + +This time our process spent almost no time at all (according to eprof, 0%) +fiddling with the socket opts. Instead it spent all of its time in the +read_loop doing the work we actually want to be doing. + +## So what does this mean? + +I'm by no means advocating never using `{active,once}`. The security concern is +still a completely valid concern and one that `{active,once}` mitigates quite +well. I'm simply pointing out that this mitigation has some fairly serious +performance implications which have the potential to bite you if you're not +careful, especially in cases where a socket is going to be receiving a large +amount of traffic. + +## Meta + +These tests were done using R15B03, but I've done similar ones in R14 and found +similar results. I have not tested R16. + +* \[0] http://learnyousomeerlang.com/buckets-of-sockets +* \[1] http://www.erlang.org/doc/man/gen_tcp.html#examples +* \[2] http://erlycoder.com/25/erlang-tcp-server-tcp-client-sockets-with-gen_tcp + +[0]: http://learnyousomeerlang.com/content +[1]: http://www.metabrew.com/article/a-million-user-comet-application-with-mochiweb-part-1 +[2]: http://www.erlang.org/doc/man/inet.html#setopts-2 +[3]: http://www.erlang.org/doc/man/gen_tcp.html#recv-2 +[4]: http://www.erlang.org/doc/man/eprof.html diff --git a/_posts/2013-07-11-goplus.md b/_posts/2013-07-11-goplus.md new file mode 100644 index 0000000..5ee121e --- /dev/null +++ b/_posts/2013-07-11-goplus.md @@ -0,0 +1,77 @@ +--- +title: Go+ +description: >- + A simple proof-of-concept script for doing go dependency management. +--- + +Compared to other languages go has some strange behavior regarding its project +root settings. If you import a library called `somelib`, go will look for a +`src/somelib` folder in all of the folders in the `$GOPATH` environment +variable. This works nicely for globally installed packages, but it makes +encapsulating a project with a specific version, or modified version, rather +tedious. Whenever you go to work on this project you'll have to add its path to +your `$GOPATH`, or add the path permanently, which could break other projects +which may use a different version of `somelib`. + +My solution is in the form of a simple script I'm calling go+. go+ will search +in currrent directory and all of its parents for a file called `GOPROJROOT`. If +it finds that file in a directory, it prepends that directory's absolute path to +your `$GOPATH` and stops the search. Regardless of whether or not `GOPROJROOT` +was found go+ will passthrough all arguments to the actual go call. The +modification to `$GOPATH` will only last the duration of the call. + +As an example, consider the following: +``` +/tmp + /hello + GOPROJROOT + /src + /somelib/somelib.go + /hello.go +``` + +If `hello.go` depends on `somelib`, as long as you run go+ from `/tmp/hello` or +one of its children your project will still compile + +Here is the source code for go+: + +```bash +#!/bin/sh + +SEARCHING_FOR=GOPROJROOT +ORIG_DIR=$(pwd) + +STOPSEARCH=0 +SEARCH_DIR=$ORIG_DIR +while [ $STOPSEARCH = 0 ]; do + + RES=$( find $SEARCH_DIR -maxdepth 1 -type f -name $SEARCHING_FOR | \ + grep -P "$SEARCHING_FOR$" | \ + head -n1 ) + + if [ "$RES" = "" ]; then + if [ "$SEARCH_DIR" = "/" ]; then + STOPSEARCH=1 + fi + cd .. + SEARCH_DIR=$(pwd) + else + export GOPATH=$SEARCH_DIR:$GOPATH + STOPSEARCH=1 + fi +done + +cd "$ORIG_DIR" +exec go $@ +``` + +## UPDATE: Goat + +I'm leaving this post for posterity, but go+ has some serious flaws in it. For +one, it doesn't allow for specifying the version of a dependency you want to +use. To this end, I wrote [goat][0] which does all the things go+ does, plus +real dependency management, PLUS it is built in a way that if you've been +following go's best-practices for code organization you shouldn't have to change +any of your existing code AT ALL. It's cool, check it out. + +[0]: http://github.com/mediocregopher/goat diff --git a/_posts/2013-10-08-generations.md b/_posts/2013-10-08-generations.md new file mode 100644 index 0000000..c1c433d --- /dev/null +++ b/_posts/2013-10-08-generations.md @@ -0,0 +1,100 @@ +--- +title: Generations +description: >- + A simple file distribution strategy for very large scale, high-availability + file-services. +--- + +## The problem + +At [cryptic.io][cryptic] we plan on having millions of different +files, any of which could be arbitrarily chosen to be served any given time. +These files are uploaded by users at arbitrary times. + +Scaling such a system is no easy task. The solution I've seen implemented in the +past involves shuffling files around on a nearly constant basis, making sure +that files which are more "popular" are on fast drives, while at the same time +making sure that no drives are at capicty and at the same time that all files, +even newly uploaded ones, are stored redundantly. + +The problem with this solution is one of coordination. At any given moment the +app needs to be able to "find" a file so it can give the client a link to +download the file from one of the servers that it's on. Full-filling this simple +requirement means that all datastores/caches where information about where a +file lives need to be up-to-date at all times, and even then there are +race-conditions and network failures to contend with, while at all times the +requirements of the app evolve and change. + +## A simpler solution + +Let's say you want all files which get uploaded to be replicated in triplicate +in some capacity. You buy three identical hard-disks, and put each on a separate +server. As files get uploaded by clients, each file gets put on each drive +immediately. When the drives are filled (which should be at around the same +time), you stop uploading to them. + +That was generation 0. + +You buy three more drives, and start putting all files on them instead. This is +going to be generation 1. Repeat until you run out of money. + +That's it. + +### That's it? + +It seems simple and obvious, and maybe it's the standard thing which is done, +but as far as I can tell no-one has written about it (though I'm probably not +searching for the right thing, let me know if this is the case!). + +### Advantages + +* It's so simple to implement, you could probably do it in a day if you're +starting a project from scratch + +* By definition of the scheme all files are replicated in multiple places. + +* Minimal information about where a file "is" needs to be stored. When a file is +uploaded all that's needed is to know what generation it is in, and then what +nodes/drives are in that generation. If the file's name is generated +server-side, then the file's generation could be *part* of its name, making +lookup even faster. + +* Drives don't need to "know" about each other. What I mean by this is that +whatever is running as the receive point for file-uploads on each drive doesn't +have to coordinate with its siblings running on the other drives in the +generation. In fact it doesn't need to coordinate with anyone. You could +literally rsync files onto your drives if you wanted to. I would recommend using +[marlin][0] though :) + +* Scaling is easy. When you run out of space you can simply start a new +generation. If you don't like playing that close to the chest there's nothing to +say you can't have two generations active at the same time. + +* Upgrading is easy. As long as a generation is not marked-for-upload, you can +easily copy all files in the generation into a new set of bigger, badder drives, +add those drives into the generation in your code, remove the old ones, then +mark the generation as uploadable again. + +* Distribution is easy. You just copy a generation's files onto a new drive in +Europe or wherever you're getting an uptick in traffic from and you're good to +go. + +* Management is easy. It's trivial to find out how many times a file has been +replicated, or how many countries it's in, or what hardware it's being served +from (given you have easy access to information about specific drives). + +### Caveats + +The big caveat here is that this is just an idea. It has NOT been tested in +production. But we have enough faith in it that we're going to give it a shot at +[cryptic.io][cryptic]. I'll keep this page updated. + +The second caveat is that this scheme does not inherently support caching. If a +file suddenly becomes super popular the world over your hard-disks might not be +able to keep up, and it's probably not feasible to have an FIO drive in *every* +generation. I think that [groupcache][1] may be the answer to this problem, +assuming your files are reasonably small, but again I haven't tested it yet. + +[cryptic]: https://cryptic.io +[0]: https://github.com/cryptic-io/marlin +[1]: https://github.com/golang/groupcache diff --git a/_posts/2013-10-8-generations.md b/_posts/2013-10-8-generations.md deleted file mode 100644 index c1c433d..0000000 --- a/_posts/2013-10-8-generations.md +++ /dev/null @@ -1,100 +0,0 @@ ---- -title: Generations -description: >- - A simple file distribution strategy for very large scale, high-availability - file-services. ---- - -## The problem - -At [cryptic.io][cryptic] we plan on having millions of different -files, any of which could be arbitrarily chosen to be served any given time. -These files are uploaded by users at arbitrary times. - -Scaling such a system is no easy task. The solution I've seen implemented in the -past involves shuffling files around on a nearly constant basis, making sure -that files which are more "popular" are on fast drives, while at the same time -making sure that no drives are at capicty and at the same time that all files, -even newly uploaded ones, are stored redundantly. - -The problem with this solution is one of coordination. At any given moment the -app needs to be able to "find" a file so it can give the client a link to -download the file from one of the servers that it's on. Full-filling this simple -requirement means that all datastores/caches where information about where a -file lives need to be up-to-date at all times, and even then there are -race-conditions and network failures to contend with, while at all times the -requirements of the app evolve and change. - -## A simpler solution - -Let's say you want all files which get uploaded to be replicated in triplicate -in some capacity. You buy three identical hard-disks, and put each on a separate -server. As files get uploaded by clients, each file gets put on each drive -immediately. When the drives are filled (which should be at around the same -time), you stop uploading to them. - -That was generation 0. - -You buy three more drives, and start putting all files on them instead. This is -going to be generation 1. Repeat until you run out of money. - -That's it. - -### That's it? - -It seems simple and obvious, and maybe it's the standard thing which is done, -but as far as I can tell no-one has written about it (though I'm probably not -searching for the right thing, let me know if this is the case!). - -### Advantages - -* It's so simple to implement, you could probably do it in a day if you're -starting a project from scratch - -* By definition of the scheme all files are replicated in multiple places. - -* Minimal information about where a file "is" needs to be stored. When a file is -uploaded all that's needed is to know what generation it is in, and then what -nodes/drives are in that generation. If the file's name is generated -server-side, then the file's generation could be *part* of its name, making -lookup even faster. - -* Drives don't need to "know" about each other. What I mean by this is that -whatever is running as the receive point for file-uploads on each drive doesn't -have to coordinate with its siblings running on the other drives in the -generation. In fact it doesn't need to coordinate with anyone. You could -literally rsync files onto your drives if you wanted to. I would recommend using -[marlin][0] though :) - -* Scaling is easy. When you run out of space you can simply start a new -generation. If you don't like playing that close to the chest there's nothing to -say you can't have two generations active at the same time. - -* Upgrading is easy. As long as a generation is not marked-for-upload, you can -easily copy all files in the generation into a new set of bigger, badder drives, -add those drives into the generation in your code, remove the old ones, then -mark the generation as uploadable again. - -* Distribution is easy. You just copy a generation's files onto a new drive in -Europe or wherever you're getting an uptick in traffic from and you're good to -go. - -* Management is easy. It's trivial to find out how many times a file has been -replicated, or how many countries it's in, or what hardware it's being served -from (given you have easy access to information about specific drives). - -### Caveats - -The big caveat here is that this is just an idea. It has NOT been tested in -production. But we have enough faith in it that we're going to give it a shot at -[cryptic.io][cryptic]. I'll keep this page updated. - -The second caveat is that this scheme does not inherently support caching. If a -file suddenly becomes super popular the world over your hard-disks might not be -able to keep up, and it's probably not feasible to have an FIO drive in *every* -generation. I think that [groupcache][1] may be the answer to this problem, -assuming your files are reasonably small, but again I haven't tested it yet. - -[cryptic]: https://cryptic.io -[0]: https://github.com/cryptic-io/marlin -[1]: https://github.com/golang/groupcache diff --git a/_posts/2013-4-9-erlang-tcp-socket-pull-pattern.md b/_posts/2013-4-9-erlang-tcp-socket-pull-pattern.md deleted file mode 100644 index 3e5f0af..0000000 --- a/_posts/2013-4-9-erlang-tcp-socket-pull-pattern.md +++ /dev/null @@ -1,256 +0,0 @@ ---- -title: "Erlang, tcp sockets, and active true" -description: >- - Using `{active:once}` isn't always the best way to handle connections. ---- - -If you don't know erlang then [you're missing out][0]. If you do know erlang, -you've probably at some point done something with tcp sockets. Erlang's highly -concurrent model of execution lends itself well to server programs where a high -number of active connections is desired. Each thread can autonomously handle its -single client, greatly simplifying the logic of the whole application while -still retaining [great performance characteristics][1]. - -## Background - -For an erlang thread which owns a single socket there are three different ways -to receive data off of that socket. These all revolve around the `active` -[setopts][2] flag. A socket can be set to one of: - -* `{active,false}` - All data must be obtained through [recv/2][3] calls. This - amounts to syncronous socket reading. - -* `{active,true}` - All data on the socket gets sent to the controlling thread - as a normal erlang message. It is the thread's - responsibility to keep up with the buffered data in the - message queue. This amounts to asyncronous socket reading. - -* `{active,once}` - When set the socket is placed in `{active,true}` for a - single packet. That is, once set the thread can expect a - single message to be sent to when data comes in. To receive - any more data off of the socket the socket must either be - read from using [recv/2][3] or be put in `{active,once}` or - `{active,true}`. - -## Which to use? - -Many (most?) tutorials advocate using `{active,once}` in your application -\[0]\[1]\[2]. This has to do with usability and security. When in `{active,true}` -it's possible for a client to flood the connection faster than the receiving -process will process those messages, potentially eating up a lot of memory in -the VM. However, if you want to be able to receive both tcp data messages as -well as other messages from other erlang processes at the same time you can't -use `{active,false}`. So `{active,once}` is generally preferred because it -deals with both of these problems quite well. - -## Why not to use `{active,once}` - -Here's what your classic `{active,once}` enabled tcp socket implementation will -probably look like: - -```erlang --module(tcp_test). --compile(export_all). - --define(TCP_OPTS, [ - binary, - {packet, raw}, - {nodelay,true}, - {active, false}, - {reuseaddr, true}, - {keepalive,true}, - {backlog,500} -]). - -%Start listening -listen(Port) -> - {ok, L} = gen_tcp:listen(Port, ?TCP_OPTS), - ?MODULE:accept(L). - -%Accept a connection -accept(L) -> - {ok, Socket} = gen_tcp:accept(L), - ?MODULE:read_loop(Socket), - io:fwrite("Done reading, connection was closed\n"), - ?MODULE:accept(L). - -%Read everything it sends us -read_loop(Socket) -> - inet:setopts(Socket, [{active, once}]), - receive - {tcp, _, _} -> - do_stuff_here, - ?MODULE:read_loop(Socket); - {tcp_closed, _}-> donezo; - {tcp_error, _, _} -> donezo - end. -``` - -This code isn't actually usable for a production system; it doesn't even spawn a -new process for the new socket. But that's not the point I'm making. If I run it -with `tcp_test:listen(8000)`, and in other window do: - -```bash -while [ 1 ]; do echo "aloha"; done | nc localhost 8000 -``` - -We'll be flooding the the server with data pretty well. Using [eprof][4] we can -get an idea of how our code performs, and where the hang-ups are: - -```erlang -1> eprof:start(). -{ok,<0.34.0>} - -2> P = spawn(tcp_test,listen,[8000]). -<0.36.0> - -3> eprof:start_profiling([P]). -profiling - -4> running_the_while_loop. -running_the_while_loop - -5> eprof:stop_profiling(). -profiling_stopped - -6> eprof:analyze(procs,[{sort,time}]). - -****** Process <0.36.0> -- 100.00 % of profiled time *** -FUNCTION CALLS % TIME [uS / CALLS] --------- ----- --- ---- [----------] -prim_inet:type_value_2/2 6 0.00 0 [ 0.00] - -....snip.... - -prim_inet:enc_opts/2 6 0.00 8 [ 1.33] -prim_inet:setopts/2 12303599 1.85 1466319 [ 0.12] -tcp_test:read_loop/1 12303598 2.22 1761775 [ 0.14] -prim_inet:encode_opt_val/1 12303599 3.50 2769285 [ 0.23] -prim_inet:ctl_cmd/3 12303600 4.29 3399333 [ 0.28] -prim_inet:enc_opt_val/2 24607203 5.28 4184818 [ 0.17] -inet:setopts/2 12303598 5.72 4533863 [ 0.37] -erlang:port_control/3 12303600 77.13 61085040 [ 4.96] -``` - -eprof shows us where our process is spending the majority of its time. The `%` -column indicates percentage of time the process spent during profiling inside -any function. We can pretty clearly see that the vast majority of time was spent -inside `erlang:port_control/3`, the BIF that `inet:setopts/2` uses to switch the -socket to `{active,once}` mode. Amongst the calls which were called on every -loop, it takes up by far the most amount of time. In addition all of those other -calls are also related to `inet:setopts/2`. - -I'm gonna rewrite our little listen server to use `{active,true}`, and we'll do -it all again: - -```erlang --module(tcp_test). --compile(export_all). - --define(TCP_OPTS, [ - binary, - {packet, raw}, - {nodelay,true}, - {active, false}, - {reuseaddr, true}, - {keepalive,true}, - {backlog,500} -]). - -%Start listening -listen(Port) -> - {ok, L} = gen_tcp:listen(Port, ?TCP_OPTS), - ?MODULE:accept(L). - -%Accept a connection -accept(L) -> - {ok, Socket} = gen_tcp:accept(L), - inet:setopts(Socket, [{active, true}]), %Well this is new - ?MODULE:read_loop(Socket), - io:fwrite("Done reading, connection was closed\n"), - ?MODULE:accept(L). - -%Read everything it sends us -read_loop(Socket) -> - %inet:setopts(Socket, [{active, once}]), - receive - {tcp, _, _} -> - do_stuff_here, - ?MODULE:read_loop(Socket); - {tcp_closed, _}-> donezo; - {tcp_error, _, _} -> donezo - end. -``` - -And the profiling results: - -```erlang -1> eprof:start(). -{ok,<0.34.0>} - -2> P = spawn(tcp_test,listen,[8000]). -<0.36.0> - -3> eprof:start_profiling([P]). -profiling - -4> running_the_while_loop. -running_the_while_loop - -5> eprof:stop_profiling(). -profiling_stopped - -6> eprof:analyze(procs,[{sort,time}]). - -****** Process <0.36.0> -- 100.00 % of profiled time *** -FUNCTION CALLS % TIME [uS / CALLS] --------- ----- --- ---- [----------] -prim_inet:enc_value_1/3 7 0.00 1 [ 0.14] -prim_inet:decode_opt_val/1 1 0.00 1 [ 1.00] -inet:setopts/2 1 0.00 2 [ 2.00] -prim_inet:setopts/2 2 0.00 2 [ 1.00] -prim_inet:enum_name/2 1 0.00 2 [ 2.00] -erlang:port_set_data/2 1 0.00 2 [ 2.00] -inet_db:register_socket/2 1 0.00 3 [ 3.00] -prim_inet:type_value_1/3 7 0.00 3 [ 0.43] - -.... snip .... - -prim_inet:type_opt_1/1 19 0.00 7 [ 0.37] -prim_inet:enc_value/3 7 0.00 7 [ 1.00] -prim_inet:enum_val/2 6 0.00 7 [ 1.17] -prim_inet:dec_opt_val/1 7 0.00 7 [ 1.00] -prim_inet:dec_value/2 6 0.00 10 [ 1.67] -prim_inet:enc_opt/1 13 0.00 12 [ 0.92] -prim_inet:type_opt/2 19 0.00 33 [ 1.74] -erlang:port_control/3 3 0.00 59 [ 19.67] -tcp_test:read_loop/1 20716370 100.00 12187488 [ 0.59] -``` - -This time our process spent almost no time at all (according to eprof, 0%) -fiddling with the socket opts. Instead it spent all of its time in the -read_loop doing the work we actually want to be doing. - -## So what does this mean? - -I'm by no means advocating never using `{active,once}`. The security concern is -still a completely valid concern and one that `{active,once}` mitigates quite -well. I'm simply pointing out that this mitigation has some fairly serious -performance implications which have the potential to bite you if you're not -careful, especially in cases where a socket is going to be receiving a large -amount of traffic. - -## Meta - -These tests were done using R15B03, but I've done similar ones in R14 and found -similar results. I have not tested R16. - -* \[0] http://learnyousomeerlang.com/buckets-of-sockets -* \[1] http://www.erlang.org/doc/man/gen_tcp.html#examples -* \[2] http://erlycoder.com/25/erlang-tcp-server-tcp-client-sockets-with-gen_tcp - -[0]: http://learnyousomeerlang.com/content -[1]: http://www.metabrew.com/article/a-million-user-comet-application-with-mochiweb-part-1 -[2]: http://www.erlang.org/doc/man/inet.html#setopts-2 -[3]: http://www.erlang.org/doc/man/gen_tcp.html#recv-2 -[4]: http://www.erlang.org/doc/man/eprof.html diff --git a/_posts/2013-7-11-goplus.md b/_posts/2013-7-11-goplus.md deleted file mode 100644 index 5ee121e..0000000 --- a/_posts/2013-7-11-goplus.md +++ /dev/null @@ -1,77 +0,0 @@ ---- -title: Go+ -description: >- - A simple proof-of-concept script for doing go dependency management. ---- - -Compared to other languages go has some strange behavior regarding its project -root settings. If you import a library called `somelib`, go will look for a -`src/somelib` folder in all of the folders in the `$GOPATH` environment -variable. This works nicely for globally installed packages, but it makes -encapsulating a project with a specific version, or modified version, rather -tedious. Whenever you go to work on this project you'll have to add its path to -your `$GOPATH`, or add the path permanently, which could break other projects -which may use a different version of `somelib`. - -My solution is in the form of a simple script I'm calling go+. go+ will search -in currrent directory and all of its parents for a file called `GOPROJROOT`. If -it finds that file in a directory, it prepends that directory's absolute path to -your `$GOPATH` and stops the search. Regardless of whether or not `GOPROJROOT` -was found go+ will passthrough all arguments to the actual go call. The -modification to `$GOPATH` will only last the duration of the call. - -As an example, consider the following: -``` -/tmp - /hello - GOPROJROOT - /src - /somelib/somelib.go - /hello.go -``` - -If `hello.go` depends on `somelib`, as long as you run go+ from `/tmp/hello` or -one of its children your project will still compile - -Here is the source code for go+: - -```bash -#!/bin/sh - -SEARCHING_FOR=GOPROJROOT -ORIG_DIR=$(pwd) - -STOPSEARCH=0 -SEARCH_DIR=$ORIG_DIR -while [ $STOPSEARCH = 0 ]; do - - RES=$( find $SEARCH_DIR -maxdepth 1 -type f -name $SEARCHING_FOR | \ - grep -P "$SEARCHING_FOR$" | \ - head -n1 ) - - if [ "$RES" = "" ]; then - if [ "$SEARCH_DIR" = "/" ]; then - STOPSEARCH=1 - fi - cd .. - SEARCH_DIR=$(pwd) - else - export GOPATH=$SEARCH_DIR:$GOPATH - STOPSEARCH=1 - fi -done - -cd "$ORIG_DIR" -exec go $@ -``` - -## UPDATE: Goat - -I'm leaving this post for posterity, but go+ has some serious flaws in it. For -one, it doesn't allow for specifying the version of a dependency you want to -use. To this end, I wrote [goat][0] which does all the things go+ does, plus -real dependency management, PLUS it is built in a way that if you've been -following go's best-practices for code organization you shouldn't have to change -any of your existing code AT ALL. It's cool, check it out. - -[0]: http://github.com/mediocregopher/goat diff --git a/_posts/2014-01-11-clojure-diamond-square.md b/_posts/2014-01-11-clojure-diamond-square.md new file mode 100644 index 0000000..a3aee03 --- /dev/null +++ b/_posts/2014-01-11-clojure-diamond-square.md @@ -0,0 +1,493 @@ +--- +title: Random Terrain Generation, A Clojure Walkthrough +description: >- + Tackling the problem of semi-realistic looking terrain generation in + clojure. +--- + +![terrain][terrain] + +I recently started looking into the diamond-square algorithm (you can find a +great article on it [here][diamondsquare]). The following is a short-ish +walkthrough of how I tackled the problem in clojure and the results. You can +find the [leiningen][lein] repo [here][repo] and follow along within that, or +simply read the code below to get an idea. + +Also, Marco ported my code into clojurescript, so you can get random terrain +in your browser. [Check it out!][marco] + +```clojure +(ns diamond-square.core) + +; == The Goal == +; Create a fractal terrain generator using clojure + +; == The Algorithm == +; Diamond-Square. We start with a grid of points, each with a height of 0. +; +; 1. Take each corner point of the square, average the heights, and assign that +; to be the height of the midpoint of the square. Apply some random error to +; the midpoint. +; +; 2. Creating a line from the midpoint to each corner we get four half-diamonds. +; Average the heights of the points (with some random error) and assign the +; heights to the midpoints of the diamonds. +; +; 3. We now have four square sections, start at 1 for each of them (with +; decreasing amount of error for each iteration). +; +; This picture explains it better than I can: +; https://raw2.github.com/mediocregopher/diamond-square/master/resources/dsalg.png +; (http://nbickford.wordpress.com/2012/12/21/creating-fake-landscapes/dsalg/) +; +; == The Strategy == +; We begin with a vector of vectors of numbers, and iterate over it, filling in +; spots as they become available. Our grid will have the top-left being (0,0), +; y being pointing down and x going to the right. The outermost vector +; indicating row number (y) and the inner vectors indicate the column number (x) +; +; = Utility = +; First we create some utility functions for dealing with vectors of vectors. + +(defn print-m + "Prints a grid in a nice way" + [m] + (doseq [n m] + (println n))) + +(defn get-m + "Gets a value at the given x,y coordinate of the grid, with [0,0] being in the + top left" + [m x y] + ((m y) x)) + +(defn set-m + "Sets a value at the given x,y coordinat of the grid, with [0,0] being in the + top left" + [m x y v] + (assoc m y + (assoc (m y) x v))) + +(defn add-m + "Like set-m, but adds the given value to the current on instead of overwriting + it" + [m x y v] + (set-m m x y + (+ (get-m m x y) v))) + +(defn avg + "Returns the truncated average of all the given arguments" + [& l] + (int (/ (reduce + l) (count l)))) + +; = Grid size = +; Since we're starting with a blank grid we need to find out what sizes the +; grids can be. For convenience the size (height and width) should be odd, so we +; easily get a midpoint. And on each iteration we'll be halfing the grid, so +; whenever we do that the two resultrant grids should be odd and halfable as +; well, and so on. +; +; The algorithm that fits this is size = 2^n + 1, where 1 <= n. For the rest of +; this guide I'll be referring to n as the "degree" of the grid. + + +(def exp2-pre-compute + (vec (map #(int (Math/pow 2 %)) (range 31)))) + +(defn exp2 + "Returns 2^n as an integer. Uses pre-computed values since we end up doing + this so much" + [n] + (exp2-pre-compute n)) + +(def grid-sizes + (vec (map #(inc (exp2 %)) (range 1 31)))) + +(defn grid-size [degree] + (inc (exp2 degree))) + +; Available grid heights/widths are as follows: +;[3 5 9 17 33 65 129 257 513 1025 2049 4097 8193 16385 32769 65537 131073 +;262145 524289 1048577 2097153 4194305 8388609 16777217 33554433 67108865 +;134217729 268435457 536870913 1073741825]) + +(defn blank-grid + "Generates a grid of the given degree, filled in with zeros" + [degree] + (let [gsize (grid-size degree)] + (vec (repeat gsize + (vec (repeat gsize 0)))))) + +(comment + (print-m (blank-grid 3)) +) + +; = Coordinate Pattern (The Tricky Part) = +; We now have to figure out which coordinates need to be filled in on each pass. +; A pass is defined as a square step followed by a diamond step. The next pass +; will be the square/dimaond steps on all the smaller squares generated in the +; pass. It works out that the number of passes required to fill in the grid is +; the same as the degree of the grid, where the first pass is 1. +; +; So we can easily find patterns in the coordinates for a given degree/pass, +; I've laid out below all the coordinates for each pass for a 3rd degree grid +; (which is 9x9). + +; Degree 3 Pass 1 Square +; [. . . . . . . . .] +; [. . . . . . . . .] +; [. . . . . . . . .] +; [. . . . . . . . .] +; [. . . . 1 . . . .] (4,4) +; [. . . . . . . . .] +; [. . . . . . . . .] +; [. . . . . . . . .] +; [. . . . . . . . .] + +; Degree 3 Pass 1 Diamond +; [. . . . 2 . . . .] (4,0) +; [. . . . . . . . .] +; [. . . . . . . . .] +; [. . . . . . . . .] +; [2 . . . . . . . 2] (0,4) (8,4) +; [. . . . . . . . .] +; [. . . . . . . . .] +; [. . . . . . . . .] +; [. . . . 2 . . . .] (4,8) + +; Degree 3 Pass 2 Square +; [. . . . . . . . .] +; [. . . . . . . . .] +; [. . 3 . . . 3 . .] (2,2) (6,2) +; [. . . . . . . . .] +; [. . . . . . . . .] +; [. . . . . . . . .] +; [. . 3 . . . 3 . .] (2,6) (6,6) +; [. . . . . . . . .] +; [. . . . . . . . .] + +; Degree 3 Pass 2 Diamond +; [. . 4 . . . 4 . .] (2,0) (6,0) +; [. . . . . . . . .] +; [4 . . . 4 . . . 4] (0,2) (4,2) (8,2) +; [. . . . . . . . .] +; [. . 4 . . . 4 . .] (2,4) (6,4) +; [. . . . . . . . .] +; [4 . . . 4 . . . 4] (0,6) (4,6) (8,6) +; [. . . . . . . . .] +; [. . 4 . . . 4 . .] (2,8) (6,8) + +; Degree 3 Pass 3 Square +; [. . . . . . . . .] +; [. 5 . 5 . 5 . 5 .] (1,1) (3,1) (5,1) (7,1) +; [. . . . . . . . .] +; [. 5 . 5 . 5 . 5 .] (1,3) (3,3) (5,3) (7,3) +; [. . . . . . . . .] +; [. 5 . 5 . 5 . 5 .] (1,5) (3,5) (5,5) (7,5) +; [. . . . . . . . .] +; [. 5 . 5 . 5 . 5 .] (1,7) (3,7) (5,7) (7,7) +; [. . . . . . . . .] + +; Degree 3 Pass 3 Square +; [. 6 . 6 . 6 . 6 .] (1,0) (3,0) (5,0) (7,0) +; [6 . 6 . 6 . 6 . 6] (0,1) (2,1) (4,1) (6,1) (8,1) +; [. 6 . 6 . 6 . 6 .] (1,2) (3,2) (5,2) (7,2) +; [6 . 6 . 6 . 6 . 6] (0,3) (2,3) (4,3) (6,3) (8,3) +; [. 6 . 6 . 6 . 6 .] (1,4) (3,4) (5,4) (7,4) +; [6 . 6 . 6 . 6 . 6] (0,5) (2,5) (4,5) (6,5) (8,5) +; [. 6 . 6 . 6 . 6 .] (1,6) (3,6) (5,6) (7,6) +; [6 . 6 . 6 . 6 . 6] (0,7) (2,7) (4,7) (6,7) (8,7) +; [. 6 . 6 . 6 . 6 .] (1,8) (3,8) (5,8) (7,8) +; +; I make two different functions, one to give the coordinates for the square +; portion of each pass and one for the diamond portion of each pass. To find the +; actual patterns it was useful to first look only at the pattern in the +; y-coordinates, and figure out how that translated into the pattern for the +; x-coordinates. + +(defn grid-square-coords + "Given a grid degree and pass number, returns all the coordinates which need + to be computed for the square step of that pass" + [degree pass] + (let [gsize (grid-size degree) + start (exp2 (- degree pass)) + interval (* 2 start) + coords (map #(+ start (* interval %)) + (range (exp2 (dec pass))))] + (mapcat (fn [y] + (map #(vector % y) coords)) + coords))) +; +; (grid-square-coords 3 2) +; => ([2 2] [6 2] [2 6] [6 6]) + +(defn grid-diamond-coords + "Given a grid degree and a pass number, returns all the coordinates which need + to be computed for the diamond step of that pass" + [degree pass] + (let [gsize (grid-size degree) + interval (exp2 (- degree pass)) + num-coords (grid-size pass) + coords (map #(* interval %) (range 0 num-coords))] + (mapcat (fn [y] + (if (even? (/ y interval)) + (map #(vector % y) (take-nth 2 (drop 1 coords))) + (map #(vector % y) (take-nth 2 coords)))) + coords))) + +; (grid-diamond-coords 3 2) +; => ([2 0] [6 0] [0 2] [4 2] [8 2] [2 4] [6 4] [0 6] [4 6] [8 6] [2 8] [6 8]) + +; = Height Generation = +; We now work on functions which, given a coordinate, will return what value +; coordinate will have. + +(defn avg-points + "Given a grid and an arbitrary number of points (of the form [x y]) returns + the average of all the given points that are on the map. Any points which are + off the map are ignored" + [m & coords] + (let [grid-size (count m)] + (apply avg + (map #(apply get-m m %) + (filter + (fn [[x y]] + (and (< -1 x) (> grid-size x) + (< -1 y) (> grid-size y))) + coords))))) + +(defn error + "Returns a number between -e and e, inclusive" + [e] + (- (rand-int (inc (* 2 e))) e)) + +; The next function is a little weird. It primarily takes in a point, then +; figures out the distance from that point to the points we'll take the average +; of. The locf (locator function) is used to return back the actual points to +; use. For the square portion it'll be the points diagonal from the given one, +; for the diamond portion it'll be the points to the top/bottom/left/right from +; the given one. +; +; Once it has those points, it finds the average and applies the error. The +; error function is nothing more than a number between -interval and +interval, +; where interval is the distance between the given point and one of the averaged +; points. It is important that the error decreases the more passes you do, which +; is why the interval is used. +; +; The error function is what should be messed with primarily if you want to +; change what kind of terrain you generate (a giant mountain instead of +; hills/valleys, for example). The one we use is uniform for all intervals, so +; it generates a uniform terrain. + +(defn- grid-fill-point + [locf m degree pass x y] + (let [interval (exp2 (- degree pass)) + leftx (- x interval) + rightx (+ x interval) + upy (- y interval) + downy (+ y interval) + v (apply avg-points m + (locf x y leftx rightx upy downy))] + (add-m m x y (+ v (error interval))))) + +(def grid-fill-point-square + "Given a grid, the grid's degree, the current pass number, and a point on the + grid, fills in that point with the average (plus some error) of the + appropriate corner points, and returns the resultant grid" + (partial grid-fill-point + (fn [_ _ leftx rightx upy downy] + [[leftx upy] + [rightx upy] + [leftx downy] + [rightx downy]]))) + +(def grid-fill-point-diamond + "Given a grid, the grid's degree, the current pass number, and a point on the + grid, fills in that point with the average (plus some error) of the + appropriate edge points, and returns the resultant grid" + (partial grid-fill-point + (fn [x y leftx rightx upy downy] + [[leftx y] + [rightx y] + [x upy] + [x downy]]))) + +; = Filling in the Grid = +; We finally compose the functions we've been creating to fill in the entire +; grid + +(defn- grid-fill-point-passes + "Given a grid, a function to fill in coordinates, and a function to generate + those coordinates, fills in all coordinates for a given pass, returning the + resultant grid" + [m fill-f coord-f degree pass] + (reduce + (fn [macc [x y]] (fill-f macc degree pass x y)) + m + (coord-f degree pass))) + +(defn grid-pass + "Given a grid and a pass number, does the square then the diamond portion of + the pass" + [m degree pass] + (-> m + (grid-fill-point-passes + grid-fill-point-square grid-square-coords degree pass) + (grid-fill-point-passes + grid-fill-point-diamond grid-diamond-coords degree pass))) + +; The most important function in this guide, does all the work +(defn terrain + "Given a grid degree, generates a uniformly random terrain on a grid of that + degree" + ([degree] + (terrain (blank-grid degree) degree)) + ([m degree] + (reduce + #(grid-pass %1 degree %2) + m + (range 1 (inc degree))))) + +(comment + (print-m + (terrain 5)) +) + +; == The Results == +; We now have a generated terrain, probably. We should check it. First we'll +; create an ASCII representation. But to do that we'll need some utility +; functions. + +(defn max-terrain-height + "Returns the maximum height found in the given terrain grid" + [m] + (reduce max + (map #(reduce max %) m))) + +(defn min-terrain-height + "Returns the minimum height found in the given terrain grid" + [m] + (reduce min + (map #(reduce min %) m))) + +(defn norm + "Given x in the range (A,B), normalizes it into the range (0,new-height)" + [A B new-height x] + (int (/ (* (- x A) new-height) (- B A)))) + +(defn normalize-terrain + "Given a terrain map and a number of \"steps\", normalizes the terrain so all + heights in it are in the range (0,steps)" + [m steps] + (let [max-height (max-terrain-height m) + min-height (min-terrain-height m) + norm-f (partial norm min-height max-height steps)] + (vec (map #(vec (map norm-f %)) m)))) + +; We now define which ASCII characters we want to use for which heights. The +; vector starts with the character for the lowest height and ends with the +; character for the heighest height. + +(def tiles + [\~ \~ \" \" \x \x \X \$ \% \# \@]) + +(defn tile-terrain + "Given a terrain map, converts it into an ASCII tile map" + [m] + (vec (map #(vec (map tiles %)) + (normalize-terrain m (dec (count tiles)))))) + +(comment + (print-m + (tile-terrain + (terrain 5))) + +; [~ ~ " " x x x X % $ $ $ X X X X X X $ x x x X X X x x x x " " " ~] +; [" ~ " " x x X X $ $ $ X X X X X X X X X X X X X X x x x x " " " "] +; [" " " x x x X X % $ % $ % $ $ X X X X $ $ $ X X X X x x x x " " "] +; [" " " x x X $ % % % % % $ % $ $ X X $ $ $ $ X X x x x x x x " " x] +; [" x x x x X $ $ # % % % % % % $ X $ X X % $ % X X x x x x x x x x] +; [x x x X $ $ $ % % % % % $ % $ $ $ % % $ $ $ $ X X x x x x x x x x] +; [X X X $ % $ % % # % % $ $ % % % % $ % $ $ X $ X $ X X x x x X x x] +; [$ $ X $ $ % $ % % % % $ $ $ % # % % % X X X $ $ $ X X X x x x x x] +; [% X X % % $ % % % $ % $ % % % # @ % $ $ X $ X X $ X x X X x x x x] +; [$ $ % % $ $ % % $ $ X $ $ % % % % $ $ X $ $ X X X X X X x x x x x] +; [% % % X $ $ % $ $ X X $ $ $ $ % % $ $ X X X $ X X X x x X x x X X] +; [$ $ $ X $ $ X $ X X X $ $ $ $ % $ $ $ $ $ X $ X x X X X X X x X X] +; [$ $ $ $ X X $ X X X X X $ % % % % % $ X $ $ $ X x X X X $ X X $ $] +; [X $ $ $ $ $ X X X X X X X % $ % $ $ $ X X X X X x x X X x X X $ $] +; [$ $ X X $ X X x X $ $ X X $ % X X X X X X X X X x X X x x X X X X] +; [$ $ X X X X X X X $ $ $ $ $ X $ X X X X X X X x x x x x x x X X X] +; [% % % $ $ X $ X % X X X % $ $ X X X X X X x x x x x x x x x X X $] +; [$ % % $ $ $ X X $ $ $ $ $ $ X X X X x X x x x x " x x x " x x x x] +; [$ X % $ $ $ $ $ X X X X X $ $ X X X X X X x x " " " " " " " " x x] +; [$ X $ $ % % $ X X X $ X X X x x X X x x x x x " " " " " ~ " " " "] +; [$ $ X X % $ % X X X X X X X X x x X X X x x x " " " " " " ~ " " "] +; [$ $ X $ % $ $ X X X X X X x x x x x x x x x " " " " " " " " " ~ ~] +; [$ $ $ $ $ X X $ X X X X X x x x x x x x x " " " " " " " ~ " " " ~] +; [$ % X X $ $ $ $ X X X X x x x x x x x x x x " " " " ~ " " ~ " " ~] +; [% $ $ X $ X $ X $ X $ X x x x x x x x x x x " " " " ~ ~ ~ " ~ " ~] +; [$ X X X X $ $ $ $ $ X x x x x x x x x x x " " " " ~ ~ ~ ~ ~ ~ ~ ~] +; [X x X X x X X X X X X X X x x x x x x x x x " " " ~ ~ " " ~ ~ ~ ~] +; [x x x x x x X x X X x X X X x x x x x x x " x " " " " " ~ ~ ~ ~ ~] +; [x x x x x x x x X X X X $ X X x X x x x x x x x x " ~ ~ ~ ~ ~ ~ ~] +; [" x x x x x X x X X X X X X X X X x x x x x x " " " " ~ ~ ~ ~ ~ ~] +; [" " " x x x X X X X $ $ $ X X X X X X x x x x x x x x " " ~ ~ ~ ~] +; [" " " " x x x X X X X X $ $ X X x X X x x x x x x x " " " " " ~ ~] +; [~ " " x x x x X $ X $ X $ $ X x X x x x x x x x x x x x x " " " ~] +) + +; = Pictures! = +; ASCII is cool, but pictures are better. First we import some java libraries +; that we'll need, then define the colors for each level just like we did tiles +; for the ascii representation. + +(import + 'java.awt.image.BufferedImage + 'javax.imageio.ImageIO + 'java.io.File) + +(def colors + [0x1437AD 0x04859D 0x007D1C 0x007D1C 0x24913C + 0x00C12B 0x38E05D 0xA3A3A4 0x757575 0xFFFFFF]) + +; Finally we reduce over a BufferedImage instance to output every tile as a +; single pixel on it. + +(defn img-terrain + "Given a terrain map and a file name, outputs a png representation of the + terrain map to that file" + [m file] + (let [img (BufferedImage. (count m) (count m) BufferedImage/TYPE_INT_RGB)] + (reduce + (fn [rown row] + (reduce + (fn [coln tile] + (.setRGB img coln rown (colors tile)) + (inc coln)) + 0 row) + (inc rown)) + 0 (normalize-terrain m (dec (count colors)))) + (ImageIO/write img "png" (File. file)))) + +(comment + (img-terrain + (terrain 10) + "resources/terrain.png") + + ; https://raw2.github.com/mediocregopher/diamond-square/master/resources/terrain.png +) + +; == Conclusion == +; There's still a lot of work to be done. The algorithm starts taking a +; non-trivial amount of time around the 10th degree, which is only a 1025x1025px +; image. I need to profile the code and find out where the bottlenecks are. It's +; possible re-organizing the code to use pmaps instead of reduces in some places +; could help. +``` + +[marco]: http://marcopolo.io/diamond-square/ +[terrain]: /img/dsqr-terrain.png +[diamondsquare]: http://www.gameprogrammer.com/fractal.html +[lein]: https://github.com/technomancy/leiningen +[repo]: https://github.com/mediocregopher/diamond-square diff --git a/_posts/2014-1-11-clojure-diamond-square.md b/_posts/2014-1-11-clojure-diamond-square.md deleted file mode 100644 index a3aee03..0000000 --- a/_posts/2014-1-11-clojure-diamond-square.md +++ /dev/null @@ -1,493 +0,0 @@ ---- -title: Random Terrain Generation, A Clojure Walkthrough -description: >- - Tackling the problem of semi-realistic looking terrain generation in - clojure. ---- - -![terrain][terrain] - -I recently started looking into the diamond-square algorithm (you can find a -great article on it [here][diamondsquare]). The following is a short-ish -walkthrough of how I tackled the problem in clojure and the results. You can -find the [leiningen][lein] repo [here][repo] and follow along within that, or -simply read the code below to get an idea. - -Also, Marco ported my code into clojurescript, so you can get random terrain -in your browser. [Check it out!][marco] - -```clojure -(ns diamond-square.core) - -; == The Goal == -; Create a fractal terrain generator using clojure - -; == The Algorithm == -; Diamond-Square. We start with a grid of points, each with a height of 0. -; -; 1. Take each corner point of the square, average the heights, and assign that -; to be the height of the midpoint of the square. Apply some random error to -; the midpoint. -; -; 2. Creating a line from the midpoint to each corner we get four half-diamonds. -; Average the heights of the points (with some random error) and assign the -; heights to the midpoints of the diamonds. -; -; 3. We now have four square sections, start at 1 for each of them (with -; decreasing amount of error for each iteration). -; -; This picture explains it better than I can: -; https://raw2.github.com/mediocregopher/diamond-square/master/resources/dsalg.png -; (http://nbickford.wordpress.com/2012/12/21/creating-fake-landscapes/dsalg/) -; -; == The Strategy == -; We begin with a vector of vectors of numbers, and iterate over it, filling in -; spots as they become available. Our grid will have the top-left being (0,0), -; y being pointing down and x going to the right. The outermost vector -; indicating row number (y) and the inner vectors indicate the column number (x) -; -; = Utility = -; First we create some utility functions for dealing with vectors of vectors. - -(defn print-m - "Prints a grid in a nice way" - [m] - (doseq [n m] - (println n))) - -(defn get-m - "Gets a value at the given x,y coordinate of the grid, with [0,0] being in the - top left" - [m x y] - ((m y) x)) - -(defn set-m - "Sets a value at the given x,y coordinat of the grid, with [0,0] being in the - top left" - [m x y v] - (assoc m y - (assoc (m y) x v))) - -(defn add-m - "Like set-m, but adds the given value to the current on instead of overwriting - it" - [m x y v] - (set-m m x y - (+ (get-m m x y) v))) - -(defn avg - "Returns the truncated average of all the given arguments" - [& l] - (int (/ (reduce + l) (count l)))) - -; = Grid size = -; Since we're starting with a blank grid we need to find out what sizes the -; grids can be. For convenience the size (height and width) should be odd, so we -; easily get a midpoint. And on each iteration we'll be halfing the grid, so -; whenever we do that the two resultrant grids should be odd and halfable as -; well, and so on. -; -; The algorithm that fits this is size = 2^n + 1, where 1 <= n. For the rest of -; this guide I'll be referring to n as the "degree" of the grid. - - -(def exp2-pre-compute - (vec (map #(int (Math/pow 2 %)) (range 31)))) - -(defn exp2 - "Returns 2^n as an integer. Uses pre-computed values since we end up doing - this so much" - [n] - (exp2-pre-compute n)) - -(def grid-sizes - (vec (map #(inc (exp2 %)) (range 1 31)))) - -(defn grid-size [degree] - (inc (exp2 degree))) - -; Available grid heights/widths are as follows: -;[3 5 9 17 33 65 129 257 513 1025 2049 4097 8193 16385 32769 65537 131073 -;262145 524289 1048577 2097153 4194305 8388609 16777217 33554433 67108865 -;134217729 268435457 536870913 1073741825]) - -(defn blank-grid - "Generates a grid of the given degree, filled in with zeros" - [degree] - (let [gsize (grid-size degree)] - (vec (repeat gsize - (vec (repeat gsize 0)))))) - -(comment - (print-m (blank-grid 3)) -) - -; = Coordinate Pattern (The Tricky Part) = -; We now have to figure out which coordinates need to be filled in on each pass. -; A pass is defined as a square step followed by a diamond step. The next pass -; will be the square/dimaond steps on all the smaller squares generated in the -; pass. It works out that the number of passes required to fill in the grid is -; the same as the degree of the grid, where the first pass is 1. -; -; So we can easily find patterns in the coordinates for a given degree/pass, -; I've laid out below all the coordinates for each pass for a 3rd degree grid -; (which is 9x9). - -; Degree 3 Pass 1 Square -; [. . . . . . . . .] -; [. . . . . . . . .] -; [. . . . . . . . .] -; [. . . . . . . . .] -; [. . . . 1 . . . .] (4,4) -; [. . . . . . . . .] -; [. . . . . . . . .] -; [. . . . . . . . .] -; [. . . . . . . . .] - -; Degree 3 Pass 1 Diamond -; [. . . . 2 . . . .] (4,0) -; [. . . . . . . . .] -; [. . . . . . . . .] -; [. . . . . . . . .] -; [2 . . . . . . . 2] (0,4) (8,4) -; [. . . . . . . . .] -; [. . . . . . . . .] -; [. . . . . . . . .] -; [. . . . 2 . . . .] (4,8) - -; Degree 3 Pass 2 Square -; [. . . . . . . . .] -; [. . . . . . . . .] -; [. . 3 . . . 3 . .] (2,2) (6,2) -; [. . . . . . . . .] -; [. . . . . . . . .] -; [. . . . . . . . .] -; [. . 3 . . . 3 . .] (2,6) (6,6) -; [. . . . . . . . .] -; [. . . . . . . . .] - -; Degree 3 Pass 2 Diamond -; [. . 4 . . . 4 . .] (2,0) (6,0) -; [. . . . . . . . .] -; [4 . . . 4 . . . 4] (0,2) (4,2) (8,2) -; [. . . . . . . . .] -; [. . 4 . . . 4 . .] (2,4) (6,4) -; [. . . . . . . . .] -; [4 . . . 4 . . . 4] (0,6) (4,6) (8,6) -; [. . . . . . . . .] -; [. . 4 . . . 4 . .] (2,8) (6,8) - -; Degree 3 Pass 3 Square -; [. . . . . . . . .] -; [. 5 . 5 . 5 . 5 .] (1,1) (3,1) (5,1) (7,1) -; [. . . . . . . . .] -; [. 5 . 5 . 5 . 5 .] (1,3) (3,3) (5,3) (7,3) -; [. . . . . . . . .] -; [. 5 . 5 . 5 . 5 .] (1,5) (3,5) (5,5) (7,5) -; [. . . . . . . . .] -; [. 5 . 5 . 5 . 5 .] (1,7) (3,7) (5,7) (7,7) -; [. . . . . . . . .] - -; Degree 3 Pass 3 Square -; [. 6 . 6 . 6 . 6 .] (1,0) (3,0) (5,0) (7,0) -; [6 . 6 . 6 . 6 . 6] (0,1) (2,1) (4,1) (6,1) (8,1) -; [. 6 . 6 . 6 . 6 .] (1,2) (3,2) (5,2) (7,2) -; [6 . 6 . 6 . 6 . 6] (0,3) (2,3) (4,3) (6,3) (8,3) -; [. 6 . 6 . 6 . 6 .] (1,4) (3,4) (5,4) (7,4) -; [6 . 6 . 6 . 6 . 6] (0,5) (2,5) (4,5) (6,5) (8,5) -; [. 6 . 6 . 6 . 6 .] (1,6) (3,6) (5,6) (7,6) -; [6 . 6 . 6 . 6 . 6] (0,7) (2,7) (4,7) (6,7) (8,7) -; [. 6 . 6 . 6 . 6 .] (1,8) (3,8) (5,8) (7,8) -; -; I make two different functions, one to give the coordinates for the square -; portion of each pass and one for the diamond portion of each pass. To find the -; actual patterns it was useful to first look only at the pattern in the -; y-coordinates, and figure out how that translated into the pattern for the -; x-coordinates. - -(defn grid-square-coords - "Given a grid degree and pass number, returns all the coordinates which need - to be computed for the square step of that pass" - [degree pass] - (let [gsize (grid-size degree) - start (exp2 (- degree pass)) - interval (* 2 start) - coords (map #(+ start (* interval %)) - (range (exp2 (dec pass))))] - (mapcat (fn [y] - (map #(vector % y) coords)) - coords))) -; -; (grid-square-coords 3 2) -; => ([2 2] [6 2] [2 6] [6 6]) - -(defn grid-diamond-coords - "Given a grid degree and a pass number, returns all the coordinates which need - to be computed for the diamond step of that pass" - [degree pass] - (let [gsize (grid-size degree) - interval (exp2 (- degree pass)) - num-coords (grid-size pass) - coords (map #(* interval %) (range 0 num-coords))] - (mapcat (fn [y] - (if (even? (/ y interval)) - (map #(vector % y) (take-nth 2 (drop 1 coords))) - (map #(vector % y) (take-nth 2 coords)))) - coords))) - -; (grid-diamond-coords 3 2) -; => ([2 0] [6 0] [0 2] [4 2] [8 2] [2 4] [6 4] [0 6] [4 6] [8 6] [2 8] [6 8]) - -; = Height Generation = -; We now work on functions which, given a coordinate, will return what value -; coordinate will have. - -(defn avg-points - "Given a grid and an arbitrary number of points (of the form [x y]) returns - the average of all the given points that are on the map. Any points which are - off the map are ignored" - [m & coords] - (let [grid-size (count m)] - (apply avg - (map #(apply get-m m %) - (filter - (fn [[x y]] - (and (< -1 x) (> grid-size x) - (< -1 y) (> grid-size y))) - coords))))) - -(defn error - "Returns a number between -e and e, inclusive" - [e] - (- (rand-int (inc (* 2 e))) e)) - -; The next function is a little weird. It primarily takes in a point, then -; figures out the distance from that point to the points we'll take the average -; of. The locf (locator function) is used to return back the actual points to -; use. For the square portion it'll be the points diagonal from the given one, -; for the diamond portion it'll be the points to the top/bottom/left/right from -; the given one. -; -; Once it has those points, it finds the average and applies the error. The -; error function is nothing more than a number between -interval and +interval, -; where interval is the distance between the given point and one of the averaged -; points. It is important that the error decreases the more passes you do, which -; is why the interval is used. -; -; The error function is what should be messed with primarily if you want to -; change what kind of terrain you generate (a giant mountain instead of -; hills/valleys, for example). The one we use is uniform for all intervals, so -; it generates a uniform terrain. - -(defn- grid-fill-point - [locf m degree pass x y] - (let [interval (exp2 (- degree pass)) - leftx (- x interval) - rightx (+ x interval) - upy (- y interval) - downy (+ y interval) - v (apply avg-points m - (locf x y leftx rightx upy downy))] - (add-m m x y (+ v (error interval))))) - -(def grid-fill-point-square - "Given a grid, the grid's degree, the current pass number, and a point on the - grid, fills in that point with the average (plus some error) of the - appropriate corner points, and returns the resultant grid" - (partial grid-fill-point - (fn [_ _ leftx rightx upy downy] - [[leftx upy] - [rightx upy] - [leftx downy] - [rightx downy]]))) - -(def grid-fill-point-diamond - "Given a grid, the grid's degree, the current pass number, and a point on the - grid, fills in that point with the average (plus some error) of the - appropriate edge points, and returns the resultant grid" - (partial grid-fill-point - (fn [x y leftx rightx upy downy] - [[leftx y] - [rightx y] - [x upy] - [x downy]]))) - -; = Filling in the Grid = -; We finally compose the functions we've been creating to fill in the entire -; grid - -(defn- grid-fill-point-passes - "Given a grid, a function to fill in coordinates, and a function to generate - those coordinates, fills in all coordinates for a given pass, returning the - resultant grid" - [m fill-f coord-f degree pass] - (reduce - (fn [macc [x y]] (fill-f macc degree pass x y)) - m - (coord-f degree pass))) - -(defn grid-pass - "Given a grid and a pass number, does the square then the diamond portion of - the pass" - [m degree pass] - (-> m - (grid-fill-point-passes - grid-fill-point-square grid-square-coords degree pass) - (grid-fill-point-passes - grid-fill-point-diamond grid-diamond-coords degree pass))) - -; The most important function in this guide, does all the work -(defn terrain - "Given a grid degree, generates a uniformly random terrain on a grid of that - degree" - ([degree] - (terrain (blank-grid degree) degree)) - ([m degree] - (reduce - #(grid-pass %1 degree %2) - m - (range 1 (inc degree))))) - -(comment - (print-m - (terrain 5)) -) - -; == The Results == -; We now have a generated terrain, probably. We should check it. First we'll -; create an ASCII representation. But to do that we'll need some utility -; functions. - -(defn max-terrain-height - "Returns the maximum height found in the given terrain grid" - [m] - (reduce max - (map #(reduce max %) m))) - -(defn min-terrain-height - "Returns the minimum height found in the given terrain grid" - [m] - (reduce min - (map #(reduce min %) m))) - -(defn norm - "Given x in the range (A,B), normalizes it into the range (0,new-height)" - [A B new-height x] - (int (/ (* (- x A) new-height) (- B A)))) - -(defn normalize-terrain - "Given a terrain map and a number of \"steps\", normalizes the terrain so all - heights in it are in the range (0,steps)" - [m steps] - (let [max-height (max-terrain-height m) - min-height (min-terrain-height m) - norm-f (partial norm min-height max-height steps)] - (vec (map #(vec (map norm-f %)) m)))) - -; We now define which ASCII characters we want to use for which heights. The -; vector starts with the character for the lowest height and ends with the -; character for the heighest height. - -(def tiles - [\~ \~ \" \" \x \x \X \$ \% \# \@]) - -(defn tile-terrain - "Given a terrain map, converts it into an ASCII tile map" - [m] - (vec (map #(vec (map tiles %)) - (normalize-terrain m (dec (count tiles)))))) - -(comment - (print-m - (tile-terrain - (terrain 5))) - -; [~ ~ " " x x x X % $ $ $ X X X X X X $ x x x X X X x x x x " " " ~] -; [" ~ " " x x X X $ $ $ X X X X X X X X X X X X X X x x x x " " " "] -; [" " " x x x X X % $ % $ % $ $ X X X X $ $ $ X X X X x x x x " " "] -; [" " " x x X $ % % % % % $ % $ $ X X $ $ $ $ X X x x x x x x " " x] -; [" x x x x X $ $ # % % % % % % $ X $ X X % $ % X X x x x x x x x x] -; [x x x X $ $ $ % % % % % $ % $ $ $ % % $ $ $ $ X X x x x x x x x x] -; [X X X $ % $ % % # % % $ $ % % % % $ % $ $ X $ X $ X X x x x X x x] -; [$ $ X $ $ % $ % % % % $ $ $ % # % % % X X X $ $ $ X X X x x x x x] -; [% X X % % $ % % % $ % $ % % % # @ % $ $ X $ X X $ X x X X x x x x] -; [$ $ % % $ $ % % $ $ X $ $ % % % % $ $ X $ $ X X X X X X x x x x x] -; [% % % X $ $ % $ $ X X $ $ $ $ % % $ $ X X X $ X X X x x X x x X X] -; [$ $ $ X $ $ X $ X X X $ $ $ $ % $ $ $ $ $ X $ X x X X X X X x X X] -; [$ $ $ $ X X $ X X X X X $ % % % % % $ X $ $ $ X x X X X $ X X $ $] -; [X $ $ $ $ $ X X X X X X X % $ % $ $ $ X X X X X x x X X x X X $ $] -; [$ $ X X $ X X x X $ $ X X $ % X X X X X X X X X x X X x x X X X X] -; [$ $ X X X X X X X $ $ $ $ $ X $ X X X X X X X x x x x x x x X X X] -; [% % % $ $ X $ X % X X X % $ $ X X X X X X x x x x x x x x x X X $] -; [$ % % $ $ $ X X $ $ $ $ $ $ X X X X x X x x x x " x x x " x x x x] -; [$ X % $ $ $ $ $ X X X X X $ $ X X X X X X x x " " " " " " " " x x] -; [$ X $ $ % % $ X X X $ X X X x x X X x x x x x " " " " " ~ " " " "] -; [$ $ X X % $ % X X X X X X X X x x X X X x x x " " " " " " ~ " " "] -; [$ $ X $ % $ $ X X X X X X x x x x x x x x x " " " " " " " " " ~ ~] -; [$ $ $ $ $ X X $ X X X X X x x x x x x x x " " " " " " " ~ " " " ~] -; [$ % X X $ $ $ $ X X X X x x x x x x x x x x " " " " ~ " " ~ " " ~] -; [% $ $ X $ X $ X $ X $ X x x x x x x x x x x " " " " ~ ~ ~ " ~ " ~] -; [$ X X X X $ $ $ $ $ X x x x x x x x x x x " " " " ~ ~ ~ ~ ~ ~ ~ ~] -; [X x X X x X X X X X X X X x x x x x x x x x " " " ~ ~ " " ~ ~ ~ ~] -; [x x x x x x X x X X x X X X x x x x x x x " x " " " " " ~ ~ ~ ~ ~] -; [x x x x x x x x X X X X $ X X x X x x x x x x x x " ~ ~ ~ ~ ~ ~ ~] -; [" x x x x x X x X X X X X X X X X x x x x x x " " " " ~ ~ ~ ~ ~ ~] -; [" " " x x x X X X X $ $ $ X X X X X X x x x x x x x x " " ~ ~ ~ ~] -; [" " " " x x x X X X X X $ $ X X x X X x x x x x x x " " " " " ~ ~] -; [~ " " x x x x X $ X $ X $ $ X x X x x x x x x x x x x x x " " " ~] -) - -; = Pictures! = -; ASCII is cool, but pictures are better. First we import some java libraries -; that we'll need, then define the colors for each level just like we did tiles -; for the ascii representation. - -(import - 'java.awt.image.BufferedImage - 'javax.imageio.ImageIO - 'java.io.File) - -(def colors - [0x1437AD 0x04859D 0x007D1C 0x007D1C 0x24913C - 0x00C12B 0x38E05D 0xA3A3A4 0x757575 0xFFFFFF]) - -; Finally we reduce over a BufferedImage instance to output every tile as a -; single pixel on it. - -(defn img-terrain - "Given a terrain map and a file name, outputs a png representation of the - terrain map to that file" - [m file] - (let [img (BufferedImage. (count m) (count m) BufferedImage/TYPE_INT_RGB)] - (reduce - (fn [rown row] - (reduce - (fn [coln tile] - (.setRGB img coln rown (colors tile)) - (inc coln)) - 0 row) - (inc rown)) - 0 (normalize-terrain m (dec (count colors)))) - (ImageIO/write img "png" (File. file)))) - -(comment - (img-terrain - (terrain 10) - "resources/terrain.png") - - ; https://raw2.github.com/mediocregopher/diamond-square/master/resources/terrain.png -) - -; == Conclusion == -; There's still a lot of work to be done. The algorithm starts taking a -; non-trivial amount of time around the 10th degree, which is only a 1025x1025px -; image. I need to profile the code and find out where the bottlenecks are. It's -; possible re-organizing the code to use pmaps instead of reduces in some places -; could help. -``` - -[marco]: http://marcopolo.io/diamond-square/ -[terrain]: /img/dsqr-terrain.png -[diamondsquare]: http://www.gameprogrammer.com/fractal.html -[lein]: https://github.com/technomancy/leiningen -[repo]: https://github.com/mediocregopher/diamond-square diff --git a/_posts/2015-03-11-rabbit-hole.md b/_posts/2015-03-11-rabbit-hole.md new file mode 100644 index 0000000..97c2b80 --- /dev/null +++ b/_posts/2015-03-11-rabbit-hole.md @@ -0,0 +1,165 @@ +--- +title: Rabbit Hole +description: >- + Complex systems sometimes require complex debugging. +--- + +We've begun rolling out [SkyDNS][skydns] at my job, which has been pretty neat. +We're basing a couple future projects around being able to use it, and it's made +dynamic configuration and service discovery nice and easy. + +This post chronicles catching a bug because of our switch to SkyDNS, and how we +discover its root cause. I like to call these kinds of bugs "rabbit holes"; they +look shallow at first, but anytime you make a little progress forward a little +more is always required, until you discover the ending somewhere totally +unrelated to the start. + +## The Bug + +We are seeing *tons* of these in the SkyDNS log: + +``` +[skydns] Feb 20 17:21:15.168 INFO | no nameservers defined or name too short, can not forward +``` + +I fire up tcpdump to see if I can see anything interesting, and sure enough run +across a bunch of these: + +``` +# tcpdump -vvv -s 0 -l -n port 53 +tcpdump: listening on eth0, link-type EN10MB (Ethernet), capture size 65535 bytes + ... + $fen_ip.50257 > $skydns_ip.domain: [udp sum ok] 16218+ A? unknown. (25) + $fen_ip.27372 > $skydns_ip.domain: [udp sum ok] 16218+ A? unknown. (25) + $fen_ip.35634 > $skydns_ip.domain: [udp sum ok] 59227+ A? unknown. (25) + $fen_ip.64363 > $skydns_ip.domain: [udp sum ok] 59227+ A? unknown. (25) +``` + +It appears that some of our front end nodes (FENs) are making tons of DNS +fequests trying to find the A record of `unknown`. Something on our FENs is +doing something insane and is breaking. + +## The FENs + +Hopping over to my favorite FEN we're able to see the packets in question +leaving on a tcpdump as well, but that's not helpful for finding the root cause. +We have lots of processes running on the FENs and any number of them could be +doing something crazy. + +We fire up sysdig, which is similar to systemtap and strace in that it allows +you to hook into the kernel and view various kernel activites in real time, but +it's easier to use than both. The following command dumps all UDP packets being +sent and what process is sending them: + +``` +# sysdig fd.l4proto=udp +... +2528950 22:17:35.260606188 0 php-fpm (21477) < connect res=0 tuple=$fen_ip:61173->$skydns_ip:53 +2528961 22:17:35.260611327 0 php-fpm (21477) > sendto fd=102(<4u>$fen_ip:61173->$skydns_ip:53) size=25 tuple=NULL +2528991 22:17:35.260631917 0 php-fpm (21477) < sendto res=25 data=.r...........unknown..... +2530470 22:17:35.261879032 0 php-fpm (21477) > ioctl fd=102(<4u>$fen_ip:61173->$skydns_ip:53) request=541B argument=7FFF82DC8728 +2530472 22:17:35.261880574 0 php-fpm (21477) < ioctl res=0 +2530474 22:17:35.261881226 0 php-fpm (21477) > recvfrom fd=102(<4u>$fen_ip:61173->$skydns_ip:53) size=1024 +2530476 22:17:35.261883424 0 php-fpm (21477) < recvfrom res=25 data=.r...........unknown..... tuple=$skydns_ip:53->$fen_ip:61173 +2530485 22:17:35.261888997 0 php-fpm (21477) > close fd=102(<4u>$fen_ip:61173->$skydns_ip:53) +2530488 22:17:35.261892626 0 php-fpm (21477) < close res=0 +``` + +Aha! We can see php-fpm is requesting something over udp with the string +`unknown` in it. We've now narrowed down the guilty process, the rest should be +easy right? + +## Which PHP? + +Unfortunately we're a PHP shop; knowing that php-fpm is doing something on a FEN +narrows down the guilty codebase little. Taking the FEN out of our load-balancer +stops the requests for `unknown`, so we *can* say that it's some user-facing +code that is the culprit. Our setup on the FENs involves users hitting nginx +for static content and nginx proxying PHP requests back to php-fpm. Since all +our virtual domains are defined in nginx, we are able to do something horrible. + +On the particular FEN we're on we make a guess about which virtual domain the +problem is likely coming from (our main app), and proxy all traffic from all +other domains to a different FEN. We still see requests for `unknown` leaving +the box, so we've narrowed the problem down a little more. + +## The Despair + +Nothing in our code is doing any direct DNS calls as far as we can find, and we +don't see any places PHP might be doing it for us. We have lots of PHP +extensions in place, all written in C and all black boxes; any of them could be +the culprit. Grepping through the likely candidates' source code for the string +`unknown` proves fruitless. + +We try xdebug at this point. xdebug is a profiler for php which will create +cachegrind files for the running code. With cachegrind you can see every +function which was ever called, how long spent within each function, a full +call-graph, and lots more. Unfortunately xdebug outputs cachegrind files on a +per-php-fpm-process basis, and overwrites the previous file on each new request. +So xdebug is pretty much useless, since what is in the cachegrind file isn't +necessarily what spawned the DNS request. + +## Gotcha (sorta) + +We turn back to the tried and true method of dumping all the traffic using +tcpdump and perusing through that manually. + +What we find is that nearly everytime there is a DNS request for `unknown`, if +we scroll up a bit there is (usually) a particular request to memcache. The +requested key is always in the style of `function-name:someid:otherstuff`. When +looking in the code around that function name we find this ominous looking call: + +```php +$ipAddress = getIPAddress(); +$geoipInfo = getCountryInfoFromIP($ipAddress); +``` + +This points us in the right direction. On a hunch we add some debug +logging to print out the `$ipAddress` variable, and sure enough it comes back as +`unknown`. AHA! + +So what we surmise is happening is that for some reason our geoip extension, +which we use to get the location data of an IP address and which +`getCountryInfoFromIP` calls, is seeing something which is *not* an IP address +and trying to resolve it. + +## Gotcha (for real) + +So the question becomes: why are we getting the string `unknown` as an IP +address? + +Adding some debug logging around the area we find before showed that +`$_SERVER['REMOTE_ADDR']`, which is the variable populated with the IP address +of the client, is sometimes `unknown`. We guess that this has something to do +with some magic we are doing on nginx's side to populate `REMOTE_ADDR` with the +real IP address of the client in the case of them going through a proxy. + +Many proxies send along the header `X-Forwarded-For` to indicate the real IP of +the client they're proxying for, otherwise the server would only see the proxy's +IP. In our setup I decided that in those cases we should set the `REMOTE_ADDR` +to the real client IP so our application logic doesn't even have to worry about +it. There are a couple problems with this which render it a bad decision, one +being that if some misbahaving proxy was to, say, start sending +`X-Forwarded-For: unknown` then some written applications might mistake that to +mean the client's IP is `unknown`. + +## The Fix + +The fix here was two-fold: + +1) We now always set `$_SERVER['REMOTE_ADDR']` to be the remote address of the +requests, regardless of if it's a proxy, and also send the application the +`X-Forwarded-For` header to do with as it pleases. + +2) Inside our app we look at all the headers sent and do some processing to +decide what the actual client IP is. PHP can handle a lot more complex logic +than nginx can, so we can do things like check to make sure the IP is an IP, and +also that it's not some NAT'd internal ip, and so forth. + +And that's it. From some weird log messages on our DNS servers to an nginx +mis-configuration on an almost unrelated set of servers, this is one of those +strange bugs that never has a nice solution and goes unsolved for a long time. +Spending the time to dive down the rabbit hole and find the answer is often +tedious, but also often very rewarding. + +[skydns]: https://github.com/skynetservices/skydns diff --git a/_posts/2015-3-11-rabbit-hole.md b/_posts/2015-3-11-rabbit-hole.md deleted file mode 100644 index 97c2b80..0000000 --- a/_posts/2015-3-11-rabbit-hole.md +++ /dev/null @@ -1,165 +0,0 @@ ---- -title: Rabbit Hole -description: >- - Complex systems sometimes require complex debugging. ---- - -We've begun rolling out [SkyDNS][skydns] at my job, which has been pretty neat. -We're basing a couple future projects around being able to use it, and it's made -dynamic configuration and service discovery nice and easy. - -This post chronicles catching a bug because of our switch to SkyDNS, and how we -discover its root cause. I like to call these kinds of bugs "rabbit holes"; they -look shallow at first, but anytime you make a little progress forward a little -more is always required, until you discover the ending somewhere totally -unrelated to the start. - -## The Bug - -We are seeing *tons* of these in the SkyDNS log: - -``` -[skydns] Feb 20 17:21:15.168 INFO | no nameservers defined or name too short, can not forward -``` - -I fire up tcpdump to see if I can see anything interesting, and sure enough run -across a bunch of these: - -``` -# tcpdump -vvv -s 0 -l -n port 53 -tcpdump: listening on eth0, link-type EN10MB (Ethernet), capture size 65535 bytes - ... - $fen_ip.50257 > $skydns_ip.domain: [udp sum ok] 16218+ A? unknown. (25) - $fen_ip.27372 > $skydns_ip.domain: [udp sum ok] 16218+ A? unknown. (25) - $fen_ip.35634 > $skydns_ip.domain: [udp sum ok] 59227+ A? unknown. (25) - $fen_ip.64363 > $skydns_ip.domain: [udp sum ok] 59227+ A? unknown. (25) -``` - -It appears that some of our front end nodes (FENs) are making tons of DNS -fequests trying to find the A record of `unknown`. Something on our FENs is -doing something insane and is breaking. - -## The FENs - -Hopping over to my favorite FEN we're able to see the packets in question -leaving on a tcpdump as well, but that's not helpful for finding the root cause. -We have lots of processes running on the FENs and any number of them could be -doing something crazy. - -We fire up sysdig, which is similar to systemtap and strace in that it allows -you to hook into the kernel and view various kernel activites in real time, but -it's easier to use than both. The following command dumps all UDP packets being -sent and what process is sending them: - -``` -# sysdig fd.l4proto=udp -... -2528950 22:17:35.260606188 0 php-fpm (21477) < connect res=0 tuple=$fen_ip:61173->$skydns_ip:53 -2528961 22:17:35.260611327 0 php-fpm (21477) > sendto fd=102(<4u>$fen_ip:61173->$skydns_ip:53) size=25 tuple=NULL -2528991 22:17:35.260631917 0 php-fpm (21477) < sendto res=25 data=.r...........unknown..... -2530470 22:17:35.261879032 0 php-fpm (21477) > ioctl fd=102(<4u>$fen_ip:61173->$skydns_ip:53) request=541B argument=7FFF82DC8728 -2530472 22:17:35.261880574 0 php-fpm (21477) < ioctl res=0 -2530474 22:17:35.261881226 0 php-fpm (21477) > recvfrom fd=102(<4u>$fen_ip:61173->$skydns_ip:53) size=1024 -2530476 22:17:35.261883424 0 php-fpm (21477) < recvfrom res=25 data=.r...........unknown..... tuple=$skydns_ip:53->$fen_ip:61173 -2530485 22:17:35.261888997 0 php-fpm (21477) > close fd=102(<4u>$fen_ip:61173->$skydns_ip:53) -2530488 22:17:35.261892626 0 php-fpm (21477) < close res=0 -``` - -Aha! We can see php-fpm is requesting something over udp with the string -`unknown` in it. We've now narrowed down the guilty process, the rest should be -easy right? - -## Which PHP? - -Unfortunately we're a PHP shop; knowing that php-fpm is doing something on a FEN -narrows down the guilty codebase little. Taking the FEN out of our load-balancer -stops the requests for `unknown`, so we *can* say that it's some user-facing -code that is the culprit. Our setup on the FENs involves users hitting nginx -for static content and nginx proxying PHP requests back to php-fpm. Since all -our virtual domains are defined in nginx, we are able to do something horrible. - -On the particular FEN we're on we make a guess about which virtual domain the -problem is likely coming from (our main app), and proxy all traffic from all -other domains to a different FEN. We still see requests for `unknown` leaving -the box, so we've narrowed the problem down a little more. - -## The Despair - -Nothing in our code is doing any direct DNS calls as far as we can find, and we -don't see any places PHP might be doing it for us. We have lots of PHP -extensions in place, all written in C and all black boxes; any of them could be -the culprit. Grepping through the likely candidates' source code for the string -`unknown` proves fruitless. - -We try xdebug at this point. xdebug is a profiler for php which will create -cachegrind files for the running code. With cachegrind you can see every -function which was ever called, how long spent within each function, a full -call-graph, and lots more. Unfortunately xdebug outputs cachegrind files on a -per-php-fpm-process basis, and overwrites the previous file on each new request. -So xdebug is pretty much useless, since what is in the cachegrind file isn't -necessarily what spawned the DNS request. - -## Gotcha (sorta) - -We turn back to the tried and true method of dumping all the traffic using -tcpdump and perusing through that manually. - -What we find is that nearly everytime there is a DNS request for `unknown`, if -we scroll up a bit there is (usually) a particular request to memcache. The -requested key is always in the style of `function-name:someid:otherstuff`. When -looking in the code around that function name we find this ominous looking call: - -```php -$ipAddress = getIPAddress(); -$geoipInfo = getCountryInfoFromIP($ipAddress); -``` - -This points us in the right direction. On a hunch we add some debug -logging to print out the `$ipAddress` variable, and sure enough it comes back as -`unknown`. AHA! - -So what we surmise is happening is that for some reason our geoip extension, -which we use to get the location data of an IP address and which -`getCountryInfoFromIP` calls, is seeing something which is *not* an IP address -and trying to resolve it. - -## Gotcha (for real) - -So the question becomes: why are we getting the string `unknown` as an IP -address? - -Adding some debug logging around the area we find before showed that -`$_SERVER['REMOTE_ADDR']`, which is the variable populated with the IP address -of the client, is sometimes `unknown`. We guess that this has something to do -with some magic we are doing on nginx's side to populate `REMOTE_ADDR` with the -real IP address of the client in the case of them going through a proxy. - -Many proxies send along the header `X-Forwarded-For` to indicate the real IP of -the client they're proxying for, otherwise the server would only see the proxy's -IP. In our setup I decided that in those cases we should set the `REMOTE_ADDR` -to the real client IP so our application logic doesn't even have to worry about -it. There are a couple problems with this which render it a bad decision, one -being that if some misbahaving proxy was to, say, start sending -`X-Forwarded-For: unknown` then some written applications might mistake that to -mean the client's IP is `unknown`. - -## The Fix - -The fix here was two-fold: - -1) We now always set `$_SERVER['REMOTE_ADDR']` to be the remote address of the -requests, regardless of if it's a proxy, and also send the application the -`X-Forwarded-For` header to do with as it pleases. - -2) Inside our app we look at all the headers sent and do some processing to -decide what the actual client IP is. PHP can handle a lot more complex logic -than nginx can, so we can do things like check to make sure the IP is an IP, and -also that it's not some NAT'd internal ip, and so forth. - -And that's it. From some weird log messages on our DNS servers to an nginx -mis-configuration on an almost unrelated set of servers, this is one of those -strange bugs that never has a nice solution and goes unsolved for a long time. -Spending the time to dive down the rabbit hole and find the answer is often -tedious, but also often very rewarding. - -[skydns]: https://github.com/skynetservices/skydns diff --git a/_posts/2017-09-06-brian-bars.md b/_posts/2017-09-06-brian-bars.md new file mode 100644 index 0000000..2c56272 --- /dev/null +++ b/_posts/2017-09-06-brian-bars.md @@ -0,0 +1,105 @@ +--- +title: Brian Bars +description: >- + Cheap and easy to make, healthy, vegan, high-carb, high-protein. "The Good + Stuff". +updated: 2018-01-18 +--- + +It actually blows my mind it's been 4 years since I used this blog. It was +previously a tech blog, but then I started putting all my tech-related posts on +[the cryptic blog](https://cryptic.io). As of now this is a lifestyle/travel +blog. The me of 4 years ago would be horrified. + +Now I just have to come up with a lifestyle and do some traveling. + +## Recipe + +This isn't a real recipe because I'm not going to preface it with my entire +fucking life story. Let's talk about the food. + +Brian bars: + +* Are like Clif Bars, but with the simplicity of ingredients that Larabars have. +* Are easy to make, only needing a food processor (I use a magic bullet) and a + stovetop oven. +* Keep for a long time and don't really need refrigerating (but don't mind it + neither) +* Are paleo, vegan, gluten-free, free-range, grass-fed, whatever... +* Are really really filling. +* Are named after me, deal with it. + +I've worked on this recipe for a bit, trying to make it workable, and will +probably keep adjusting it (and this post) as time goes on. + +### Ingredients + +Nuts and seeds. Most of this recipe is nuts and seeds. Here's the ones I used: + +* 1 cup almonds +* 1 cup peanuts +* 1 cup walnuts +* 1 cup coconut flakes/shavings/whatever +* 1/2 cup flax seeds +* 1/2 cup sesame seeds + +For all of those above it doesn't _really_ matter what nuts/seeds you use, it's +all gonna get ground up anyway. So whatever's cheap works fine. Also, avoid +salt-added ones if you can. + +The other ingredients are: + +* 1 cup raisins/currants +* 1.5 lbs of pitted dates (no added sugar! you don't need it!) +* 2 cups oats + +### Grind up the nuts + +Throw the nuts into the food processor and grind them into a powder. Then throw +that powder into a bowl along with the seeds, coconuts, raisins, and oats, and +mix em good. + +I don't _completely_ grind up the nuts, instead leaving some chunks in it here +and there, but you do you. + +### Prepare the dates + +This is the harder part, and is what took me a couple tries to get right. The +best strategy I've found is to steam the dates a bit over a stove to soften +them. Then, about a cup at a time, you can throw them in the food processor and +turn them into a paste. You may have to add a little water if your processor is +having trouble. + +Once processed you can add the dates to the mix from before and stir it all up. +It'll end up looking something like cookie dough. Except unlike cookie dough +it's completely safe to eat and maybe sorta healthy. + +### Bake it, Finish it + +Put the dough stuff in a pan of some sort, flatten it out, and stick it in the +oven at like 250 or 300 for a few hours. You're trying to cook out the water you +added earlier when you steamed the dates, as well as whatever little moisture +the dates had in the first place. + +Once thoroughly baked you can stick the pan in the fridge to cool and keep, +and/or cut it up into individual bars. Keep in mind that the bars are super +filling and allow for pretty small portions. Wrap em in foil or plastic wrap and +take them to-go, or keep them around for a snack. Or both. Or whatever you want +to do, it's your food. + +### Cleanup + +Dates are simultaneously magical and the most annoying thing to work with, so +there's cleanup problems you may run into with them: + +Protip #1: When cleaning your processed date slime off of your cooking utensils +I'd recommend just letting them soak in water for a while. Dry-ish date slime +will stick to everything, while soaked date slime will come right off. + +Protip #2: Apparently if you want ants, dates are a great way to get ants. My +apartment has never had an ant problem until 3 hours after I made a batch of +these and didn't wipe down my counter enough. I'm still dealing with the ants. +Apparently there's enviromentally friendly ant poisons where the ants happily +carry the poison back into the nest and the whole nest eats it and dies. Which +feels kinda mean in some way, but is also pretty clever and they're just ants +anyway so fuck it. diff --git a/_posts/2017-9-6-brian-bars.md b/_posts/2017-9-6-brian-bars.md deleted file mode 100644 index 2c56272..0000000 --- a/_posts/2017-9-6-brian-bars.md +++ /dev/null @@ -1,105 +0,0 @@ ---- -title: Brian Bars -description: >- - Cheap and easy to make, healthy, vegan, high-carb, high-protein. "The Good - Stuff". -updated: 2018-01-18 ---- - -It actually blows my mind it's been 4 years since I used this blog. It was -previously a tech blog, but then I started putting all my tech-related posts on -[the cryptic blog](https://cryptic.io). As of now this is a lifestyle/travel -blog. The me of 4 years ago would be horrified. - -Now I just have to come up with a lifestyle and do some traveling. - -## Recipe - -This isn't a real recipe because I'm not going to preface it with my entire -fucking life story. Let's talk about the food. - -Brian bars: - -* Are like Clif Bars, but with the simplicity of ingredients that Larabars have. -* Are easy to make, only needing a food processor (I use a magic bullet) and a - stovetop oven. -* Keep for a long time and don't really need refrigerating (but don't mind it - neither) -* Are paleo, vegan, gluten-free, free-range, grass-fed, whatever... -* Are really really filling. -* Are named after me, deal with it. - -I've worked on this recipe for a bit, trying to make it workable, and will -probably keep adjusting it (and this post) as time goes on. - -### Ingredients - -Nuts and seeds. Most of this recipe is nuts and seeds. Here's the ones I used: - -* 1 cup almonds -* 1 cup peanuts -* 1 cup walnuts -* 1 cup coconut flakes/shavings/whatever -* 1/2 cup flax seeds -* 1/2 cup sesame seeds - -For all of those above it doesn't _really_ matter what nuts/seeds you use, it's -all gonna get ground up anyway. So whatever's cheap works fine. Also, avoid -salt-added ones if you can. - -The other ingredients are: - -* 1 cup raisins/currants -* 1.5 lbs of pitted dates (no added sugar! you don't need it!) -* 2 cups oats - -### Grind up the nuts - -Throw the nuts into the food processor and grind them into a powder. Then throw -that powder into a bowl along with the seeds, coconuts, raisins, and oats, and -mix em good. - -I don't _completely_ grind up the nuts, instead leaving some chunks in it here -and there, but you do you. - -### Prepare the dates - -This is the harder part, and is what took me a couple tries to get right. The -best strategy I've found is to steam the dates a bit over a stove to soften -them. Then, about a cup at a time, you can throw them in the food processor and -turn them into a paste. You may have to add a little water if your processor is -having trouble. - -Once processed you can add the dates to the mix from before and stir it all up. -It'll end up looking something like cookie dough. Except unlike cookie dough -it's completely safe to eat and maybe sorta healthy. - -### Bake it, Finish it - -Put the dough stuff in a pan of some sort, flatten it out, and stick it in the -oven at like 250 or 300 for a few hours. You're trying to cook out the water you -added earlier when you steamed the dates, as well as whatever little moisture -the dates had in the first place. - -Once thoroughly baked you can stick the pan in the fridge to cool and keep, -and/or cut it up into individual bars. Keep in mind that the bars are super -filling and allow for pretty small portions. Wrap em in foil or plastic wrap and -take them to-go, or keep them around for a snack. Or both. Or whatever you want -to do, it's your food. - -### Cleanup - -Dates are simultaneously magical and the most annoying thing to work with, so -there's cleanup problems you may run into with them: - -Protip #1: When cleaning your processed date slime off of your cooking utensils -I'd recommend just letting them soak in water for a while. Dry-ish date slime -will stick to everything, while soaked date slime will come right off. - -Protip #2: Apparently if you want ants, dates are a great way to get ants. My -apartment has never had an ant problem until 3 hours after I made a batch of -these and didn't wipe down my counter enough. I'm still dealing with the ants. -Apparently there's enviromentally friendly ant poisons where the ants happily -carry the poison back into the nest and the whole nest eats it and dies. Which -feels kinda mean in some way, but is also pretty clever and they're just ants -anyway so fuck it. -- cgit v1.2.3