Even a basic planning problem, such as bin packing, can be notoriously hard to solve and scale. One might consider the brute force algorithm. Let's take a look at how that algorithm works out on the cloud balance example of Drools Planner: Given a set of servers with different hardware (CPU, memory and network bandwidth) and given a set of processes with different hardware requirements, assign each process to 1 server and minimize the total cost of the active servers. The brute force algorithm is simple: try every combination between processes where each process is assigned to each server. For example, if we have 6 processes (P0, P1, P2, P3, P4, P5) and 2 servers (S0, S1), we'd try these solutions: P0->S0, P1->S0, P2->S0, P3->S0, P4->S0, P5->S0 P0->S0, P1->S0, P2->S0, P3->S0, P4->S0, P5->S1 P0->S0, P1->S0, P2->S0, P3->S0, P4->S1, P5->S0 P0->S0, P1->S0, P2->S0, P3->S0, P4->S1, P5->S1 ... P0->S1, P1->S1, P2->S1, P3->S1, P4->S1, P5->S1 On my machine, it takes 15ms to calculate the score of these 2^6 combinations. When I scale out to 9 processes and 3 servers, which are 3^9 combinations, it becomes 1582ms. So it scales like this: Notice that despite that the number of processes has not even doubled, the running time multiplied by 100! For comparison, I 've added the running time of the First Fit algorithm. And it gets worse: for 12 processes and 4 servers, which are 4^12 combinations, it take more than 17 minutes: What if we want to distribute 3000 processes over 1000 servers? With this kind of scalability, it will take too long. In fact, the brute force algorithm is useless. Luckily, Drools Planner implements several other optimization algorithms, which can handle such loads. If you want to know more about them, take a look at the Drools Planner manual or come to my talk at JUDCon London (31 Oct - 1 Nov). This article was originally posted on the Drools & jBPM blog.

Hadoop Map/Reduce model is very good in processing large amount of data in parallel. It provides a general partitioning mechanism (based on the key of the data) to distribute aggregation workload across different machines. Basically, map/reduce algorithm design is all about how to select the right key for the record at different stage of processing. However, "time dimension" has a very different characteristic compared to other dimensional attributes of data, especially when real-time data processing is concerned. It presents a different set of challenges to the batch oriented, Map/Reduce model. Real-time processing demands a very low latency of response, which means there isn't too much data accumulated at the "time" dimension for processing. Data collected from multiple sources may not have all arrived at the point of aggregation. In the standard model of Map/Reduce, the reduce phase cannot start until the map phase is completed. And all the intermediate data is persisted in the disk before download to the reducer. All these added to significant latency of the processing. Here is a more detail description of this high latency characteristic of Hadoop. Although Hadoop Map/Reduce is designed for batch-oriented work load, certain application, such as fraud detection, ad display, network monitoring requires real-time response for processing large amount of data, have started to looked at various way of tweaking Hadoop to fit in the more real-time processing environment. Here I try to look at some technique to perform low-latency parallel processing based on the Map/Reduce model. General stream processing model In this model, data are produced at various OLTP system, which update the transaction data store and also asynchronously send additional data for analytic processing. The analytic processing will write the output to a decision model, which will feed back information to the OLTP system for real-time decision making. Notice the "asynchronous nature" of the analytic processing which is decoupled from the OLTP system, this way the OLTP system won't be slow down waiting for the completion of the analytic processing. Nevetheless, we still need to perform the analytic processing ASAP, otherwise the decision model will not be very useful if it doesn't reflect the current picture of the world. What latency is tolerable is application specific. Micro-batch in Map/Reduce One approach is to cut the data into small batches based on time window (e.g. every hour) and submit the data collected in each batch to the Map Reduce job. Staging mechanism is needed such that the OLTP application can continue independent of the analytic processing. A job scheduler is used to regulate the producer and consumer so each of them can proceed independently. Continuous Map/Reduce Here lets imagine some possible modification of the Map/Reduce execution model to cater for real-time stream processing. I am not trying to worry about the backward compatibility of Hadoop which is the approach that Hadoop online prototype (HOP) is taking. Long running The first modification is to make the mapper and reducer long-running. Therefore, we cannot wait for the end of the map phase before starting the reduce phase as the map phase never ends. This implies the mapper push the data to the reducer once it complete its processing and let the reducer to sort the data. A downside of this approach is that it offers no opportunity to run the combine() function on the map side to reduce the bandwidth utilization. It also shift more workload to the reducer which now needs to do the sorting. Notice there is a tradeoff between latency and optimization. Optimization requires more data to be accumulated at the source (ie: the Mapper) so local consolidation (ie: combine) can be performed. Unfortunately, low latency requires the data to be sent ASAP so not much accumulation can be done. HOP suggest an adaptive flow control mechanism such that data is pushed out to reducer ASAP until the reducer is overloaded and push back (using some sort of flow control protocol). Then the mapper will buffer the processed message and perform combine() before it send to the reducer. This approach automatically shift back and forth the aggregation workload between the reducer and the mapper. Time Window: Slice and Range This is a "time slice" concept and a "time range" concept. "Slice" defines a time window where result is accumulated before the reduce processing is executed. This is also the minimum amount of data that the mapper should accumulate before sending to the reducer. "Range" defines the time window where results are aggregated. It can be a landmark window where it has a well-defined starting point, or a jumping window (consider a moving landmark scenario). It can also be a sliding window where is a fixed size window from the current time is aggregated. After receiving a specific time slice from every mapper, the reducer can start the aggregation processing and combine the result with the previous aggregation result. Slice can be dynamically adjusted based on the amount of data sent from the mapper. Incremental processing Notice that the reducer need to compute the aggregated slice value after receive all records of the same slice from all mappers. After that it calls the user-defined merge() function to merge the slice value with the range value. In case the range need to be refreshed (e.g. reaching a jumping window boundary), the init() functin will be called to get a refreshed range value. If the range value need to be updated (when certain slice value falls outside a sliding range), the unmerge() function will be invoked. Here is an example of how we keep tracked of the average hit rate (ie: total hits per hour) within a 24 hour sliding window with update happens per hour (ie: an one-hour slice). # Call at each hit record map(k1, hitRecord) { site = hitRecord.site # lookup the slice of the particular key slice = lookupSlice(site) if (slice.time - now > 60.minutes) { # Notify reducer whole slice of site is sent advance(site, slice) slice = lookupSlice(site) } emitIntermediate(site, slice, 1) } combine(site, slice, countList) { hitCount = 0 for count in countList { hitCount += count } # Send the message to the downstream node emitIntermediate(site, slice, hitCount) } # Called when reducer receive full slice from all mappers reduce(site, slice, countList) { hitCount = 0 for count in countList { hitCount += count } sv = SliceValue.new sv.hitCount = hitCount return sv } # Called at each jumping window boundary init(slice) { rangeValue = RangeValue.new rangeValue.hitCount = 0 return rangeValue } # Called after each reduce() merge(rangeValue, slice, sliceValue) { rangeValue.hitCount += sliceValue.hitCount } # Called when a slice fall out the sliding window unmerge(rangeValue, slice, sliceValue) { rangeValue.hitCount -= sliceValue.hitCount }

