When a chain health monitor process makes a major state transition, it will notify the Admin Server of the change. The Admin Server will then broadcast, or "spam" status notifications to all server and client nodes. The data structure spammed is a #g_hash_r record, or simply a "global hash record". This record is maintained by the admin server per table. Each table has its own unique global hash record.

	Among other things, the global hash contains the bricks and their roles in each chain. In this manner, a gdss client can know which chain a key belongs to and what brick in that chain is acting as head or tail. In this manner they can talk directly to the correct brick for a given operation.

	The admin server increments a minor revision number in the global hash for each update. Bricks and clients can then compare this revision number to what they already have to ensure that they don’t revert to using an older global hash.

The brick_admin:fast_sync() family of functions are an attempt to help Hibari cluster administrators to perform bulk-copies of data from in-service bricks to bricks that have zero data. For example, consider a physical brick has crashed due to data loss caused by a hard disk failure. The crashed brick can be put back into service after fixing the disk problem, but the brick’s data has been lost. Chain replication can create new replicas of the lost data, but the chain replication implementation can create a lot of disk I/O on the upstream brick for long periods of time, e.g. several days for terabytes of data. The fast_sync() function attempts to minimize the amount of random disk I/O by copying keys & values in file+offset sorted order.

See the section called “Scavenger and code reuse”.

Originally, the principal process for a logical brick was a "gen_server" behavior process that was implemented by brick_ets.erl. When the brick_ets.erl module was split apart, the choice was made to do the following:

	This choice complicates brick_server.erl a little bit but avoided a lot of refactoring work in brick_ets.erl. It isn’t clear if now is a good time to review that decision.

The #state record used by brick_ets.erl has members in several major categories:

	The #state record is probably too big. Profiling suggests that a substantial amount of CPU time is being spent in erlang:setelement(); I’m guessing that’s related to #state record updates, but I’m not 100% certain. There are about 43 members in that record, so refactoring by moving some items (e.g. operation counts like n_add) to the process dictionary or ETS is likely a good idea.

A "store tuple" is the internal representation of a key’s metadata. It uses a variable-sized tuple to try to save some memory, avoiding storing common values. This is the tuple that is stored in the #state.ctab table.

Types used:

The time required for full initialization of a logical brick is not predictable. We cannot know in advance how much metadata must be read from the brick’s private write-ahead log, nor do we know how much time it will take to read that data.

The OTP "supervisor" behavior places a limit on how long a worker process’s init() function can take, and while a supervisor is starting a worker process, it is blocked from starting/restarting/stopping other workers. Therefore, it’s very important that the logical brick initialization function execute in a short amount of time.

The second-to-last statement in brick_ets:init/1 is this:

self() ! do_init_second_half,

Then the handle_info/3 callback can take as much time as is necessary to read & process the updates in the private write-ahead log.

Here are some examples of why the dirty keys table, #state.dirty_tab, is used (not an exhaustive list):

A Hibari micro-transaction is designed to avoid holding locks by forcing the client to send the entire micro-transaction in a single message. The server brick’s gen_server should immediately be able to enforce the above properties, correct? Yes and no, unfortunately.

Because each logical brick is implemented as a single "gen_server" process (we ignore the helper processes enumerated in the section called “Processes created by brick_ets.erl”), all messages processed by the brick are automatically serialized. That serialization property makes it much easier to implement immediate commit/abort decisions. However, there’s a small problem: disk I/O is slow. Here is one example of a race condition that is caused by slow disk I/O:

Any key that is updated by an operation that is waiting for its write-ahead log entry to be flushed to disk will have an entry in the #state.dirty_tab ETS table. When the fsync(2) system call is finished, the key will be removed from #state.dirty_tab and the #state.ctab (or the "shadow table", if a checkpoint is in progress) will be updated to make the key’s update visible.

If a Hibari client calls do when the first op in the DoList is the atom txn, then the DoList will be evaluated as a micro-transaction. The check is done by do_do2/3, with micro-transaction preconditions checked by do_txnlist/3.

If do_txnlist/3 detects that a micro-transaction precondition has been violated, e.g. add a key that already exists, then an error accumulator is built to inform the client of which items in DoList failed. Note that the txn op is removed from the DoList before do_txnlist/3 starts.

If do_txnlist/3 finds no errors in the micro-transaction, then the DoList is then executed by the same function that processes non-micro-transaction lists, do_dolist/4.

The management of the write-ahead log and maintaining strong consistency was a more difficult problem than I had first realized. To preserve strong consistency, the order of all updates must be preserved when writing log entries to the write-ahead log. Updates come from two sources:

The brick maintains a monotonically-increasing counter, #state.logging_op_serial, to assign a serial number to each update. Each update is written in increasing serial number order. After an update is written, the brick will request an fsync(2) system call on the log. The write-ahead log manager will initiate the call (if no fsync(2) call is currently in progress) or queue the request for a later time (because an fsync(2) system call is in progress already).

