Erlang Answers - A Companion to Erlang Questions

SharingDataStructures.html

paul-erlanganswers@mineiro.com (Paul Mineiro) — Thu, 17 Sep 2009 17:34:59 GMT

Sharing Data Structures

Introduction
Converting an Existing Term
Sending a Term in a Message

Introduction

On the list recently, the question of ensuring maximal sharing of an Erlang term came up.

I've run into several cases where enforcing the sharing of data
resulted in a significant memory savings.  I'm talking about a
reduction in heap size from 60MB to under half that. By "enforcing the
sharing of data" I mean making sure that identical elements in a data
structure are actually referencing the same locations in memory.

This is easy to do in Erlang, because the compiler is very literal:

   fix_tuple({H, H}) -> {H, H};
   ...

That ensures that identical looking elements in the tuple are sharing
memory locations.  But there is absolutely no reason the compiler has
to do this.  It would be perfectly valid to optimize away the entire
function, just returning the original value.

Would any existing standard library functions make this nicer?  What I
really want is to have a gb_trees:insert function that returns
{NewTree, InsertedValue} where InsertedValue references existing data
(unless it wasn't already in the tree; in that case, InsertedValue is
exactly what I passed in).  Then I can happily use InsertedValue,
knowing data is being shared.

James

There were alot of responses: it's a very interesting thread.

Converting an Existing Term

The task here is to take an existing Erlang term and convert it into something which shares components, but is semantically equivalent (i.e., would compare equal via =:=). Bjorn offered a key insight

In Wings3D (which is an application that depends heavily on sharing),
I use a gb tree to keep track of values that I want to share.
I enter each term as both the key and the value and then I just do
gb trees:get/2 to retrieve the shared value.

Using this we can write a function to convert a term to a shared form.

share (Term) ->
  element (1, share (Term, dict:new ())).

share (Term, Dict) ->
  case dict:find (Term, Dict) of
    { ok, OrigTerm } ->
      { OrigTerm, Dict };
    error ->
      { NewTerm, NewDict } = share_copy (Term, Dict),
      { NewTerm, dict:store (NewTerm, NewTerm, NewDict) }
  end.

share_copy ([ H | T ], Dict) ->
  { NewH, NewDict } = share (H, Dict),
  { NewT, NewNewDict } = share (T, NewDict),
  { [ NewH | NewT ], NewNewDict };
share_copy (Term, Dict) when is_tuple (Term) ->
  share_copy (Term, Dict, size (Term));
share_copy (Term, Dict) ->
  { Term, Dict }.

share_copy (Tuple, Dict, N) when N > 0 ->
  { NewElement, NewDict } = share (element (N, Tuple), Dict),
  share_copy (setelement (N, Tuple, NewElement), NewDict, N - 1);
share_copy (Tuple, Dict, _) ->
  { Tuple, Dict }.

Basically we traverse the collection types (list, tuple) and share the components; and the sharing is done via a dict in the manner Bjorn outlines.

Note that for all Term, Term = share (Term) should be true, which makes this routine easy to test with QuickCheck.

Sending a Term in a Message

Even if a Term has a high degree of sharing within itself, this sharing is not currently preserved when the Term is sent in an Erlang message. Although one could send the Term and then postprocess the message with share/1 from above, this could lead to a large intermediate value. Therefore the strategy for sharing a term when sending in a message involves encoding the Term into a structure which has a high degree of sharing and which can be decoded into something equivalent to Term but with a high degree of sharing.

Tony Rogvall also posted a solution to this problem.

The encode is similar to the share routine, but replaces every Term with an index into a term table.

encode (Term) ->
  { _, _, _, Codec } = encode (Term, dict:new (), dict:new ()),
  list_to_tuple ([ X || { _, X } <- lists:sort (dict:to_list (Codec)) ]).

encode (Term, Dict, Codec) ->
  case dict:find (Term, Dict) of
    { ok, { Ref, OrigTerm } } ->
      { Ref, OrigTerm, Dict, Codec };
    error ->
      { NewTerm, NewDict, NewCodec } = encode_copy (Term, Dict, Codec),
      Ref = 1 + dict:size (NewDict),
      { Ref,
        NewTerm,
        dict:store (Term, { Ref, NewTerm }, NewDict),
        dict:store (Ref, NewTerm, NewCodec)
      }
  end.

encode_copy ([ H | T ], Dict, Codec) ->
  { HRef, _, NewDict, NewCodec } = encode (H, Dict, Codec),
  { TRef, _, NewNewDict, NewNewCodec } = encode (T, NewDict, NewCodec),
  { [ HRef | TRef ], NewNewDict, NewNewCodec };
encode_copy (Term, Dict, Codec) when is_tuple (Term) ->
  { ListTerm, NewDict, NewCodec } =
    encode_copy (tuple_to_list (Term), Dict, Codec),
  { { t, ListTerm }, NewDict, NewCodec };
encode_copy (Term, Dict, Codec) when is_integer (Term) ->
  { { i, Term }, Dict, Codec };
encode_copy (Term, Dict, Codec) ->
  { Term, Dict, Codec }.

The decode function starts with the last element of the term table (which is the term to be decoded), and expands each occurrence of a reference to the term table.

decode (Codec) ->
  decode (element (size (Codec), Codec), Codec).

decode ([ HRef | TRef ], Codec) when is_integer (HRef), is_integer (TRef) ->
  [ decode (HRef, Codec) | decode (TRef, Codec) ];
decode ({ t, Encoded }, Codec) ->
  list_to_tuple (decode (Encoded, Codec));
decode ({ i, Literal }, _Codec) when is_integer (Literal) ->
  Literal;
decode (Ref, Codec) when is_integer (Ref) ->
  decode (element (Ref, Codec), Codec);
decode (Literal, _Codec) ->
  Literal.

Here what some terms look like encoded:

11> hashcons:encode (lists:duplicate (5, wazzup)).                 
{wazzup,[],[1|2],[1|3],[1|4],[1|5],[1|6]}
12> hashcons:encode ([ a, [ a, b ], [ a, b, c ] ]).
{a,b,[],[2|3],[1|4],c,[6|3],[2|7],[1|8],[9|3],[5|10],[1|11]}

Again for all Term, Term = decode (encode (Term)) should be true, which makes this routine easy to test with QuickCheck.

mnesia/OrderedBy.html

paul-erlanganswers@mineiro.com (Paul Mineiro) — Mon, 27 Jul 2009 03:56:56 GMT

Mnesia Ordered By Queries

Table of Contents

Introduction
Inefficient General Solution
Efficient Solution: Primary Key
Efficient General Solution: Secondary Sorted Index

Introduction

Mnesia is not a relational database engine; it's better described as a distributed transactional key-value store. Relational databases do not have their feature set by accident, however, so periodically somebody asks the list about range queries:

Hi,

What's the simplest, most efficient way of expressing the following
sql query in mnesia:

"SELECT * FROM foo ORDER BY creation_date LIMIT 500,10"

?

Btw, I don't care about transactions.

Thanks,
Yariv

Asking for simultaneous simplicity and efficiency is certainly optimistic.

As with many complicated Mnesia problems, the solution involves doing manually what relational databases do automatically behind the scenes. Thus, if your application mostly consists of complicated relational access patterns, you should consider another database engine rather than Mnesia.

Inefficient General Solution

An inefficient general solution consists of doing a full table scan, accumulating the records into a tree, and reading out the result at the end of the scan. This is what a relational database engine will do for you behind the scenes assuming you have not indexed the column being ordered. If the number of records in the table is not that large and the query infrequent this can be an acceptable solution.

The mnesia:select/4 function can be used to extract records from a table according to a match specification. Match specifications are quite general; in this case, because all records are eligible (i.e., no WHERE clauses in the SQL) we will just select all records, but we will select 10 at a time to prevent exhausting available memory.

-module (testsort).
-export ([ limit/4 ]).

limit (Tab, Field, Offset, Number) ->
limit (get_field_number (Tab, Field),
         Offset,
         Number,
         mnesia:select (Tab,
                        [ { mnesia:table_info (Tab, wild_pattern), [], [ '$_' ] } ],
                        10,
                        read),
         gb_sets:empty ()).

get_offset ([ Field | _ ], Field, N) -> N;
get_offset ([ _ | T ], Field, N) -> get_offset (T, Field, N + 1).

get_field_number (Tab, Field) ->
get_offset (mnesia:table_info (Tab, attributes), Field, 2).

limit (_FieldNumber, Offset, Number, '$end_of_table', Tree) ->
Candidates = [ Record || { _, Record } <- gb_sets:to_list (Tree) ],
{ _, Rest } = safe_split (Offset, Candidates),
{ Result, _ } = safe_split (Number, Rest),
Result;
limit (FieldNumber, Offset, Number, { Results, Cont }, Tree) ->
NewTree =
    lists:foldl (fun (Record, AccTree) ->
                   Key = { element (FieldNumber, Record), Record },
                   gb_sets:add (Key, AccTree)
                 end,
                 Tree,
                 Results),

PrunedTree = prune_tree (NewTree, Offset + Number),

limit (FieldNumber,
         Offset,
         Number,
         mnesia:select (Cont),
         PrunedTree).

prune_tree (Tree, Max) ->
case gb_sets:size (Tree) > Max of
    true ->
      { _, NewTree } = gb_sets:take_largest (Tree),
      prune_tree (NewTree, Max);
    false ->
      Tree
end.

safe_split (N, L) when length (L) >= N ->
lists:split (N, L);
safe_split (_N, L) ->
{ L, [] }.

