4-10-7. Preventing Combinatorial Explosions

The terms bucket dynamically builds buckets based on your data; it doesn’t know up front how many buckets will be generated. While this is fine with a single aggregation, think about what can happen when one aggregation contains another aggregation, which contains another aggregation, and so forth. The combination of unique values in each of these aggregations can lead to an explosion in the number of buckets generated.

terms bucket은 데이터에 기반한 bucket을 동적으로 생성한다. 얼마나 많은 bucket을 생성해야 할지를 미리 알 수는 없다. 이것은 단일 aggregation에서는 잘 되겠지만, 어떤 aggregation이 다른 aggregation을 포함하고, 또 그것이 다른 aggregation을 포함하는 등의 경우에는 어떤 일이 일어날지를 생각해 보자. 이런 aggregation 각각에서, 유일한 값의 조합은, bucket 수의 폭발적인 증가로 이어질 것이다.

Imagine we have a modest dataset that represents movies. Each document lists the actors in that movie:

영화를 나타내는 적당한 데이터 집합을 가지고 있다고 가정해 보자. 각 document는 해당 영화의 배우를 나열하고 있다.

{
  "actors" : [
    "Fred Jones",
    "Mary Jane",
    "Elizabeth Worthing"
  ]
}

If we want to determine the top 10 actors and their top costars, that’s trivial with an aggregation:

10대 배우와 그들의 최고 조연을 알아내려면, aggregation을 사용하면 쉬운 일이다.

{
  "aggs" : {
    "actors" : {
      "terms" : {
         "field" : "actors",
         "size" :  10
      },
      "aggs" : {
        "costars" : {
          "terms" : {
            "field" : "actors",
            "size" :  5
          }
        }
      }
    }
  }
}

This will return a list of the top 10 actors, and for each actor, a list of their top five costars. This seems like a very modest aggregation; only 50 values will be returned!

이것은 10대 배우의 목록과, 각 배우에 대해, 그들의 조연 배우의 목록을 반환한다. 이것은 매우 적절한 aggregation처럼 보인다. 50개의 값만 반환될 것이다.

However, this seemingly innocuous query can easily consume a vast amount of memory. You can visualize a terms aggregation as building a tree in memory. The actors aggregation will build the first level of the tree, with a bucket for every actor. Then, nested under each node in the first level, the costars aggregation will build a second level, with a bucket for every costar, as seen in Figure 42, “전체 tree 구축”. That means that a single movie will generate n2 buckets!

그러나, 외견상 문제가 없어 보이는, 이 query는 어마어마한 양의 메모리를 소모한다. 메모리에 tree를 만들기 위해, terms aggregation을 시각화할 수 있다. actors aggregation은 모든 배우의 bucket을 이용하여, tree의 첫 번째 단계를 만든다. 그 다음에, Figure 42, “전체 tree 구축”에서 볼수 있듯이, 첫 번째 단계에서 각 node의 아래에 중첩된, costars aggregation은 모든 조연 배우 bucket을 이용하여, 두 번째 단계를 만든다. 즉, 어떤 하나의 영화는 n2 개의 bucket을 생성한다.

Figure 42. 전체 tree 구축

To use some real numbers, imagine each movie has 10 actors on average. Each movie will then generate 102 == 100 buckets. If you have 20,000 movies, that’s roughly 2,000,000 generated buckets.

실제로 발생하는 수를 생각해보기 위해, 각 영화에 평균 10명의 배우가 출연했다고 가정해 보자. 그러면, 각 영화는 102 == 100 개의 bucket을 생성한다.. 20,000개의 영화를 가지고 있다면, 대략, 2,000,000 개의 bucket을 생성할 것이다.

Now, remember, our aggregation is simply asking for the top 10 actors and their co-stars, totaling 50 values. To get the final results, we have to generate that tree of 2,000,000 buckets, sort it, and finally prune it such that only the top 10 actors are left. This is illustrated in Figure 43, “tree의 정렬” and Figure 44, “tree의 정리”.

자, 이 aggregation은 단순하게, 10명의 주연 배우와 그들의 조연 배우, 합해서 50명을 찾고 있다. 최종 결과를 얻으려면, 2,000,000개 bucket의 tree를 생성하고, 그것을 정렬하고, 마지막으로, 10명의 배우가 남을 때까지 정리해야 한다. 이것이 Figure 43, “tree의 정렬”과 Figure 44, “tree의 정리”에 묘사되어 있다.

Figure 43. tree의 정렬

Figure 44. tree의 정리

At this point you should be quite distraught. Twenty thousand documents is paltry, and the aggregation is pretty tame. What if you had 200 million documents, wanted the top 100 actors and their top 20 costars, as well as the costars' costars?

지금, 약간 혼란스러울 것이다. 20,000개의 document는 별 것 아니고 aggregation도 마찬가지이다. 만약, 2억 개의 document를 가지고 있는데, 100 대 배우와 그들의 최고 조연 20명을, 마찬가지로, 조연의 조연을 알아내려면, 무슨 일이 일어날까?

You can appreciate how quickly combinatorial expansion can grow, making this strategy untenable. There is not enough memory in the world to support uncontrolled combinatorial explosions.

얼마나 빨리 조합의 확장이 커질지, 이 전략은 말이 안 된다는 것을 알 수 있을 것이다. 통제되지 않는 조합의 폭발을 지원하는 세계에서는, 메모리가 부족할 수 밖에 없다.

