Shahzad Bhatti Welcome to my ramblings and rants!

August 30, 2007

Design/Code Smells

Filed under: Computing — admin @ 10:59 am

I have been redesigning a J2EE system recently that was written about a year ago and I have done this countless in my career of over fifteen years. But I found a quite a number of code smells that show up every time. I find that badly design procedural code is easier to fix than badly design object oriented code. Often the systems are written in object oriented languages and using state of the art technologies such as Hibernate/Spring, so you would think that they also follow good principles of object oriented or domain driven design, but you will be surprised. First, let me summarize characteristics of good systems that I learned at school and over the years:

  • loosely coupled or separation of concerns – this is by far the most important ingredient of good software.
  • good abstraction that focus on areas of domain that are focus of the system
  • separation of concerns – good use layers. Here by layer, I mean logical layer not physical layer (tier), which is also source of confusion to many.
  • single responsibility principle – high encapsulated modules that have high cohesion within and low coupling across

Also, when you are developing large systems, it is also important to consider physical separation of modules and interdependencies, which means system with:

  • low cyclomatic complexity
  • Acyclic Dependency Principle – No circular dependencies
  • Dependency injection – This greatly helps coupling and facilitates testing.
  • Multiple codebases – Though, it doesn’t matter for small systems, but when dealing with hundreds of thousands of lines of code, it is important to separate code into multiple codebases along the line of business functionality.

And now the actual code smells that I have found time and again while maintaining, extending or rewriting systems:

Procedural code in disguise of Object Oriented code

It says, old habits are hard to break, often I find systems that are written in object oriented languages, but in procedural style. The smells I often find are:

  • anemic model (thanks to the EJB legacy), where domain classes are just like C structs and all business logic is in services. Often I find that service managers have methods that take domain class as an argument and do some business logic and return. Such business logic is better off in the domain object itself.
  • static methods and attributes – this is also big code smell often from developers that started with C like languages.

Tight Coupling

This would be the winner of code smell that is found most often. For example, in my current system I found that domain classes were more like structs, and services where all the fun happened. The services did all database queries (Hibernate) and business logic. Worse, the application had severe performance issues so for every service there was a sister class for caching the service methods and often those caching classes also had database access methods. Clearly, they violated coupling and separation of concerns. I am trying to divide all those responsibilities into domain classes, Dao/Repositories, and Services. In this case, most of the business logic will go to the domain classes, all database access will go to Dao/Repositories and high level business or orchestration logic will go to the services. In this design, cross cutting concerns like transactions, caching are defined at service layer in declarative manner. For example, I added some caching annotations to signify the methods that should be cached. Another violation of separation of concerns was coupling of user view in the service layer and a lot of service managers took Locale as argument and looked up resource file. All that logic will be in the view layer.

Factories and Singletons

The GoF made Factories and Singleton a must have pattern for all cool object oriented systems, but in reality they make maintenance and testing hard. I found plenty of usage of these patterns in my current system and I am replacing them with dependency injection.

Too much Code

Though, for a large system you do end up with a lot of code, but I have seen even smaller projects with a lot of code. Also, some languages are more verbose than others. For example, often I find that code I write in Ruby takes less than half number of lines of code.

Distinction between Classes and Objects

I have found this smell in a number of projects where many of the classes were just classes with different values or slightly different data. For example, I found over 400 classes in my current project that I would consider objects with a little bit of difference. Though, for complicated systems where meta information is slightly different, you may use adaptive object model pattern, but that is not for the faint of heart.

Over Engineering

This is another reason for large code base when the system adds some technical requirements when they are not really needed. For example, in my current system we don’t have internationalization requirement, but we have sporadic use of localization. It may not be too bad, except all that localization is inconsistent, which would have to be changed if i18n becomes real requirement. Meanwhile, you will have to maintain all localization code. In this regard, I would follow agile principle of YAGNI.

Cross Cutting Concerns/Separation of Policies

The cross cutting concerns such as caching, security, transactions should be handled centrally in a declarative manner. Though, AOP is not for faint of heart, but EJB 3.0 and Spring provide nice support for that. Also, with annotations in Java, you can define your own policies. For example, caching was one thing that I found embedded in every piece of code (in addition to separate sister classes for services) in my system and it was really hard to track how things work.

Strings as glorified DSL

This is another code smell that I have seen where strings store some complicated data structure that you have to parse. For example, prior to JDK 1.4, developers had to parse line numbers of source code from stack trace, because it would return String. I found countless examples of this in my current system where strings stored complicated data structures or in other cases where strings were used when actual typing such as Long, Date would have been better.

Pareto principle (80/20 Rule)

I believe the system should be design based on the majority of use cases. Unfortunately, I have seen some systems where the whole design was sacrificed to fit some corner cases. This made the whole system very convoluted. The special cases should be handled specially and not at the cost of entire system. Again, I found an example of this in my current system where primary keys were defined with convoluted abstraction just because a couple of classes could not support surrogate keys for primary ids.

Conclusion

These days, I find most the projects are driven by quick wins. I find that in most of the development shops, developers are facing impossible deadlines where they must ship the system. In these circumstances, they do the quick and dirty job to ship the product, but soon it becomes the maintenance hell. I have found that since the dot bombs era, the working environment in most shops have degraded for developers and offshoring has worsened this situation. Many of the managers consider developers “code monkeys” that can be easily replaced. Unfortunately, I don’t see things improving anytime soon.

PS: Further reading:

August 29, 2007

Polymorphism in Erlang

Filed under: Computing — admin @ 4:48 pm

