Hourglass-A library for incremental processing on Hadoop IEEE International Conference on Big Data, 2013 2015.12.03 정보통신공학 전현욱

INDEX Introduction Related Work Incremental Model Evaluation Conclusion

1. Introduction (1/2) Hadoop enables processing of large data sets through its relatively easy-to-use semantics. At LinkedIn Hadoop is used for people, job, and other entity recommendations, ad targeting, news feed updates, analytical dashboards, and ETL, among others. ① 클라이언트로부터 작업요청을 받은 JobTracker는 TaskTracker별로 처리할 작업 목록을 구성한다. ② TaskTracker 는 주기적으로 heartbeat를 전송하고, JobTracker는 이 메시지의 반환 값에 처리할 작업 ID를 반환한다. ③ 작업 ID를 받은 TaskTracker 는 관련된 작업의 정보를 하둡 파일 시스템에서 가져오고, 수행할 프로그램도 하둡 파일 시스템으로부터 로컬에 저장한다. ④ TaskTracker 에서는 fork 명령을 이용해 Map 과 Reduce 를 실행하고 JobTracker에게 메세지를 전달하면서 파일에 대한 변경사항은 DataNode와 통신한다. DataNode는 다시 NameNode에게 파일 블럭에 대한 정보를 전달한다.

1. Introduction (2/2) However, jobs are often written inefficiently for tasks that could be computed incrementally due to the burdensome incremental state management for the programmer. This paper introduces Hourglass, a library for developing incremental monoid computations on Hadoop. ① 클라이언트로부터 작업요청을 받은 JobTracker는 TaskTracker별로 처리할 작업 목록을 구성한다. ② TaskTracker 는 주기적으로 heartbeat를 전송하고, JobTracker는 이 메시지의 반환 값에 처리할 작업 ID를 반환한다. ③ 작업 ID를 받은 TaskTracker 는 관련된 작업의 정보를 하둡 파일 시스템에서 가져오고, 수행할 프로그램도 하둡 파일 시스템으로부터 로컬에 저장한다. ④ TaskTracker 에서는 fork 명령을 이용해 Map 과 Reduce 를 실행하고 JobTracker에게 메세지를 전달하면서 파일에 대한 변경사항은 DataNode와 통신한다. DataNode는 다시 NameNode에게 파일 블럭에 대한 정보를 전달한다.

2. Related Work There are two broad classes of approaches to incremental computation over large data sets. The first class of systems provides abstractions the programmer can use to store and use state across successive runs so that only the necessary sub-computations need be performed. The second class of approaches are systems that attempt to reuse the results of prior computations transparently. Our approach borrows techniques from systems in the first class to accommodate incremental processing atop Hadoop. ① 클라이언트로부터 작업요청을 받은 JobTracker는 TaskTracker별로 처리할 작업 목록을 구성한다. ② TaskTracker 는 주기적으로 heartbeat를 전송하고, JobTracker는 이 메시지의 반환 값에 처리할 작업 ID를 반환한다. ③ 작업 ID를 받은 TaskTracker 는 관련된 작업의 정보를 하둡 파일 시스템에서 가져오고, 수행할 프로그램도 하둡 파일 시스템으로부터 로컬에 저장한다. ④ TaskTracker 에서는 fork 명령을 이용해 Map 과 Reduce 를 실행하고 JobTracker에게 메세지를 전달하면서 파일에 대한 변경사항은 DataNode와 통신한다. DataNode는 다시 NameNode에게 파일 블럭에 대한 정보를 전달한다.

3. Incremental Model (1/7) Problem Definition Computing the last login time in this way is an example of what we will call an append-only sliding window problem. In this case, the start of the window is fixed and the end grows as new data becomes available. As a result, the window length is always increasing ① 클라이언트로부터 작업요청을 받은 JobTracker는 TaskTracker별로 처리할 작업 목록을 구성한다. ② TaskTracker 는 주기적으로 heartbeat를 전송하고, JobTracker는 이 메시지의 반환 값에 처리할 작업 ID를 반환한다. ③ 작업 ID를 받은 TaskTracker 는 관련된 작업의 정보를 하둡 파일 시스템에서 가져오고, 수행할 프로그램도 하둡 파일 시스템으로부터 로컬에 저장한다. ④ TaskTracker 에서는 fork 명령을 이용해 Map 과 Reduce 를 실행하고 JobTracker에게 메세지를 전달하면서 파일에 대한 변경사항은 DataNode와 통신한다. DataNode는 다시 NameNode에게 파일 블럭에 대한 정보를 전달한다.