How it works:

limit/4 is the entry point. The SQL query in the original post would correspond to testsort:limit (foo, creation_date, 500, 10).
get_field_number/2 computes the column of the specified field in the specified table.
the initial mnesia:select/4 call says to select all records all columns 10 records at a time. depending upon your record size you can get a favorable space-time tradeoff by increasing the number of records fetched per select.
the select results are inserted into a tree. the key for the tree is a tuple whose first element is the field being sorted, so that the keys are in the desired sort order (the comparison function here is Erlang term order).
via prune_tree/2, the temporary tree is sized so that it contains at most (Offset + Number) entries.
at the end of the full table scan, the first Offset results are discarded and then the next Number results are returned.

Efficient Solution: Primary Key

Efficiency can be significantly improved if the column in question is either the primary key or a prefix of the primary key, and the table type is ordered_set. Relational database engines recognize this condition for you automatically during query planning and choose an efficient method for computing the result similar to what we shall do.

We will again use mnesia:select/4, but this time to seek to the first desired result, and then we will read the answer directly. If the record is defined as

-record (foo, { creation_date, something, something_else }).

then creation_date is the primary key, so we will select in table order, as in this code listing.

-module (testsort2).
-export ([ limit/3 ]).

limit (Tab, Offset, Number) ->
seek (Offset,
        Number,
        mnesia:select (Tab,
                       [ { mnesia:table_info (Tab, wild_pattern), [], [ '$_' ] } ],
                       10,
                       read)).

seek (_Offset, _Number, '$end_of_table') ->
[];
seek (Offset, Number, X) when Offset =< 0 ->
read (Number, X, []);
seek (Offset, Number, { Results, Cont }) ->
NumResults = length (Results),
case Offset > NumResults of
    true ->
      seek (Offset - NumResults, Number, mnesia:select (Cont));
    false ->
      { _, DontDrop } = lists:split (Offset, Results),
      Keep = lists:sublist (DontDrop, Number),
      read (Number - length (Keep), mnesia:select (Cont), [ Keep ])
end.

read (Number, _, Acc) when Number =< 0 ->
lists:foldl (fun erlang:'++'/2, [], Acc);
read (_Number, '$end_of_table', Acc) ->
lists:foldl (fun erlang:'++'/2, [], Acc);
read (Number, { Results, Cont }, Acc) ->
NumResults = length (Results),
case Number > NumResults of
    true ->
      read (Number - NumResults, mnesia:select (Cont), [ Results | Acc ]);
    false ->
      { Keep, _ } = lists:split (Number, Results),
      lists:foldl (fun erlang:'++'/2, Keep, Acc)
end.

Here's how it works:

limit/3 is the entry point. It assumes the ordering desired is by the primary key. The SQL in the original post would become limit (foo, 500, 10).
the initial mnesia:select/4 call says to select all records all columns 10 records at a time. depending upon your record size you can get a favorable space-time tradeoff by increasing the number of records fetched per select.
the seek/3 consumes the output of the select until the desired offset is reached.
the read/3 consumes the output of the select until the desired limit is reached.

We can use this routine even if creation_date is only a prefix of the primary key, i.e., if it were the leading element of a tuple or list that is used as the primary key. That is because Erlang term order for tuples and lists will compare the first element first, and so will sort in the desired fashion.

This solution is linear in (Offset + Count). If the equivalent SQL query is slightly modified to

SELECT * FROM foo WHERE creation_date > X ORDER BY creation_date LIMIT 10

then the initial mnesia:select/4 can be made more efficient with a guard that constrains the primary key, e.g.,