Because the brick does not know when the fsync(2) system call will finish, the brick stores the operation and its serial number in a queue called #state.logging_op_q.

The write-ahead log manager will notify the brick when an fsync(2) system call is finished, telling the brick the largest serial number N. The brick will remove all pending requests from the #state.logging_op_q that have serial numbers less than or equal to serial N. Processing of those pending requests is then resumed.

As described above, the "syncpid"'s job is pretty simple:

The tricky part is step #2, specifically, when should "now and then" be? There are a couple of easy answers to the question:

The current implementation, in collect_sync_requests/3, uses a variable amount of time in step #1 by waiting a maximum of 5 milliseconds since the last fsync request before going to step #2. The method is virtuous by being simple and for being "good enough" for both very low and very high load conditions.

As explained in the section called “The "store tuple"”, when a value blob is stored on disk, its store tuple representation is {FileNumber::integer(), Offset::integer()}. These two integers are used to find the value blob’s storage location on disk. See the section called “gmt_hlog.erl” for API details.

A brick’s behavior for value storage is defined by the value of #state.bigdata_dir:

When a key is set by a set/add/replace operation in a table that stores value blobs on disk, there are actually two hunks written to the brick’s write-ahead log:

To retrieve a hunk, the gmt_hlog API is used, passing the FileNumber and Offset as arguments. The library function then:

The serial nature of message handling by the "gen_server" behavior is almost always a good thing. However, dealing with disk I/O is one of the few times when it would be really nice to have "gen_server" handle multiple messages in parallel.

It’s certainly possible to have "gen_server" handle multiple messages in parallel, but it’s the developer’s responsibility to juggle the asynchronous replies to clients. This can get very tricky very quickly. However, a logical brick must do this kind of juggling to minimize latency across all Hibari client requests.

The Erlang virtual machine does not expose an API to the OS’s mmap(2) and mincore(2) system calls, so it is impossible for a logical brick to know which parts of a file are in the page cache and which are not. Without that knowledge, the brick cannot predict how long it will take to open or read a log sequence file to retrieve a value blob.

To make the unpredictable disk I/O pattern into something almost 100% predictable, Hibari bricks borrow a trick from the Squid HTTP Caching Proxy server and the Flash HTTP server. To avoid having computation threads blocked by disk I/O, both servers use a pool of OS processes or Pthreads whose sole job is to perform disk I/O. The model goes something like this:

The logical brick uses the same basic strategy, which I’ve called "squid/flash priming" or simply "priming", as in "priming a pump". A brick will spawn a short-lived Erlang process to read the log hunk, notify the main gen_server that the I/O is finished, and then the main gen_server process can open & read the file with virtual certainty that it will not be blocked by disk I/O.

Primer processes are used when reading data from a Hibari client get or get_many request as well as when reading value blobs during brick repair operations. Each has a separate throttle configuration attribute.

	There is a throttle mechanism to keep too many squid/flash primer processes from executing simultaneously: the brick_primer_limit attribute in central.conf. Too many primer processes can cause several problems, separately or in combination or together: Consume too many Erlang processes Consume too many OS file descriptors Consume too much virtual machine memory

There is plenty of opportunity for refactoring here. The current implementation has been "good and fast enough", but there’s almost certainly room for optimization, especially if very large blobs (greater than 4MB, approximately) are routinely used. Some possible optimizations would included: Use Erlang NIF functions to use mmap(2) and mincore(2) system calls. Use the readahead(2) system call on Linux platforms. Try to find substitutes on other platforms aren’t mmap(2) and mincore(2). Experiment with libprefetch. Adding a bytes-per-second throttle for priming operations. Perhaps using mmap(2) instead of file:read() for the final blob reading step?

There are two magic values that an Erlang client can use in a set/add/replace operation in place of the usual binary or iolist value blob.

The implementation of the contents table and the shadow table, #state.ctab and #state.shadowtab respectively, causes some problems. The biggest problem is that when a checkpoint is in progress and the #state.shadowtab exists, then the "does the key exist?" decision must consult both tables in a sane manner.

The get_many operation is most affected by the necessity to look in both tables. The get_many_shadow() function implements the tricky logic that’s required to combine the contents of both contents and shadow tables into a consistent set of results.

	Because get_many is really complicated by the shadow table, and because there has been no hard requirement for a client get_many op that returns keys in reverse order (i.e. search backwards), a reverse- ordered get_many operation does not exist. There is no foreseeable technical reason why one couldn’t be added.

By default, MD5 checksums are generated for all data written to all write-ahead logs, and those MD5 checksums are checked for all data read from write-ahead logs.

If the file "disable-md5" exists in the Hibari server data directory, then data will be written to write-ahead logs without MD5 checksums, and data read from write-ahead logs will not have MD5 checksums verified.

If the file "use-md5-bif" exists in the Hibari server data directory, then the erlang:md5/1 function will be used to create MD5 checksums. By default, the crypto:md5/1 is used to create MD5 checksums.

