CHASM

Crytpograph-Hash-Algorithm-Secured Mirroring

Reflections on a Mirroring Solution: End of FSoC

Those of you who have followed my blog this summer know that I have been working on CHASM, a Cryptographic-Hash-Algorithm-Secured Mirroring solution. I am sad to announce that the end of FSoC 2010 is upon us. Working on CHASM this summer has been an invaluable learning experience and a great deal of fun.

My mentors Ben Boeckel and Rob Escriva have been a joy to work with and an excellent source of information. We had a good deal of discussion over the summer through which I learned a lot. Not all discussions were about the project, some were off-topic and about Linux in general. In a recent discussion Ben provided me with an overview on how some of the major projects implement versioning, and how it related to Fedora, specifically the NEVRA system used by Koji. Overall, both of them did a _great_ job as mentors and I look forward to continuing our work together.

As for the project, I did not quite finish all that I had set out to. I still need to finish a local domain socket library that can be used by all daemons that constitute CHASM. One critical part of this did get finished and is done as a separate library. We hope it might be useful to other projects and plan to have it packaged for Fedora soon -- I will write a separate post on this later. CHASM is far from complete, but I do not plan on going anywhere; I am committed to helping see this project through and will do my best to help out where I can.

Lastly, I would like to again thank the Fedora Community for making FSoC possible. It was nice to finally be working with other people and with such a great community.

-mfm

The Git Experience

Git is, without a doubt, the SCM of choice these days. I started using Git about a year ago, beginning with my exploration of the Linux Kernel. Eventually I began using git for my own purposes, although I rarely ventured outside of a few basic commands. Working on CHASM has required me to become proficient with Git; fortunately, my summer mentors, Ben Boeckel and Rob Escriva, are well-versed in the use of the program.

A week or two into the summer coding session, I happen to make a true rookie mistake, and did a 'git reset --hard' on my current tree. Initially I was not committing my work because I was afraid of breaking the build, this lead to the stupid decision to keep about 3 days worth of work uncommitted on one branch. Sometime after, I was trying to merge with another branch, ended up not liking the results, and did the reset. That was my Git lesson the hard-way -- I am sure some people can relate.

After that, I took a side excursion to learn a little bit more about Git. One resource that proved itself useful, was a very informative lecture given by Rob. I recommend this as it is an excellent explanation into the way Git works. Rob starts with an overview of Git itself, giving a nice breakdown of the design and the theory on which it is built. He then discusses some commands pointing out how all the concepts gel together, and illuminates these points with concrete examples. Throughout the lecture you gain an insightful look into how Git can best be used; Git users of all levels will find this to be a valuable resource. (Rob does make one fallacious statement based on unsound logic, he states that the editor of choice is Vim, of course we all know Emacs is far superior!) Secondly, and of course not to be forgotten, are the Git manpages . These are some of the most complete I have ever read, and provide a number of examples, along with sample workflows.

-mfm

The Refractions of Design: Part IV

My original intent for this thread happened to be discussing the iterations of my design, so this is how I will conclude.

Only having a working knowledge of C++ definitely added to my inability to settle on a proper design -- or maybe I should say my lack of knowledge in object-oriented and structured programming. The initial design was completely imperative in style, with a lot of shared state and an inadequate use of classes. There was a plan in place and I knew where I wanted to take it, but looking back it was not the best approach for the problem.

For example, the hello message is the first message sent or received in the protocol, so I had a function:

void v0 :: upstream :: priv :: recv_hello(const boost::system::error_code& ec,
                                          const std::size_t bytes)
{
    ...
    // setup recv_msg for hello
    m_recv_msg.reset(new v0::msg_manifest());
    boost::shared_ptr<v0::msg_manifest> msg =
               boost::dynamic_pointer_cast<msg_manifest>(m_recv_msg);
    ...
}

There were similar functions for every message in the protocol, all shared a number of variables that were data members of the upstream class. Two were message variables descending from an abstract base class developed for messages; one was for sending and one was for receiving. The two statements shown above characterize their usage: a pointer to the base class is reset and then dynamically cast into the type of message expected. Every function followed a basic pattern: 1) setup the buffer, and 2) do a read or write on the socket -- if anyone has looked at the code, there is a fatal flaw in the way I read in the msg; however, I feel that could have easily been corrected.

Another major difference between the designs, is that I originally did not expect to know the read or write size, so I used a message parser class. Boost.Tribool came in handy for this purpose and the code had the pattern:

