Tuesday, May 06, 2008

High peformance TCP server using completion ports

Completion ports were first introduced in Windows NT 4.0. This technology makes simultaneous asynchronous I/O possible and extremely effective. When building high performance network software one has to think of effective threading model. Having too many or too little server threads in the system can result in poor server performance.


The goal of a server is to incur as few context switches as possible by having its threads avoid unnecessary blocking, while at the same time maximizing parallelism by using multiple threads. The ideal is for there to be a thread actively servicing a client request on every processor and for those threads not to block if there are additional requests waiting when they complete a request. For this to work correctly however, there must be a way for the application to activate another thread when one processing a client request blocks on I/O (like when it reads from a file as part of the processing). (read more...)

Smart reader may admit that I/O completion ports (IOCP) are not directly available in .NET. Well, that was pure truth until SP1 of .NET 2.0. From .NET 2.0 SP1 this marvelous technology can be accessed using following Socket class methods:
  • AcceptAsync
  • ConnectAsync
  • DisconnectAsync
  • ReceiveAsync
  • SendAsync
  • and other XxxAsync methods
In one of my previous posts about receiving variable length messages I used BeginXXX/EndXXX asynchronous approach. Main drawback of this approach is presence of the repeated allocation and synchronization of objects during high-volume asynchronous socket I/O. That is because BeginXXX/EndXXX design pattern currently implemented by the System.Net.Sockets.Socket class requires a System.IAsyncResult object be allocated for each asynchronous socket operation.

Completion port approach on the other hands avoids the above mentioned problems altogether. Asynchronous operations are described by instances of SocketAsyncEventArgs. These objects can be reused by the application, more over, application can create as many SocketAsyncEventArgs objects that it needs to perform well under sustainable load.

The pattern for performing an asynchronous socket operation with this class consists of the following steps:
  1. Allocate a new SocketAsyncEventArgs context object, or get a free one from an application defined pool
  2. Set properties on the context object to the operation about to be performed (the completion callback method, the data buffer, the offset into the buffer, and the maximum amount of data to transfer, for example).
  3. Call the appropriate socket method (XxxAsync) to initiate the asynchronous operation
  4. If the asynchronous socket method (XxxAsync) returns true, in the callback, query the context properties for completion status
  5. If the asynchronous socket method (XxxAsync) returns false, the operation completed synchronously. The context properties may be queried for the operation result
  6. Reuse the context for another operation, put it back in the pool, or discard it
In How to Transfer Fixed Sized Data With Async Sockets I've presented server code that uses BeginXXX/EndXXX model for data receive handling. In the next post I'll show how that code can be rewritten to use IOCP server model.
Sample code of IOCP based TCP server

Sunday, April 20, 2008

What is peeking in TCP and why should it be avoided

Typical network receive operation via sockets looks like this:

socket.Receive(userBuffer, userBuffer.Length, SocketFlags.None);

In the above code received data is moved from Winsock internal buffers into the buffer specified by the user. Next time when socket.Receive is called another data chunk from TCP stream will be moved into the userBuffer.



On the other hand there is a receive method that is not moving data from system to user buffer but instead copies it. This process is called peeking.


Following code is peeking data from system buffer:
socket.Receive(userBuffer, userBuffer.Length, SocketFlags.Peek);

Every time Receive is called it copies the very same data from internal (system) buffer into user buffer.

One may ask why do wee need this peeking at all and why it is present in sockets API?

Peeking was introduced to preserve compatibility with Unix BSD sockets.
So, where one can use peeking? The answer is nowhere, do not use it at all when doing network I/O. Peeking is very inefficient and must be avoided.

Monday, April 14, 2008

Change socket send and receive timeout

Sometimes synchronous Socket I/O methods like Send or Receive take too long to complete or produce an error (exception). This default behavior can be changed using socket options. Namely, SocketOptionName.SendTimeout and SocketOptionName.ReceiveTimeout.

Here's code sample how to get/set these socket options:


//get socket receive timeout
int timeout = (int)socket.GetSocketOption(SocketOptionLevel.Socket,
SocketOptionName.ReceiveTimeout);

//set socket receive timeout
int timeout = 0;
socket.SetSocketOption(SocketOptionLevel.Socket,
SocketOptionName.ReceiveTimeout, timeout);

Nearly the same code is for SendTimeout socket option

//get socket send timeout
int timeout = (int)socket.GetSocketOption(SocketOptionLevel.Socket,
SocketOptionName.SendTimeout);