If an MD5 checksum error is detected, the easy thing to do is crash the brick. In practice, this approach causes some additional problems that we would rather avoid. The logic is in bigdata_dir_get_val():

The "scavenger" procedure is used to reclaim disk space in the "common log" that is no longer used by a local logical brick. It is essentially a copying garbage collector:

	By default, the scavenger is run once every 24 hours at 03:00.

Each write-ahead log is divided into log sequence files. Each log sequence files contains a sequence of "hunks". The hunks are put into one of two categories:

The goal of the scavenger is to reclaim disk space. The only way to reclaim disk space is to delete files. If the scavenger finds a log sequence file with 0% live hunks, that file can be deleted immediately. However, it is quite rare to find a log sequence file that has 0% live hunks. For all other log sequence files, a different strategy is used:

	The current scavenger implementation trades (relatively) low memory usage for increased execution time and increased disk I/O. There are probably opportunities to refactor the scavenger to operate faster or to generate less disk I/O to its temp files.

The only method that should be used for new Hibari tables is the chash method. The other three, naive, ``var_prefix`, and fixed_prefix, are deprecated and will be removed at some point. The chash method supports all three schemes and also provides migration-related features that the three deprecated schemes alone cannot.

See the EDoc entry for chash_init/3 for full details on all the valid properties that can be passed in the 3rd argument proplist.

The two properties that are mandatory are prefix_method and new_chainweights. We strongly advise that you also include the old_float_map property; the float map can be extracted from a #g_hash_r or a #hash_r record using the chash_extract_new_float_map/1 function.

	Do not use the chash_extract_old_float_map/1 function to extract the consistent hash "float map" from the current global hash record. In the context of the current global hash, the "old float map" is the float map used from the global hash prior to the current one, which is almost certainly not the float map you want when making a new global hash record.

The chain changing example in ??? shows how to verify that the #hash_r that you’ve created will result in the key distribution across chains that you desire. See the example of using ``brick_simple:chash_migration_pre_check/2` ???.

Older versions of Hibari made substantial use of timer:send_interval/2 for sending periodic timer messages. The timer module’s implementation can be too inefficient when over 1,000 separate timer interval requests are made. The brick_itimer module creates a more CPU-efficient implementation for heavily used timer intervals, for example 1 second.

The latency jitter in delivering these shared timer messages is intentional. Strict real-time accuracy for sending these periodic messages is not required. If stricter delivery timings are required, do not use this module.

See also the section called “"gen_server" nested inside a "gen_server", Matroshka-style”.

After the split of brick_ets.erl and brick_server.erl, the "gen_server" callback functions of both were preserved, even though both are used by a single process. As far as OTP is concerned, brick_server.erl is the callback module used for the main logical brick gen_server process. If a call, cast, or message isn’t handled by brick_server's callback function, then the message is handled by brick_ets's callback function.

The wrinkle in this otherwise flawless scheme is that brick_server.erl has to maintain the #state record that brick_ets.erl uses, keeping it completely separate from brick_server.erl's record of the same name.

	The brick_server #state record is pretty simple, compared to brick_ets's, and much smaller. Note that brick_server's #state record also contains a logging_op_q member, which is used for a similar purpose as brick_ets's. Maintaining two separate queues of log entries is quite messy. It would be really tricky to refactor without breaking anything, but the effort would be worthwhile.

See ??? for examples that use the do() client interface.

All of the basic do operations are encoded into a small number of tuples. See make_op2(), make_op5(), and make_op6(). Note that if you want to manage your own timestamps, rather than use ones based on the OS system clock, you must use the make_op6() function yourself. A more convenient API doesn’t yet exist because there’s been no need for it … but it would be easy & quick to write.

By default, the various operations within a do call’s DoList do not have any transaction semantics. If a DoList contains 5 operations, then there is almost no difference between sending that DoList to a server than there is sending 5 different do operations, each containing a single op. However…

There are two types of flags that can be sent with a do op:

The Admin Server maintains the table-specific settings for disk logging and log flush parameters for all bricks in the table. By default, both disk logging and log flushing are enabled. Both features are actually implemented by brick_ets.erl, but the API to change those parameters at runtime are handled through brick_server.erl.

See set_do_logging/2 and set_do_sync.

The role management functions were designed for use by the Admin Server to manage the brick lifecycle state machine. See comment "Chain admin & related API" in -export statements at top of the file.

See Hibari Sysadmin Guide, "Brick Lifecycle Finite State Machine" section for a description of a brick’s lifecycle within chain replication.

When a brick’s role is set, the brick knows at most its immediate upstream brick and its immediate downstream brick. Most of the time, this decision works well. However, occasionally it’s useful for a brick to know all members of its chain, e.g. when the brick_mboxmon needs to signal the head brick to slow down. These cases haven’t happened often enough to trigger a refactoring, but it might be useful later.

