Friday, June 20, 2014

Homemade Internet Service Relay (X)

Ready for receive? Receive is much more complicated than send. Similar to Send, Read happens mostly within Connection. As an overview, Connection spread the work for receive to TransportReceiveActor and ChannelReceiveActor.

TransportReceiveActor deals with the data from transport, demultiplex it, and send to ChannelReceiveActor.
ChannelReceiveActor response to Channel ReadRequest by providing data provided by TransportReceiveActor, after copying back to Channel, ChannelReceiveActor will response to TransportReceiveActor the data is consumed. This is to free buffer to allow space for further receives.

Here is a more detailed view:

TransportReceiveActor maintains a buffer – this buffer is used to store data from TCP transport. Before this buffer is full, TransportReceiveActor keep requesting transport for data. This buffer also serve the purpose of choking the sender. Because of we are at low capacity to process the data, the buffer will remain not empty and receive will not proceed, effectively stopping sender because its TCP sliding window is used up.

After data arrives in the buffer, TransportReceiveActor decodes them. Decoding is a simple state machine – read the channel, read the size, read size bytes, and repeats. However, since data is not available, the state machine must stop when there is no data, and the state is saved until the next packet arrives. Here the unread count is increased by the total size of the payload.

The decoded payloads are then sent to ChannelReceiveActor, one complication arise here if the ChannelReceiveActor is not there yet. This is a new channel! There must be someone else trying to accept the Channel, the payload will be enqueued in pending accept list. If there are any pending accept request, the accept request is satisfied. Beyond that, the data will be sent to the ChannelReceiveActor.


After ChannelReceiveActor received the data, it enqueues it into a queue. The queue is then checked to see if there are any pending read request, and if there is one, try to fill the buffer and return. After filling the buffer, the used count is send back to TransportReceiveActor to reduce the unused count. Once the unused count goes back to 0, transport receive can start again.

Homemade Internet Service Relay (IX)

Writing data is considerably simpler, so we will start with looking at write. Channel.Write() simply calls Connection.Write(), so the bulk of the logic is in Connection. When Connection receive a Write request, it breakdown the request into frames. Each frame contain a simple header that indicate which Channel it comes from, and the size of the frame so that it can be decoded later, and the bulk of the frame is then forwarded to SenderActor for processing. Note that while frame headers are newly allocated memory blocks, the frames are simply created using integer indexes so that the buffer is not copied.

After receiving frames, SenderActor keeps them in a list of SegmentHandlePairs. A SegmentHandlePair is a pair of Segment (of data to send) and a Completion handle to notify the sender the send is completed. Only the last frame has the segment handle pair attached. Normally it will just send the data through the socket, but it must be careful not to do it when the last sending is in progress.

On writing to transport completed, TCP will give us a notification how many bytes are written. SenderActor will receive this notification and then go back to the segment handle pairs. A scanning of the list will be done to see if there are completion handle to update. It is quite probable that not all data are sent, in that case we need to update the list with the right index, and then request the send to transport again.

These logic are best illustrated by an example. For simplicity, the frame size is 8 and the channel id/size take 1 byte.
Write request with 10 bytes comes from channel 1
1 2 3 4 5 6 7 8 9 10
The data are packed into frames
[Channel 1, Size 8] 1 2 3 4 5 6 7 8 [Channel 1 Size 2] 9 10
The frames are sent to SenderActor, sender Actor marks the last segment with the completion handle
[Channel 1, Size 4] 1 2 3 4 [Channel 1 Size 4] 5 6 7 8 [Channel 1 Size 2] 9 10
Sender Actor send these to the transports
Write request with 7 bytes comes from Channel 2
The data are packed into frames
[Channel 2, Size 7] A B C D E F G
[Channel 1, Size 4] 1 2 3 4 [Channel 1 Size 4] 5 6 7 8 [Channel 1 Size 2] 9 10 [Channel 2, Size 7] A B C D E F G
Sender Actor can’t send the data yet because it is transport write in progress.
Transport reports 11 bytes are written
Sender Actor updates its data structure
[Channel 1, Size 4] 1 2 3 4 [Channel 1 Size 4] 5 6 7 8 [Channel 1 Size 2] 9 10 [Channel 2, Size 7] A B C D E F G
Sender Actor realize there are more data to send, so it request transport to send these again.
Transport reports 6 bytes are written
Sender Actor updates its data structure
8 [Channel 1 Size 2] 9 10 [Channel 2, Size 7] A B C D E F G
Sender Actor knows it needs to notify a completion handle a send is completed.
Sender Actor realize there are more data to send, so it request transport to send these again.