//set socket send send timeout
int timeout = 0;
socket.SetSocketOption(SocketOptionLevel.Socket,
SocketOptionName.SendTimeout, timeout);


When you do not use synchronous I/O but instead use BeginXXX/EndXXX or non-blocking sockets then you can let the system handle long lasting I/O. You no longer need to handle timeouts, since your code is not waiting for the I/O to complete.

If you still want to wait for asynchronous operation to complete you can use AsyncWaitHandle property of the IAsyncResult interface.

IAsyncResult result = socket.BeginReceive(/*parameters come here*/);
//here we can wait for 5 minutes for completion of receive operation
result.AsyncWaitHandle.WaitOne(5*60*1000, false);

Thursday, April 10, 2008

Proper way to close TCP socket

This question arises very often in the developers communities.
For simplification I'll talk about synchronous sockets.

Generally, the procedure is like this:

  1. Finish sending data

  2. Call Socket.Shutdown with SocketShutdown.Send parameter

  3. Loop on Receive until it returns 0 or fails with an exception

  4. Call Close()

Here's a small sample in pseudo code that is very similar to C# :)

void CloseConnection(Socket socket)
{
socket.Send(/*last data of the connection*/);
socket.Shutdown(SocketShutdown.Send);

try
{
int read = 0;
while( (read = socket.Receive(/*application data buffers*/)) > 0 )
{}
}
catch
{
//ignore
}
socket.Close();
}

If first and third steps are skipped - data loss can happen.

Things become more complicated when using asynchronous sockets.
To prevent data loss while closing connection: termination logic can be added to the data exchange protocol.
For example, it can be some kind of termination message (depends on data protocol). When peer receives message of this kind, it can proceed with connection termination logic described above.

Another way is to put socket in a blocking mode (if socket was in non blocking mode) and close the connection in the way described above.

When designing network application one has to think also about its connection closing procedure. The purpose of proper connection close is prevention of data loss.

Sunday, March 23, 2008

Part 2: How to Transfer Variable Length Messages With Async Sockets

In my previous post about transferring data in the async manner. I was talking about designing a small data exchange protocol to transfer a message over the network. All I/O was done in the async manner using BeginXXX/EndXXX pattern. Code on that post was handling single message only. However, in the real world it rarely happens that only one message is being transferred over single connection. It is more common to expect that several messages can be received by the peer.



Data exchange protocol contains messages prefixed by the size. Size prefix has fixed length.

Prefixing data with its size is the corner stone of the simple data transfer protocol introduced in the previous example. There is no problem transferring multiple messages over single connection. Remote peer should have no problem distinguishing separate messages from the data stream.
This post will provide code sample how to read multiple messages from the network.

What to expect when multiple messages arrive at the server?
While dealing with multiple messages one has to remember that receive operation can return arbitrary number of bytes being read from the net. Typically that size is from 0 to specified buffer length in the Receive or BeginReceive methods.

Our data exchange format is illustrated on the image above.
Peer code after receiving number of bytes should be able to answer what part of the message it has just received. Is it part of the size prefix or it is a message body?
Sometimes, several messages can be received at one Receive call.

Let's see what situations we can encounter while processing incoming data:
- received data contain only data size prefix
- received data contain part of the data size prefix
- received data contain prefix and part of the data
- received data contain prefix, message data and part of the prefix of the next message
- received data contain prefix, message, prefix of the next message and part of its body.



When developing data processing code one has to expect the above illustrated scenarios will happen.

Here's the server code that handles conditions described above. I present here only server callback function. Client sending code can be obtained from the previous post .