3. Incremental Model (2/7) Problem Definition Computing the impression counts in this way is an example of what we will call a fixed-length sliding window problem. For this type of problem the length of the window is fixed. The start and end of the window both advance as new data becomes available ① 클라이언트로부터 작업요청을 받은 JobTracker는 TaskTracker별로 처리할 작업 목록을 구성한다. ② TaskTracker 는 주기적으로 heartbeat를 전송하고, JobTracker는 이 메시지의 반환 값에 처리할 작업 ID를 반환한다. ③ 작업 ID를 받은 TaskTracker 는 관련된 작업의 정보를 하둡 파일 시스템에서 가져오고, 수행할 프로그램도 하둡 파일 시스템으로부터 로컬에 저장한다. ④ TaskTracker 에서는 fork 명령을 이용해 Map 과 Reduce 를 실행하고 JobTracker에게 메세지를 전달하면서 파일에 대한 변경사항은 DataNode와 통신한다. DataNode는 다시 NameNode에게 파일 블럭에 대한 정보를 전달한다.

3. Incremental Model (3/7) Our Approach (Append-only Sliding Window) First we introduce the concept of a partition-collapsing job, which reads partitioned data as input and merges the data together, producing a single piece of output data. Suppose that the reduce step can be represented particular key: a⊕b⊕c⊕d (a⊕b)⊕(c⊕d) When new data e arrives, we can compute (a⊕b)⊕(c⊕d)⊕e without having to recompute (a⊕b) and (c⊕d) ① 클라이언트로부터 작업요청을 받은 JobTracker는 TaskTracker별로 처리할 작업 목록을 구성한다. ② TaskTracker 는 주기적으로 heartbeat를 전송하고, JobTracker는 이 메시지의 반환 값에 처리할 작업 ID를 반환한다. ③ 작업 ID를 받은 TaskTracker 는 관련된 작업의 정보를 하둡 파일 시스템에서 가져오고, 수행할 프로그램도 하둡 파일 시스템으로부터 로컬에 저장한다. ④ TaskTracker 에서는 fork 명령을 이용해 Map 과 Reduce 를 실행하고 JobTracker에게 메세지를 전달하면서 파일에 대한 변경사항은 DataNode와 통신한다. DataNode는 다시 NameNode에게 파일 블럭에 대한 정보를 전달한다.

3. Incremental Model (4/7) Our Approach (Append-only Sliding Window) We refer to this as a partition-preserving job. This achieves the same result as running a separate MapReduce job on each day of input without the scheduling overhead. ① 클라이언트로부터 작업요청을 받은 JobTracker는 TaskTracker별로 처리할 작업 목록을 구성한다. ② TaskTracker 는 주기적으로 heartbeat를 전송하고, JobTracker는 이 메시지의 반환 값에 처리할 작업 ID를 반환한다. ③ 작업 ID를 받은 TaskTracker 는 관련된 작업의 정보를 하둡 파일 시스템에서 가져오고, 수행할 프로그램도 하둡 파일 시스템으로부터 로컬에 저장한다. ④ TaskTracker 에서는 fork 명령을 이용해 Map 과 Reduce 를 실행하고 JobTracker에게 메세지를 전달하면서 파일에 대한 변경사항은 DataNode와 통신한다. DataNode는 다시 NameNode에게 파일 블럭에 대한 정보를 전달한다.

3. Incremental Model (5/7) Our Approach (Append-only Sliding Window) Partition-preserving jobs provide one way to address the inefficiency of the append-only sliding window problem presented in Figure 1. Assuming the last login times are first computed for each day as in Figure 4, the results can serve as a substitute for the original login data. One interesting property of the last-login problem is that the previous output can be reused. ① 클라이언트로부터 작업요청을 받은 JobTracker는 TaskTracker별로 처리할 작업 목록을 구성한다. ② TaskTracker 는 주기적으로 heartbeat를 전송하고, JobTracker는 이 메시지의 반환 값에 처리할 작업 ID를 반환한다. ③ 작업 ID를 받은 TaskTracker 는 관련된 작업의 정보를 하둡 파일 시스템에서 가져오고, 수행할 프로그램도 하둡 파일 시스템으로부터 로컬에 저장한다. ④ TaskTracker 에서는 fork 명령을 이용해 Map 과 Reduce 를 실행하고 JobTracker에게 메세지를 전달하면서 파일에 대한 변경사항은 DataNode와 통신한다. DataNode는 다시 NameNode에게 파일 블럭에 대한 정보를 전달한다.