mnesia:select (foo, [ { #foo { creation_date = '$1', _ = '_' }, [ { '>', '$1', X } ], [ '$_' ] } ], 10, read).

With this mnesia:select/4 initial call, the seek/3 portion of the processing can be skipped, and only the read/3 portion need be executed. Update: actually it looks like ets does not optimize this condition, although tcerl does. However for an ordered_set table ets:next/2 will return the next key in the table even if the key supplied as argument is not in the table, so this could be exploited to walk an ets table starting at a particular lower bound. Also, if the Offset in the limit query is resulting from continuing a previous query (e.g., paging through results in a search engine), then an alternate strategy is to serialize the select continuation, repair it (via ets:repair_continuation/2), and reuse via mnesia:select/1, which will seek to the next key in the table similar to ets:next/2. mnesia:select/1 will outperform repeated calls to ets:next/2 as Count increases, so generally the former is preferred.

Efficient General Solution: Secondary Sorted Index

If the column being sorted is not (a prefix of) the primary key than efficient operation will require creating a secondary sorted index. This is done for you automatically by a relational database engine when you index the column appropriately. Mnesia's built-in indices are not sorted so you will have to do this by creating another table. For example if the record is

-record (foo, { id, stuff, creation_date }).

then assuming that foo is of type set or ordered_set, you could make an ordered_set table with records

-record (foo_cd_index, { creation_date_id_tuple, void = [] }).

The primary keys of foo_cd_index will be tuples of the form { creation_date, id }, and we do not care about the void value but mnesia requires at least 2 columns, so we populate with nil (which has a small external format representation). When we insert an element F into foo, we insert a corresponding element

#foo_cd_index{ creation_date_id_tuple = { F#foo.creation_date, F#foo.id } }

into the index table. Once the secondary index has been constructed, we can use the primary key techniques from the previous section on the secondary table, extract the identifiers, and then query the primary table to extract the records (if only the list of identifiers is to be returned, the join can be skipped, yet another condition that a typical relational database engine recognizes for you under the hood).

If foo is of type bag, we cannot make an "ordered_bag" table for the index because mnesia does not support such a type; however we can achieve something similar with records

-record (foo_cd_index, { creation_date_id_stuff, void = [] }).

Essentially we have duplicated the record but reordered the fields. When we insert an element F into foo, we insert a corresponding element

#foo_cd_index{ creation_id_stuff = { F#foo.creation_date, F#foo.id, F#foo.stuff } }

This solution is space intensive because the bag table type does not allow us to refer to an element by a subset of its attributes. However, once the secondary index table has been created we can use the primary key solution on the secondary table to extract the desired records directly, without having to join against the primary table.

Counters.html

paul-erlanganswers@mineiro.com (Paul Mineiro) — Sat, 18 Jul 2009 00:36:41 GMT

Introduction

Erlang, as a functional language, strives for a side-effect free sequential syntax. Sometimes side-effects are desirable, the classic example being the collection of serving statistics.

I want to add counters to my gen_tcp implementation to track total
number of connections made, total number of requests serviced, total
number of bytes transfered, etc.
I need to have numbers like this for production monitoring. In python
or java I would just have a singleton class that had these counters
with thread safe increment/decrement methods. How would I get this
same behavior using Erlang?

Slower but Ideologically Pure

Although Erlang strives for a side-effect free sequential syntax, it can generally handle what are normally considered side-effects via the concurrent syntax. In particular, by sending a message to a process which is in a tail-recursive loop, you can change the arguments to the tail-recursive call. This is analogous to changing the state of an object via a method call, but in a manner acceptable to functional programmers. For example, given a process executing the tail-recursive loop

loop (on) -> receive _ -> loop (off) end;
loop (off) -> receive _ -> loop (on) end.

sending a message to this process would cause the argument to toggle between on and off. This technique will be the basis for our counter.

Generally, except for pedagogical fun, it is not a good idea to create your own loops to implement persistent processes. Rather, you should use one of the standard OTP implementations, which at their core consist of a loop like the one above, but with many failure cases and operational capabilities built-in. Here, we will use gen_server.

-module (counter).
-export ([ new/0,
           increment/2,
           read/2,
           free/1 ]).
-behaviour (gen_server).
-export ([ init/1,
           handle_call/3,
           handle_cast/2,
           handle_info/2,
           terminate/2,
           code_change/3 ]).

new () ->
gen_server:start_link (?MODULE, [], []).

increment (Counter, Keys) when is_list (Keys) ->
gen_server:cast (Counter, { increment, Keys }).

read (Counter, Keys) when is_list (Keys) ->
gen_server:call (Counter, { read, Keys }).

free (Counter) ->
gen_server:cast (Counter, stop).

init (_) ->
{ ok, dict:new () }.

handle_call ({ read, Keys }, _From, State) ->
{ reply, [ read_key (K, State) || K <- Keys ], State };
handle_call (_Msg, _From, State) ->
{ noreply, State }.

handle_cast ({ increment, Keys }, State) ->
{ noreply, lists:foldl (fun increment_key/2, State, Keys) };
handle_cast (stop, State) ->
{ stop, normal, State };
handle_cast (_Msg, State) ->
{ noreply, State }.

handle_info (_Info, State) ->
{ noreply, State }.

terminate (_Reason, _State) ->
ok.

code_change (_OldVsn, State, _Extra) ->
{ ok, State }.

read_key (Key, Dict) ->
case dict:find (Key, Dict) of
    { ok, Value } -> Value;
    error -> 0
end.

increment_key (Key, Dict) ->
dict:store (Key, read_key (Key, Dict) + 1, Dict).

And an example usage in the shell

% erl
Erlang (BEAM) emulator version 5.6.5 [source] [async-threads:0] [kernel-poll:false]

Eshell V5.6.5 (abort with ^G)
1> f (), { ok, Counter } = counter:new (), A = now (), [ counter:increment (Counter, [ test ]) || _ <- lists:seq (1, 100000) ], B = now (), Final = counter:read (Counter, [test]), counter:free (Counter), { timer:now_diff (B, A), Final }.
{1166675,[100000]}

Here's how it works:

A new counter is constructed via new/0. This results in a spawned gen_server process which is linked to the caller.
- Analysis of init/1 indicates a dictionary is being used as the process state.
Counters are incremented via the increment/2 call, which takes a counter id and a list of keys whose counters are to be incremented. increment/2 sends a message to the counter process and then returns immediately without waiting for a reply.
- This message is processed in handle_cast/2 which calls increment_key/2 for each key; here we can see new keys are initialized with the default value of 0.
Counters are read via the read/2 call, which takes a counter id and a list of keys whose counters are to be read. read/2 sends a message to the counter process and then waits until the counter process replies.
- This message is processed in handle_call/3.
The counter process is reclaimed via free/1. It will also automatically exit if the creating process exits, due to the use of start_link.

Faster

The above counter implementation, although simple, is analogous to how more complicated stateful computations are encapsulated in Erlang. Because of practical concerns such as messaging overhead, however, Erlang design strives for "small messages, large computations". The counter implementation above does not achieve this ideal (although, allowing for multiple keys to be incremented with a single call is a step in the right direction).

Erlang is a practical language, and there are some elements of the sequential syntax which are not side-effect free. In particular ets tables provide destructive operations of a datastore which can be used to implement an efficient counter. In order to avoid resource leaks, ets tables have to be owned by a process, so we will continue to use gen_server to represent our ets table, but the increment and read calls will not involve messaging the process. The resulting API is the same as with the previous counter.

-module (counter2).
-export ([ new/0,
           increment/2,
           read/2,
           free/1 ]).
-behaviour (gen_server).
-export ([ init/1,
           handle_call/3,
           handle_cast/2,
           handle_info/2,
           terminate/2,
           code_change/3 ]).

new () ->
{ ok, Pid } = gen_server:start_link (?MODULE, [], []),
Tab = gen_server:call (Pid, get_tab),
{ ok, { Pid, Tab } }.

increment ({ _, Tab }, Keys) when is_list (Keys) ->
lists:foldl (fun increment_key/2, Tab, Keys),
ok.

read ({ _, Tab }, Keys) when is_list (Keys) ->
[ read_key (K, Tab) || K <- Keys ].

free ({ Pid, _ }) ->
gen_server:cast (Pid, stop).

init (_) ->
Tab = ets:new (?MODULE, [ public, set ]),
% if you are using R13 or above, use this line instead
% Tab = ets:new (?MODULE, [ public, set, { write_concurrency, true } ]),
{ ok, Tab }.

handle_call (get_tab, _From, State) ->
{ reply, State, State };
handle_call (_Msg, _From, State) ->
{ noreply, State }.

handle_cast (stop, State) ->
{ stop, normal, State };
handle_cast (_Msg, State) ->
{ noreply, State }.

handle_info (_Info, State) ->
{ noreply, State }.

terminate (_Reason, _State) ->
ok.

code_change (_OldVsn, State, _Extra) ->
{ ok, State }.

read_key (Key, Tab) ->
case ets:lookup (Tab, Key) of
    [ { _, Value } ] -> Value;
    [] -> 0
end.

increment_key (Key, Tab) ->
try ets:update_counter (Tab, Key, 1)
catch
    _ : _ ->
      case ets:insert_new (Tab, { Key, 1 }) of
        true ->
          ok;
        false ->
          ets:update_counter (Tab, Key, 1)
      end
end,
Tab.

And an example use in the shell:

% erl
Erlang (BEAM) emulator version 5.6.5 [source] [async-threads:0] [kernel-poll:false]

Eshell V5.6.5 (abort with ^G)
1> f (), { ok, Counter } = counter2:new (), A = now (), [ counter2:increment (Counter, [ test ]) || _ <- lists:seq (1, 100000) ], B = now (), Final = counter2:read (Counter, [test]), counter2:free (Counter), { timer:now_diff (B, A), Final }.
{906200,[100000]}

That may not seem much faster (20% wall clock), but essentially no messages are generated in the ets-based version. I worked on a large system with a sophisticated statistics gathering system which heavily leveraged Erlang messaging, analogous the first counter implementation above. After significant work optimizing the main application operations, profiling indicated the statistics process (consuming the message queue) had the highest CPU utilization. Presumably, using ets for node-local collection and then messaging to assemble statistics across the cluster would have further improved overall system performance.

Here's how it works:

A new counter is constructed via new/0. This actually creates a public ets table which will contain the counters, plus a gen_server process which will own the ets table.
- Except for a single message to get the table identifier from the process, no messages will be sent to the owning process during the lifetime of the counter (until free/1 is called).
Counters are incremented via the increment/2 call, which takes a counter id and a list of keys whose counters are to be incremented. increment/2 loops over the supplied keys and increments each one.
- The increment_key/2 function is now significantly more complicated than in the previous implementation. Because the ets table will be accessed concurrently, we have to be careful. The complexities are:
  1. You cannot update a counter record that does not exist.
  2. Two simultaneous inserts of the initial counter record, if not guarded against, will cause a loss in one of the increments.
  3. Most of the time we will be updating a counter record that does exist, so we should optimistically try that first for efficiency purposes.
- Is it good to be forced to think about all these complications regarding concurrent access? No, so take no pride in it. Notice the first implementation didn't have any of this complexity to it; we handled one message at a time, and we used an immutable data structure to hold state. This is a very simple example (a concurrently incremented counter), and it is still easy to get it wrong. Erlang was designed to help you avoid the need to reason about concurrent access to mutable data structures. If you find yourself doing that alot, you are not thinking in the Erlang way.
Counters are read via the read/2 call, which takes a counter id and a list of keys whose counters are to be read. This reads from the ets table directly, without messaging the owning process.
The counter process is reclaimed via free/1. It will also automatically exit if the creating process exits, due to the use of start_link. Note the Erlang VM will delete the ets table when the owning (counter) process exists.

index.html

paul-erlanganswers@mineiro.com (Paul Mineiro) — Fri, 17 Jul 2009 20:19:18 GMT

Welcome

This is a site devoted to providing color commentary for erlang questions. You can peruse the recently updated content indicated in the left bar, or you can check out the index of all content.

I am also working on a searchable socialized Erlang Questions archive. I'm slowly populating it with messages so you may or may not find it useful right now.

Naturally the site is written entirely in Erlang. If you are curious how it is put together, I provide some information.

mnesia/DistributedHelloWorld.html

paul-erlanganswers@mineiro.com (Paul Mineiro) — Tue, 07 Jul 2009 17:15:08 GMT

Mnesia Distributed Hello World

Introduction
Hello World
Problem Solved
Dynamic Maintenance
- Schema
- Other Tables

Introduction

One of the simultaneously coolest and most challenging features of Mnesia is distributed operation. Before even tackling the complexities of managing failure cases, some developers have trouble starting it up, leading to solicitations for help like the following:

Hi
I've recently started learning erlang/mnesia and need help setting up mnesia
on two nodes. Here's the series of steps (on same host):
$cd ~/test/foo
$erl -sname foo -setcookie chip_cookie

1. mnesia:create_schema([node()]).
2. mnesia:start().
3. rd(person, {name,age}).
4.
mnesia:create_table(person,[{attributes,record_info(fields,person)},{disc_copies,[node()]}]).
5. mnesia:dirty_write(#person{name="george", age=30}).

# in another window, on same host:
$cd ~/test/bar
$erl -sname bar -setcookie chip_cookie
1> mnesia:start().
#back on foo node:
net_adm:ping('foo@*hostname*').
*pong*
mnesia:add_table_copy(schema, 'bar@*hostname*', disc_copies).
*{aborted,{badarg,schema,disc_copies}} <--- WHY DOES THIS FAIL?*
mnesia:add_table_copy(schema, 'bar@*hostname*', ram_copies).
*{atomic,ok}*
mnesia:add_table_copy(person, 'bar@*hostname*', disc_copies).
*{atomic,ok}*
*# back on node bar*
mnesia:info().
*It doesn't show the 'person' table that was copied from foo. Why is that?*
How can I add more nodes to an existing mnesia database which was created
with only one node ie. mnesia:create_schema([node()]).
Thanks
--
Yellowfish Technologies Inc
http://www.yellowfish.biz
praveen.ray@yellowfish.biz

It happens alot in Erlang that the error messages only make sense if you know alot about Erlang already, as is the case above.

Hello World

First, let's do a distributed hello world, and then we'll be in a better position to understand what went wrong for the poster. You can follow along by typing in these commands into two OS shells, which I identify as shell1 and shell2.

shell1% erl -name one -setcookie yum
shell2% erl -name two -setcookie yum

At this point you have two Erlang shells started. For this next bit, everything we will type will be inside the Erlang shells, which I identify as one@ted-teds-computer.local and two@ted-teds-computer.local. In what follows you should substitute ted-teds-computer.local with your hostname as identified by the Erlang shell.

(one@ted-teds-computer.local)1> mnesia:start ().
ok
(two@ted-teds-computer.local)1> mnesia:start ().
ok
(one@ted-teds-computer.local)2> mnesia:change_config (extra_db_nodes, [ 'two@ted-teds-computer.local' ]).
{ok,['two@ted-teds-computer.local']}
(one@ted-teds-computer.local)3> mnesia:system_info (running_db_nodes).
['two@ted-teds-computer.local', 'one@ted-teds-computer.local']

At this point you have a distributed Mnesia system running on the two nodes. Let's dissect the steps.

Mnesia is started on both nodes via mnesia:start/0.
- Since this is a fresh start of Mnesia on two brand new nodes, each node creates a ram-resident schema. To make these nodes have persistent databases the schema must be converted to disc-resident. Once converted to disc-resident, this will be remembered across node restarts.
On (either) one of the nodes Mnesia is told there is an additional node, via mnesia:change_config/2. Behind the scenes, it tries to contact the Mnesia on the other node and merge the schemas. Assuming the schemas are compatible, a unified schema containing all the nodes is created and installed on all the nodes.
- Newly created ram-resident schemas are always considered consistent with any other schema, in order to facilitate reintroduction of stateless nodes. Disc-resident schemas that were part of a distributed schema but were out of contact for a while, e.g. due to node failure, will also be made consistent if possible. However, two persistent schemas created in isolation cannot be merged in this fashion; it's really intended for building up a distributed schema starting with a single node.

So far so good. To persist the situation so that it survives restart we need to convert the schemas to disc-resident.

(one@ted-teds-computer.local)4> mnesia:change_table_copy_type(schema, node(), disc_copies).
{atomic,ok}
(two@ted-teds-computer.local)2> mnesia:change_table_copy_type(schema, node(), disc_copies).
{atomic,ok}

At this point (but not before) you should see directories on your disk where you started the Erlang nodes.

shell1% ls -l Mnesia.*
Mnesia.one@ted-teds-computer.local:
total 40
-rw-r--r--   1 pmineiro admin   170 Jun 26 14:43 DECISION_TAB.LOG
-rw-r--r--   1 pmineiro admin   195 Jun 26 14:43 LATEST.LOG
-rw-r--r--   1 pmineiro admin 8824 Jun 26 14:43 schema.DAT

Mnesia.two@ted-teds-computer.local:
total 40
-rw-r--r--   1 pmineiro admin   170 Jun 26 14:43 DECISION_TAB.LOG
-rw-r--r--   1 pmineiro admin   195 Jun 26 14:43 LATEST.LOG
-rw-r--r--   1 pmineiro admin 8824 Jun 26 14:43 schema.DAT

Only at this point, with a persistent on-disc database, can you succesfully create disc-based table copies.

(one@ted-teds-computer.local)5> mnesia:create_table (foo, [ { disc_copies, mnesia:system_info (running_db_nodes) } ]).
{atomic,ok}
(one@ted-teds-computer.local)6> mnesia:dirty_write ({ foo, hello, world }).
ok
(two@ted-teds-computer.local)3> mnesia:dirty_read (foo, hello).
[{foo,hello,world}]

The data was written on the first node and read on the second. Cool!

Problem Solved

Now you have enough intuition that I can explain what was wrong with the original poster's sequence.

He creates a disc-resident schema on the node foo via mnesia:create_schema/1.
He starts mnesia on the node foo via mnesia:start/0. Node foo is now running a disc-resident schema.
He creates a disc-resident table called person on node foo via mnesia:create_table/2, and writes a record via mnesia:dirty_write/1.
He creates a ram-resident schema on the node bar via mnesia:start/0.
- So far so good, but now the trouble starts.
He tries to add a disc-resident schema on the node bar via mnesia:add_table_copy/3. This fails because he already has a table copy of schema on the node bar which is ram-resident. He would need to call mnesia:change_table_copy_type/3 instead to change the schema to disc-resident.
He tries to add a disc-resident copy of the person table on node bar via mnesia:add_table_copy/3, which would work, except that adding a disc-resident table copy to a node with a ram-resident schema is not allowed; first the schema must be made disc-resident.

For pedagogical fun, see if you can modify the sequence in the original message to cause the person table to be replicated disc-based on both nodes.

Dynamic Maintenance

Schema

In general if one wants to create or update a distributed Mnesia configuration, the sequence of operations is:

mnesia:start/0
- If this is the first time starting mnesia for this node, a fresh ram-based schema will be created, which can be merged with any existing schema. If this is not the first time starting mnesia for this node, any previously created disc-based schema will be loaded, otherwise a fresh ram-based schema will be created.
mnesia:change_config (extra_db_nodes, NodeList)
- In theory this can be done at any time in order to add additional nodes to the mnesia distributed schema, assuming the additional nodes have compatible schemas. In practice, the best way to ensure a compatible schema is to join the distributed configuration as a fresh ram-based schema which is guaranteed to merge with any existing schema.
mnesia:change_table_copy_type (schema, node (), disc_copies)
- This will change the local mnesia schema type from ram-based to disc-based.

Schemafinder is a project on Google Code which automates these steps of maintaining a distributed mnesia configuration, working in conjunction with a nodefinder strategy to discover other Erlang nodes. Schemafinder tries to avoid extra work by not calling mnesia:change_config/2 if the node list has not changed, and not calling mnesia:change_table_copy_type/3 if the schema is already disc-based. Although these functions are idempotent, they acquire a schema transaction in order to run which can introduce latency when a cluster is under extreme load. You can inspect the relevant bit of code for inspiration.

In the event you want to remove a node from the schema, you can use mnesia:del_table_copy/2 on the schema table.

Other Tables

For other tables, tables can be initialized with a node list using the ram_copies, disc_copies, and/or disc_only_copies options to mnesia:create_table/2. In addition an existing table can have additional copies placed via mnesia:add_table_copy/3, and removed via mnesia:del_table_copy/2. Note a node can only have one copy of a table, so if you want to change the type of a table at a node use mnesia:change_table_copy_type/3. Continuing with the above example:

(one@ted-teds-computer.local)7> mnesia:create_table (bar, [ { ram_copies, [ node () ] } ]).
{atomic,ok}
(two@ted-teds-computer.local)4> mnesia:table_info (bar, active_replicas).
['one@ted-teds-computer.local']
(two@ted-teds-computer.local)5> mnesia:add_table_copy (bar, node (), disc_copies).
{atomic,ok}
(two@ted-teds-computer.local)6> mnesia:table_info (bar, active_replicas).
['two@ted-teds-computer.local',
'one@ted-teds-computer.local']
(two@ted-teds-computer.local)7> mnesia:add_table_copy (bar, node (), ram_copies).
{aborted,{already_exists,bar,'two@ted-teds-computer.local'}}
(two@ted-teds-computer.local)8> mnesia:change_table_copy_type (bar, node (), ram_copies).
{atomic,ok}

The sequence is as follows:

Initially table bar is created with a single ram copy on node one.
A disc copy is added to node two.
- Note there is no requirement that the copy type be the same across the nodes.
An attempt to add another copy of the table to node two fails.
The copy on node two is changed from disc copies to ram copies.

mnesia/SchemaFree.html

paul-erlanganswers@mineiro.com (Paul Mineiro) — Fri, 03 Jul 2009 00:25:25 GMT

Mnesia Schema Free Operation

Introduction

Most programmers are aware of the distinction between statically typed and dynamically typed programming languages, with respective advantages and disadvantages. Analogously, databases can be schema driven or schema-free. All relational database engines that I am familiar with are schema driven, while recent champions of the schema-free approach include CouchDB and SimpleDB. A schema-free database can simplify issues around the evolution of the database-driven application, in exchange for more work from the application developer (and more opportunities to introduce defects).

Since the Erlang ethos embraces continuous application upgrades and operational simplicity, it is natural to ask whether Mnesia can be used in an essentially schema-free way. The answer is yes. Futhermore, relational database engines utilize the schema for validation, consistency, indexing, and query planning, but Mnesia's built-in capabilities in this regard are primitive that the cost of forgoing them is minimal (typically, the application programmer does these things manually). This, plus the ability to store an arbitrary Erlang term in an Mnesia table, leads to a natural way to use Mnesia in a disciplined but essentially schema-free manner.

The Strategy

An approach I've taken successfully on large projects in the past is as follows:

Mnesia tables require a schema, but the table is created with a trivial initial specification and never changed over the lifetime of the application.
Records in the table consist of a key (Mnesia requirement) and an additional record which is coupled with an API for manipulation.
As the application evolves, the implementation term changes for newly created database records, and the application interprets old implementation terms to the extent possible.

An example is best, so let's do one. Our database driven application will utilize a table called notes to keep web-sticky notes.

-record (note, { id, impl }).

mnesia:create_table (note, [ { attributes, record_info (fields, note) } ]).

So far so good. Initially our note will have an id and an owner.

-module (notes).
-export ([ make_note/2,
           get_id/1,
           get_owner/1,
           set_id/2,
           set_owner/2 ]).

-include ("notes.hrl").

-record (notes_impl, { owner }).

make_note (Id, Owner) ->
#note { id = Id,
          impl = #notes_impl { owner = Owner }
}.

get_id (#note { id = Id }) ->
Id.

get_owner (#note { impl = #notes_impl { owner = Owner } }) ->
Owner.

set_id (Note = #note{}, Id) ->
Note#note { id = Id }.

set_owner (Note = #note { impl = #notes_impl {} }, Owner) ->
Note#note { impl = #notes_impl { owner = Owner } }.

The declaration of #notes_impl{} is localized to the notes module, and by convention any access or mutation of a note is done exclusively via the functions in the notes module.

Well our application happily exists for a while persisting notes to the data store. Finally we get a feature request that our notes contain some content in addition to an owner. Now we are going to make the change without changing the schema, by changing the notes module.

-module (notes).
-export ([ make_note/3,
           get_id/1,
           get_owner/1,
           get_contents/1,
           set_id/2,
           set_owner/2,
           set_contents/2 ]).

-include ("notes.hrl").

-record (notes_impl, { owner }). % deprecated
-record (notes_implv2, { owner, contents="" }).

make_note (Id, Owner, Contents) ->
#note { id = Id,
          impl = #notes_implv2 { owner = Owner, contents = Contents }
}.

get_id (#note { id = Id }) ->
Id.

get_owner (#note { impl = #notes_implv2 { owner = Owner } }) ->
Owner;
get_owner (Note) ->
get_owner (convert_old (Note)).

get_contents (#note { impl = #notes_implv2 { contents = Contents } }) ->
Contents;
get_contents (Note) ->
get_contents (convert_old (Note)).

set_id (Note = #note{}, Id) ->
Note#note { id = Id }.

set_owner (Note = #note { impl = Impl = #notes_implv2 {} }, Owner) ->
Note#note { impl = Impl#notes_implv2 { owner = Owner } };
set_owner (Note, Owner) ->
set_owner (convert_old (Note), Owner).

set_contents (Note = #note { impl = Impl = #notes_implv2 {} }, Contents) ->
Note#note { impl = Impl#notes_implv2 { contents = Contents } };
set_contents (Note, Contents) ->
set_contents (convert_old (Note), Contents).

%%% Private

convert_old (Note = #note { impl = #notes_impl { owner = Owner } }) ->
Note#note { impl = #notes_implv2 { owner = Owner } }.

The changes can be summarized thusly:

A new implementation record (#notes_implv2{}) containing the new field (contents) is introduced.
The constructor is modified to return the latest implementation type.
The accessors and mutators are modified to pattern match on the latest implementation type; and to otherwise attempt to convert an old implementation to the latest implementation and try again.
- I like to centralize all the "backwards compatibility" logic into a single function like convert_old/1 for maintainability.

In practice the database will consist of a mixture of the latest and older implementation records, with individual records being migrated when mutated and persisted. In this case there is a perfectly reasonable interpretation of old records so this is not a problem. Sometimes this is not possible. In such cases I would suggest doing an "unreasonable" interpretation of old records, which is designed to operate only transiently, while the database is incrementally transformed to the latest implementation record (e.g., using an expensive one-time operation which joins against or precomputes from another data source).

Pros and Cons

There's no free lunch. Let's enumerate some of the disadvantages:

We've exchanged record syntax (e.g., Note#note.contents) for function calls (e.g., notes:get_contents (Note)). It's (probably irrelevantly) slower and more code maintenance, although fancy use of parse-transforms might be able to mitigate both of these problems.
- The backwards compatibility mapping is an interesting source of defects and good testing strategies are required to cover all the cases.
We can't use Mnesia's built-in indexing capabilities on the "hidden columns". In my experience this is totally moot, since I always end up making my own indices (e.g., functional indices, ordered indices, composite column indices, etc).
QLC usage is also frustrated. Again in my experience this is totally moot since I tend to manually query plan my joins in Mnesia.
Nice-to-haves like mnesia:dirty_update_counter/3 are unavailable. In my opinion this is a real pain point, but a hybrid approach can admit this.

So why do it? There is one big advantage:

The application and the datastore are now loosely coupled, rather than strongly coupled. Therefore, synchronization requirements between the two are greatly mitigated.

What this means in practice is, you can:

Launch a software change to an entire cluster a few boxes at a time, without worry.
Continue to operate your datastore with no delays or performance degradations during launch, and (if necessary) migrate the data asynchronously using a background process (e.g., consuming only spare capacity).

In my experience the advantages outweigh the disadvantages. YMMV.

Final Note

It is possible to take a hybrid approach, with records that have some columns represented explicitly and part of the schema, and other columns represented implicitly via an implementation member as indicated here. This can be a way to instrument an application for flexibility to future changes.

mnesia/SchemaMaintenance.html

paul-erlanganswers@mineiro.com (Paul Mineiro) — Thu, 02 Jul 2009 23:20:14 GMT

Mnesia Schema Maintenance

Introduction
Basics: Making Sure Tables are There
Advanced: Schema Migrations

Introduction

Any database driven application faces the problem of initialization and maintenance of the data store in conjunction with the rest of the application, and Mnesia driven applications are no exception. Consequently the following type of inquiry is periodically directed to the list

Hi all,

I have a question about how folks bootstrap an OTP application that
depends on mnesia. Consider an OTP application foo that uses mnesia.
Since mnesia is specified in the needed applications list, mnesia must
be started before you start foo.

For the first run of foo, one needs to call mnesia:create_schema/1
_before_ mnesia is started.

I'd like to be able to start foo on a clean system and have the schema
created if needed, but don't see a way to handle this. I suspect that
I need to adjust my expectations :-)

Is there a recommended way to handle mnesia initialization? Is the
standard practice to create the schema outside of the application
start up flow or am I missing a way to handle this as part of foo's
application initialization?

Thanks,

+ seth

Digging into the thread there are actually two questions here:

How to initialize and maintain the (distributed) schema.
How to initialize and maintain application specific tables.

The first question was answered in another article Mnesia Distributed Hello World, so I'll focus on the second question.

Basics: Making Sure Tables are There

My favorite solution is to have a gen_server in the application supervision tree which owns the schema, and I use this strategy for erlanganswers.com. The init callback for the gen_server owning the schema for this site is

init ([]) ->
ensure_schema (),

{ ok, #statev4 { backup = none } }.

All the heavy lifting is in the ensure_schema/0 function. Note: if you adapt this code for your own purposes, you will find that unless you are using mnesiaex the calls mentioning external_copies will fail, since vanilla mnesia lacks the concept.

ensure_schema () ->
case fast_change_table_copy_type (schema, node (), disc_copies) of
    { atomic, ok } -> ok;
    { aborted, { already_exists, schema, _, disc_copies } } -> ok
end,

ensure_table (mcedoc,
                [ { attributes, record_info (fields, mcedoc) },
                  { type, { external, ordered_set, tcbdbtab } },
                  { external_copies, [ node () ] },
                  { user_properties, [
                    { deflate, true },
                    { async_write, true },
                    { bucket_array_size, 101 },
                    { leaf_node_cache, 1 },
                    { nonleaf_node_cache, 1 },
                    { leaf_members, 256 },
                    { non_leaf_members, 512 }
                  ] }
                ]),

maybe_transform_mcedoc (),

ensure_table (mcedoctime,
                [ { attributes, record_info (fields, mcedoctime) },
                  { type, { external, ordered_set, tcbdbtab } },
                  { external_copies, [ node () ] },
                  { user_properties, [
                    { deflate, true },
                    { async_write, true },
                    { bucket_array_size, 101 },
                    { leaf_node_cache, 1 },
                    { nonleaf_node_cache, 1 },
                    { leaf_members, 256 },
                    { non_leaf_members, 512 }
                  ] }
                ]),

ensure_table (mcecomment,
                [ { attributes, record_info (fields, mcecomment) },
                  { type, { external, ordered_set, tcbdbtab } },
                  { external_copies, [ node () ] },
                  { user_properties, [
                    { deflate, true },
                    { async_write, true },
                    { bucket_array_size, 101 },
                    { leaf_node_cache, 1 },
                    { nonleaf_node_cache, 1 },
                    { leaf_members, 256 },
                    { non_leaf_members, 512 }
                  ] }
                ]),

ok.

ensure_table (TableName, TabDef) ->
Result = case fast_create_table (TableName, TabDef) of
    { atomic, ok } -> ok;
    { aborted, { already_exists, _ } } -> ok;
    { aborted, { combine_error, _, _ } } -> ok % wtf: why not already_exists?
end,
ok = mnesia:wait_for_tables ([ TableName ], infinity),
ok = mnesia:wait_for_tables ([ frag_table_name (TableName, N)
                                 || N <- lists:seq (1, num_frags (TableName)),
                                    N > 1 ],
                               infinity),
Result.

fast_change_table_copy_type (TableName, Node, CopyType) ->
try { lists:member (Node, used_nodes (TableName)),
        lists:member (Node, used_nodes (TableName, CopyType)) } of
    { true, true } ->
      { aborted, { already_exists, TableName, Node, CopyType } };
    { true, false } ->
      mnesia:change_table_copy_type (TableName, Node, CopyType);
    { false, _ } ->
      { aborted, { no_exists, TableName, Node } }
catch
    _ : _ ->
      { aborted, { no_exists, TableName } }
end.

fast_create_table (TableName, TabDef) ->
try mnesia:table_info (TableName, type),
      { aborted, { already_exists, TableName } }
catch
    _ : _ ->
      mnesia:create_table (TableName, TabDef)
end.

frag_table_name (TableName, 1) -> TableName;
frag_table_name (TableName, FragNum) when FragNum > 1 ->
list_to_atom (atom_to_list (TableName) ++
                "_frag" ++
                integer_to_list (FragNum)).

maybe_transform_mcedoc () ->
case mnesia:table_info (mcedoc, attributes) =:=
       record_info (fields, mcedoc) of
    true ->
      ok;
    false ->
      transform_mcedoc ()
end.

num_frags (TableName) ->
FragProps = mnesia:table_info (TableName, frag_properties),
case lists:keysearch (n_fragments, 1, FragProps) of
    { value, { n_fragments, NFrags } } -> NFrags;
    _ -> 1
end.

transform_mcedoc () ->
{ atomic, ok } =
    mnesia:transform_table (mcedoc,
                            fun ({ mcedoc, PathTime, Contents }) ->
                              #mcedoc { path_time = PathTime,
                                        contents = Contents,
                                        draft = false };
                                ({ mcedoc, PathTime, Contents, Draft }) ->
                              #mcedoc { path_time = PathTime,
                                        contents = Contents,
                                        draft = Draft }
                            end,
                            record_info (fields, mcedoc),
                            mcedoc).

used_nodes (TableName) ->
lists:usort (used_nodes (TableName, ram_copies) ++
               used_nodes (TableName, disc_copies) ++
               used_nodes (TableName, external_copies) ++
               used_nodes (TableName, disc_only_copies)).

used_nodes (TableName, CopyType) ->
mnesia:table_info (TableName, CopyType).

Let's go through it step-by-step.

First I ensure that the local schema is disc-based by essentially calling mnesia:change_table_copy_type/3. fast_change_table_copy_type/3 is a local function that I wrote for schemafinder to prevent unnecessary calls to mnesia:change_table_copy_type/3. Here it is overkill, but in a large distributed configuration under load the latency associated with acquiring a schema transaction can be sizeable so using "dirty schema reads" (mnesia:table_info/2, mnesia:system_info/1) can save time.
Next via ensure_table/2 I ensure that the mcedoc table exists, and otherwise create it with the indicated parameters. (These are tcerl tables which leverage mnesiaex, you should modify them to be ets or dets tables if you are using standard mnesia.) The ensure_table/2 function creates the table if it does not already exist, and then calls mnesia:wait_for_tables/1 to guarantee the table (and any associated fragments) are ready to be used. Note that ensure_table/2 is idempotent.
Ignore the maybe_transform_mcedoc/0 call for now, we'll cover it in the next section.
The mcedoctime and mcecomment tables are similarly treated via ensure_table/2.

Since this is called in the init callback of a gen_server which is in the application hierarchy of the application providing the API to the document store for the site, we are assured that the application is not started until the database is ready. In addition, we can list this gen_server as the first child in the childspec for the application, to ensure that no other processes associated with the document store attempt to access the schema prematurely.

If you do time-consuming initialization of the database during the init/1 callback (e.g., loading in a large starting dataset), you should increase the timeout passed to gen_server:start_link/3,4 appropriately (or, alternatively, do not specify a timeout).

Advanced: Schema Migrations

Rarely is the initial schema associated with the first version of the application sufficient as the application evolves (unless an essentially schema-free approach is taken). One of the nice features of Mnesia is the ability to migrate the schema while the database is live, via mnesia:transform_table/4. Since we have delegated ownership of our schema to a gen_server, we can migrate the schema as part of the code upgrade process.

In particular the relevant section of code for erlanganswers.com is

-record (state, {}).
-record (statev2, { backup }).
-record (statev3, { backup }).
-record (statev4, { backup }).

code_change (_OldVsn, #state{}, _Extra) ->
register (?MODULE, self ()),
ensure_schema (),
{ ok, #statev4 { backup = none } };
code_change (_OldVsn, #statev2{ backup = Backup }, _Extra) ->
ensure_schema (),
{ ok, #statev4 { backup = Backup } };
code_change (_OldVsn, #statev3{ backup = Backup }, _Extra) ->
ensure_schema (),
{ ok, #statev4 { backup = Backup } };
code_change (_OldVsn, State, _Extra) ->
{ ok, State }.

This is the code change handler for the gen_server. There have been 3 hot upgrades of this server since it was launched, and by convention I represent these as different records.

#state{}: This was the original version of the server.
#statev2{}: For this upgrade, the mcedoc table was modified. In addition I forgot to register the server (I used gen_server:start_link/3 instead of gen_server:start_link/4) which was frustrating implementation of the backup system. Therefore I register the server in the code change handler. Newly started instances of the server will be registered so this is not required for subsequent code changes.
#statev3{}: Another change to the mcedoc table was introduced.
#statev4{}: The mcecomments table was introduced as part of the launch of the comments system.

In all cases I write ensure_schema/0 to take any version of the database and bring it all the way up to date. In most cases this is the easiest way to reason about the system, but sometimes migration must take a certain path through database versions (this is more likely on a commercial project where only certain database state transitions have been tested and quality assurance is paramount).

We have already met much of the ensure_schema/0 function, with the exception of the maybe_transform_mcedoc/0 function. Let's analyze that now.

maybe_transform_mcedoc () ->
case mnesia:table_info (mcedoc, attributes) =:=
       record_info (fields, mcedoc) of
    true ->
      ok;
    false ->
      transform_mcedoc ()
end.

transform_mcedoc () ->
{ atomic, ok } =
    mnesia:transform_table (mcedoc,
                            fun ({ mcedoc, PathTime, Contents }) ->
                              #mcedoc { path_time = PathTime,
                                        contents = Contents,
                                        draft = false };
                                ({ mcedoc, PathTime, Contents, Draft }) ->
                              #mcedoc { path_time = PathTime,
                                        contents = Contents,
                                        draft = Draft }
                            end,
                            record_info (fields, mcedoc),
                            mcedoc).

The decision to transform is driven by whether the record fields associated with the table match the current definition of the record in the software. If there is a mismatch, mnesia:transform_table/4 is invoked. Importantly, we cannot use the record syntax to access an old version of the record, as this will lead to a run-time error. Instead we use the correspondence between records and tuples and access the old versions of the record as tuples. In this case, there was originally a definition of the mcedoc record, #mcedoc{path_time, contents=""}, which was then augmented with a draft column, #mcedoc{path_time, contents="", draft=true}, when I introduced the ability to have work-in-progress articles. This was further augmented with a comments_ok column, #mcedoc{path_time, contents="", draft=true, comments_ok=true}, when I added the comments system. The transform function can map any version of the record that has ever been used into the latest version.

Since the default timeout on a code change handler is 5 seconds, you should use one of the high level release instructions in your appup file to increase the timeout when doing nontrivial amounts of work in a code change handler.

about/infrastructure.html

paul-erlanganswers@mineiro.com (Paul Mineiro) — Fri, 26 Jun 2009 21:05:05 GMT

About the Site

The site consists of a document store written in Mnesia, a serving layer provided by inets httpd, a presentation layer which leverages Nitrogen, and an editing interface which leverages TinyMCE. (CouchDB looked like a good choice for the document store, but I am super familiar with Mnesia so that was very easy for me to get going).

The application style portions of the site are implemented via Nitrogen. The comment system utilizes postbacks which update the Mnesia store. The CMS capabilities of the site are only available if you authenticate as myself. Essentially I made a Nitrogen element out of the TinyMCE editor and I use this to modify the content in a WYSIWYG style. Here's a picture of me editing this page:

TinyMCE is very cool.

The rss feed and recently updated features are implemented with a separate ordered_set Mnesia table with a timestamp as a key. I use on disk ordered_set via tcerl. When I make changes it sets a flag which causes Mnesia to backup to S3 at the next interval. I use s3fs to make that easy.

PrivilegedPort.html

paul-erlanganswers@mineiro.com (Paul Mineiro) — Wed, 24 Jun 2009 23:07:16 GMT

Binding to a Privileged Port

Table of Contents

Introduction
Do not do this: setuid beam as root
Port forwarding
Capabilities
Reverse proxy
Disable privileged ports

Introduction

Erlang is a natural fit for web applications and there are several webservers available for Erlang. Since ports 80 and 443 are privileged ports, this question arises periodically.

Hello!

Often we have to run some kinds of our erlang programs with root
privileges, e.g. to allow them to bind a system port (< 1024). It is
quite dangerous, because once your web-server has been hacked by a bad
guy, the whole system can be affected. I was very impressed to know
that some servers drop root priveleges right after port binding.

Is there a way which will help me to change the privileges of a
running program to the minimum after a system port has been bound?

Thanks.

--
Sergey Samokhin

Here are some ideas.

Do not do this: setuid beam as root

Setting beam setuid root will technically work, but this is a very bad idea. Erlang is a full service environment with functions like os:cmd/1 that will rip a huge security hole in your system.

Port forwarding

This technique involves using your OS's port forwarding capabilities to forward ports 80 and 443 to non-privileged ports, and then binding those ports in a beam that runs as an ordinary user. For Linux iptables forwarding port 80 to port 8080 is accomplished via

iptables -t nat -A PREROUTING -p tcp -m tcp --dport 80 -j REDIRECT --to-ports 8080

and then the beam can bind port 8080 as an ordinary user.

Capabilities

Some OS's can selectively grant only the ability to bind privileged ports. Under Linux this is done by setting the capabilities on the beam executable (or beam.smp if the smp emulator is used), e.g.,

setcap 'cap_net_bind_service=+ep' /usr/lib/erlang/erts-5.6.5/bin/beam setcap 'cap_net_bind_service=+ep' /usr/lib/erlang/erts-5.6.5/bin/beam.smp

Reverse proxy

For http, there are programs specifically designed to drop privileges after binding the privileged port, and then act as a reverse proxy. Nginx is a popular example, and has many other interesting capabilities, including load balancing across a set of backends with failure detection, query rewriting recapabilities, keepalive support, and ssl support.

Disable privileged ports

The concept of privileged ports generally creates more problems than it solves, since becoming root is a very small barrier these days (unlike the early days of the internet), yet the possibility of remote compromise is increased. Some OS's provide the ability to disable the concept of privileged ports entirely. On FreeBSD this can be done via

sysctl net.inet.ip.portrange.reservedhigh=0

facebook/VerifySignature.html

paul-erlanganswers@mineiro.com (Paul Mineiro) — Sun, 21 Jun 2009 18:33:45 GMT

Verifying a Facebook Connect Signature

This site uses Facebook connect to authenticate. Basically, Facebook javascript sets cookies in my domain (erlanganswers.com) which the server can read, and one of these cookies contains a user id. In order to prevent malicious persons from faking authentication by setting the cookie values themselves, the cookies are signed via a secret key associated with the application. This signature can be verified by the server in order to reject cookies not produced by Facebook.

The algorithm for verifying the signature is described extensively on the Facebook developer wiki. Essentially all cookies prefixed by your application key are concatenated in sorted order, the secret key is appended, and the signature is the md5sum. The signature is contained in another cookie for verification.

-define (FB_APP_KEY, "YOURAPPKEY").
-define (FB_SECRET_KEY, "YOURSECRETKEY").

check_fb_auth () ->
case wf_platform:get_cookie (?FB_APP_KEY) of
    undefined ->
      false;
    Sig ->
      FbMac =
        erlang:md5 (
          [
            lists:sort (
              [ [ Key, "=", Value ]
                || Cookie <-
                     string:tokens (wf_platform:get_header (cookie), "; "),
                   { ?FB_APP_KEY "_" ++ Key, Value } <-
                      [ list_to_tuple (string:tokens (Cookie, "=")) ]
              ]
            ),
            ?FB_SECRET_KEY
          ]
        ),
      FbHexMac = [ C || <<N:4>> <= FbMac,
                        H <- io_lib:format ("~1.16.0b", [ N ]),
                        C <- H ],
      if FbHexMac =:= Sig ->
           { ok, facebook, wf_platform:get_cookie (?FB_APP_KEY "_user") };
         true ->
           false
      end
end.

How it works:

I use the Nitrogen web framework for Erlang which provides an abstraction for extracting cookies and headers (wf_platform).
The signature if present is contained in a cookie whose key is your application key: wf_platform:get_cookie (?FB_APP_KEY).
All cookies prefixed by the application key and an underbar are concatenated in sorted order, the secret key appended, and the md5sum is computed.
- Erlang, like C, will compile-time concatenate string constants together, so { ?FB_APP_KEY "_" ++ Key, Value } <- selects only the Facebook Connect cookies.
- erlang:md5/1, like many Erlang functions, takes an iolist argument. We do not waste time flattening the list after constructing it.
The md5sum is converted to hex and compared with the signature.

mnesia/EqualsIgnoresCase.html

paul-erlanganswers@mineiro.com (Paul Mineiro) — Sat, 20 Jun 2009 15:10:56 GMT

Mnesia Equals Ignores Case Query

Introduction
Maintain the Data Canonicalized
Match Specification Solution
Secondary Index Solution

Introduction

Many more people know SQL than know Mnesia, so questions about how to translate a particular SQL construct into Mnesia arise frequently on the list, and in particular this question arose:

Hi,

I can't see any advice previously offered for the best way to query a
(large) mnesia table with a query comparable to "equals ignore case".

My first thought is to storing an indexed lower or upper "case"
version of the data in an additional field, but with nearly 20 million
records that doesn't seem very attractive.

TIA for any thoughts,

Regards,
Steve

There are several approaches which mimic approaches in relational databases.

Maintain the Data Canonicalized

One very simple solution is to maintain the column in canonical form so that no transformations need to be applied to compute constraints. If this is practical, this is a very efficient solution, not just for Mnesia.

Match Specification Solution

This solution is relatively inefficient but general. This technique is analogous to an unoptimized SQL statement of the form

SELECT * from foo WHERE upper(key) = 'VALUE'

The pivotal step is to create a match specification corresponding to the WHERE clause. Match specifications can only contain guards so the case folding has to be translated into a match specification. Ulf Wiger posted a reply containing a pointer to software he wrote to convert (some) regular expressions into match specifications. This can be used to emulate LIKE where clauses using techniques similar to those listed below.

I will hand-roll an implementatation of (ascii) case-folding into match specifications here. As an additional optimization, I will bind the first character of the constrained field in the pattern and issue multiple (up to 2) selects, which will be faster if the field compared is the primary key of an ordered_set table, but slower otherwise. Thus you might want to adapt the example given below to a single select. (It would of course be nice to detect this condition automatically and adapt. Query planning is one of the many things that come with most relational database engines). Because we issue multiple selects, the return value will be a list of list of results, rather than a list of results.

-module (testequalsignorecase).
-export ([ equals_ignores_case/3 ]).

equals_ignores_case (Tab, Field, Value) ->
Guard = case_fold_guard (Value),
FieldOffset = get_field_number (Tab, Field),
WildPattern = mnesia:table_info (Tab, wild_pattern),

  [mnesia:select (Tab,
                   [ { setelement (FieldOffset, WildPattern, Vars),
                     [ Guard ],
                     [ '$_' ] } ])
    || Vars <- construct_vars (Value) ].

case_fold_char (H) when H >= $A, H =< $Z -> [ H, H + ($a - $A) ];
case_fold_char (H) when H >= $a, H =< $z -> [ H + ($A - $a), H ];
case_fold_char (H) -> [ H ].

case_fold_guard ([]) -> [];
case_fold_guard ([ _ | T ]) -> case_fold_guard (T, 1, true).

case_fold_guard ([], _N, Acc) -> Acc;
case_fold_guard ([ H | T ], N, Acc) ->
case case_fold_char (H) of
    [ Singleton ] ->
      case_fold_guard (T,
                       N + 1,
                       { 'andalso',
                         { '=:=', nth_variable (N), Singleton },
                         Acc });
    [ Upper, Lower ] ->
      case_fold_guard (T,
                       N + 1,
                       { 'andalso',
                         { 'or',
                           { '=:=', nth_variable (N), Upper },
                           { '=:=', nth_variable (N), Lower }
                         },
                         Acc })
end.

construct_vars ([]) ->
[];
construct_vars ([ H ]) ->
[ [ First ] || First <- case_fold_char (H) ];
construct_vars ([ H | T ]) ->
Vars = [ nth_variable (N) || N <- lists:seq (1, length (T)) ],
[ [ First | Vars ] || First <- case_fold_char (H) ].

nth_variable (N) ->
list_to_atom (lists:flatten (io_lib:format ("$~b", [ N ]))).

get_offset ([ Field | _ ], Field, N) -> N;
get_offset ([ _ | T ], Field, N) -> get_offset (T, Field, N + 1).

get_field_number (Tab, Field) ->
get_offset (mnesia:table_info (Tab, attributes), Field, 2).

Here's how it works:

equals_ignores_case/3 is the entry point, e.g., equals_ignores_case (foo, key, "hello").
case_fold_guard/1 computes the guard from the value. It ignores the first character of the value, and creates a conjunction of disjunctions for the rest of the characters. It uses '$1' to refer to the second character of the field being matched, '$2' to refer to the third, etc.
construct_vars/1 computes the pattern(s) from the value. It binds the first element to each case of the desired value, and binds subsequent elements to variables. This ensures variable '$1' corresponds to the second character of the field being matched, '$2' the third, etc. Because construct_vars/1 can return 0, 1, or 2 patterns, we end up doing 0, 1, or 2 selects.
the patterns returned by construct_vars/1 are substituted into the wildcard pattern for the table at the field position to bind that field as desired, and the selects are issued.

Here are some example invocations:

% erl
Erlang (BEAM) emulator version 5.6.5 [source] [async-threads:0] [kernel-poll:false]

Eshell V5.6.5 (abort with ^G)
1> mnesia:start (), mnesia:create_table (foo, []), mnesia:dirty_write ({ foo, "hello", "world" }), mnesia:dirty_write ({ foo, "HeLlO", "WoRlD" }), mnesia:dirty_write ({ foo, "goodbye", "world" }), mnesia:dirty_write ({ foo, "123", "456" }).
ok
2> mnesia:async_dirty (fun testequalsignorecase:equals_ignores_case/3, [ foo, key, "hello" ]).
[[{foo,"HeLlO","WoRlD"}],[{foo,"hello","world"}]]
3> mnesia:async_dirty (fun testequalsignorecase:equals_ignores_case/3, [ foo, key, "hi" ]).
[[],[]]
4> mnesia:async_dirty (fun testequalsignorecase:equals_ignores_case/3, [ foo, key, "goodbye" ]).
[[],[{foo,"goodbye","world"}]]
5> mnesia:async_dirty (fun testequalsignorecase:equals_ignores_case/3, [ foo, key, "goodbYe" ]).
[[],[{foo,"goodbye","world"}]]
6> mnesia:async_dirty (fun testequalsignorecase:equals_ignores_case/3, [ foo, key, "" ]).
[]
7> mnesia:async_dirty (fun testequalsignorecase:equals_ignores_case/3, [ foo, key, "123" ]).
[[{foo,"123","456"}]]

Secondary Index Solution

Relational database practitioners will tell you that a select statement of the form

SELECT * from foo WHERE upper(field) = 'VALUE'

can be very inefficient. One solution is to index the case folded version of the column. There are several ways to do this.

With an equality condition such as above, Mnesia's built-in (bag) indices are sufficient; so one could add another column to the table which contains a canonically cased version of the original column, and an index lookup can be done on this auxiliary column. If space is an issue, the canonical casing function can return a hash which has a very high probability of not colliding (e.g., md5), which reduces the size of the auxiliary column.

With an inequality condition such as

SELECT * from foo WHERE upper (field) >= 'VALUE'

Mnesia's built-in indices are not powerful enough, and a secondary ordered_set table needs to be maintained manually. It would contain records of the form

-record (foo_upper_index, { canon_plus_key, void = [] }).

When a record F is written into the primary table, a record of the form #foo_upper_index{ canon_plus_key = { canonicalize (F#foo.field), F#foo.key } } would be inserted into the secondary table. The secondary table can be queried efficiently for ranges of the canonicalized version of the field, and the resulting list of keys can be used to query the original table for records.

ComplexCasePatterns.html

paul-erlanganswers@mineiro.com (Paul Mineiro) — Wed, 17 Jun 2009 22:10:45 GMT

Complex Case Patterns

Introduction
Disjunctive Guards
Universal Clause
Transform Expression

Introduction

Erlang case statements have clauses that are guards, and since they can do pattern matching the case statement resembles conditional constructs from other languages. However the correspondence breaks down when complicated conditionals are required, especially attempts to share clause bodies against distinct deconstructors. Thus periodically someone emails the list with something like the following:

Hi All,

How to formulate a "complex pattern" in a case clause ?

case Expr of
a,b -> block1; % if Expr = a or b then block1
c -> block2 % if Expr = c then block2
end

(a,b) gives an error
What is the correct syntax ?

John

The answer is complicated. Here are some suggestions offered.

Disjunctive Guards

When the patterns being matched have identical structure but there are different possibilities for each component, guard disjunction can be useful. In this case it would become

case Expr of
   X when X =:= a; X =:= b ->
      block1;
   c ->
      block2
end

However in a more complicated situation this approach breaks down. Suppose for instance we want to share a block between ok and { error, eexist }, e.g., some of the possible return values of file:make_link/2. In this case it becomes

case Expr of
   X when X =:= ok; is_tuple (X), size (X) =:= 2, element (1, X) =:= error, element (2, X) =:= eexist ->
      block1;
   _ ->
      block2 % error we don't like has occurred
end

which isn't going to win any beauty contests.

Universal Clause

In the original example, we could match on c and then assume everything else is either a or b.

case Expr of
   c ->
      block2;
   _ ->
      block1 % assumes (not c) implies (a or b): different than original!
end

This is a bad idea for the original poster, because it is not semantically equivalent. The original post would crash if Expr was not one of (a, b, or c), whereas this case statement will accept any expression. However in some situations this can be a good idea, such as when there are only a small number of "acceptable" return values from a function and anything else is to be considered an error.

Transform Expression

The idea here is to use an auxiliary function to map the original expression into a set of equivalence classes which are easily managed by the case statement.

case my_type (Expr) of
   class1 ->
      block1;
   class2 ->
      block2
end

with auxiliary function

my_type (a) -> class1;
my_type (b) -> class1;
my_type (c) -> class2.

For simple examples such as this one this seems overkill, but for complicated examples involving matching using distinct deconstruction clauses, this can be a win. For instance with the ok and { error, eexist } example from above

case exists_ok (file:make_link (Existing, New)) of
   ok ->
      block1;
   { error, BadError } ->
      block2
end

with auxiliary function

exists_ok ({ error, eexist }) -> ok;
exists_ok (X) -> X.

seems nicer than attempting the same with guard disjunction.

VersionedVariables.html

paul-erlanganswers@mineiro.com (Paul Mineiro) — Wed, 17 Jun 2009 18:21:22 GMT

Versioned Variables

Introduction
Numbered Variables
Function Arguments
Introduce New Scope
Let Construct
Folding

Introduction

Erlang doesn't have an assignment operator, but it has a pattern matching operator that looks like one. The first time a variable is used in a pattern match it is bound, and subsequent uses of the variable become a matching assertion. This is different from the typical imperative language (which has destructive assignments) and the typical functional language (which has a let construct).

Thus periodically a question arises on the list regarding what to do about a sequence of statements for which temporary intermediates are uninteresting, like the following:

Hello!

I think there wasn't any grumbling this month about the immutable
local variables in Erlang, so here's real world code I've found just
today:

% Take away underscore and replace with hyphen
MO1 = re:replace(MO, "_", "-", [{return, list}, global]),
MO2 = toupper(MO1),
% Replace zeros
MO3 = re:replace(MO2, "RX0", "RXO", [{return, list}, global]),
% Insert hyphen if missing
MO5 = case re:run(MO3, "-", [{capture, none}]) of
   nomatch ->
     insert_hyphen(MO3);
   match ->
     MO3
end,

I think it's fairly clumsy to use MOx (MO for managed object) in the
code. MO4 was removed during the regexp->re refactoring step. How to
eliminate the versioned variable names? The
MOAfterUnderscoresWereReplaced, UpperCaseMO, MOAfterRX0WasReplaced,
etc. variablenames are really ugly. It used to use regexp, so at that
point it wasn't possible to easily nest the whole into one call, but
that would be still ugly. So any other ideas?

We can see the poster is intentionally trying to stir up the hornet's nest. Kudos! Without further ado, the proposed solutions:

Numbered Variables

This is the "original" solution: use different variable names for the different intermediate values. This solution has some proponents, but mostly everybody agrees that it sucks. For instance, it's very easy to unintentionally use a previously computed temporary value. In the above example a maintenance programmer might have put

nomatch ->
insert_hyphen(MO2);

Which would compile just fine and cause a bug.

Function Arguments

Arguments to functions can be expressions, in which case anonymous temporaries are introduced. This can be good for short sequences such as h (g (f (x))) but would be unwieldy for the poster's original example

maybe_insert_hyphen (
   re:replace (
   toupper (
       re:replace (MO, "_", "-", [{return, list}, global])
     ),
     "RX0",
     "RXO",
     [{return, list}, global]
   )
)

and would also require defining a helper function maybe_insert_hyphen/1

maybe_insert_hyphen (X) ->
   case re:run (X, "-", [{capture, none}]) of
nomatch ->
   insert_hyphen (X);
      match ->
       X
   end.

in order to avoid recomputing the temporary unnecessarily.

Introduce New Scope

Named Functions

Functions introduce a new scope, so judicious use of functions can eliminate temporaries.

% Take away underscore and replace with hyphen
doit_stage1 (X) -> doit_stage2 (re:replace (X, "_", "-", [{return, list}, global])).

doit_stage2 (X) -> doit_stage3 (toupper (X)).

% Replace zeros
doit_stage3 (X) -> doit_stage4 (re:replace (X, "RX0", "RXO", [{return, list}, global])).

% Insert hyphen if missing
doit_stage4 (X) ->
case re:run (X, "-", [{capture, none}]) of
    nomatch ->
      insert_hyphen (X);
match ->
      X
end.

In this case the result is not very compelling.

List Comprehensions

List comprehensions also introduce new scope so this could be done as

hd ([X || X <- [re:replace (MO, "_", "-", [{return, list}, global])],
              X <- [toupper (X)],
              % Replace zeros
              X <- [re:replace (X, "RX0", "RXO", [{return, list}, global])],
              % Insert hyphen if missing
              X <- [case re:run (X, "-", [{capture, none}]) of
                          nomatch ->
                               insert_hyphen (X);
                          match ->
                               X
                        end]
      ])

which is not in danger of winning any beauty contests, but is arguably a superior amalgamation of the folding technique and the anonymous functions technique. In particular unlike several solutions here this one is not "backwards": computations are listed in the order performed.

Anonymous Functions

Anonymous functions also introduce new scope so this could be done as

(fun (X) ->
     case re:run (X, "-", [{capture, none}]) of
        nomatch ->
          insert_hyphen (X);
match ->
          X
     end
end) (
(fun (X) ->
   re:replace (X, "RX0", "RXO", [{return, list}, global])
   end) (
     toupper (re:replace (MO, "_", "-", [{return, list}, global]))
   )
)

which is also not very compelling, but this form is interesting because it is essentially a let construct expanded into lambda constructs.

Let Construct

Erlang doesn't have a native let construct but a parse transform can be used to expand something that looks like a let construct into an equivalent sequence of lambda constructs. The result looks like

let_ (
% Take away underscore and replace with hyphen
MO = re:replace (MO, "_", "-", [{return, list}, global]),
MO = toupper (MO),
% Replace zeros
MO = re:replace (MO,"RX0","RXO",[{return, list}, global]),
% Insert hyphen if missing
case re:run(MO, "-", [{capture, none}]) of
     nomatch ->
        insert_hyphen(MO);
     match ->
        MO
end
)

which looks nice enough, but parse transforms cannot change the syntax of the language, just the semantics. Thus the let_ usage must look like a function call, and for other examples this would mean using begin ... end blocks to make sequences of expressions act like a single expression.

Folding

A fold can be thought of as threading state through a sequence of computations, and given a list of lambda expressions this is very flexible. The poster's example becomes

lists:foldl (fun (Fun, Acc) -> Fun (Acc) end,
                  MO,
                  [ fun (X) -> re:replace (X, "_", "-", [ { return, list }, global ]) end,
                    fun toupper/1,
                    fun (X) -> re:replace (X, "RX0", "RXO", [ { return, list }, global ]) end,
                    fun (X) -> case re:run (X, "-", [ { capture, none } ]) of
                                      nomatch ->
                                         insert_hyphen (X);
                                      match ->
                                         X
                                   end
                    end ])

This is neither pretty nor concise, but it does make maintaining a sequence of operations less error prone (i.e., inserting or removing a computation step). With several temporaries it's necessary to fold with a tuple accumulator and the ugliness goes up.