# A Cloud-Based Framework for Large-Scale Log Mining through Apache Spark and Elasticsearch
## 4 Methodology
### Log Partitioner  
In the information flow, a pattern occurs repeatedly in which all users are recognized by Elasticsearch and partitioned into small groups. This repetitive process for user-level analyses can be performed in parallel, e.g., constructing sessions from a user's logs. In the process, term aggregation, one of the most beneficial features that Elasticsearch offers, returns the unique terms for a given field along with the count of matching documents on the fly [27]. Given an IP, term aggregation returns all IPs in the log and the count of logs associated with each IP. Apache Spark divides the IP list into  
Figure 4: The framework for log mining. sub-datasets and distributes them to different computing nodes for the same analyses. HashPartitioner, the default partitioner in Spark, assigns IPs to different groups according to the hash value of the IP address. In the log-mining process, the Spark driver splits all users into \(k\) partitions, each of which will be passed to an executor and run as a task. Although the HashPartitioner splits the user list evenly with the hash code of IP address, the log size in each task (partition) is significantly different because the partitioner ignores the fact that different users have different behavior. Some users interacting with the website frequently produce many logs, while others who visit the website seldom populate few logs. As a result, the workloads are quite different, known as the skewed data problem (Figure 6). The skewed data problem will result in most tasks waiting for a slow task, which is the bottleneck of the whole process, since the Spark application runtime depends on the slowest task. To solve the problem, we propose a customized partitioner called LogPartitioner to balance logs across Spark tasks. As shown in Figures 7 and 8, the LogPartitioner algorithm consists of the following steps:  
1. Calculate log records for each user. A user map stores the user and the corresponding log count as (user\({}_{1}\), log\({}_{\text{count}}_{1}\)), (user\({}_{2}\), log\({}_{\text{count}}_{2}\)),..., (user\({}_{k}\), log\({}_{\text{count}}_{k}\)). The calculation module is implemented with the Elasticsearch term aggregation API and the performance depends on the cluster configuration and unique IPs in the log. Generally, the runtime increases linearly with the increment of log number; thus, the time complexity is approximately O(\(n\)). Figure 5: Information flow of the log-mining framework. Figure 6: The skewed data problem caused by the default HashPartitioner. 2. Sort the user map by the log number in descending order. The higher a user is ranked in the map, the more frequently the user uses the website. The time complexity of the map sort operation is O(\(n\)log\({}_{2}\)_nt_)). 3. Split users into \(k\) groups using the greedy algorithm [28]. The top \(k\) users in the sorted user map are assigned to \(k\) groups in series. For the rest, each user is assigned to the group with minimal logs until all users are assigned to the \(k\) groups. A user group map stores the split strategy in the format of (useri\({}_{i}\) group\({}_{1}\)), (userj\({}_{i}\) group\({}_{1}\)),..., (userk\({}_{k}\), group\({}_{n}\)). Note that the greedy algorithm yields local optimum group strategy. The dynamic planning solutions can be adopted to split users too. In addition, to maximize the usage of all computation resources, \(k\) is suggested to be equal to or be multiples of the total number of Central Processing Unit (CPU) cores managed by Spark. The greedy algorithm is straightforward, and the time complexity is linear (O(\(n\))). 4. Load all users into Spark and distribute user data across Spark tasks with a customized partitioner. The partitioner receives the user map and partition number as input and assigns each user to a partition using the corresponding group identifier instead of the hash value of the user IP. As a result, the logs are nearly evenly distributed across all partitions, which prevents significant slow tasks and improves the log-mining performance.