3. Incremental Model (6/7) Our Approach (Append-only Sliding Window) This suggests that the problem can be solved with a single partition-collapsing job that reuses output This has two advantages over the previous two-pass version. First, the output data is usually smaller than both the input data and the intermediate data Second, it avoids scheduling overhead and increased wall clock time from having two sequentially executed MapReduce jobs ① 클라이언트로부터 작업요청을 받은 JobTracker는 TaskTracker별로 처리할 작업 목록을 구성한다. ② TaskTracker 는 주기적으로 heartbeat를 전송하고, JobTracker는 이 메시지의 반환 값에 처리할 작업 ID를 반환한다. ③ 작업 ID를 받은 TaskTracker 는 관련된 작업의 정보를 하둡 파일 시스템에서 가져오고, 수행할 프로그램도 하둡 파일 시스템으로부터 로컬에 저장한다. ④ TaskTracker 에서는 fork 명령을 이용해 Map 과 Reduce 를 실행하고 JobTracker에게 메세지를 전달하면서 파일에 대한 변경사항은 DataNode와 통신한다. DataNode는 다시 NameNode에게 파일 블럭에 대한 정보를 전달한다.

3. Incremental Model (7/7) Our Approach (Fixed-length Sliding Window) Similar to the append-only sliding window case, this problem can be solved using a sequence of two jobs, the first partition-preserving and the second partition-collapsing. ① 클라이언트로부터 작업요청을 받은 JobTracker는 TaskTracker별로 처리할 작업 목록을 구성한다. ② TaskTracker 는 주기적으로 heartbeat를 전송하고, JobTracker는 이 메시지의 반환 값에 처리할 작업 ID를 반환한다. ③ 작업 ID를 받은 TaskTracker 는 관련된 작업의 정보를 하둡 파일 시스템에서 가져오고, 수행할 프로그램도 하둡 파일 시스템으로부터 로컬에 저장한다. ④ TaskTracker 에서는 fork 명령을 이용해 Map 과 Reduce 를 실행하고 JobTracker에게 메세지를 전달하면서 파일에 대한 변경사항은 DataNode와 통신한다. DataNode는 다시 NameNode에게 파일 블럭에 대한 정보를 전달한다.

4. Evaluation (1/2) Four benchmarks were used to evaluate the performance of Hourglass. All used fixed-length sliding windows. Use Hadoop 1.0.4 ① 클라이언트로부터 작업요청을 받은 JobTracker는 TaskTracker별로 처리할 작업 목록을 구성한다. ② TaskTracker 는 주기적으로 heartbeat를 전송하고, JobTracker는 이 메시지의 반환 값에 처리할 작업 ID를 반환한다. ③ 작업 ID를 받은 TaskTracker 는 관련된 작업의 정보를 하둡 파일 시스템에서 가져오고, 수행할 프로그램도 하둡 파일 시스템으로부터 로컬에 저장한다. ④ TaskTracker 에서는 fork 명령을 이용해 Map 과 Reduce 를 실행하고 JobTracker에게 메세지를 전달하면서 파일에 대한 변경사항은 DataNode와 통신한다. DataNode는 다시 NameNode에게 파일 블럭에 대한 정보를 전달한다.

4. Evaluation (1/4) Weibo Impressions Benchmark The Weibo recommendation training data consists of a set of item recommendations. These were partitioned by day according to their timestamp, producing data spanning a month in time. ① 클라이언트로부터 작업요청을 받은 JobTracker는 TaskTracker별로 처리할 작업 목록을 구성한다. ② TaskTracker 는 주기적으로 heartbeat를 전송하고, JobTracker는 이 메시지의 반환 값에 처리할 작업 ID를 반환한다. ③ 작업 ID를 받은 TaskTracker 는 관련된 작업의 정보를 하둡 파일 시스템에서 가져오고, 수행할 프로그램도 하둡 파일 시스템으로부터 로컬에 저장한다. ④ TaskTracker 에서는 fork 명령을 이용해 Map 과 Reduce 를 실행하고 JobTracker에게 메세지를 전달하면서 파일에 대한 변경사항은 DataNode와 통신한다. DataNode는 다시 NameNode에게 파일 블럭에 대한 정보를 전달한다.