Hopefully one can appreciate how actor makes the concurrency issue trivial here. If we had to deal with concurrency here it would be more complicated. With SenderActor, we can happily ignore the fact that the Channels and transport are concurrent because we are processing the messages one by one, the data structure need no locks.

Homemade Internet Service Relay (VIII)

Now we switch to the highest level of abstraction that we provides. To use the library, the client must first establish a TCP connection, and then constructs a Connection object.

public Connection(Socket socket, ConnectionType connectionType)

Since the connection is shared, one cannot send/receive data through the Connection directly, instead, one create Channels. On the client side (i.e. initiator), he can simply create a channel by calling Connect.

public Channel ConnectChannel()

Unlike TCP, the call is synchronous because the connection is already established. Currently we do not check if the other side is ready to accept this connection, we simply assumes the server eventually will. This could be improved in the future.

On the other hand, the server side will need to wait for a Channel establishment request, this is done by calling Accept

public IAsyncResult BeginAcceptChannel(AsyncCallback callback, object state)
public Channel EndAcceptChannel(IAsyncResult ar)

This call is necessarily asynchronous not because it involves I/O, but because it blocks on waiting.
Channel itself is just a Stream. This design make it very easy for other stream processing code (e.g. serialization) to use the library without modification. In addition, it provides a teardown that stop sending data to model TCP one-way shutdown.

public void StopSending()
public IAsyncResult BeginStopSending(AsyncCallback callback, object state)
public void EndStopSending(IAsyncResult ar)
public Task StopSendingAsync()

In the next post we will talk about how the connector work inside.

Homemade Internet Service Relay (VII)

As with any networking textbook, we could go top down or bottom up. To give the journey an overview, we talk about the lowest level (i.e. TCP transport) abstraction that we use and the highest level abstraction we provide for caller. Interesting reader will then get a sense what could be in the middle.

The abstraction we use from TCP transport is the Sockets API, in particular, these few calls are used.
public IAsyncResult BeginReceive(byte[] buffer, int offset, int size, SocketFlags socketFlags, AsyncCallback callback, object state);

public IAsyncResult BeginSend(IList<ArraySegment<byte>> buffers, SocketFlags socketFlags, AsyncCallback callback, object state);

The establishment/teardown of the socket (i.e. TCP bind/listen/accept/connect/close) is outside of the scope of this library, this library simply assumes one.

Note that we use a complicated variant for the send method. The flexibility of the sockets API to read from discontinuous regions to send data allows me to avoid copying data frames comes from various data streams.


The current version ignored transport errors – a huge mistake – we should improve it.

Homemade Internet Service Relay (VI)


Before we proceed to the detailed design of the service, I must confess I screwed up in the initial versions. I underestimate how difficult it is to code this up. On one hand, there isn’t much logic at all, this is not graph matching algorithm, or assembly hacking techniques. On the other hand, there are many threads, and at any time there are incomplete messages, and error conditions. Complexity grows exponentially when all these get coupled together. We must decouple them.

My first revision involves re-thinking about concurrency. At its core our concurrency problem is about shared mutable states, and if we can be sure no such thing existed, we can freely code without concerning about concurrent edits.

Think about the human world, everyone thinks at the same time, that’s okay because brains are not shared, they don’t interfere. When a group of people work together, they talks and listen, and that message is shared. However, it is immutable and is therefore also safe. We can model our computation as such. Actors are objects that receives message, access it only by reading it, and can freely modify its own state. They can also send messages, but they never reach each other directly without going through messages. That way we can guarantee the no shared mutable state guarantee.

In typical actor system implementation – such as Akka, these constraints (e.g. always send message, don’t call methods, messages are immutable) are enforced by the framework though various means (e.g. encapsulating the actor object instances, staying immutable in a functional language, serializing the message), but in mine, it is only the spirit that is important. I enforced these constraint simply by following them myself, this is done so because they is no need to invest in a framework, and in general that is more performant.
Each actor is simply modeled as a concurrent safe queue of messages called a mailbox, each actor override the OnReceiveMessage() method to respond to the message object, make sure it don’t modify the message object, and that’s it. When a message is sent to an actor, if the actor is not already processing a message, a thread is requested from the ThreadPool and will call the OnReceiveMessage() on it.

Last but not least, an actor can voluntarily terminate itself, which is done by returning ActorContinuation.Done in the OnReceiveMessage call, otherwise the actor should return ActorContinuation.BlockOnReceive to get itself ready to process another message.

With this programming model, I can focus on the next level without worrying about concurrency now.

Homemade Internet Service Relay (V)

To achieve high performance, my implementation do two things. Asynchronous I/O and no redundant copies.