Depth-First Versus Breadth-Firstedit

Elasticsearch allows you to change the collection mode of an aggregation, for exactly this situation. The strategy we outlined previously—building the tree fully and then pruning—is called depth-firstand it is the default. Depth-first works well for the majority of aggregations, but can fall apart in situations like our actors and costars example.

정확히 이런 상황을 위해, Elasticsearch는 aggregation의 수집 모드(collection mode) 를 변경할 수 있다.위에서 설명한 전략(완전한 tree를 구축하고, 정리하는)을 depth-first 라 하는데, 이것이 기본이다. depth-first는 aggregation의 대부분에서 잘 동작하지만, 위와 같은 주연-조연 배우 예제에서는 아니다.

For these special cases, you should use an alternative collection strategy called breadth-first. This strategy works a little differently. It executes the first layer of aggregations, and then performs a pruning phase before continuing, as illustrated in Figure 45, “첫 번째 단계의 구축” through Figure 47, “첫 번째 단계의 정리”.

이런 특별한 상황에서는, breadth-first 라는 대조적인 수집 전략을 사용해야 한다. 이 전략은 약간 다르게 동작한다. Figure 45, “첫 번째 단계의 구축” 에서 Figure 47, “첫 번째 단계의 정리” 처럼, aggregation의 첫 번째 단계를 실행한 다음, 계속하기 전에 정리 작업을 수행한다.

In our example, the actors aggregation would be executed first. At this point, we have a single layer in the tree, but we already know who the top 10 actors are! There is no need to keep the other actors since they won’t be in the top 10 anyway.

이 예에서, actors aggregation이 먼저 실행된다. 이 시점에서, tree의 첫 번째 단계를 가지고 있다. 즉, 10대 배우가 누구인지 알고 있다. 어쨌든 10대 배우가 아닌 다른 배우들을 가지고 있을 필요가 없다.

Figure 45. 첫 번째 단계의 구축

Figure 46. 첫 번째 단계의 정렬

Figure 47. 첫 번째 단계의 정리

Since we already know the top ten actors, we can safely prune away the rest of the long tail. After pruning, the next layer is populated based on its execution mode, and the process repeats until the aggregation is done, as illustrated in Figure 48, “남아있는 node의 전체 단계를 채운다”. This prevents the combinatorial explosion of buckets and drastically reduces memory requirements for classes of queries that are amenable to breadth-first.

이미 10대 배우를 알고 있기 때문에, 불필요한 나머지는 아무 문제 없이 정리할 수 있다. 정리 후에, 다음 단계가 그것의 실행 모드를 기반으로 채워지고, Figure 48, “남아있는 node의 전체 단계를 채운다”에서 묘사된 것처럼, process는 aggregation이 완료될 때까지 반복한다. 이것은 bucket 조합의 폭발을 방지하고, breadth-first를 처리할 수 있는 종류의 query에 대한 메모리 요구량을 급격하게 줄인다.

Figure 48. 남아있는 node의 전체 단계를 채운다

To use breadth-first, simply enable it via the collect parameter:

breadth-first를 사용하기 위해, collect 매개변수를 사용하여 간단하게 활성화할 수 있다.

{
  "aggs" : {
    "actors" : {
      "terms" : {
         "field" :        "actors",
         "size" :         10,
         "collect_mode" : "breadth_first" 
      },
      "aggs" : {
        "costars" : {
          "terms" : {
            "field" : "actors",
            "size" :  5
          }
        }
      }
    }
  }
}

기본적으로 aggregation 별로 breadth-first 를 활성화할 수 있다.

Breadth-first should be used only when you expect more buckets to be generated than documents landing in the buckets. Breadth-first works by caching document data at the bucket level, and then replaying those documents to child aggregations after the pruning phase.

breadth-first는 bucket에 있는 document보다 더 많은 bucket이 생성될 것으로 예상되는 경우에만 사용되어야 한다. breadth-first는 bucket 수준에서 document 데이터를 잡고(caching), 정리한 후에, 하위 aggregation에 이들 document를 다시 적용(replaying)한다.

The memory requirement of a breadth-first aggregation is linear to the number of documents in each bucket prior to pruning. For many aggregations, the number of documents in each bucket is very large. Think of a histogram with monthly intervals: you might have thousands or hundreds of thousands of documents per bucket. This makes breadth-first a bad choice, and is why depth-first is the default.

breadth-first aggregation의 메모리 요구량은 정리하기 전에 각 bucket에 있는 document 수에 비례한다. 많은 aggregation에서, 각 bucket에 있는 document의 수는 매우 크다. 월간 histogram을 생각해 보면, bucket별로 수 천 또는 수 십만개의 document를 가지고 있을 것이다. 이런 경우 breadth-first는 좋지 않은 선택이 되고, depth-first가 기본이 되는 이유이다.

But for the actor example—which generates a large number of buckets, but each bucket has relatively few documents—breadth-first is much more memory efficient, and allows you to build aggregations that would otherwise fail.

그러나, 배우 예제(각 bucket은 상대적으로 적은 document를 가지고 있지만, 매우 많은 bucket을 만들어 내는 상황)에서, breadth-first는 메모리 사용이 훨씬 더 효율적이고, 그렇게 하지 않으면 실패할 aggregation을 구축할 수 있다.