재미있는 ArrayList(와 TroubleShooting)

들어가며

지난번에는 ArrayList가 add를 수행하는 방법에 대해 정리했다.

이번에는 업무 수행 중 발생했던 이슈를 통해 ArrayList 의 addAll 에 대해 알아보자.

 

문제 발생 배경

Affiliate System 구축은 아키텍처 설계, 데이터 모델링부터 개발/배포/운영까지 내가 총괄하는 첫 프로젝트였다.

N레벨까지 무한 확장 가능한 다단계 트레이더 영입 및 커미션 지급 시스템인데,

거래소에서 인플루언서 등 영업력이 있는 사람들을 Affiliate 으로 영입하고, Affiliate 은 하위에 또다른 Affiliate 을 데려오거나 직속 고객을 모아 자신의 하부로부터 발생한 거래 수수료의 일정 퍼센티지를 커미션으로 지급받는, 한마디로 다단계 구조라고 할 수 있다.

 

Affiliate 하위에 또 Affiliate, 그 하위에 또다른 Affiliate, 하부에 Affiliate, 그 하부에 또다른 Affiliate, ...

이렇게 N레벨까지 깊이와 너비 모두 무한 확장 가능하도록 구현하는 것이 요구사항이었고, 수많은 회의를 통해 세부 요구사항을 확정했다.

Tree 를 사용해 구현했고, Node 내 필드는 다음과 같이 구성했다.

public class Node {
    private AffiliateInfo me;
    private Node parent;
    private List<Node> children;
}

 

문제는 여기에서 발생한다.

'자기 자신을 포함한 하부 모든 어필리엇을 대상으로 특정 통계 데이터를 집계' 하는 요구사항을 구현할 때, 이렇게 로직을 작성한 것.

public void aggregateStatisticalInfo() {
    Tree.Node me = findNode(affiliateId);
    List<Tree.Node> targets = me.getChildren();
    targets.add(me);

    for (Tree.Node node : targets) {
    	// children 에 접근해 특정 데이터를 찾는 코드
    }
    
    // ...
  }

 

StackOverFlow 는 아닐 줄 알았지

StackOverFlow 가 발생했고, 원인은 한번에 찾았지만 미리 이 문제를 생각하지 못한 것이 못내 아쉬웠다.

문제가 되는 부분은 me.getChildren() 과 targets.add(me) 였는데, 이유를 짐작할 수 있을 것이다.

 

1. me.getChildren()

- 문제 : Node 내 children ArrayList 를 그대로 return 했다.

 

2. targets.add(me)

- 문제 : targets 에 원본 객체를 add 했다.

 

2번은 그 자체로는 문제가 되지 않고 1번으로 인해 문제가 된 로직이므로, 1번 getter method 를 중심으로 살펴보자.

public List<Tree.Node> getChildren() {
    return this.children;
}

 

원본 배열 리턴이 뭐 어때서

맞다. 그 자체로는 큰문제가 아닐 수도 있지.

하지만 해당 배열에 자기 자신 객체를 추가함으로써 children 탐색에 이상이 생길 것이라고 생각하지 못한 게 문제다.

 

예를 들어, 다음과 같은 구조를 가진 Tree 가 있다.

- A 라는 Affiliate 하부에는 B, C, D 라는 자식 Affiliate 들이 존재한다.

- B 라는 Affiliate 하부에는 1, 2, 3 이라는 자식 Affiliate 들이 존재한다.

- C 라는 Affiliate 하부에는 4, 5, 6 이라는 자식 Affiliate 들이 존재한다.

- D 라는 Affiliate 하부에는 7, 8, 9 라는 자식 Affiliate 들이 존재한다.

 

그림1과 같은 트리 구조가 있고, A.getChildren() 을 한 후 A 객체를 해당 배열에 추가하면 그림2와 같은 ArrayList 가 된다.

 

 

자, 그럼 문제는?

targets 배열을 순회하면서 Node.getChildren() 을 통해 깊이 우선 탐색을 하며 특정 정보를 찾는데, A가 또 들어있다.

A의 자식들 중에는 B, C, D 가 있고 B의 자식들 중에는 1, 2, 3 이, C의 자식들 중에는 4, 5, 6 이, D의 자식들 중에는 7, 8, 9 가 있다.

짐작했겠지만 여기에서 StackOverFlow 가 발생한다.

 

결국 문제는 reference 임을 잊고 원본 배열을 리턴한 것도 모자라, 원본 배열을 변경하는 위험천만한 일을 한 것이 원인이 되어 발생했다.

 

다시는 안 잊어버릴 ArrayList addAll() 내부 로직 살펴보기

결국 getter method 로직에서 원본 배열을 그대로 리턴하지 않고, 복사해서 리턴하도록 변경해 해결했다.

ArrayList 의 addAll 을 이용해 원본 배열이 변경될 여지를 없애고, 탐색 시 영향이 없도록 해 준 것이다.

 

1. addAll()

public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    modCount++;
    int numNew = a.length;
    if (numNew == 0)
        return false;
    Object[] elementData;
    final int s;
    if (numNew > (elementData = this.elementData).length - (s = size))
        elementData = grow(s + numNew);
    System.arraycopy(a, 0, elementData, s, numNew);
    size = s + numNew;
    return true;
}

위 코드는 ArrayList.java 의 addAll 메서드 내부 로직이다.

Collection 을 매개변수로 받아 배열로 변경한 후 해당 배열의 요소를 복사해 처리하고 있다.

 

2. add()

private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}

이 코드는 ArrayList.java 의 add 메서드 내부 로직이다.

매개변수로 받은 객체 e를 ArrayList 내부 배열에 그대로 할당하고 있다.

 

결론

너무나도 잘 알고 잘 사용하고 있다고 생각했던 ArrayList, 잘 핸들링하고 있다고 생각한 StackOverFlow 가 내게 준 것...

이번 일을 계기로 항상 꼼꼼하게 확인하며 로직을 작성하는 습관이 생겼다.

 

번외로 Affiliate System 정산 로직을 Python 으로 작성할 때 list 가 Java ArrayList 와 작동방식이 달라 당황한 적이 있는데,

이번 일을 계기로 쉽게 해결할 수 있었던 기억이 있다.

 

내부 구현을 확인하고 나니 ArrayList 의 addAll 이나 add 를 사용할 때 전보다 더 주의하고 더 깊게 생각하며 작성하게 된다.

입체적으로 사고하고, 객체지향 원칙대로 프로그래밍하는 것도 잊지 말자.