When I was trying to search for "leaders vs. rulers" on Google, I found many references to governments, royalty, and the military, throughout history. But the strange thing is that none of the articles seemed to distinguish between leaders and rulers. As if leaders and rulers are the same kind of people. They are not. Leaders Last week I was reading the book Tribes, by Seth Godin. In his book Seth says that never in history has it been so easy for anyone to be a leader. These days, with the use of social media, each of us is able to attract our own followers. And on Twitter, this is exactly what we're doing (quite literally). Seth explains that a crowd becomes a tribe when it has a leader that the people are following out of their own free will. And the interesting thing is that people can follow different leaders for different causes. In software projects it is the same. Some people can take the lead on an architectural level, while some have the lead on a functional level. Still others may be the first ones to turn to when people need advice about tools or processes. A complex system does not need a single leader. In fact, I believe a cross-functional team functions best when it has multiple leaders, each with his own area(s) of interest. Rulers In social systems the rulers are of an entirely different breed. While leaders use the power of attraction to convince people what to do, rulers use the power of authority to tell people what to do. Ruling people's lives is the very purpose of the ruler's job. With ruling comes law-making, enforcement and sanctioning, also called the trias politica (legislature, executive, judiciary). Unfortunately, rulers have gotten a bit of a bad name over the centuries. (Much of it deserved, by the way.) But ruling isn't all that bad. Laws, enforcement and sanctions are necessary evils, and in many social systems rulers can peacefully co-exist with leaders. For example: in any football (or soccer) match you will find leaders (one in each team) and rulers (the referees). They all play their parts in making the game work for everyone. Are managers rulers? There's no doubt in my mind that managers are rulers. They are (usually) the only ones with the authority to hire and fire people, and to place them in (or remove them from) teams or departments. They are able to tell people what software to use, what clothes to wear, and how much to pay for a place at the parking lot. Are managers leaders? This is a more interesting question. Lots of management book have been trying hard to turn managers into leaders. The last one I read was Good to Great, by Jim Collins. In his book Jim listed a 5-level hierarchy: Level 5 Executive: Builds enduring greatness through a paradoxical blend of personal humility and professional will. Level 4 Effective Leader: Catalyzes commitment to and vigorous pursuit of a clear and compelling vision, stimulating higher performance standards. Level 3 Manager: Organizes people and resources toward the effective and efficient pursuit of pre-determined objectives. Level 2 Contributing Team Member: Contributes individual capabilities to the achievement of group objectives and works effectively with others in a group setting. Level 1 Highly Capable Individual: Makes productive contributions through talent, knowledge, skills, and good work habits. The problem I have with Jim's hierarchy is that it suggests a linear progression to "higher" levels (where a leader is on a "higher" level than a manager). This doesn't fit with my observations of how social networks operate. In a software project, or any other social network, there can be many leaders, each with his or her own goals and desires. Some are taking initiatives for better architectures, some are leading the way to better user interface design, and some are guiding their followers towards better customer service, better processes, better software tools, or better coffee. To be a leader is not the next step for managers It is the manager's job to give room to leaders There are thousands of leaders on Twitter, and they all have their own huge numbers of followers. But who are the managers of Twitter? Only Evan Williams, Biz Stone and Jack Dorsey are. It's their platform. It's their game. They are the referees, making the laws, enforcing them, and sanctioning, while thousands of leaders and tribes are running around trying to score. Sure, it's ok when managers are trying to be leaders. Nothing wrong with that. Evan, Biz and Jack have a large number of followers themselves too. But they don't have the largest tribes. Managers are on top of things, but they are not on top. Rulers don't need to have the largest tribes themselves. Being a great ruler is hard enough already. If you think you need to be a great leader too, you're just making it hard for yourself. Referees contribute to great football/soccer games by being great rulers. They don't attempt to lead. It's not their job. They are in charge, but they are not the ones with the biggest egos. In his presentation Step Back from Chaos Jonathan Whitty shows that managers are often not the hubs in a social network. It's the informal leaders in a network through which most of the communication flows. It's the managers' job to make sure that leadership is cultivated, and that the emerging leaders are following the rules. So, you can be a leader, or you can be a ruler. And if you're exceptionally talented, perhaps you can be both. Which one will you be?