Though, Joe Armstrong denies that Erlang is object oriented language, but according Ralph Johnson concurrent Erlang is object oriented. Erlang is based on Actor model, where each object has a mailbox associated that receives messages. In this model, the message passing takes literal form rather than method invocation. Erlang also has strong pattern matching support, so you can achieve polymorphism by pattern matching. This kind of polymorphism is similar to duck typing rather than inheritance based polymorphism in object oriented languages. One of the hardest thing in object oriented language is to know when something can be a subclass of another class because you have to measure IS-A test or Liskov substitution principle. Most people also consider inheritance bad due to encapsulation leakage so duck typing will be easier. Since, all states are immutable in Erlang, you can’t really keep state as traditional object oriented language, but you can create a new state with every mutation and attach it to the process. For example, here is a simple example of polymorphism in Java :

  1 import junit.framework.Test;
  2 import junit.framework.TestCase;
  3 import junit.framework.TestSuite;
  4
  5 import java.util.*;
  6
  7
  8 public class PolymorTest extends TestCase {
  9     Shape[] shapes;
 10
 11     protected void setUp() {
 12         shapes = new Shape[] {
 13                 new Circle(3.5), new Rectangle(20, 50), new Square(10)
 14             };
 15     }
 16
 17     protected void tearDown() {
 18     }
 19
 20     public void testArea() {
 21         assertEquals(38.484, shapes[0].area(), 0.001);
 22         assertEquals(1000.0, shapes[1].area(), 0.001);
 23         assertEquals(100.0, shapes[2].area(), 0.001);
 24     }
 25
 26     public void testPerimeter() {
 27         assertEquals(21.991, shapes[0].perimeter(), 0.001);
 28         assertEquals(140.0, shapes[1].perimeter(), 0.001);
 29         assertEquals(40.0, shapes[2].perimeter(), 0.001);
 30     }
 31
 32     public static Test suite() {
 33         TestSuite suite = new TestSuite();
 34         suite.addTestSuite(PolymorTest.class);
 35
 36         return suite;
 37     }
 38
 39     public static void main(String[] args) {
 40         junit.textui.TestRunner.run(suite());
 41     }
 42
 43     interface Shape {
 44         public double area();
 45
 46         public double perimeter();
 47     }
 48
 49     class Rectangle implements Shape {
 50         double height;
 51         double width;
 52
 53         Rectangle(double height, double width) {
 54             this.height = height;
 55             this.width = width;
 56         }
 57
 58         public double area() {
 59             return height * width;
 60         }
 61
 62         public double perimeter() {
 63             return (2 * height) + (2 * width);
 64         }
 65
 66         public void setWidth(double width) {
 67             this.width = width;
 68         }
 69
 70         public double getWidth() {
 71             return this.width;
 72         }
 73
 74         public double getHeight() {
 75             return this.height;
 76         }
 77
 78         public void setHeight(double height) {
 79             this.height = height;
 80         }
 81     }
 82
 83     class Square extends Rectangle {
 84         Square(double side) {
 85             super(side, side);
 86         }
 87     }
 88
 89     class Circle implements Shape {
 90         double radius;
 91
 92         Circle(double radius) {
 93             this.radius = radius;
 94         }
 95
 96         public double getRadius() {
 97             return this.radius;
 98         }
 99
100         public void setRadius(double radius) {
101             this.radius = radius;
102         }
103
104         public double area() {
105             return Math.PI * radius * radius;
106         }
107
108         public double perimeter() {
109             return Math.PI * diameter();
110         }
111
112         public double diameter() {
113             return 2 * radius;
114         }
115     }
116 }
117

And here is Ruby equivalent, which uses duck typing:

 1 require 'test/unit'
 2 require 'test/unit/ui/console/testrunner'
 3
 4
 5 class Rectangle
 6   attr_accessor :height, :width
 7   def initialize(height, width)
 8         @height = height
 9         @width = width
10   end
11   def area()
12       height*width
13   end
14   def perimeter()
15       2*height + 2*width
16   end
17 end
18
19
20 class Square
21   attr_accessor :side
22   def initialize(side)
23         @side = side
24     end
25     def area()
26       side*side
27     end
28     def perimeter()
29       4 * side
30     end
31 end
32
33
34 class Circle
35     attr_accessor :radius
36    def initialize(radius)
37         @radius = radius
38     end
39     def area()
40      Math::PI*radius*radius
41     end
42     def perimeter()
43     Math::PI*diameter()
44       end
45      def diameter()
46       2*radius
47     end
48 end
49
50 class PolymorTest < Test::Unit::TestCase
51     def setup
52         @shapes = [Circle.new(3.5), Rectangle.new(20, 50), Square.new(10)]
53     end
54
55     def test_area
56         assert_in_delta(38.484, @shapes[0].area(), 0.001, "didn't match area0 #{@shapes[0].area()}")
57         assert_in_delta(1000.0, @shapes[1].area(), 0.001, "didn't match area1 #{@shapes[1].area()}")
58         assert_in_delta(100.0, @shapes[2].area(), 0.001, "didn't match area2 #{@shapes[2].area()}")
59     end
60     def test_perimeter
61         assert_in_delta(21.991, @shapes[0].perimeter(), 0.001, "didn't match perim0 #{@shapes[0].perimeter()}")
62         assert_in_delta(140.0, @shapes[1].perimeter(), 0.001, "didn't match perim1 #{@shapes[1].perimeter()}")
63         assert_in_delta(40.0, @shapes[2].perimeter(), 0.001, "didn't match perim2 #{@shapes[2].perimeter()}")
64     end
65 end
66
67
68 Test::Unit::UI::Console::TestRunner.run(PolymorTest)
69