First, it never block any threads on I/O requests. This can reduces resource consumption. When multiple requests arrives when all threads are in use (blocked or not), requests need to be served by new threads. Thread creation takes significant amount of time. If we eliminate the possibility that a thread is blocked on I/O, we significantly decrease the need for thread creation.

Practical experience is, if you can make sure the server don’t block on I/O for all operations within a request, then we can save significant amount of time. But if some operation block on I/O anyway, then we are essentially in the situation of having one thread per request, and doing asynchronous I/O will be meaningless.


Another observation is that copying of the data take significant amount of time as most of the relay is handshaking the messages and very little other processing. The design attempts to reduce to amount of copy to minimum, except from the stream abstraction we are required to copy the data to the user specified buffer, which we cannot avoid if we wanted to reuse the same abstraction.

Homemade Internet Service Relay (IV)

Once I started with the implementation, difficulty arise when we have more than one connection. There is just one TCP connection between the internal networks and there are more than one connections between the external world and the internal service. Clearly there is a need to multiplex more than one connections into a single connection. The situation is very much like multiple TCP connections are multiplexed a single piece of network cable.

When multiple TCP connections use the same network cable, the input is broken down into multiple packets. At any time, only one packet got written to the cable. On the receiving end, the network pick up the packet, look at the header, and dispatch the packet to the right connection by port number.

In our case, we will design our multiplexing the same way. First, we define streams. Streams are simply a user-level connection, being multiplexed on top of the underlying TCP connections. Each stream break down its input into frames (similar to an IP packet), and then they are sent through the connection. On the receiving end, the packets are received and re-assemble into a data stream.

Streams are created when a new stream ID is sent. On the receiving a new stream ID a new stream object is created if there are pending accepts. The programming model is the same as normal TCP programming.

Homemade Internet Service Relay (III)

Instead of relaying messages, we can relay connections. This way the relay is completely agnostic to whatever the service is doing, which is good because that will allow a wide range of services to be relayed without being known or modified at all. Case in point could be Remote Desktop. We couldn’t possibly change remote desktop, or we are interested in knowing the details of the protocol. But if we relay the whole connection, we can make it possible to relay any service on top of TCP.

With just a tiny twist from above, this can be easily done.

Step 1) The relay client service, live in the internal network, make a TCP connection to the Azure relay server service.

Step 2) The Azure relay server service make itself available to the Internet.

Step 3) When Azure relay server service receives a connection, it sends to the relay client service through the connection it established.

Step 4) The relay client service connects to the internal service

Step 5.1) If the Azure relay server service receive a message, it sends to the relay client service and the relay client service send to the connection.

Step 5.2) If the relay client service receive a message, it sends to the Azure relay server services and the Azure relay server services send to the client.

Step 6.1) If the Azure relay server service receive a connection close, it sends to the relay client service and the relay client service close the connection.

Step 6.2) If the relay client service receive a connection close, it sends to the Azure relay server service and the Azure relay server service close the connection.


That is something I wanted to build.

Homemade Internet Service Relay (II)

The key idea to make service hosted in an internal network available through the Internet is to allow the external world to send a message actively and get a response. Normally this is done by the external world to connect to the service through a new TCP connection and the service accepts, but this is frequently impossible because it is blocked by the firewall.

However, most internal network do NOT block their user from connecting to somewhere else, for example, to browse the Internet. This creates an opportunity. TCP connections are actually full duplex, meaning that once a connection is established, either side can initiate to send a message. Here we will demonstrate how that can be leveraged to create an illusion that the internal network is available.

Step 1) The internal service make a TCP connection to the Azure service.

Step 2) The Azure service make itself available to the Internet.

Step 3) When Azure receives a message, it sends to the internal service through the connection it established.

Step 4) When Internal Service processing completes, it sends the response to Azure through the connection is established.

Step 5) When Azure receives the message, it send the client as a response.

Overall, to the client, it looks just like Azure is the internal service.

Homemade Internet Service Relay (I)

Inspired by the Service Bus Relay – I am interested in building a relay myself utilizing the same basic principle. In the coming series of posts, I will document how I build a usable Internet Service Relay leveraging Azure – stay tuned.

Andrew Technical Blog is now open

Sometimes, I have some idea and got it implemented, but very often, the implementation is either lost or saved somewhere, but the reasoning about that idea is lost.

This is unfortunate – because sometimes those are good ideas.

This blog is used to save those reasoning in terms of blog posts. I hope this can be good for my future reference, as well as sharing those ideas to others.

My ideas are quite diverse, so there is not a single thing (or theme) that covers them. This is not a distributed system blog, or a game programming blog, but just a general blog that talks about various ideas.