Management of the #chain_r record is tricky whenever a role is changed. There are some attributes of the record that should be reset to a default value and other attributes that must be preserved. Examples of the latter are log serial numbers used by the brick as well as serial numbers ack’ed downstream & upstream. Some role transitions must also be reflected in the brick_pingee helper process (see the section called “brick_pingee.erl”). The result looks more complex than you’d first believe is necessary, but there isn’t much excess code to remove: much of that complexity is necessary.

As described in the section called “brick_hash.erl”, the brick_hash.erl module is used for consistent hashing calculations by Hibari clients. However, because a client may be acting on old/stale data, each Hibari brick also uses brick_hash to verify that each operation it receives should be executed locally.

If a client sends a do call to the wrong brick, as calculated by the brick’s global hash, then that brick will forward the do call to what it believes is the correct brick. However, due to asynchronous message passing, scheduling latencies, network latencies, etc., the brick itself may have an old/stale version of the global hash. In such a case, the do will be forwarded to the wrong brick. However, because each brick will forward the do to where it believes the do should go, eventually the do call will arrive at its proper location. In the event that the forwarding takes too long, the client will see a timeout.

The forwarding mechanism is limited by a couple of factors:

Each time the do call is forwarded, the SentAt time (which is originally set by the client node) is reset to the current wall-clock time. This reset is done to prevent brick_do_op_too_old_timeout configuration attribute enforcement; see Hibari Sysadmin Guide, "NTP configuration of all Hibari server and client nodes" section.

See Hibari Sysadmin Guide, "Chain Lifecycle Finite State Machine" section for background information.

Both chain replication protocol messages and client replies are sent "downstream", i.e. they are sent to the next brick in the chain.

The reply term for a do call is piggy-backed onto the chain replication message that is sent down the chain. When a chain replication protocol message reaches a brick has the "official tail" role, then:

If the do operation has the ignore_role property in its DoFlags property list, then the reply is sent directly to the client (instead of the default behavior of being sent downstream with the chain replication message).

The chain replication protocol messages are:

See the section called “Log flushing and the sync pid and the logging_op_q” for background on the write-ahead log serial number’s use and management.