And here is Erlang equivalent (obviously it’s a lot more verbose):

  1 -module(rectangle).
  2 -compile(export_all).
  3
  4
  5 -record(rectangle, {height, width}).
  6
  7 new_rectangle(H, W) ->
  8     #rectangle{height = H, width = W}.
  9
 10 start(H, W) ->
 11     Self = new_rectangle(H, W),
 12     {Self, spawn(fun() -> loop(Self) end)}.
 13
 14 rpc(Pid, Request) ->
 15         Pid ! {self(), Request},
 16         receive
 17             {Pid, ok, Response} ->
 18                 Response
 19         end.
 20
 21
 22 area(Self) ->
 23   Self#rectangle.height * Self#rectangle.width.
 24
 25 perimeter(Self) ->
 26   2 * Self#rectangle.height + 2 * Self#rectangle.width.
 27
 28 set_width(Self, W) ->
 29     Self#rectangle{width = W}.
 30
 31 get_width(Self) ->
 32     Self#rectangle.width.
 33
 34 set_height(Self, H) ->
 35     Self#rectangle{height = H}.
 36
 37 get_height(Self) ->
 38     Self#rectangle.height.
 39
 40 loop(Self) ->
 41     receive
 42         {From, area} ->
 43             From ! {self(), ok, area(Self)},
 44             loop(Self);
 45
 46         {From, perimeter} ->
 47             From ! {self(), ok, perimeter(Self)},
 48             loop(Self);
 49
 50         {From, get_width} ->
 51             From ! {self(), ok, get_width(Self)},
 52             loop(Self);
 53
 54         {From, get_height} ->
 55             From ! {self(), ok, get_height(Self)},
 56             loop(Self);
 57
 58         {set_width, W} ->
 59             loop(set_width(Self, W));
 60
 61         {set_height, H} ->
 62             loop(set_height(Self, H))
 63     end.
 64
 65
 66
 67
 68
 69
 70
 71 -module(circle).
 72 -compile(export_all).
 73 -define(PI, 3.14159).
 74
 75 -record(circle, {radius}).
 76
 77 new_circle(R) ->
 78     #circle{radius = R}.
 79
 80 start(R) ->
 81     Self = new_circle(R),
 82     {Self, spawn(fun() -> loop(Self) end)}.
 83
 84 rpc(Pid, Request) ->
 85         Pid ! {self(), Request},
 86         receive
 87             {Pid, ok, Response} ->
 88                 Response
 89         end.
 90
 91
 92 area(Self) ->
 93   ?PI * Self#circle.radius * Self#circle.radius.
 94
 95 perimeter(Self) ->
 96   ?PI * diameter(Self).
 97
 98 set_radius(Self, R) ->
 99     Self#circle{radius = R}.
100
101 get_radius(Self) ->
102     Self#circle.radius.
103 diameter(Self) ->
104     Self#circle.radius * 2.
105
106
107 loop(Self) ->
108     receive
109         {From, area} ->
110             From ! {self(), ok, area(Self)},
111             loop(Self);
112
113         {From, perimeter} ->
114             From ! {self(), ok, perimeter(Self)},
115             loop(Self);
116
117         {From, get_radius} ->
118             From ! {self(), ok, get_radius(Self)},
119             loop(Self);
120
121         {set_radius, R} ->
122             loop(set_radius(Self, R))
123     end.
124
125
126
127
128
129 -module(square).
130 -compile(export_all).
131
132
133 -record(square, {side}).
134
135 new_square(S) ->
136     #square{side = S}.
137
138 start(S) ->
139     Self = new_square(S),
140     {Self, spawn(fun() -> loop(Self) end)}.
141
142 rpc(Pid, Request) ->
143         Pid ! {self(), Request},
144         receive
145             {Pid, ok, Response} ->
146                 Response
147         end.
148
149
150 area(Self) ->
151   Self#square.side * Self#square.side.
152
153 perimeter(Self) ->
154   4 * Self#square.side.
155
156 set_side(Self, S) ->
157     Self#square{side = S}.
158
159 get_side(Self) ->
160     Self#square.side.
161
162 loop(Self) ->
163     receive
164         {From, area} ->
165             From ! {self(), ok, area(Self)},
166             loop(Self);
167
168         {From, perimeter} ->
169             From ! {self(), ok, perimeter(Self)},
170             loop(Self);
171
172         {From, get_side} ->
173             From ! {self(), ok, get_side(Self)},
174             loop(Self);
175
176         {set_side, S} ->
177             loop(set_side(Self, S))
178     end.
179
180
181
182
183 -module(poly_test).
184 -compile(export_all).
185
186 create() ->
187    [circle:start(3.5), rectangle:start(20, 50), square:start(10)].
188
189 area(ShapeNPid) ->
190     {_Shape, Pid} = ShapeNPid,
191     Pid ! {self(), area},
192     receive
193         {Pid, ok, Response} ->
194             Response
195     end.
196
197 perimeter(ShapeNPid) ->
198     {_Shape, Pid} = ShapeNPid,
199     Pid ! {self(), perimeter},
200     receive
201         {Pid, ok, Response} ->
202             Response
203     end.
204
205 get_area(ShapesNPids) ->
206    lists:map(fun(ShapeNPid) -> area(ShapeNPid) end, ShapesNPids).
207 get_perimeter(ShapesNPids) ->
208    lists:map(fun(ShapeNPid) -> perimeter(ShapeNPid) end, ShapesNPids).
209
210 test_area() ->
211     D = create(),
212     %[CircleArea, RectangleArea, SquareArea] = [38.4845,1000,100],
213     [CircleArea, RectangleArea, SquareArea] = get_area(D).
214
215 test_perimeter() ->
216     D = create(),
217     %[CirclePerimeter, RectanglePerimeter, SquarePerimeter] = [21.9911,140,40],
218     [CirclePerimeter, RectanglePerimeter, SquarePerimeter] = get_perimeter(D).
219

Lessons Learned:

Though, Erlang supports object oriented features in its concurrent model, but it is a lot more verbose. For example, in above example Ruby was roughly 60 lines of code and Java was twice as long, whereas Erlang was about four times long.