private void ServerReadCallback(IAsyncResult ar)
{
try
{
ServerState state = (ServerState)ar.AsyncState;
Socket client = state.Client;
SocketError socketError;

int dataRead = client.EndReceive(ar, out socketError);
int dataOffset = 0; //to simplify logic
int restOfData = 0;

if (socketError != SocketError.Success)
{
client.Close();
return;
}

if (dataRead <= 0)
{
client.Close();
return;
}

while (dataRead > 0)
{
//check to determine what income data contain: size prefix or message
if (!state.DataSizeReceived)
{
//there is already some data in the buffer
if (state.Data.Length > 0)
{
restOfData = PrefixSize - (int)state.Data.Length;
state.Data.Write(state.Buffer, dataOffset, restOfData);
dataRead -= restOfData;
dataOffset += restOfData;
}
else if (dataRead >= PrefixSize)
{ //store whole data size prefix
state.Data.Write(state.Buffer, dataOffset, PrefixSize);
dataRead -= PrefixSize;
dataOffset += PrefixSize;
}
else
{ // store only part of the size prefix
state.Data.Write(state.Buffer, dataOffset, dataRead);
dataOffset += dataRead;
dataRead = 0;
}

if (state.Data.Length == PrefixSize )
{ //we received data size prefix
state.DataSize = BitConverter.ToInt32(state.Data.GetBuffer(), 0);
state.DataSizeReceived = true;
//reset internal data stream
state.Data.Position = 0;
state.Data.SetLength(0);
}
else
{ //we received just part of the prefix information
//issue another read
client.BeginReceive(state.Buffer, 0, state.Buffer.Length,
SocketFlags.None, new AsyncCallback(ServerReadCallback),
state);
return;
}
}

//at this point we know the size of the pending data
if ((state.Data.Length + dataRead) >= state.DataSize)
{ //we have all the data for this message

restOfData = state.DataSize - (int)state.Data.Length;

state.Data.Write(state.Buffer, dataOffset, restOfData);
Console.WriteLine("Data message received. Size: {0}",
state.DataSize);

//store received messages
//lock(messages)
// messages.Add(state.Data.ToArray());

dataOffset += restOfData;
dataRead -= restOfData;

//message received - cleanup internal memory stream
state.Data.SetLength(0);
state.Data.Position = 0;
state.DataSizeReceived = false;
state.DataSize = 0;

if (dataRead == 0)
{ //no more data remaining to process - issue another receive
client.BeginReceive(state.Buffer, 0, state.Buffer.Length,
SocketFlags.None, new AsyncCallback(ServerReadCallback),
state);
return;
}
else
continue; //there's still some data to process in the buffers
}
else
{ //there is still data pending, store what we've
//received and issue another BeginReceive
state.Data.Write(state.Buffer, dataOffset, dataRead);

client.BeginReceive(state.Buffer, 0, state.Buffer.Length,
SocketFlags.None, new AsyncCallback(ServerReadCallback), state);

dataRead = 0;
}
}
}
catch (Exception ex)
{
Console.WriteLine(ex.ToString());
}
}

Wednesday, February 20, 2008

How To Go Slow: Summing Arrays



In this entry I'll talk about thrashing when iterating over complex arrays.

Consider a square array with the size of N = 10000;
Now, consider the code that summs elements of the square array

for (int row = 0; row < N;, ++row)
for (int col = 0; col < N; ++col)
sum += A[row, col];

Or on the other hand:
for (int col = 0; col < N; ++col)
for (int row = 0; row < N; ++row)
sum += A[row, col];


How do you think is there any difference between these two approaches?
The answer is yes - difference is quite noticeable... in terms of performance.

First approach takes about 1 second to complete, while the second - nearly 14 seconds! How can this be you may ask?

The answer is memory layout, caching and thrashing.

In .NET much like in C++ arrays are stored row-wise in contiguous memory. So, if you will access array rows first you will access contiguous memory. That means that the next data item you need will be be in pipeline, cache, RAM, and the next hard drive sector before you need it will be in the cache.

But if you go through columns first then you will be repeatedly reading just one item from each row before reading from the next row. As a result your system's caching mechanism and lookahead will fail to give you recent items, and you will waste a lot of time waiting for RAM, which is about three to five times slower than cache. It can get even worse, you may end up waiting for the hard drive. HDD can be millions of times slower than RAM if accessed in large random jumps.

The moral: the less sequential your data access, the slower your program will run :)

Friday, February 01, 2008

When string.ToLower() is Evil


Did you know how evil string.ToLower() can sometimes be?

Let me explain...

Very often I see code similar to this:

void DoBadAction (string val)
{
if (val.ToLower() == "someValue")
{ //do something
}
}

The code above can lead up to 4 times in performance loss when doing string comparison operations.

Best method to do such kind of case insensitive comparison is using string.Equals(...) method.

void DoGoodAction(string val)
{
if (val.Equals("someValue", StringComparison.OrdinalIgnoreCase))
{ //do something
}
}

Why is it so? The reason lies in the string type peculiarity - it is immutable.

Since it is an immutable - string.ToLower() will always return new string instance. Thus generating extra instance of string on every ToLower() call.

Detailed information about string.Equals with StringComparison enumeration can be found here.
Other performance related tips and tricks can be found here.

Wednesday, January 23, 2008

How to Transfer Fixed Sized Data With Async Sockets

This post was inspired by the discussion in MDSN forums.

Discussion on that forum showed that there is misunderstanding of the principles of data transfer across the network, especially in asynchronous way.