void v0 :: upstream :: priv :: recv_hello(const boost::system::error_code& ec,
                                          const std::size_t bytes)
{
    ...
    boost::tribool result(m_msg_parser.parse_hello(bytes, msg));
    if (result)
    {
        // the next state
        send_manifest_req_to_the_oracle(boost::system::error_code());
    }
    else if (!result)
    {
        m_socket.close();
        start_accept();
    }
    else
    {
        m_socket.async_read_some(boost::asio::buffer(m_msg_parser.buffer()),
                                 boost::bind(&v0::upstream::priv::recv_hello,
                                             shared_from_this(),
                                             boost::asio::placeholders::error,
                                             boost::asio::placeholders::bytes_transferred));
    }
    ...
}

The message parser class was responsible for reading in the raw data using a stateful, somewhat optimistic, algorithm for the specific message that was being received. It would then set the specific fields for the given message type to be used by subsequent functions in the upstream class.

The aforementioned design is what I was referring to as the jumping-off point in Part I. This code was all scrapped but was the genesis for the current design briefly discussed in Part III. A more thorough explanation of the current design can be found in doc/chasm-p2p-design.rst within the repository.

In conclusion, I can not say for a fact that my initial design was good or bad, it happened to not be right for the project. The design process has been an enlightening experience; it has provided an insightful look into the process that I was severely lacking. The open-source development model is such a great way to learn, I can not even imagine ever working on closed-source software again.

-mfm

The Refractions of Design: Part III

Both upstream and downstream can have multiple connections concurrently, at a high level this is accomplished using async calls. Each connection instantiates a connection chain, which is functionally a state machine where each state is a message in the protocol. A message framework provides the structure for sending and receiving. It consists of two classes send_message and recv_message that take a state object, either a send_state or recv_state, respectively. The state object handles preparing and processing the message by implementing the operations used by send_message and recv_message.

class send_state
{
    ...
    // send operations
    virtual void prepare(connection_ptr conn, chasm::buffer& msg)
            throw (std::bad_alloc);
    virtual recv_state_ptr next_state() const;
    ...
};

Although briefly more than one state per connection will exist, usually there will only be one at any given point in time. The ephemeral nature of the states is accomplished through pointers and callbacks. A state is instantiated as a shared pointer and then started, shortly after that an async call will be made that will unwind the stack and the calling object will be destroyed. Callbacks provide a mechanism for keeping objects alive. The state becomes the callback through the use of bind and the this pointer. Following is a snippet of code demonstrating the concepts used:

void v0 :: send_message :: start()
{
    ...
    m_state_obj->prepare(m_conn, m_msg);
    ...
    send();
}

void v0 :: send_message :: send() const
{
    boost::asio::async_write(*m_conn->_socket, boost::asio::buffer(m_msg),
                             boost::bind(&v0::send_message::goto_next_state,
                                         shared_from_this(),
                                         boost::asio::placeholders::error));
}

void v0 :: send_message :: goto_next_state(...) const
{
    ...
    v0::recv_state_ptr state_obj = m_state_obj->next_state();
    if (state_obj.get())
    {
        boost::shared_ptr<v0::recv_message>
            rm(new v0::recv_message(m_conn, state_obj));
        rm->start();
    }
    ...
}

...

-mfm

The Refractions of Design: Part II

I would like to digress a bit and talk about the whole design of the CHASM peer-to-peer protocol, eventually leading to design specifics with code samples. The material in this post is for a technical document I am writing, so it may come off as dry and boring to most. For those whose native tongue is C or C++, the new direction of this thread will have its redeeming qualities in the end.

CHASM Peer-to-Peer Design

The Boost.Asio ("asio") library is used for communicating over the network, all calls are made using asynchronous variants. Asynchronous calls were deliberately chosen to provide a level of concurrency within the daemon without the need for multiple threads or forking. Two functions are primarily used: async_read and async_write.

The chasm-p2p daemon is composed of two central parts, the downstream client ("downstream") and upstream server ("upstream"). Downstream uses a timer object to periodically check for manifest revisions and will make connections to one or more upstream nodes when necessary. Both of these components follow a similar structure utilizing the pimpl idiom for separation of interface and implementation. The public interface of each is defined in a downstream and upstream class with the implementation being in downstream::priv and upstream::priv, respectively.

A protocol namespace is used along with a unique version number namespace. The version number depends on the official peer-to-peer protocol in use and will be utilized for protocol version negotiation between upstream and downstream. Specifics of this functionality are yet to be determined.

...

-mfm

chasm-p2p(8)

NAME

chasm-p2p - CHASM peer-to-peer server and client

SYNOPSIS