August 20, 2007

Benchmarking Java Vs Erlang

Filed under: Computing — admin @ 3:07 pm

I have been reading Joe Armstrong’s Erlang book recently and one of the assignment is to compare performance of processes and message communication by creating a ring of processes and sending messages. The assignment needs to be done in two languages so I Java as another language.

Here is the Java version:

  1 import java.util.*;
  2 import java.util.concurrent.*;
  3
  4 /**
  5  * Create N followers in a ring. Send a message round the ring M times so that a total of N * M messages get sent.
  6  * Time how long this takes for different value of N and M.
  7  * javac Ring.java
  8  * java -Xss48k -cp . Ring
  9  */
 10 public class Ring {
 11     //
 12     public class Follower extends Thread {
 13         final BlockingQueue queue = new LinkedBlockingQueue();
 14         Follower nextFollower;
 15         int pid;
 16         int numberOfMessages;
 17
 18         public Follower(int pid, int numberOfMessages) {
 19             this.pid = pid;
 20             this.numberOfMessages = numberOfMessages;
 21         }
 22
 23         public void setNextFollower(Follower nextFollower) {
 24             this.nextFollower = nextFollower;
 25         }
 26
 27
 28         public void sendAsynchronous(Object message) {
 29             queue.add(message);
 30         }
 31
 32         public void run() {
 33             //System.out.println("Starting Pid " + pid + ", numberOfMessages " + numberOfMessages);
 34             for (int i=0; i<numberOfMessages; i++) {
 35                 try {
 36                     Object message = queue.take();
 37                     nextFollower.sendAsynchronous(message);
 38                 } catch (InterruptedException e) {
 39                     Thread.currentThread().interrupted();
 40                 }
 41             }
 42             //System.out.println("Ending Pid " + pid + ", numberOfMessages " + numberOfMessages);
 43         }
 44     }
 45
 46     public class Leader extends Follower {
 47         public Leader(int pid) {
 48             super(pid, 0);
 49         }
 50
 51
 52         public void run() {
 53             // leader will not run asynchronously
 54         }
 55
 56         public void sendReceiveSynchronous(Object message) {
 57             try {
 58                 nextFollower.sendAsynchronous(message);
 59                 message = queue.take();
 60             } catch (InterruptedException e) {
 61                 Thread.currentThread().interrupted();
 62             }
 63         }
 64     }
 65
 66
 67     public Ring() {
 68     }
 69
 70
 71
 72     public void runRing(int numberOfProcesses, int numberOfMessages) {
 73         Leader leader = new Leader(-1);
 74         Follower[] followers = buildFollowers(numberOfProcesses-1, numberOfMessages, leader);
 75         startFollowers(followers);
 76         for (int i=0; i<numberOfMessages; i++) {
 77             leader.sendReceiveSynchronous(Boolean.TRUE); // we are not taking message size into account
 78         }
 79     }
 80
 81
 82     public void benchmarkRing(int numberOfProcesses, int numberOfMessages) {
 83         System.out.println("Starting ring for " + numberOfProcesses + " threads and " + numberOfMessages + " messages");
 84         long start = System.currentTimeMillis();
 85         //
 86         runRing(numberOfProcesses, numberOfMessages);
 87
 88         long elapsed = System.currentTimeMillis() - start;
 89         System.out.println("Ring for " + numberOfProcesses + " threads and " + numberOfMessages + " messages took " + elapsed + " milliseconds.");
 90     }
 91
 92     private void startFollowers(Follower[] followers) {
 93         for (int i=0; i<followers.length; i++) {
 94             followers[i].setDaemon(true);
 95             followers[i].start();
 96         }
 97     }
 98
 99
100     private Follower[] buildFollowers(int numberOfFollowers, int numberOfMessages, Leader leader) {
101         Follower[] followers = new Follower[numberOfFollowers];
102         for (int i=0; i<followers.length; i++) {
103             followers[i] = new Follower(i, numberOfMessages);
104         }
105         leader.setNextFollower(followers[0]);
106         for (int i=0; i<followers.length; i++) {
107             if (i == followers.length-1) {
108                 followers[i].setNextFollower(leader);
109             } else {
110                 followers[i].setNextFollower(followers[i+1]);
111             }
112         }
113         return followers;
114     }
115
116
117     //
118     public static void main(String[] args) {
119         for (int i=100; i<10000; i+=100) {
120             for (int j=100; j<10000; j+=1000) {
121                 new Ring().benchmarkRing(i, j);
122             }
123         }
124     }
125 }
126

And here is the Erlang version:

 1 -module(ring).
 2 -compile(export_all).
 3
 4 % c(ring).
 5 % Pid = ring:start(2).
 6 % Pid ! {self(), 0}.
 7 % Pid ! {self(), 2}.
 8 % ring:benchmark_ring(10, 4).
 9