4. Evaluation (2/4) PYMK Impressions Benchmark “People You May Know” (PYMK) is a recommendation system at LinkedIn that suggests connections to members. This data is recorded as a sequence of (src,destIds) pairs, partitioned by day. ① 클라이언트로부터 작업요청을 받은 JobTracker는 TaskTracker별로 처리할 작업 목록을 구성한다. ② TaskTracker 는 주기적으로 heartbeat를 전송하고, JobTracker는 이 메시지의 반환 값에 처리할 작업 ID를 반환한다. ③ 작업 ID를 받은 TaskTracker 는 관련된 작업의 정보를 하둡 파일 시스템에서 가져오고, 수행할 프로그램도 하둡 파일 시스템으로부터 로컬에 저장한다. ④ TaskTracker 에서는 fork 명령을 이용해 Map 과 Reduce 를 실행하고 JobTracker에게 메세지를 전달하면서 파일에 대한 변경사항은 DataNode와 통신한다. DataNode는 다시 NameNode에게 파일 블럭에 대한 정보를 전달한다.

4. Evaluation (3/4) Page Views Benchmark At LinkedIn, page views are recorded in an event stream, where for each event, the member ID and page that was viewed is recorded. For this benchmark we computed several metrics from this event stream over a 30 day sliding window. ① 클라이언트로부터 작업요청을 받은 JobTracker는 TaskTracker별로 처리할 작업 목록을 구성한다. ② TaskTracker 는 주기적으로 heartbeat를 전송하고, JobTracker는 이 메시지의 반환 값에 처리할 작업 ID를 반환한다. ③ 작업 ID를 받은 TaskTracker 는 관련된 작업의 정보를 하둡 파일 시스템에서 가져오고, 수행할 프로그램도 하둡 파일 시스템으로부터 로컬에 저장한다. ④ TaskTracker 에서는 fork 명령을 이용해 Map 과 Reduce 를 실행하고 JobTracker에게 메세지를 전달하면서 파일에 대한 변경사항은 DataNode와 통신한다. DataNode는 다시 NameNode에게 파일 블럭에 대한 정보를 전달한다.

4. Evaluation (4/4) Cardinality Estimation Benchmark The page views data from the previous example can also be used to determine the total number of LinkedIn members who accessed the website over a span of time. ① 클라이언트로부터 작업요청을 받은 JobTracker는 TaskTracker별로 처리할 작업 목록을 구성한다. ② TaskTracker 는 주기적으로 heartbeat를 전송하고, JobTracker는 이 메시지의 반환 값에 처리할 작업 ID를 반환한다. ③ 작업 ID를 받은 TaskTracker 는 관련된 작업의 정보를 하둡 파일 시스템에서 가져오고, 수행할 프로그램도 하둡 파일 시스템으로부터 로컬에 저장한다. ④ TaskTracker 에서는 fork 명령을 이용해 Map 과 Reduce 를 실행하고 JobTracker에게 메세지를 전달하면서 파일에 대한 변경사항은 DataNode와 통신한다. DataNode는 다시 NameNode에게 파일 블럭에 대한 정보를 전달한다.

5. Conclusion In this paper we presented Hourglass, a framework for efficiently processing data incrementally on Hadoop by providing an easy accumulator-based interface for the programmer. Using real-world use cases and data from LinkedIn, we show that a 50–98% reduction in total task time and a 25–50% reduction in wall clock time are possible compared to baseline non-incremental implementations. ① 클라이언트로부터 작업요청을 받은 JobTracker는 TaskTracker별로 처리할 작업 목록을 구성한다. ② TaskTracker 는 주기적으로 heartbeat를 전송하고, JobTracker는 이 메시지의 반환 값에 처리할 작업 ID를 반환한다. ③ 작업 ID를 받은 TaskTracker 는 관련된 작업의 정보를 하둡 파일 시스템에서 가져오고, 수행할 프로그램도 하둡 파일 시스템으로부터 로컬에 저장한다. ④ TaskTracker 에서는 fork 명령을 이용해 Map 과 Reduce 를 실행하고 JobTracker에게 메세지를 전달하면서 파일에 대한 변경사항은 DataNode와 통신한다. DataNode는 다시 NameNode에게 파일 블럭에 대한 정보를 전달한다.

감사합니다