chasm-p2p  [--no-daemon | -f] [--host | -H] [--help | -h]
           [--port | -p] [--timer | -t] [--version | -V]
           [--verbose | -v]
           [COMMAND]

DESCRIPTION

The chasm-p2p daemon is responsible for the sending and receiving of blobs. It consists of two major modes called upstream and downstream. The normal function is to be in both modes simultaneously.

Upstream is a server, it does the sending of blobs. Once a connection is established, a manifest revision request will be read and blobs will be transferred accordingly.

Downstream is a client that receives blobs. It uses a timer that notifies it to periodically check for manifest revisions. If a revision exists, a connection to one or more upstream servers will be made.

Both upstream and downstream are not responsible for determining what blobs are sent or received, the Pool-Manifest Oracle is in charge of that. The actual storage of the blobs is the job of the Pool Manager. chasm-p2p is solely responsible for the transfer of blobs and is used as an intermediary for the negotiation. The protocol version in use specifies the extent of each components role.

The Refractions of Design: Part I

"...the very best designers produce structures that are faster, smaller, simpler, cleaner, and produced with less effort."

Frederick P. Brooks Jr., The Mythical Man-Month

I did not know the real project was not in the code but in the design. A program that is well designed is not merely an accident: it is an act of human thought that transforms an idea into a tangible structure. I do not consider myself a great designer. In fact, I am not sure if I would know great design if I saw it. My goal is to learn what great design is, to strive for this ideal that Frederick P. Brooks Jr. speaks of. Thankfully, I have help in achieving this goal.

Not being experienced in design, I have had to learn numerous design patterns, patterns I previously knew only by name. Learning these, however, has not been a magical solution by any means. With a plethora of possible designs and my having only an abstract understanding of each, this has only added to my inability to decide on any one design. In the end, I did settle on a primitive design that has proven a good jumping-off point.

So, the design of the CHASM peer-to-peer protocol is now going through its second iteration in code -- many more never made it past my white-board. It has been an invaluable learning experience to receive feedback on the design from my mentors Ben Boeckel and Rob Escriva. After much discussion with them, I will implement a new design to reduce redundancy and temporary-state variables. This will increase clarity and provide a cleaner design.

In Part II, I will discuss the design in greater detail and provide a code snippet.

-mfm

[chasm-announce]

CHASM now officially has a mailing list! The lists are posted at lists.robescriva.com. We have the traditional low-volume chasm-announce and the always exciting, and my personal favorite, chasm-dev lists. We encourage all people interested in changing Linux mirroring, even those working on competing products, to join.

-mfm

A Look Into the Mirror: CHASM

The CHASM protocol is still a work-in-progress; however, the part of the protocol that pertains to peer-to-peer communication is fairly complete. All communication between nodes will be application level messages as described in the technical design document. Any feedback about the design is more than welcome; my email address can be found in my git tree and we do have an irc channel #chasmd, so feel free to stop in and start up a conversation.

For the implementation of the protocol, I will be using Boost.Asio and all communication will be done using asynchronous calls -- at least for this initial version. The upstream (server) node will be responsible for receiving and servicing connections. The downstream (client) node will be on a timer that periodically checks with the Pool-Manifest Oracle for manifest modifications, and, when necessary, will connect to one or more upstream nodes to update the collection. Both nodes will communicate with the Pool Manager (handles active blobs) to read and write blobs.

In closing, my git tree is here and soon more of my actual code will be pushed there. Again, for feedback on anything I mentioned or on coding issues that you find, please contact me.

-mfm

Reflections on a Mirroring Solution

Hello Fedora Community! Thank you all for making the Fedora Summer of Code possible. I am excited to announce that I will be working on CHASM this summer with my two mentors Ben and Robert. They have developed a great solution to a well-known problem, and I am grateful for the opportunity to work with them.

In short, CHASM is a Cryptographic-Hash-Algorithm-Secured Mirroring solution, it provides a true peer-to-peer network for keeping mirrors in sync. rsync, the canonical tool used for mirroring, has many deficiencies as it pertains to mirroring large repositories. Existing solutions that solve problems inherent to rsnyc, have used a top-down approach, hence, continuing their reliance on rsync for low-level functions. CHASM has been designed specifically for mirroring from the bottom-up. It will provide a stand-alone solution as well as a modern foundation for other high-level tools to run on.

Here is my FSoC proposal which provides a brief insight into who I am, along with my responsibilities and projected timeline for the project. The CHASM site contains more information and has an Atom feed for those interested in following all developer posts.

-mfm

Copyright © 2010 Robert Escriva ¦ Powered by Firmant