10
11 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
12 % start - spawns a process and runs receive_send_loop function. It passes M - # of messages to the
13 % loop.
14 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
15 start(M, NextPid) ->
16     spawn(fun() -> receive_send_loop(M, NextPid) end).
17
18
19 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
20 % ring stars N processes, each will run receive_send_loop.
21 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
22 start_ring(N, M) ->
23     LastPid = self(),
24     start_ring(N-1, M, LastPid).
25
26 start_ring(N, M, LastPid) when N > 0 ->
27     Pid = start(M, LastPid),
28     start_ring(N-1, M, Pid);
29 start_ring(N, _M, LastPid) when N == 0 ->
30     LastPid.
31
32 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
33 % send_receive_message sends a message with D, M number of times to all processes inside in list L
34 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
35 send_receive_message(M, D, LastPid) when M > 0 ->
36     Payload = case M of
37       1 -> {nomore, D};
38       _Else -> {ok, D}
39     end,
40     %io:format("Master ~p Sending message to ~p~n", [self(), LastPid]),
41     LastPid ! Payload,
42
43     %io:format("Master ~p Reciving message ~n", [self()]),
44     receive
45             {ok, Response} ->
46                 Response
47     end,
48     %io:format("Master ~p Received message ~n", [self()]),
49     send_receive_message(M-1, D, LastPid);
50
51 send_receive_message(M, _D, _LastPid) when M == 0 ->
52     true.
53
54 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
55 % benchmark_ring invokes ring function and calculates timings.
56 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
57 benchmark_ring() ->
58     benchmark_ring(100).
59
60 benchmark_ring(N) when N < 10000 ->
61     benchmark_ring(N, 100),
62     benchmark_ring(N+100);
63 benchmark_ring(N) when N >= 10000 ->
64     true.
65
66 benchmark_ring(N, M) when M < 10000 ->
67     io:format("Starting ring for ~w processes and ~w messages.~n", [N, M]),
68     statistics(runtime),
69     statistics(wall_clock),
70     LastPid = start_ring(N, M),
71     send_receive_message(M, 'message', LastPid),
72     {_, RT} = statistics(runtime),
73     {_, WC} = statistics(wall_clock),
74     io:format("Ring for ~w processes and ~w messages took ~p (~p) milliseconds.~n", [N, M, RT, WC]),
75     benchmark_ring(N, M+1000);
76 benchmark_ring(_N, M) when M >= 10000 ->
77     true.
78
79
80
81 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
82 % receive_send_loop receives messages in a loop until it receives nomore.
83 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
84 receive_send_loop(M, NextPid) ->
85     receive
86         {nomore, Any} ->
87             %io:format("~p received ~p last message ~p nextPid ~p ~n", [self(), M, NextPid, Any]),
88             NextPid ! {ok, Any};
89         {ok, Any} ->
90             %io:format("~p received ~p message ~p nextPid ~p ~n", [self(), M, NextPid, Any]),
91             NextPid ! {ok, Any},
92             receive_send_loop(M-1, NextPid)
93      end.
94
95

And the verdict is Erlang is much more efficient than Java in process/thread creation and message communication I had to actually explicitly reduce the stack size to run Java program, but there is no comparison. Here is the results of benchmarks.

Here is simple ruby script that I used to merge output statistics from both runs:

 1 class Stats
 2   attr_accessor :processes
 3   attr_accessor :messages
 4   attr_accessor :java_time
 5   attr_accessor :erlang_time
 6   def initialize(procs, msgs, jtime, etime)
 7     @processes = procs.to_i
 8     @messages = msgs.to_i
 9     @java_time = jtime.to_i if jtime
10     @erlang_time = etime.to_i if etime
11   end
12   def key
13     "#{@processes}/#{@messages}"
14   end
15
16   def to_s
17     "#{@processes},#{@messages},#{@java_time},#{@erlang_time}"
18   end
19 end
20
21 stats = {}
22 File.open("javaring.out", "r").readlines.each do |line|
23   if line =~ /Ring for/
24     t = line.split(/ /)
25     stat = Stats.new(t[2], t[5], t[8], nil)
26     stats[stat.key] = stat
27     #puts "#{stat} --- for line #{t.join(', ')}" 
28   end
29 end
30
31 File.open("erlout", "r").readlines.each do |line|
32   if line =~ /Ring for/
33     t = line.split(/ /)
34     stat = Stats.new(t[2], t[5], nil, t[8])
35     old = stats[stat.key]
36     if old
37       old.erlang_time = stat.erlang_time
38     else
39       stats[stat.key] = stat
40     end
41     #puts "#{stat} --- for line #{t.join(', ')}" 
42   end
43 end
44 stats.values.sort_by {|stat| stat.processes * stat.messages}.each do |stat|
45   puts stat
46 end
47
48

Final Thoughts

Erlang is great for writing highly concurrent applications. It shows that smart use of green threads can outperform native threads. The only thing I found a bit verbose about Erlang is that you have to write a switch statement to receive messages. I wish these processes be more object oriented where message passing is done by method invocation instead of explicitly as it’s done in Erlang. What I mean is, instead of writing

  receive
     {label1, From, RealData} ->
          action;
     {label2, From, RealData} ->
          action;

It be more like module with functions defined as label1, label2, .. and arguments that accept From, RealData. Also, a lot of time, you have to send back a message, which can also be implicitly sent if the function returns anything. Back in mid 90s I wrote a Java based ORB that had a ServiceFactory that took any POJO object and converted that into Service. I consider these processes as small services and it would be nice to have same mechanism to convert  module into service. Another thing I find hard about Erlang (besides immutable data) are cryptic error messages. I am used to seeing the line number or stack trace where the error occurred, but Erlang error are very cryptic. As with learning a new language, you also have to learn all the libraries and Erlang has huge OTP beast that I will have to tame. Nevertheless, I like Erlang so far and it’s going to be favorite language.

August 7, 2007

Ten Commandments for Scalable Architecture

Filed under: Computing — admin @ 9:45 pm

Scalability generally means a system can support more users when adding more resources. It can be vertical meaning adding more memory, CPUs or horizontal meaning more computers. Following are commandments that I have learned to make scalable systems such as large traffic sites, travel sites and e-commerce sites:

1. Divide and conquer – Design a loosely coupled and shared nothing architecture by breaking a large system into a set of smaller shared services. The services should be stateless that can deployed on any number of machines. You can use Theory of constraints to find bottlenecks because these will limit how many servers or requests you can perform.

2. Use messaging oriented middleware (ESB) to communicate with the services. This avoids temporal dependencies that are inherent in RPC style services.