Of all the complications that were introduced by the separation of the ‘brick_ets.erl` and brick_server.erl modules, the largest source of nasty, hard-to-find bugs has been management of the write-ahead log queues, the #state.logging_op_q term in both modules’ state record. Refactoring this log management would probably help performance by reducing CPU consumption as well as making the core server code less fragile. One area that might be easier to refactor is the management of the serial number associated with each queue. Incrementing the serial number is done by the caller after writing something to the queue. It would likely be much less error-prone if the writing and the incrementing were done by the same call.

There is a lot of code in chain_send_downstream_iff_empty_log_q/6 and elsewhere to make certain that log events are sent downstream without violating ordering constraints. I confess it isn’t pretty, but all of the bugs that I know of have been wrung out. If there are still bugs (and I suspect but cannot prove that there is one more), the paranoid sanity checking done by the downstream/receiving brick will crash if Serial numbers are received out-of-order. It isn’t a pretty way to recover from such an error, but it’s the safest reaction that I know of.

The chain repair protocol has been implemented twice. The first protocol was a brute-force, "as simple as possible" affair. The upstream brick would send a series of {ch_repair, Serial, RepairList} messages to the repairing brick. RepairList contained a list of store tuples (see the section called “The "store tuple"”) for all keys in the table. Note that these store tuples will always contain the full value blob.

The first protocol was deprecated after it became clear that "as simple as possible" had too much overhead. When in-RAM storage of value blobs was the only option, then it was cheap to fetch the value blobs and send them across the network to the repairing brick. But when "bigdata" storage was introduced (see the section called “Value blob storage on disk: bigdata_dir”), then the disk I/O, network bandwidth, and total latency became far too high to be practical.

The second chain repair protocol uses two rounds of messages to avoid the I/O problems caused by the first protocol:

The following messages are exchanged:

While these repair protocol messages are exchanged, the upstream brick will send all {ch_log_replay,...} chain replication messages as updates occur. On the upstream brick, the {ch_repair_diff_round1, Serial, RepairList} is created without interference from client updates; any keys not in RepairList are immediately deleted by the downstream brick before replying with the {ch_repair_diff_round1_ack,...} message. Therefore, any possible race conditions involving client updates of keys within the RepairList range of keys are resolved correctly by the log serial mechanism, because only one of two races can happen inside the upstream brick:

The data migration mechanism is used to move keys from one chain to another when chains are added, removed, or reweighted. The task of moving keys while maintaining strong consistency is a delicate business. The protocol, which uses two rounds (or phases), described below is used to move keys safely between chains.

During migration, the head of each chain maintains a "sweep key pointer". This pointer moves through the keys, first to last (in lexicographic sorting order).

The sweep key advances through the head brick’s keys, advancing by a maximum of max_keys_per_iter configuration attributed in central.conf or a maximum of 64MB of blob values (hardcoded for now in get_sweep_tuples/4. These keys are what the code calls the "sweep zone": those keys between the sweep key’s current value and the sweep key’s value from the last successful iteration of the migration protocol.

In between round 1 and round 2 of a migration sweep iteration, the same value blob "priming" technique is used to prevent disk I/O from blocking the brick’s gen_server process. See sweep_move_or_keep/3 and spawn_val_prime_worker_for_sweep/3.

"SSF" stands for "Server-Side Fun". An SSF is an Erlang fun that is created by a Hibari client and executed on a Hibari server brick. The SSF has the ability to rewrite the DoList of operations in the do call based on the ability to examine the brick’s internal state.

In the end, the SSF cannot do anything that cannot be done with multiple queries to a brick. For example, here is a simple two-query scheme to update simple counter value in a race-safe manner:

Incrementing a counter. 

{ok, TS, OldValBin} = brick_simple:get(TableName, Key),
OldVal = binary_to_term(OldValBin),
ok = brick_simple:replace(TableName, Key, term_to_binary(OldVal + 1),
                          [{testset, TS}]),
%% Use OldVal in code below this point.

An SSF would use a very similar bit of logic and would create the same replace operation.

Incrementing a counter with an SSF. 

F = fun(Key, _DoOp, _DoFlags, S) ->
      [{_Key, TS, Val, _Exp, _KeyFlags}] = brick_server:ssf_peek(Key, true, S),
      OldVal = binary_to_term(Val),
      {ok, [brick_server:make_replace(Key, term_to_binary(OldVal + 1), 0,
                                      [{testset, TS}]),
            {current_val, OldVal}]}
    end,
Op = brick_server:make_ssf(Key, F),
[ok, {current_val, OldVal}] = brick_server:do(TableName, [op]),
%% Use OldVal in code below this point.

The SSF fun creates a list of do primitive operations, in this case two operations:

Here is an example that uses the SSF above. It assumes that the shell variable F has been bound to the fun above. A cut-and-paste of the code above will work well, assuming that F is not already bound to a shell variable and that the final "end," is replaced with "end.".

(hibari_dev@bb3)13> brick_simple:set(tab1, "c1", term_to_binary(0)).
ok

(hibari_dev@bb3)14> Op = brick_server:make_ssf("c1", F).
{ssf,<<"c1">>,[#Fun<erl_eval.4.105156089>]}

(hibari_dev@bb3)15> brick_simple:do(tab1, [Op]).
[ok,{current_val,0}]

(hibari_dev@bb3)16> brick_simple:do(tab1, [Op]).
[ok,{current_val,1}]

The SSF is executed to create a list of do primitive operations. All attempts to examine brick keys must be done using the brick_server:ssf_peek/3 function. The brick_server:ssf_peek/3 cannot guarantee that the key will not be modified immediately after the ssf_peek/3 call and the actual execution of the DoList created by the SSF. For example, here is a case where the timestamp of the key has been modified in a race with another client. Note that the 2nd element in the return term, {current_val, N}, is included in the results despite the error. The client must perform sufficient pattern matching and/or other sanity checks to verify that the SSF and its DoList output were successful. (hibari_dev@bb3)21> brick_simple:do(tab1, [Op2]). [{ts_error,1272654442441669},{current_val,2}]

	The API of the SSF is a work-in-progress. It is used by one internal Cloudian project but otherwise does not have strong backward-compatibility requirements.

	The API of the SSF is a work-in-progress. It is used by one internal Cloudian project but otherwise does not have strong backward-compatibility requirements.

The implementation of SSFs (server-side funs) on the server side of the world is an experiment using a general framework for modifying do operations on the client side before they are executed. This experiment is implemented by the combination of:

The current implementation allows the output of the SSF to replace the {ssf, Key, Fun} tuple inside the do call’s DoList list of operations. It does not permit the arbitrary modification of the entire DoList list, nor does it permit examination of other operations in the DoList. The reasoning for the limitation is that all DoList items ultimately come from a single client in a single do operation; if the client wanted to reorder things arbitrarily, the client has the power to do that before sending the do call.

When an MD5 checksum error is detected by brick_ets.erl or one of the write-ahead log modules, dealing with the error is a bit complex:

The common_log_sequence_file_is_bad/3 function is used by gmt_hlog_common.erl to notify each brick when an MD5 checksum error is found.

The checkpoint operation is implemented by brick_ets.erl, but the API options are documented in the EDoc for brick_server:checkpoint/3.

See the section called “ETS tables” and the section called “Processes created by brick_ets.erl” for more information information about checkpointing.

The implementation of the scavenger is spread across both two modules. As a general rule, the low-level key scanning and hunk copying is done by functions in brick_ets.erl, while the higher-level coordination is implemented in gmt_hlog_common.erl.

One property worth noting here is the destructive option. If this property is false, then the scavenger will read keys but not do anything to relocate the keys. When used in combination with {skip_live_percentage_greater_than,100}, the scavenger can verify the MD5 checksums of all value blobs by reading all value blob hunks in sorted, log file sequence order.

The scavenger can be halted manually using gmt_hlog_common:stop_scavenger_commonlog/0 and resumed using gmt_hlog_common:resume_scavenger_commonlog/2.

One of the design ideas behind the scavenger is that it should try to avoid random I/O as much as possible. The scavenger uses the same write-ahead log as everyone else, and since the write-ahead log always uses sequential file writes and does a decent job of batching multiple writes with a fewer number of fsync(2) calls, write I/O is mostly sequential. However, the scavenger’s read I/O should also be as sequential as possible … so the scavenger goes through a lot of effort to read all hunks from a single log file at the same time and in sequential offset order.

The sequential read property introduced at the section called “Scavenger and code reuse” can be useful in other areas also. For example, the "fast sync" utility in brick_admin.erl.

The utility is intended for use in cases where a very large brick has had a catastrophic failure, and all data on that brick is lost. The chain replication algorithm will perform repair based on key lexicographic sort order. The key sorting order is not correlated with storage location within the common log. The result is disk read I/O patterns that are mostly random, meaning it could take days to fully repair a brick that had lost many terabytes of data.

The "fast sync" utility uses the scavenger’s infrastructure to sort live keys into log sequence and offset order (instead of lexicographic order). Ideally, this changes the read I/O pattern on the repairing brick to be more sequential than random. Once the "fast sync" utility is finished, then usual chain replication is used to fix discrepancies caused by updates made while the "fast sync" was running.

First, let’s have a short review of Hibari brick disk storage properties and goals. See the Hibari Sysadmin Guide, "Write-Ahead Logs" section and also the "Brick Initialization" section for background info.

As a consequence of these properties:

The implementation of gmt_hlog.erl tries to resolve the conflict between I/O efficiency and short startup times by storing data in files stored in two different areas:

Top-level listing of the common log’s gmt_hlog file store. 

% ls -l hlog.commonLogServer
total 24
drwxrwxr-x 9 hibari root 4096 2010-06-09 13:56 1/
drwxrwxr-x 9 hibari root 4096 2010-06-09 13:56 2/
drwxrwxr-x 9 hibari root 4096 2010-06-09 13:56 3/
-rw-rw-r-- 1 hibari root   14 2010-06-09 13:59 flush
drwxrwxr-x 2 hibari root 4096 2010-06-09 13:56 register/
drwxrwxr-x 2 hibari root 4096 2010-06-09 13:59 s/

% ls -l hlog.commonLogServer/s
total 16760
-rw-rw-r-- 1 hibari root 2701321 2010-06-09 13:58 000000000014.HLOG
-rw-rw-r-- 1 hibari root 2719724 2010-06-09 13:58 000000000015.HLOG
-rw-rw-r-- 1 hibari root 2765506 2010-06-09 13:59 000000000016.HLOG
-rw-rw-r-- 1 hibari root 2679379 2010-06-09 13:59 000000000017.HLOG
-rw-rw-r-- 1 hibari root 3008375 2010-06-09 13:59 000000000018.HLOG
-rw-rw-r-- 1 hibari root 2785571 2010-06-09 13:59 000000000019.HLOG
-rw-rw-r-- 1 hibari root  451182 2010-06-09 13:59 000000000020.HLOG
-rw-rw-r-- 1 hibari root      45 2010-06-09 13:56 Config

% ls -l hlog.commonLogServer/1
total 28
drwxrwxr-x 2 hibari root 4096 2010-06-09 13:56 1/
drwxrwxr-x 2 hibari root 4096 2010-06-09 13:56 2/
drwxrwxr-x 2 hibari root 4096 2010-06-09 13:59 3/
drwxrwxr-x 2 hibari root 4096 2010-06-09 13:57 4/
drwxrwxr-x 2 hibari root 4096 2010-06-09 13:56 5/
drwxrwxr-x 2 hibari root 4096 2010-06-09 13:59 6/
drwxrwxr-x 2 hibari root 4096 2010-06-09 13:57 7/

% ls -l hlog.commonLogServer/1/7:
total 2688
-rw-rw-r-- 1 hibari root 2745369 2010-06-09 13:56 -000000000006.HLOG

The application can request that a hunk be written into either area by the write-ahead log. As examples:

An entire log file can moved from short term storage to long term storage by renaming it to its long term name, i.e from a positive log sequence number to a negative log sequence number. This renaming operation is done at the end of a checkpoint operation by bricks that store value blobs on disk: see the "Brick checkpoint processing steps" list in Hibari Sysadmin Guide, "Brick Checkpoint Operations" section.

Log files cannot move from long term to short term storage.

Given the separation of various log hunk types into short term and long term storage, we have a couple of new properties:

	In theory, the constants to define the number of subdirectories at each level are completely flexible. In reality, use of the ?ARCH_H1_SIZE and ?ARCH_H2_SIZE macros is hard-coded in some critical areas.

There’s a fundamental tension between writing hunks to disk as efficiently as possible and flushing them to stable storage via the fsync(2) system call. The latency overhead of fsync(2) on Winchester disks is extremely high. Also, Linux-based systems can block writes to a file descriptor when an fsync(2) operation is in progress.

To mitigate the effects of fsync(2) calls, a couple of strategies are used. First, file:sync/1 calls are performed asynchronously when feasible. Second, writes are buffered by the log’s "gen_server" process while an file:sync/1 call is in progress. The "gen_server" will promise to write the hunk at a given {FileNum,Offset} location but won’t actually write the data there until the fsync(2) is finished.

The "gen_server"'s write buffering opens up a can of worms: nasty race conditions. Races with write requests, fsync requests, in-progress fsync calls, and "advance sequence number" requests are possible. This module has been extensively reviewed and tested with both unit tests and QuickCheck to eliminate those race conditions. We believe that all bugs have been eliminated, but as with many things in the software world, we don’t really know with 100% certainty.

See Hibari Sysadmin Guide, "OS Readahead Configuration" section for background.

The key metadata for disk-based value blob storage contains both the storage location of the value blob hunk and the size of the blob. The blob’s size is usually passed through the gmt_hlog API when reading the blob. First the hunk header must be read and then the value blob can be read. A function like read_hunk_summary/5 uses the blob size argument to help combine (further down in the call chain) the two reads into a single file:pread() call via the my_pread/4 function.

The my_pread/4 function is a simple application-level readahead mechanism. The two major types of read operations both have elements of readahead to them:

The code path of hunk reads, by both sequential reads during brick init and random reads of value blob hunks, is probably sub-optimal. The addition of ?MY_PREAD_MODEST_READAHEAD_BYTES to the readahead size by read_hunk_summ_ll_middle/3 is a good thing (and should probably be even bigger) in the former case and a bad thing for the latter case. Refactoring might be a good idea here. Function tracing verifies that read_hunk_summ_ll_middle/3 is definitely used by the latter case. But for random read I/O, reading the extra ?MY_PREAD_MODEST_READAHEAD_BYTES bytes is very unlikely to have any benefit and quite possibly has negative impact.

	See also, the discussion at xref:squid-flash-priming.

See the section called “Controlling MD5 checksums”.

Another part of the lazy writeback process is to manage the transition of files from the common log’s “short term” storage area to “long term” storage. See the section called “Short term vs. long term log storage” for background; see Hibari Sysadmin Guide, "High I/O rate devices (e.g. SSD) may be used" section for a discussion of using high-speed non-volatile storage such as solid-state memory disks.

If SSD or similar disk is used, then a file system for that disk should be mounted under the common log’s short term directory: .../var/data/hlog.commonLogServer/s. The do_bigblob_hunk_writeback/3 function, together with clean_old_seqnums/2, will take care of copying the ?LOGTYPE_BLOB hunks from the short term file system to the long term file system, which (we assume) will use traditional, cheap Winchester-type disk drives.

See also: the section called “Scavenger and code reuse”.

	The scavenger presents another refactoring opportunity. An earlier version was much simpler, but it relied too heavily on in-memory sorting and consumed too much memory when scavenging systems containing tens of millions of keys. The current implementation is quite brute-force now. Perhaps a more explicitly map-reduce style, while still preserving disk-based sorting, would be useful?

When the scavenger copies a ?LOGTYPE_BLOB hunk to its new storage location, the brick that owns that value blob must be notified of its new location. A brick that isn’t running & in ok state cannot (by definition) handle such notifications. If all logical bricks are not running, the scavenger should be aborted.

The register_local_brick/2 function is used by a brick’s startup to assist the common log keep track of all logical bricks that may have records stored in the common log. If a registered brick is not running when the scavenger starts, the scavenger will be aborted. Brick failures during the scavenger’s run are handled separately.

There are two major types of tracepoints that annotate the Hibari code. The macros for both types are defined in the brick.hrl header file. The underlying mechanism is provided by macros in the gmt_elog.hrl header file.

The definition of ?E_INFO/2 macro in brick.hrl. 

-define(E_INFO(Fmt, Args),
        ?ELOG_INFO(?CAT_GENERAL, Fmt, Args)).

The definition of ?ELOG_INFO/3 macro in gmt_elog.hrl. 

-define(ELOG_INFO(Msg),
        begin
            lager:info(Msg),
            gmt_elog_policy:dtrace(info, undefined, ?MODULE, ?LINE, Msg, [])
        end).

The ?DBG_* macros use the following filtering categories. The categories use integers with C-style bit masks to allow a single trace message to use multiple categories by bit-wise AND’ing the categories together.

?DBG_* categories from brick.hrl. 

%% Any component
-define(CAT_GENERAL,              (1 bsl  0)). % General: init, terminate, ...

%% brick_ets, mostly, except where there's cross-over purpose.
-define(CAT_OP,                   (1 bsl  1)). % Op processing
-define(CAT_ETS,                  (1 bsl  2)). % ETS table
-define(CAT_TLOG,                 (1 bsl  3)). % Txn log
-define(CAT_REPAIR,               (1 bsl  4)). % Repair

%% brick_server, mostly, except where there's cross-over purpose.
-define(CAT_CHAIN,                (1 bsl  5)). % Chain-related
-define(CAT_MIGRATE,              (1 bsl  6)). % Migration-related
-define(CAT_HASH,                 (1 bsl  7)). % Hash-related

Here are a couple of examples of using these macros.

Sample usage of ?E_INFO and ?DBG_ETSx/2. 

?E_INFO("~s: got unknown message ~P\n", [?MODULE, Msg, 20]).

%% Example of ?DBG_ETSx()
?DBG_ETSx({inserted, S#state.tab, Key, size(Val)}).

In the end, the result of both these macros is a call to gmt_elog_policy:dtrace/6. When dtrace_support in sys.config is set to false or DTrace/SystemTap support is not available in Erlang VM, this function does not do anything for lowest overhead.

When dtrace_support is set to true and DTrace/SystemTap support is available, this function will trigger the "user" trace probe in the dyntrace NIF module to send the trace message to DTrace consumers.

If you want to use dbg module instead of DTrace/SystemTap, Setting dtrace_support to false is recommended to avoid unnecessary calls on the user trace probe. The Erlang tracing mechanism does not rely on the probe, but will record calls on gmt_elog_policy:dtrace/6 with the arguments.

The spec of gmt_elog_policy:dtrace/6 function. 

-type log_level() :: 'emergency' | 'alert' | 'critical' | 'error'
                     | 'warning' | 'notice' | 'info' | 'debug' | 'trace'.

-spec dtrace(log_level(), integer() | undefined, module(),
             integer(), string(), [term()]) -> true | false | error | badarg.

The arguments for the dtrace/6 function are usually generated by macros for convenience. The arguments are:

You will use dtrace or systemtap command to collect trace data not only from ?DBG_* macros but also Erlang VM and Unix/Linux kernel. You can perform simple tasks by directly giving arguments to these commands, or write D or SystemTap script for more complex tasks. Note that you’ll need root privileges to run these commands and scripts.

As of Erlang/OTP R15B, we can collect the following information about Erlang VM:

You can also collect Unix/Linux kernel information such as:

Basic DTrace/SystemTap recipes will be shipped with Hibari starting v0.3.1 or v0.3.2. But until then, please refer to the following resources:

The gmt_elog:help/0 function provides a quick reference for how to use the gmt_elog tracing functions.

Example of gmt_elog:help/0 usage. 

(hibari_dev@bb3)56> gmt_elog:help().
  gmt_elog:start_tracing().
  gmt_elog:start_tracing("/path/to/trace-file").
  gmt_elog:add_match_spec().         ... to trace everything
  gmt_elog:add_match_spec(dbg:fun2ms(fun([_, target_category, _, _, _, _]) -> return_trace() end)).
  gmt_elog:add_match_spec(dbg:fun2ms(fun([Pri, _, _, _, _, _]) when Prio > 0 -> return_trace() end)).
  gmt_elog:add_match_spec(dbg:fun2ms(fun([_, target_category, target_module, _, _, _]) -> return_trace();
                                        ([_, _, other_module, 88, _, _]) -> return_trace() end)).
  gmt_elog:del_match_spec().
  gmt_elog:stop_tracing().
  gmt_elog:format_file("/path/to/trace-file").
  gmt_elog:format_file("/path/to/trace-file", "/path/to/output").
  gmt_elog:format_file("/path/to/trace-file", "/path/to/output", MatchStr|"").
ok

When we enable tracing, we’re actually tracing calls to the gmt_elog_policy:dtrace/6 function. The Erlang VM’s tracing mechanism will tell us the module name, function name, and arguments of any function call that meets its match specification. As with any tracing match specification, we can be as general (using '_' wildcards) or as specific as we wish in filtering trace events.

For the examples of add_match_spec shown above, here is an explanation

Outline of a typical tracing session. 

> gmt_elog:start_tracing("/tmp/trace-file1").
> gmt_elog:add_match_spec(dbg:fun2ms(fun([_, Cat, _, _, _, _]) when Cat == 1 -> return_trace() end)).
> %% ... trigger some activity that you wish to trace
> %% ... when you are finished, resume with:
> gmt_elog:del_match_spec().
> gmt_elog:stop_tracing().
> gmt_elog:format_file("/tmp/trace-file1", "/tmp/trace-file1.out").

If you have a low volume of trace messages, it may be convenient to use gmt_elog:start_tracing/0 to send those messages to the shell window instead of to a file.