I wrote simple client/server application that demonstrates usage of asynchronous sockets to transfer fixed sized data from client to server.

Usually data exchange between server and client is done in some special way (or special order). Such an order is called communication protocol.
More information on network and communication protocols can be found here and here

The sample here also uses communication protocol. It is very simple, client prefixes the data with 4 bytes that hold data size. Format of the data that will go to the wire can be shown like this [4 bytes - data size][data - data size].

Here comes implementation with short comments. Asynchronous communication via sockets involves methods like BeginReceive/EndReceive - for data receiving and BeginSend/EndSend for sending. The sample demonstrates only how async sockets work and the fact that data is received in the stream like way.
More information about network programming can be found here


Server

At first we define the state that will be passed between async calls. State is defined as following:


///
/// Server state holds current state of the client socket
///

class ServerState
{
public byte[] Buffer = new byte[512]; //buffer for network i/o
public int DataSize = 0; //data size to be received by the server
public bool DataSizeReceived = false; //whether prefix was received
public MemoryStream Data = new MemoryStream(); //place where data is stored
public Socket Client; //client socket
}

Server is listening for the clients using Socket.Accept method.
Here is the server listening loop:

//server listening loop
while (true)
{
Socket client = serverSocket.Accept();
ServerState state = new ServerState();

state.Client = client;
//issue first receive
client.BeginReceive(state.Buffer, 0, state.Buffer.Length, SocketFlags.None,
new AsyncCallback(ServerReadCallback), state);
}

When data comes to the client socket ServerReadCallback is called. There server can read received data and process it.

Here is the implementation of that method:

private void ServerReadCallback(IAsyncResult
{
ServerState state = (ServerState)ar.AsyncState;
Socket client = state.Client;
SocketError socketError;

int dataRead = client.EndReceive(ar, out socketError);
int dataOffset = 0; //to simplify logic

if (socketError != SocketError.Success)
{
client.Close();
return;
}

if (dataRead <= 0)
{ //connection reset
client.Close();
return;
}

if (!state.DataSizeReceived)
{
if (dataRead >= 4)
{ //we received data size prefix
state.DataSize = BitConverter.ToInt32(state.Buffer, 0);
state.DataSizeReceived = true;
dataRead -= 4;
dataOffset += 4;
}
}

if ((state.Data.Length + dataRead) == state.DataSize)
{ //we have all the data
state.Data.Write(state.Buffer, dataOffset, dataRead);

Console.WriteLine("Data received. Size: {0}", state.DataSize);

client.Close();
return;
}
else
{ //there is still data pending, store what we've
//received and issue another BeginReceive
state.Data.Write(state.Buffer, dataOffset, dataRead);

client.BeginReceive(state.Buffer, 0, state.Buffer.Length,
SocketFlags.None, new AsyncCallback(ServerReadCallback), state);
}
}

As you can see server implementation is very simple. It receives data size prefix at first and if it is complete (first 4 bytes are received) then proceeds with data receive.

It is very important to always check the number of received bytes. This number can vary.


Client

Client implementation is pretty straightforward. It also has a state that is passed along async operations.

public class ClientState
{
public Socket Client; //client socket
public byte[] DataToSend; //data to be trasferred
public int DataSent = 0; //data already sent
}

The data being sent is prefixed with its size.

ClientState state = new ClientState();
state.Client = socket;

//add prefix to data
state.DataToSend = new byte[data.Length + 4];
byte[] prefix = BitConverter.GetBytes(data.Length);
//copy data size prefix
Buffer.BlockCopy(prefix, 0, state.DataToSend, 0, prefix.Length);
//copy the data
Buffer.BlockCopy(data, 0, state.DataToSend, prefix.Length, data.Length);

socket.BeginSend(state.DataToSend, 0, state.DataToSend.Length,
SocketFlags.None, new AsyncCallback(ClientSendCallback), state);

And finally the implementation of ClientSendCallback

private void ClientSendCallback(IAsyncResult ar)
{
ClientState state = (ClientState)ar.AsyncState;
SocketError socketError;
int sentData = state.Client.EndSend(ar, out socketError);

if ( socketError != SocketError.Success )
{
state.Client.Close();
return;
}

state.DataSent += sentData;

if (state.DataSent != state.DataToSend.Length)
{ //not all data was sent
state.Client.BeginSend(state.DataToSend, state.DataSent,
state.DataToSend.Length - state.DataSent, SocketFlags.None,
new AsyncCallback(ClientSendCallback), state);
}
else
{ //all data was sent
Console.WriteLine("All data was sent. Size: {0}",
state.DataToSend.Length);
state.Client.Close();
}
}

As you can see implementation details are very simple.
There are several important things here:
  • Data is received in pieces, you can't predict how much data you will receive during one method call
  • When using async sockets always pass the same state object in the context of the same client

Update
The code sample above illustrates the idea of tranferring size-prefixed data between client and server in the async way. Please, note that only one message per connection is passed from client to server. To add multiple message handling - server code has to be modified according to your custom the protocol.

Saturday, January 19, 2008

Unmanaged Debugging Option Very Useful in Visual Studio .NET


When developing managed code that is interacting with unmanaged world one has to be very careful, especially when working with unmanaged memory.

Here's an example how critical memory bug can be omitted.

I was developing code that used Marshal.AllocHGlobal method to allocate unmanaged memory. Naturally I was freeing that memory after usage.

The code looked like
IntPtr unmanagedMemory = IntPtr.Zero;
try
{
unmanagedMemory = Marshal.AllocaHGlobal(nBytes);
//invoking unmanaged method here via P/Invoke
}
finally
{
Marshal.FreeHGlobal(unmanagedMemory);
}

Everything was okay; application was working perfectly, except occasional crashes with AccessViolationException. Exception of this type can happen when something is writing into wrong memory offset and system reacts by throwing an exception.

Exception wasn't thrown every time application was running and it was hard to detect what was causing it. At the top of callstack was ntdll.dll module.

I decided to turn on unmanaged debugging and see what is happening under the hood in the unmanaged world.
(To turn unmanaged debugging in Visual Studio you need to go to Project Properties -> Debug -> Check "enable unmanaged code debugging").

After turning on unmanaged debugging I've got an exception immediately.


Marshal.FreeHGlobal(unmanagedMemory) was throwing exception saying that there was heap corruption. This exception was repeating constantly.

Finally, the bug was found - unmanaged function was not behaving well with the pointer passed to it.

Every time you're developing managed code that is interacting with unmanaged memory it is highly desirable to turn on unmanaged debugging. This will save a lot of time when tracking memory related issues and exceptions. Also a lot of information about debugging .NET applications can be found in .NET Debugging

Monday, December 17, 2007

Effective SQL Mindset: Cursors VS Joins



In the past I've dealt a lot with cursors. My experience was mostly negative. SQL code written using them was terribly slow. Thus our team was transforming SQL code with cursors into code without them.

Sure, cursors have their advantages. But, after conversion SQL query performance can be much better then with cursors.

Now, I'll show you how to accomplish the task using SQL with and without cursors.
There are two tables: regions and values. For example, regions represents departments while values is used to store arbitrary int data about the specific region.

SQL tables:
create table regions (id int, name varchar(10))
create table [values] (id int identity(1, 1), regid int, value int)


Table regions contains records for 100 regions, while values contains data only for region with id = 1 (only for the first region). We need to populate values table using data from the first region.

For exaple if table regions contains data





idname
1Reg 1
2Reg 2

And table values contains data only for first region




idReg Idvalue
1130
2135


So we need to populate table values for every region from regions table.

There are three ways how to do this:
  • write a computer program that will insert values into values table
  • write SQL query with cursors
  • write SQL query without cursors
I will not touch how to write a program to do this, its too ineffective.

But last two options seem to be interesting. Cursor solution is quick and dirty - you can code it almost in no time. Cursor code will be similar to the computer program's one.

select id,regionid,value into #Valuestmp from [values]

DECLARE RegionsCursor CURSOR FOR SELECT id FROM regions
declare @id int

OPEN RegionsCursor;
FETCH NEXT FROM RegionsCursor into @id;
WHILE @@FETCH_STATUS = 0
BEGIN

UPDATE #Valuestmp SET RegionId=@id
INSERT INTO [values](regionId, value) SELECT regionId, value FROM #Valuestmp
FETCH NEXT FROM RegionsCursor into @id;
END;
CLOSE RegionsCursor;
DEALLOCATE RegionsCursor;

drop table #Valuestmp
Here we store initial values from values table, and then for each region we insert data into values table.

This elegant script will accomplish the above:
insert into val (regid, value) select r.id as regid, v.value as value from reg r, val v where r.id <> 1

Central point in this script is Cartesian product - we select from two tables (bold font), joining every row of the values table with the rows in regions table.

SQL code above shows how cursor can be avoided. Every time you're tempted to use cursor - stop and think that nearly everything can be done without them. All you have to do is to think little bit.