3. Resource management – Manage http sessions and remove them for static contents, close all resources after usage such as database connections. Avoid expensive resource management protocols such as two phase commits, which can be scalability killer. Instead use optimistic locking or compensating transactions.

4. Replicate data – For write intensive systems use master-master scheme to replicate database and for read intensive systems use master-slave configuration. Use queues for all database writes so that replication don’t block incoming requests and make sure writes go through your cache system so that reads know about them. For user facing requests use high availability design and for background processes use high consistency design (CAP).

5. Partition data (Sharding) – Use multiple databases to partition the data. Use some naming services to find the data. You can also denormalized data to partion the data.

6. Avoid single point of failure – Identify any kind of single point of failures in hardware, software, network, power supply.

7. Bring processing closer to the data – Instead of transmitting large amount of data over the network, bring the processing closer to the data. May be some kind of mobile agent technology can help here to automatically move processing units.

8. Design for service failures and crashes – Write your services as idempotent so that retries can be done safely. Have a decentralized logging and monitoring. However, have a centralized way to monitor or gather logs for services. Keep an eye on performance. Invest in tools for monitoring and managing services.

9. Dynamic Resources – Design service frameworks so that resources can be removed or added automatically and clients can automatically discover them. You will need some kind of smart load balancer here. Again, all this should be connected to a centralized monitoring system.

10. Smart Caching – Cache expensive operations and contents as much as possible. Precompute your contents to reduce load on the application server. Unfortunately, caching on the same server as application server can reduce memory for application server, so I suggest doing caching on separate servers (caching farm). You can add version to cache and set time out so that you don’t have to invalidate cache. Also, use multi-level caching and store contents on  disks so if the machine crashes it can restart quickly and cache warmup is quick.

Annotation based Caching in Java

Filed under: Computing — admin @ 3:33 pm

I probably had to write cache to store results of expensive operations or queries a dozens of times over last ten years of Java. And this week, I had to redo again. Though, there are a lot of libraries such as JCS , Terracota or Tangosol, but I just decided to write a simple implementation myself.

First, I defined an annotation that will be used to mark any class or methods cachable:

import java.lang.reflect.*;
import java.lang.annotation.*;

/**
 * Annotation for any class that wish to be cacheable. This annotation can be defined
 * at the class level which will allow caching of all methods or at methods or both.
 */

@Target({ElementType.TYPE, ElementType.METHOD})
@Retention(RetentionPolicy.RUNTIME)
public @interface Cacheable {
    /**
     * This method allows disabling cache for certain methods.
     */
    boolean cache() default true;

    /**
     * This method defines maximum number of items that will be stored in cache. If
     * number of items exceed this, then old items will be removed (LRU). This value
     * should only be defined at class level and not at the method level.
     */
    int maxCapacity() default 1000;

    /**
     * @return true if block of [ if (in cache) load ] is protected with lock. This
     * will prevent two threads from executing the same load
     */
    boolean synchronizeAccess() default false;

    int timeoutInSecs() default 300;

    /**
     * @return true if cache will be populated asynchronously when it's about to expire.
     */
    public boolean canReloadAsynchronously() default false;
}
I then defined a simple map class to store cache:

import java.lang.annotation.ElementType;
import java.lang.annotation.Retention;
import java.lang.annotation.RetentionPolicy;
import java.lang.annotation.Target;
import java.lang.reflect.Method;
import java.util.*;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.locks.ReentrantLock;

/**
 * CacheMap - provides lightweight caching based on LRU size and timeout
 * and asynchronous reloads.
 */

public class CacheMap<K, V> implements Map<K, V> {
    private final static int MAX_THREADS = 10; // for all cache items across VM
    private final static int MAX_ITEMS = 10000; // for all cache items across VM

    private final static ExecutorService executorService = Executors.newFixedThreadPool(MAX_THREADS);

    static class FixedSizeLruLinkedHashMap<K, V> extends LinkedHashMap<K, V> {
        private final int maxSize;

        public FixedSizeLruLinkedHashMap(int initialCapacity, float loadFactor, int maxSize) {
            super(initialCapacity, loadFactor, true);
            this.maxSize = maxSize;
        }

        @Override
        protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) {
            return size() > maxSize;
        }

    }

    private final Cacheable classCacheable;
    private final Map<K, Pair<Date, V>> map;
    private final Map<Object, ReentrantLock> locks = new HashMap<Object, ReentrantLock>();

    public CacheMap(Cacheable cacheable) {
        this.classCacheable = cacheable;
        int maxCapacity = cacheable != null && cacheable.maxCapacity() > 0
                && cacheable.maxCapacity() < MAX_ITEMS ? cacheable.maxCapacity() : MAX_ITEMS;
        this.map = Collections.synchronizedMap(
                new FixedSizeLruLinkedHashMap<K, Pair<Date, V>>(
                        maxCapacity / 10, 0.75f, maxCapacity));
    }

    @Override
    public int size() {
        return map.size();
    }

    @Override
    public boolean isEmpty() {
        return map.isEmpty();
    }

    @Override
    public boolean containsKey(Object key) {
        return map.containsKey(key);
    }

    @Override
    public boolean containsValue(Object value) {
        return map.containsValue(value);
    }

    @Override
    public V put(K key, V value) {
        Pair<Date, V> old = map.put(key, new Pair<>(new Date(), value));
        if (old != null) {
            return old.second;
        }
        return null;
    }

    @Override
    public V remove(Object key) {
        Pair<Date, V> old = map.remove(key);
        if (old != null) {
            return old.second;
        }
        return null;
    }

    @Override
    public void putAll(Map<? extends K, ? extends V> m) {
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            put(e.getKey(), e.getValue());
        }
    }

    @Override
    public void clear() {
        map.clear();
    }

    @Override
    public Set<K> keySet() {
        return map.keySet();
    }

    @Override
    public Collection<V> values() {
        List<V> list = new ArrayList<>();
        for (Pair<Date, V> e : map.values()) {
            list.add(e.getSecond());
        }
        return list;
    }

    @Override
    public Set<Entry<K, V>> entrySet() {
        Set<Entry<K, V>> set = new HashSet<>();
        for (final Map.Entry<K, Pair<Date, V>> e : map.entrySet()) {
            set.add(new Map.Entry<K, V>() {
                @Override
                public K getKey() {
                    return e.getKey();
                }

                @Override
                public V getValue() {
                    return e.getValue().getSecond();
                }

                @Override
                public V setValue(Object value) {
                    return null;
                }
            });
        }
        return set;
    }

    /**
     * This method is simple get without any loading behavior
     *
     * @param key to fetch
     */
    @Override
    public V get(Object key) {
        Pair<Date, V> item = this.map.get(key);
        if (item == null) {
            return null;
        }
        return item.getSecond();
    }

    /**
     * This method is simple get with loading behavior
     *
     * @param key to fetch
     */
    public V get(K key, Cacheable cacheable, CacheLoader<K, V> loader) {
        Pair<Date, V > item = this.map.get(key);
        V value;
        ReentrantLock lock = null;
        try {
            synchronized (this) {
                if (cacheable.synchronizeAccess()) {
                    lock = lock(key);
                }
            }
            if (item == null) {
                // load initial value
                value = reloadSynchronously(key, loader);
            } else if (cacheable.timeoutInSecs() > 0
                    && System.currentTimeMillis() - item.getFirst().getTime() > cacheable.timeoutInSecs() * 1000L) {
                // the element has expired, reload it
                if (cacheable.canReloadAsynchronously()) {
                    reloadAsynchronously(key, loader);
                    value = item.getSecond();
                } else {
                    value = reloadSynchronously(key, loader);
                }
            } else {
                value = item.getSecond();
            }
        } finally {
            if (lock != null) {
                lock.unlock();
            }
        }
        return value;
    }

    private ReentrantLock lock(Object key) {
        ReentrantLock lock;
        synchronized (locks) {
            lock = locks.get(key);
            if (lock == null) lock = new ReentrantLock();
        }

        lock.lock();
        return lock;
    }

    private V reloadSynchronously(final K key, final CacheLoader<K, V> loader) {
        V value = loader.loadCache(key);
        put(key, value);
        return value;
    }

    private void reloadAsynchronously(final K key, final CacheLoader< K, V> loader) {
        executorService.submit(new Callable<V>() {
            public V call() {
                return reloadSynchronously(key, loader);
            }
        });
    }
}
A couple of interfaces to load or search key/values:

import java.lang.reflect.*;
public interface CacheKeyable<K> {
    K toKey(Method method, Object[] args);
}
public interface CacheLoader<K, V> {
    /** 
     * This mehod loads value for the object by calling underlying 
     * method 
     * @param key - key of the cache 
     * @return value for the key
    */
  	public V loadCache(K key);
}
Following is a simple class to convert method and its args into a unique key (I suppose we can use MD5 SHA1 instead here):

public class SimpleKeyable implements CacheKeyable<String> {
    @Override
    public String toKey(Method method, Object[] args) {
        StringBuilder sb = new StringBuilder(method.getName());
        for (int i = 0; args != null && i < args.length; i++) {
            sb.append(".");
            if (isPrimitive(args[i])) {
                sb.append(args[i].toString());
            } else {
                sb.append(System.identityHashCode(args[i]));
            }
        }
        return sb.toString();
    }

    // checks if object is primitive type
    private boolean isPrimitive(Object arg) {
        return arg.getClass().isPrimitive() ||
                arg.getClass().isEnum() ||
                arg instanceof Number ||
                arg instanceof CharSequence ||
                arg instanceof Character ||
                arg instanceof Boolean ||
                arg instanceof Date;
    }
}

A utility class for storing pair of objects:

class Pair<FIRST, SECOND> {
    final FIRST first;
    final SECOND second;

    Pair(FIRST first, SECOND second) {
        this.first = first;
        this.second = second;
    }

    public FIRST getFirst() {
        return first;
    }

    public SECOND getSecond() {
        return second;
    }
}

Following code adds support for parsing cache annotation:

import java.lang.annotation.Annotation;
import java.lang.reflect.InvocationHandler;
import java.lang.reflect.Method;
import java.lang.reflect.Proxy;

public class CacheProxy<K, V> implements InvocationHandler {
    private final Object delegate;
    private final CacheMap<K, V> cache;
    private final Cacheable classcacheable;
    private final CacheKeyable<String> keyable;

    class CacheLoaderImpl implements CacheLoader<K, V> {
        Method method;
        Object[] args;

        CacheLoaderImpl(Method method, Object[] args) {
            this.method = method;
            this.args = args;
        }

        @Override
        public V loadCache(Object key) {
            try {
                return (V) method.invoke(delegate, args);
            } catch (RuntimeException e) {
                throw e;
            } catch (Exception e) {
                throw new RuntimeException(e);
            }
        }
    }

    // Constructs cache proxy
    public CacheProxy(Object aDelegate) {
        this.delegate = aDelegate;
        this.classcacheable = getCacheable(aDelegate.getClass().getAnnotations());
        this.cache = new CacheMap<>(classcacheable);
        this.keyable = new SimpleKeyable();
    }

    // creates proxy object for cache
    public static Object proxy(Object delegate, Class<?> iface) {
        return Proxy.newProxyInstance(iface.getClassLoader(),
                new Class<?>[]{iface}, new CacheProxy(delegate));
    }

    public V invoke(
            final Object proxy,
            final Method method,
            final Object[] args) throws Exception {
        Cacheable cacheable = getCacheable(method);
        if (cacheable != null) {
            K key = toKey(method, args);
            return cache.get(key, cacheable, new CacheLoaderImpl(method, args));
        } else {
            return (V) method.invoke(delegate, args);
        }
    }

    private Cacheable getCacheable(Annotation[] ann) {
        for (int i = 0; ann != null && i < ann.length; i++) {
            if (ann[i] instanceof Cacheable) {
                return (Cacheable) ann[i];
            }
        }
        return null;
    }

    //
    private Cacheable getCacheable(Method method) throws
            Exception {
        // get method from actual class because interface method will not be annotated.
        method = delegate.getClass().getMethod(method.getName(), method.getParameterTypes());
        // first search method level annotation
        Cacheable cacheable = getCacheable(method.getDeclaredAnnotations());
        if (cacheable == null) {
            cacheable = classcacheable; // if not found search class level annotation
        }
        if (cacheable != null && !cacheable.cache()) {
            cacheable = null;
        }
        return cacheable;
    }

    private K toKey(Method method, Object[] args) {
        if (delegate instanceof CacheKeyable) {
            return (K) ((CacheKeyable) delegate).toKey(method, args);
        } else {
            return (K) keyable.toKey(method, args);
        }
    }
}

Instead of Java 1.3 proxy, we can also use aspects, e.g.

import java.util.*;
import java.lang.reflect.*;
import java.lang.annotation.*;
import org.aspectj.lang.annotation.Aspect;
import org.aspectj.lang.annotation.Pointcut;
import org.aspectj.lang.annotation.Around;
import org.aspectj.lang.ProceedingJoinPoint;
import org.aspectj.lang.reflect.MethodSignature;

@Aspect
public class CacheAspect<K, V> {
    private final CacheMap<K, V> cache;
    private final CacheKeyable<String> keyable;
    class CacheLoaderImpl implements CacheLoader<K, V> {
        ProceedingJoinPoint pjp;
        CacheLoaderImpl(ProceedingJoinPoint pjp) {
            this.pjp = pjp;
        }
        @Override
        public V loadCache(Object key) {
            try {
                return pjp.proceed();
            } catch (RuntimeException e) {
                throw e;
            } catch (Exception e) {
                throw new RuntimeException(e);
            }
        }
    }

    // Constructor
    public CacheAspect() {
        this.cache = new CacheMap<>(null);
        this.keyable = new SimpleKeyable();
    }

    @Around("@target(com.plexobject.Cacheable)")
    public Object proxy(ProceedingJoinPoint pjp) throws Exception {
        Object target = pjp.getTarget();
        Cacheable cacheable = getCacheable(pjp);
        //
        if (cacheable != null) {
            Method method = ((MethodSignature)pjp.getStaticPart().getSignature()).getMethod();
            Object key = toKey(target, method, pjp.getArgs());
            return cache.get(key, cacheable, new CacheLoaderImpl(pjp)); 51
        } else {
            try {
                return pjp.proceed();
            } catch (Exception e) {
                throw e;
            } catch (Throwable e) {
                throw new Error(e);
            }
        }
    }
    private Cacheable getCacheable(Annotation[] ann) {
        for (int i=0; ann != null && i<ann.length; i++) {
            if (ann[i] instanceof Cacheable) {
                return (Cacheable) ann[i];
            }
        }
        return null;
    }
    private Cacheable getCacheable(ProceedingJoinPoint pjp) throws Exception {
        if (pjp.getStaticPart().getSignature() instanceof MethodSignature == false) {
            return null;
        }
        Method method = ((MethodSignature)pjp.getStaticPart().getSignature()).getMethod();
        // first search method level annotation
        Cacheable cacheable = getCacheable(method.getDeclaredAnnotations());
        if (cacheable != null && cacheable.cache() == false) {
            cacheable = null;
        }
        return cacheable;
    }
    private K toKey(Object target, Method method, Object[] args) {
        if (target instanceof CacheKeyable) {
            return (K) ((CacheKeyable) target).toKey(method, args);
        } else {
            return (K) keyable.toKey(method, args);
        }
    }
}
 And finally a unit test to test everything:

import junit.framework.*;
import java.lang.reflect.*;
import java.util.*;
public class CacheProxyTest extends TestCase {
    interface IService {
        Date getCacheTime(boolean junk);
        Date getCacheTime(int junk);
        Date getRealtime(boolean junk);
    }
    @Cacheable(maxCapacity=100)
    class ServiceImpl implements IService {
        @Cacheable(timeoutInSecs = 1, synchronizeAccess = true)
        public Date getCacheTime(boolean junk) {
            return new Date();
        }
        @Cacheable(timeoutInSecs = 1, synchronizeAccess = true)
        public Date getCacheTime(int junk) {
            return new Date();
        }
        @Cacheable(cache=false)
        public Date getRealtime(boolean junk) {
            return new Date();
        }
    }

    public void testCache() throws Exception {
        ServiceImpl real = new ServiceImpl();
        Date started = new Date();
        IService svc = (IService) CacheProxy.proxy(real, IService.class);
        Date cacheDate = svc.getCacheTime(true);
        assertTrue(cacheDate.getTime() >= started.getTime());
        Date realDate = svc.getRealtime(true);
        assertTrue(realDate.getTime() >= started.getTime());
        Thread.currentThread().sleep(200);
        assertTrue(cacheDate.getTime() == svc.getCacheTime(true).getTime());
        assertTrue(svc.getCacheTime(false).getTime() > cacheDate.getTime());
        assertTrue(svc.getRealtime(true).getTime() > realDate.getTime());

        cacheDate = svc.getCacheTime(0);
        for (int i=0; i<100; i++) {
            svc.getCacheTime(i).getTime();
        }
        // after max capacity
        assertFalse(cacheDate == svc.getCacheTime(0));
    }
}

Powered by WordPress