Proxy 는 사전적인 의미로 “대리인"이라는 뜻입니다. java 에서 프록시란 대리를 수행하는 클래스를 의미합니다. Proxy 는 Client 가 사용하려고 하는 실제 대상인 것 처럼 위장을 해서 클라이언트의 요청을 받아줍니다. 여기서 위장이란 "다형성"을 의미합니다.

Proxy 를 통해 최종적으로 요청을 위임받아 처리하는 실제 오브젝트를 target 또는 real subject(실체)라 부릅니다.

Proxy 는 실제로 타겟이 담당하는 역할 요청을 대신받아서 요청 이전, 이후에 대한 로직을 추가할 수 있는 객체입니다. 이렇게 하면 실제 타겟의 코드는 수정하지 않으면서 기능적인 추가를 할 수 있다는 장점이 있습니다.

Proxy 구현

proxy 를 구현하기 위해서는 인터페이스를 이용한 방법과 상속을 이용한 방법이 있습니다.

1. target 과 같은 인터페이스를 구현
2. proxy 가 target 을 제어할 수 있는 위치에 존재

(2번이 말이 조금 어려운데, 저는 "접근 가능한 package 위치에 있다는 의미"로 이해를 했습니다. 예를 들어 접근제어자가 default 인 메소드를 제어하고 싶으면 같은 패키지에 존재해야 한다의 의미정도로 생각합니다. 제 이해가 틀렸다면 지적해주시면 감사하겠습니다 😃 )

Proxy 구현 예제

서비스를 실행하는 시간을 구하는 로깅 Proxy 를 구현해보려고 합니다.

OrderService.java

public interface OrderService {
    void orderGoods(User buyer, List<Goods> goods);
}

Proxy 객체와 Target 이 공유할 수 있는 인터페이스 입니다.

OrderServiceImpl.java

public class OrderServiceImpl implements OrderService {

    private List<Order> orderRepository = new ArrayList<>();

    @Override
    public void orderGoods(User buyer, List<Goods> goods) {
        ...
    }
}

OrderServiceImpl 는 OrderService 인터페이스를 구현합니다. Proxy 의 Target 에 해당하는 클래스입니다.

LoggingProxy.java

public class LoggingProxy implements OrderService {

    private OrderService orderService;

    public LoggingProxy(OrderService orderService) {
        this.orderService = orderService;
    }

    @Override
    public void orderGoods(User buyer, List<Goods> goods) {
        long startTime = System.nanoTime(); // 시간측정 start
        orderService.orderGoods(buyer, goods); // 본래 클라이언트가 요청했던 동작 
        long endTime = System.nanoTime(); // 시간측정 end
        System.out.println((endTime - startTime) + " nanoseconds");
    }
}

LoggingProxy 클래스가 Target 클래스인 OrderServiceImpl 과 동일한 OrderService 인터페이스를 implements 했기 때문에 클라이언트 입장에서 Proxy 객체를 OrderService 변수로 참조할 수 있게 되었습니다. 예를 들면 아래와 같습니다.

private OrderService orderService = new LoggingProxy();

(LoggingProxy 객체는 클라이언트가 직접 생성하지 않습니다.)

이렇게 함으로써 OrderService 가 제공하는 메서드를 호출할 수 있습니다. 마치 OrderService 가 동작하는 것 처럼 보입니다. 이제 이 코드를 실행시켜보려고 합니다.

Runner.java

public static void main(String[] args) {
    OrderService orderService = new OrderServiceImpl();
    LoggingProxy proxy = new LoggingProxy(orderService);

    User buyer = new User();
    buyer.setUsername("주문지");
    buyer.setUserId(1);
    buyer.setAddress("구로");

    Goods goods = new Goods();
    goods.setName("치킨");
    goods.setPrice(10000d);
    goods.setGoodsId(1);

    proxy.orderGoods(buyer, Arrays.asList(goods));
}

Runner 는 클라이언트 코드를 의미합니다. 스프링을 사용해보신 분들은 아시겠지만 우리가 직접 orderService 생성하지 않습니다. 스프링 프레임워크에서 클라이언트는 아래과 같이 코드를 작성했을 것입니다.

@Controller
public class SpringController {
    @Autowired
    private OrderService orderService;

    @RequestMapping(value = "order", method = RequestMethod.POST)
    public void order(int userId, List<Integer> goodsId) {
        // ... id 로 객체를 find 한다
        orderService.orderGoods(buyer, goods);
    }
}

OrderService 인스턴스는 스프링을 프레임 워크를 통해서 주입받았을 것입니다. 따라서 스프링이 언제든 OrderService 인스턴스 대신에 LoggingProxy 인스턴스를 넘겨줄 수 있다는 것이 핵심입니다. 그리고 클라이언트는 프록시가 아닌 OrderService 인스턴스가 orderService 변수에 DI 되었을 것이라고 가정하고 코드를 작성합니다.

AOP

AOP 는 Aspect Oriented Programming 의 약자로 관점 지향 프로그래밍이라고 불립니다. 즉, 로직을 기준으로 관점 별로 로직을 묶어서 모듈화 할 수 있도록 돕겠다는 취지에서 나온 프로그래밍 기법이라고 할 수 있습니다.

예를 들어서 보안, 로깅, 데이터베이스 연결, 캐싱, 트랜잭션, 비즈니스 로직 등등 애플리케이션이 동작하기 위해서 해주어야할 처리가 있는데 이를 하나의 Service 클래스에서 관리한다면 어떻게 될까요? 애플리케이션 여러 목적을 하는 코드가 하나의 Service 클래스에 있기 때문에 코드를 파악하기 어려워질 것입니다.

반면 특정 위치에 있는 코드의 목적이 “보안"이라는 주제로 명확하게 정해져 있다면 코드를 파악하기가 쉬워집니다. “보안"이라는 카테고리 안에서 코드의 의도를 파악하기 시작할 수 있기 때문입니다.

이런 주제를 “관심사”라고 부릅니다. AOP 라는 기술을 통해서 클라이언트가, 관심사별로 코드를 모듈화 할 수 있도록 해줍니다.

AOP 가 왜 필요했을까?

객체지향 기술은 분명 성공적인 프로그래밍 방식이었지만, 복잡해져가는 애플리케이션의 요구조건과 기술적인 부분을 모두 해결하기에는 난해함을 가지고 있었습니다.

예를 들어 객체 지향 원칙을 지키면서 기술적인 트랜잭션 & 로깅 등등을 객체지향 기술만으로 처리하기에는 문제가 있었습니다.

출처 : https://gmoon92.github.io/spring/aop/2019/02/09/why-used-aop.html

위 그림을 보면 서비스 비즈니스 로직을 담은 this.userRepo.transferUserAmt(user); 코드 이외에 위아래로 트랜잭션을 처리하기 위한 코드가 존재합니다. 이는 비즈니스 로직과는 관련이 없지만 필수적인 부가 기능입니다. 비즈니스를 처리하기 위한 목적을 가지고 AccountService 클래스를 열었다면 읽기가 난해함을 느낄 것입니다.

AOP 는 이런 객체지향 기술의 한계와 단점을 극복하기 위해 나왔습니다. 한편 AOP 를 사용하면 그 결과로 OOP 를 더더욱 OOP 답게 만들 수 있습니다.

위빙

AOP 를 이해하려면 위빙이라는 단어를 이해해야 합니다. 위빙은 원본 로직에 부가 기능을 추가하는 것을 의미합니다. 위빙을 하는 방법은 다양하게 있을 것입니다. 코드를 위빙한다고 가정하면 어떻게 사용자 코드 사이에 위빙을 할 수 있을까요?? 예를 들면 컴파일 하기 전에 .java 파일에 필요한 코드를 앞뒤로 삽입한 후 컴파일하는 방법이 있을 수 있겠네요. 이렇게 위빙을 하는 시점이 언제냐에 따라서 종류가 크게 3가지로 나누어 집니다.

• 컴파일 시점 위빙
• 클래스 로딩 시점 위빙
• 런타임 시점 위빙

출처 : https://bepoz-study-diary.tistory.com/408

java 코드를 추가하는 방법입니다. 컴파일 시점에 .java 파일을 .class 파일로 변환하는 과정에서 AspectJ 컴파일러가 부가 기능 로직을 붙이는 방식입니다. 컴파일된 .class 를 디컴파일 해보면 AspectJ 관련 호출 코드가 들어감을 알 수 있습니다.

컴파일 시점 위빙의 단점은 특별한 컴파일러가 필요하고 복잡하다는 점입니다. 기본 컴파일러는 java 코드를 변경할 수 없기 때문에 특별한 컴파일러를 사용해야 합니다.

애플리케이션 구동을 위해서는 클래스로더라는 것을 통해서 JVM 에 클래스 정보를 올리는 과정을 거쳐야 합니다. 이 때 JVM 에 올라간 .class 정보를 토대로 코드가 실행됩니다.

클래스 로딩 시점 위빙은 .class 파일을 JVM 에 저장하기 전(클래스로드 타임 전)에 코드를 조작합니다. 그리고 많은 JVM 모니터링 툴들이 사용하는 방법이다.

로드타임 위빙의 단점은 클래스 로더 조작기를 직접 조작해야 한다는 점입니다. 자바 실행 시 특별한 옵션 (java -javaagent)을 통해 클래스 로더 조작기를 지정해야하는데 이 부분이 번거롭고 운영하기 어렵게 만드는 요인입니다.

위에서 배웠던, 프록시 방식의 AOP 를 의미합니다. 이 방법을 사용하면 “컴파일타임 위빙”이나 “로드타임 위빙"의 불편한 사항들이 개선됩니다. 컴파일 시점 처럼 특별한 컴파일러를 사용한다던가 클래스 로더 조작기를 설정하지 않아도 됩니다.

런타임에 스프링으로 부터 필요한 객체를 전달 받아서 “빈포스트프로세서"라는 곳에서 객체를 프록시 객체로 변경 해줍니다.

Spring 에서 AOP 적용 기법

AOP 는 위에서 언급했던 프록시라는 기술을 사용해서 구현됩니다. Spring AOP 는 Proxy 메커니즘을 기반으로 AOP Proxy 를 제공하고 있다. 그리고 IoC 즉, 스프링이 관리하는 컨테이너에서 관리하는 빈 객체만 Proxy 를 적용할 수 있다는 말이기도 합니다.

스프링에서 프록시를 적용하는 방법에는 2가지가 있습니다.

1. JDK Dynamic Proxy
2. CGLIB 라이브러리를 이용한 Proxy

자바에서 제공하는 다이나믹 프록시를 이용하는 방법

jdk runtime proxy 라고도 부르는 이 기술은 다음과 같이 사용합니다.

Object proxy = Proxy.newProxyInstance(ClassLoader       // 클래스로더
                                    , Class<?>[]        // 타깃의 인터페이스
                                    , InvocationHandler // 타깃의 정보가 포함된 Handler
                                                        );

리플랙션을 지원하는 Proxy 클래스의 newProxyInstance 메소드를 사용하면 됩니다. JDK Dynamic Proxy 의 newProxyInstance 메소드가 Proxy 객체를 생성해주는 과정은 다음과 같습니다.

출처 : https://gmoon92.github.io/spring/aop/2019/04/20/jdk-dynamic-proxy-and-cglib.html

1. Target 의 인터페이스를 자체적인 검증 로직을 통해 검증 (access level, 인터페이스가 맞는지 등)
2. ProxyFactory 에 의해 타깃의 인터페이스를 상속한 Proxy 객체 생성
3. Proxy 객체에 InvocationHandler 를 포함시킨 하나의 객체로 반환

JDK Runtime Proxy 는 인터페이스를 기준으로 Proxy 객체를 생성해줍니다. 그렇기 때문에 인터페이스가 아닌 타입의 변수에 JDK Runtime Proxy 를 DI 하려고 하면 예외를 발생시킬 수 있습니다.

인터페이스 타입이 아닌 클래스 타입으로 DI

@RequiredArgsConstructor
@Service
public class CardServiceImpl implements CardService {
        ...
}

@RestController
public class CardController {

        private CardServiceImpl cardService;

    public CardController(CardServiceImpl cardService) {
        this.cardService = cardService;
    }
}

예외 로그

The bean is of type 'com.sun.proxy.$Proxy169' and implements:
    com.slack.slack.domain.service.CardService
    org.springframework.aop.SpringProxy
    org.springframework.aop.framework.Advised
    org.springframework.core.DecoratingProxy

Expected a bean of type 'com.slack.slack.domain.service.impl.CardServiceImpl' which implements:
    com.slack.slack.domain.service.CardService

Action:

Consider injecting the bean as one of its interfaces or forcing the use of CGLib-based proxies by setting proxyTargetClass=true on @EnableAsync and/or @EnableCaching.

Jdk Dynamic Proxy 기반으로 동작하지 않아요!

테스트를 위해서 Spring 에서 인터페이스가 아닌 타입으로 DI 를 받으려고 시도했지만 예외가 발생하지 않았습니다. 이유를 찾기 위해 디버깅 해보니 Jdk Dynamic 프록시가 아닌 GCLIB 을 기반으로 동작하고 있었습니다.

왜 그럴까 검색하다가 다음과 같은 글을 발견했습니다.

spring boot aop 에서 JDK dynamic proxy 이용하는 법

스프링을 Proxy 기반으로 AOP 를 동작시키려면 @EnableAspectJAutoProxy 어노테이션을 설정해야 하는데 이를 아래와 같은 내용을 설정파일에 추가해야 JDK Runtime Proxy 기반으로 동작시킬 수 있다고 합니다.

spring:
  aop:
    auto: false
    proxy-target-class: false

스프링에서 제공하는 CGLIB 을 사용하는 방법

CGLib 은 Code Generator Library 의 약자로 클래스의 바이트코드를 조작하여 Proxy 객체를 생성해주는 라이브러리입니다. Spring CGLib 을 사용하여 인터페이스가 아닌 타깃의 클래스에 대해서도 Proxy 를 생성해줄 수 있습니다.

CGLib 은 Enhancer 라는 클래스를 통해 Proxy 를 생성할 수 있습니다.

Enhancer enhancer = new Enhancer();
         enhancer.setSuperclass(MemberService.class); // 타깃 클래스
         enhancer.setCallback(MethodInterceptor);     // Handler
Object proxy = enhancer.create(); // Proxy 생성

CGLib 은 타깃의 클래스를 상속받아 다음 그림과 같이 프록시를 생성해줍니다.

1. Enhance 가 Target 의 Class 를 상속 받는다.
2. 해당 메소드를 Handler 로 재정의하여 Proxy 를 생성해줍니다.

이런 특성 때문에 Final 메소드 또는 클래스에 대해서 재정의를 할 수 없기 때문에 Proxy 를 생성할 수 없다는 단점이 있지만 GCLib 은 바이트코드를 조작해서 Proxy 를 생성해주기 때문에 JDK Dynamic Proxy 보다 성능이 좋습니다.

예제

public static OrderServiceImpl getOrderServiceProxy(OrderServiceImpl target) {
    Enhancer enhancer = new Enhancer();
    enhancer.setSuperclass(OrderServiceImpl.class); // 타깃 클래스
    enhancer.setCallback(new MethodInterceptor() {
        @Override
        public Object intercept(Object o, Method method, Object[] args, MethodProxy methodProxy) throws Throwable {

            long startTime = System.nanoTime();
            method.invoke(target, args);
            long endTime = System.nanoTime();
            System.out.println((endTime - startTime) + " nanoseconds");

            return null;
        }
    });     // Handler
    Object proxy = enhancer.create(); // Proxy 생성

    return (OrderServiceImpl)proxy;
}

Jdk runtime Proxy 와 CGLib 성능비교

AOP Benchmark

스프링이 CGLib 을 권장하지 않았던 이유는 뭘까?

다음과 같은 3가지 한계가 존재했기 때문입니다.

• net.sf.cglib.proxy.Enhancer 의존성 추가
• default 생성자
• 타깃의 생성자 두 번 호출

CGLib의 개선

• Enhancer 의존성은 Spring 에서 기본적으로 제공하지 않았었는데 Spring Core 패키지에 이를 추가하여 개선했습니다. 더이상 의존성을 별도로 추가하지 않아도 CGlib 을 이용해서 개발할 수 있게 되었습니다.
• CGLib 을 구현하기 위해서는 default 생성자가 필요했던 문제를 Objensis 라이브러리의 도움을 받아 default 생성자 없이도 Proxy 를 생성할 수 있도록 개선했습니다.
• Objensis 라이브러리의 도움을 받아 생성자를 2번 호출하던 문제도 개선했습니다.

⇒ Spring 은 JDK Dynamic Proxy 를 사용해서 인터페이스 방식의 DI 를 지원해주고 인터페이스가 아닌 타입에 대해서 CGlib 으로 Proxy 를 DI 해줍니다.

그러나 상속을 기반으로 하여, 인터페이스가 아닌 타입의 DI가 가능하다는 점, CGlib 이 가지고 있던 한계를 극복했습니다. 그래서 현재 Spring 은 Proxy 를 생성하는 방법으로 CGlib 을 사용합니다. 기본 설정이 CGlib 를 이용한 Proxy 생성입니다.

AOP 구현

스프링이 제공하는 aop 기능을 구현해보고 싶었습니다. AspectJ 가 아닌, 어노테이션을 이용해서 Aspect 코드를 삽입하는 방법으로 AOP 를 구현하려고 합니다.

즉, 스프링 프레임워크의 일부 기능을 구현해보려고 합니다. 이 프레임워크의 이름을 임시로 Look 이라고 부르겠습니다.

코드는 아래 저장소에 있습니다. https://github.com/donghyeon0725/study/tree/master/src/main/java/com/studyall/study/proxy/aop

스토리

아무런 스토리도 없이 구현하면 왜 이런 코드가 나왔는지 이해가 안될 수 있기 때문에 스토리를 추가하려고 합니다. 클라이언트 입장입니다. 현재 클라이언트는 Look 프레임워크를 이용해서 다음과 같은 코드를 작성하고 싶은 상황입니다.

• Service 를 호출하기 전과 후에 profile 을 측정하고 싶다. 이 때 Look 프레임워크가 제공하는 AOP 기능을 이용해서 profile 을 측정하는 코드를 구현하고 싶다.

구현 패키지

client 패키지는 사용자 입장에서 사용자가 작성한 코드를 모아놓은 패키지이고 Look 패키지는 프레임워크가 제공하는 클래스를 모아놓은 패키지입니다.

클라이언트가 알아야할 어노테이션?

클라이언트가 사용하기 어려운 프레임워크는 대체적으로 인기가 없습니다. 제가 만든 프레임워크는 세계정복(?)을 목표로 하고 있기 때문에 쉬워야 합니다. 그렇기 때문에 사용자가 AOP 사용을 위해서 알아야 할 클래스가 적으면 적을 수록 좋습니다.

클라이언트 입장에서 알아야 할 클래스와 어노테이션은 다음과 같습니다.

• @Service
• @Aspect
• AspectI

AOP 의 목적은 코드의 분리입니다.

나(클라이언트)는 코드를 분리해서 로직을 작성할 테니, 이 코드를 프레임워크가 알아서 다른 코드 사이에 끼워 넣어주기를 바래 ~

이점을 고려해서 AOP 코드를 삽입해줄 수 있도록 설계했습니다. 여기서 클라이언트가 위빙 하려는 로직을 Aspect 라고 부릅니다. 마찬가지로 Look 프레임워크도 이를 Aspect 라고 부르겠습니다.

@Aspect 는 Aspect 클래스를 만들기 위해서 사용하는 어노테이션이고, AspectI 는 Aspect 클래스가 따라야할 표준을 정의한 인터페이스입니다.

어노테이션

스프링 프레임워크에서 @Service 와 @Aspect 어노테이션이 붙은 경우 모두 Bean 으로 관리를 하고 있습니다. 마찬가지로 Look을 구현할 때 두 객체 모두 빈으로 관리할 예정입니다.

어플리케이션 구동을 위한 주요 클래스 & 인터페이스

어플리케이션을 구동하기 위해서 Look은 빈 객체를 생성하고 이를 프록시로 만들어줄 것 입니다. 구동 흐름은 다음과 같습니다.

애플리케이션 구동흐름

ApplicationRunner → ApplicationContainer → BeanDefinitionFinder → BeanProcessor → AnnotationHandlerChain → AspectHandler → ProxyCreator

ApplicationRunner.java

public static void main(String[] args) {
    ApplicationContainer applicationContainer = new ApplicationContainer();
    applicationContainer.init(args);

    ApplicationContext context = applicationContainer.getContext();
    MemberService service = context.getBean(MemberServiceImpl.class.getName(), MemberService.class);
    service.createMember("유저1");
}

애플리케이션의 시작점입니다. 마치 SpringBoot 에서 @SpringBootApplication 어노테이션이 붙은 클래스와 유사합니다.

ApplicationContainer 의 init 메소드를 호출함으로서 애플리케이션을 시작합니다. 그리고, 아직은 구현하지 않았지만 applicationContainer 에서 ApplicationContext 를 꺼내어 MemberService 의 createMember 메소드를 호출하는 과정은 나중에 스프링에서 @Autowired 어노테이션을 통해서 빈을 주입받는 DI 로 구현할 예정입니다.

ApplicationContainer.java

public class ApplicationContainer {
    private String path;
    private ApplicationContext context;
    private BeanDefinitionFinder finder;
    private BeanProcessor processor;
    private AnnotationHandlerChain annotationHandlerChain;

    public void init(String[] args) {
        // 필요한 인스턴스 로드 => 구현체 로드
        createInstance();

        // bean processing
        processor.process(finder, context);

                // add annotation handlers
        addAllAnnotationHandler();

        // annotation handling
        annotationHandlerChain.handle(context);
    }

        ...
}

ApplicationContainer 애플리케이션이 구동되기 위해서 필요한 의존성을 정의합니다. 느슨한 결합으로 구현된 클래스들에 구체적인 객체를 주입해줄 수 있도록 의존성을 정의하고 해당 객체를 생성하는 과정을 createInstance 메소드가 담당합니다.

createInstance 메소드 호출이 끝나면 빈을 로드하는 processor 가 동작합니다. 별도의 메소드로 만들어 loadBean 이라는 이름을 붙여주면 더 좋았겠지만, 시간상 그렇게 하지 못했습니다.

addAllAnnotationHandler 에서는 사용자가 커스텀으로 추가한 어노테이션 핸들러와 Look 프레임워크에서 제공하는 어노테이션 핸들러를 annotationHandlerChain 에 추가합니다.

왜 AnnotationHandlerChain 를 만들었나요?

왜 굳이 annotationHandlerChain 를 사용했으냐면 새로운 어노테이션이 추가되었을 때 기존의 코드를 건드리지 않고, 어노테이션 핸들러를 체인에 추가하고 동작시킬 수 있는 구조로 설계하고 싶었습니다.

addAllAnnotationHandler 메소드 코드를 보면 아래와 같습니다.

// 모든 어노테이션 핸들러 추가
private void addAllAnnotationHandler() {
        AnnotationHandler aopHandler = new AspectHandler(new ProxyCreator());
    this.annotationHandlerChain.add(aopHandler);
    this.addAllCustomAnnotationHandler();
}

지금은 new 키워드를 통해서 AspectHandler 객체를 생성했기 때문에, Look 프레임웤이 제공하는 새로운 어노테이션 핸들러를 추가하기 위해서는 이 코드를 수정해야합니다.

하지만, 추후 스프링이 제공하는 @Scan 어노테이션과 유사하게 어노테이션 스캔을 이용해서 핸들러를 추가하는 코드로 변경을 한다면 새로운 핸들러를 추가하더라도 이 메소드를 변경할 일이 없습니다. 즉 변경에는 닫혀 있고 확장에는 열려 있어야 한다는 OCP 원칙 을 지킬 수 있습니다.

이를 염두해두고 Chain 역할을 할 클래스를 만들었습니다.

AspectHandler.java

target 이 되는 빈을 proxy 객체로 만듭니다. 이 후 Aspect 클래스 빈을 찾아서 target 의 proxy 빈에 위빙(사용자 코드를 끼워 넣음)합니다.

현재는 하나의 Aspect 클래스만 지원합니다. 추 후 기회가 되면 여러 Aspect 클래스를 지원할 수 있도록 확장하려고 합니다.

@Override
public void handle(ApplicationContext applicationContext) {

    // aop 빈을 찾아서 service 빈에 넣어주기
    AspectI aspectI = findAspect(applicationContext);

    Object bean = findTargetBean(applicationContext, aspectI);

    Object proxy = proxyCreator.getProxy(bean, aspectI);

    applicationContext.setBean(bean.getClass().getName(), proxy);
}

ProxyCreator.java

public class ProxyCreator {
    public <T> T getProxy(T target, AspectI aspectI) {
        Enhancer enhancer = new Enhancer();
        enhancer.setSuperclass(target.getClass()); // 타깃 클래스
        enhancer.setCallback((MethodInterceptor) (o, method, args, methodProxy) -> {
            aspectI.handle(target, method, args);
            return null;
        });     // Handler
        Object proxy = enhancer.create(); // Proxy 생성

        return (T)proxy;
    }
}

마지막으로 프록시 생성기 클래스입니다.

CGlib 라이브러리를 사용해서 이를 구현 하였는데, JDK Runtime Proxy 대신 이를 사용한 주요 이유는 인터페이스 기반이 아닌 객체를 프록시로 만들 수 있기 때문입니다.

AOP 구현을 위해 Client 가 알아야 할 클래스 or 인터페이스

사용자는 @Aspect 어노테이션을 제외하고 오직 AspectI 인터페이스만 알고 있으면 Aspect 를 만들 수 있습니다.

출처 & 참고

• https://gmoon92.github.io/spring/aop/2019/04/20/jdk-dynamic-proxy-and-cglib.html
• https://bepoz-study-diary.tistory.com/408

Garbage Collector. 즉, 객체를 추적해서 쓸모 없어진 Heap 영역의 객체들을 알아서 제거하는 프로그램이다. 가비지 수집기의 구현체는 다음과 같은 두가지 원칙을 꼭 준수해야한다.

• GC 에 사용되는 알고리즘은 모든 가비지를 수집할 수 있는 알고리즘이어야 한다.
• 살아있는 객체는 절대로 수집해서는 안된다.

위 두가지 원칙을 지키지 않으면 프로그램에 결함이 생긴다. 특히, 살아있는 객체를 수집한다면 더욱 치명적일 수 있다. 프로그램에 신뢰도가 깨지기 때문이다.

GC 가 알고리즘

(GC 는 Garbage Collector 와 Garbage Collection 을 혼용해서 부르는 말이다. 이 탭에서는 Garbage Collection 을 지침하는 단어로 생각해주세요.) JVM 에서 돌아가고 있는 GC 는 Mark And Sweep 이라는 알고리즘을 기반으로 동작합니다.

Mark

GC Root 또는 다른 객체에 의해서 참조되고 있는 객체는 아직 살아있는 객체(live object) 이다. 따라서 이 객체를 GC 해서는 안된다. 이렇게 살아있는 객체를 찾고 표시 (Mark) 해두는 과정이 Mark 단계이다. GC Root 는 다음과 같은 것들이 될 수 있다.

1. 실행중인 스레드
2. 전역 변수
   • 정적 변수
   • 멤버 변수
3. 스택 프레임
   • 로컬 변수
4. JNI 레퍼런스
5. 로드된 클래스의 메타데이터

GC Root 의 참조사슬에 있는 객체는 GC 대상이 아니다. 즉, 실행중인 스레드나 변수, 그리고 JNI 레퍼런스 또는 객체 등등 의해 참조되고 있는 객체는 GC 대상이 아니다. 참조사슬이란 말은 GC Root 에 의해 직접적으로 참조되고 있는 객체 뿐만 아니라, live object 에 의해서 참조되는 객체 또한 포함하기 때문에 "사슬"이라는 말이 붙는다. 그림을 보면 명확하게 이해할 수 있다.

그림을 보면 GC Root 에 의해서 직접적인 참조는 없음에도 불구하고 Mark 된 객체들이 있다(M 으로 표시된 객체).

객체가 생성되고 참조가 일어날 때마다 객체 대한 참조정보가 저장되고 있기 때문에 Mark 알고리즘이 동작할 수 있는 것입니다.

객체를 정점이라고 보고 참조정보를 간선이라고 보면 이를 그래프라는 자료구조로 나타낼 수 있다. 그래프를 탐색하는 방법에는 대표적으로 두가지가 있다.

• 깊이 우선 탐색
• 너비 우선 탐색

Mark 알고리즘에서는 깊이 우선 탐색을 사용하고 있다.

직접 Mark 알고리즘을 구현한다면?

모든 객체의 정보를 Map에 담아두고 탐색을 통해서 발견되는 객체의 정보를 에 표시해둔다. Map 에 다음과 같은 형태도 정보를 저장한다.

Map<Integer, Boolean> mark

heap 의 모든 객체정보를 mark 변수에 담아둔다. 그리고 만약 hashcode 값이 123456 인 객체가 참조사슬에 포함되어 있다면 (살아있다면) true, 아니면 false 로 표시해둘 수 있다.

살아있는 객체 => mark.put(123456, true);
살아있지 않은 객체 => mark.put(123456, false);

그리고 Mark 단계가 끝나면 Map 을 반복하여 mark 여부가 false 인 객체를 메모리에서 해체하는 방법을 사용해서 구현할 수 있다. 실제로 Mark 알고리즘 구현에 유사한 방법을 사용하고 있다고 한다.

Sweep

객체를 순회하면서 Mark 되지 않은 객체를 메모리에서 해제하는 과정이다.

가비지 수집을 이해하기 위해 알아야 할 용어

STW (Stop The World)

GC 사이클이 발생하여 가비지를 수집하는 동안에는 모든 애플리케이션 스레드가 중단되는데 이를 STW 라고 한다.

동시

GC 스레드가 애플리케이션 스레드와 동시에 실행될 수 있는 알고리즘이 있다. 그러나 이는 아주아주 비싸고 어려운 작업이고 100% 동시 실행을 보장하는(STW 가 없는) 알고리즘은 없음. 따라서 애플리케이션과 GC 작업이 병렬적으로 일어난다고 말하는 알고리즘인 CMS (Concurrent Mark and Sweep) 알고리즘도 사실상 ‘준 동시 수집기'라고 해야 맞다. 즉, GC 에서 동시라는 개념은 완벽히 병렬 실행을 보장하는 알고리즘이 아니라는 말이다.

병렬

여러 스레드를 동원해서 가비지 수집을 할 수 있습니다.

스킴

GC 를 할 수 있도록 필요한 정보를 저장하는 공간을 스킴이라고 함. (더 깊은 개념이 있지만 이 정도까지만 알아두는 것이 정신건강에 좋을 것 같다..)

이동

객체의 메모리 주소는 항상 일정한 것이 아니라 때에 따라 달라질 수 있음. 즉, 원래 있던 자리에서 다른 자리로 "이동"이 일어날 수 있음. 이 때 단편화(조각조각 나뉜)된 메모리 사이사이를 채우는 작업이 일어날 수 있는데 이 때문에 메모리 단편화 문제를 해결할 수 있음. "압착"이라는 개념과 달리, GC 이후가 아니라, 프로그램 실행 중간에도 일어날 수 있는 동작

• 메모리 단편화를 막을 수 있음
• 한번 참조된 메모리와 인접한 주변 메모리는 다시 참조될 가능성이 높다는 원칙으로 주변 데이터를 캐싱 하는 것을 참조지역성의 원리라고 하는데 참조지역성의 원리에 따라서 "이동"이라는 작업이 일어나면 데이터가 캐싱될 확률이 높아지고, 성능 향상에 도움이 됨

  압착 (Compaction)

  GC 후에도 살아남은 객체는 메모리의 특정 영역에 나란히 배열된다. 이런 과정을 압착이라고 함.

  방출

  수집 사이클 마지막에, 할당된 영역을 비우고도 살아남은 객체를 다른 메모리 영역으로 이동시키는 것

자바 객체에 대한 이야기는 여기를 참고.

가비지 수집은 언제 발생할까?

가비지 수집을 일으키는 요인은 대표적으로 2가지가 있다.

• 할당률
• 객체 수명

할당률은 일정 기간동안 새로 생성된 객체가 사용한 메모리량이다.(단위는 보통 MB/s, 초당 메가바이트 사용). JVM 이 이 할당률을 직접 기록하지는 않지만 우리는 이 값을 비교적 쉽게 측정할 수 있습니다. 센섬 같은 툴을 사용하면 정확하게 구할 수 있습니다.

반면 객체 수명은 대부분 측정하기가 너무나도 어렵습니다. 수동 메모리 관리 시스템에서 가장 논란이 되었던 것 중 하나가 실제 애플리케이션의 객체 수명을 정확하게 파악하기가 너무 어렵다는 점입니다. 할당률이 어느정도 이상 되었어도 객체 수명이 되지 않았으면 GC 대상이 아닙니다. 따라서 객체의 수명을 정확하게 측정하고 GC할 수 있는 방법이 필요합니다.

약한 세대별 가설

약한 세대별 가설은 소프트웨어 시스템이 런타임 중에 일어나는 동작들을 관찰 하면서 알게된 경험을 바탕으로 만들어졌습니다. 이 경험을 기반으로 JVM 이 어떻게 메모리의 객체를 관리해야할지 이론적인 근간을 만든 것입니다.

JVM 기반의 소프트웨어 시스템에서 객체 수명은 이원적 (bimodel, 낙타 등같은 모양의 그래프) 분포 양상을 보인다. 대부분의 객체가 아주 짧은 시간만 살아 있으나, 일단 살아남은 객체는 기대 수명이 훨씬 길다.

이런 경험을 토대로 생성된지 얼마 안된 객체와 오랫동안 살아남은 객체를 나누어 관리하자는게 약한 세대별 가설의 핵심입니다.

핵심이론

• 방금 생성된 객체는 에덴(Eden, 메모리 영역) 공간에 생성한다. 여기서 살아남은 객체는 다른 곳으로 옮긴다.
• 객체마다 세대 카운트 (객체가 지금까지 GC 에서 살아남은 회수, instanceOop 의 Mark 헤더에 age 비트 필드에 기록됨)를 센다
• 장수했다고 할 정도로 충분히 오래 살아남은 객체는 별도의 메모리 영역 (Old 또는 Tenured[종신, 생명을 마쳤다는 뜻이지만 맥락상 장수를 의미하는 것 같음] 세대)에 보관한다.

• 새로 생성한 대부분의 객체는 Eden 영역에 위치
• Eden 영역이 꽉차면 GC 발생. 이 때 살아남은 객체는 Survivor 영역 중 하나로 이동
• 하나의 Survivor 영역이 가득 차게 되면 그 중에서 살아남은 객체를 다른 Survivor 영역으로 이동한다. 이 때 가득 찬 Survivor 영역은 아무 데이터도 없는 상태
• 다른 Survivor 영역의 GC 과정중에도 살아남은 객체는 Old 영역으로 이동한다.

GC 가 일어날 때 마다 모든 객체로 부터의 참조를 검사해야할까?

GC 를 발생시키기 위해서 GC Root 로 부터의 참조가 있는지 검사합니다. 그리고 이 참조 사슬 내에 객체가 있다면 GC 에서 살아남습니다. 이 말의 의미는 참조 사슬 내에 있는 GC root 가 아닌 객체에 의한 참조가 있는 경우에도 참조 사슬 내에만 있다면 살아남는다는 말입니다.

즉, GC Root 로 부터 직접적인 참조가 없어도 참조 사슬 내에 있는 객체이면 살아남습니다.

• B 객체는 GC Root 로 부터 참조가 없지만 살아남습니다.

따라서 GC 대상인지 확인하기 위해서는 GC Root 가 아닌 객체로 부터의 참조가 있는지도 검사를 해야합니다. 그런데 모든 객체로 부터의 참조를 검사해야할까요? 약한 세대별 가설은 그럴 필요가 없다고 말합니다.

방금 생성된 객체가 장수한 객체를 참조하는 일은 있을 수 있어도 그 반대는 드물다.

즉, 젊은 객체(Young)들이 살아남았는지 확인하기 위해서 장수한 객체(Old)로부터의 참조가 있는지 확인할 필요는 없다는 의미입니다.

더 정확하게 말하면 참조가 거의 없기 때문에 있는 경우만 따로 기록해두면 Old 객체 전체를 검사할 필요는 없다는 말입니다.

이런 기록을 해두기 위해서 핫스팟 JVM은 카드테이블(card table) 라는 자료 구조를 이용합니다. 여기서는 Old 객체가 Young 객체를 참조하는 정보를 기록하는 공간입니다.

Java 8u40 버전부터 사용한 G1 GC 가 사용되고 이는 이전 버전에 대한 내용입니다.

• GC 알고리즘의 종류와 GC 알고리즘이 지속적으로 개선되는 이유를 알고 싶으신 분은 여기 를 참고해주세요.

JVM 의 GC 가 발생하는 원리를 알아보다가, 해시코드가 정확하게 객체의 어떤 부분에 저장되어 있는 값인지 알고 싶어졌다. GC 에는 Mark 이라고 부르는, (쉽게 말해)GC 대상이 아닌 객체를 찾기 위해서 마킹(Marking) 하는 알고리즘 단계가 포함되어 있는데 이 때 참조하는 것이 객체의 메모리 주소 즉, 해시코드이다.

알아보다 보니, 이외에 많은 개념을 알게 되었고 Java 의 Lock 이라는 개념과 다형성이 어떻게 구현되고 있고 이루어져 있는지 조금 더 깊게 이해할 수 있게 된 것 같다.

Mark-And-Sweep

가비지 수집을 구현하기 위해서 사용하는 알고리즘이다. Mark 단계는 객체가 살아 있는지 검사하고 마킹(Marking) 라는 단계이고, Sweep 단계는 마킹한 객체를 메모리에 해제하는 단계이다.

자바의 객체는 어떻게 이루어져 있을까?

자바의 모든 객체는 OOP (Ordinary Object Pointer, 일반 객체 포인터) 라고 불리는 객체로 표현합니다. 쉽게 말하면 객체의 위치 정보나 메타정보를 담고 있는 단위 입니다. OOP 는 C 에서 불리는 포인터와 유사합니다. (코드는 열어보니 C++ 로 작성되어 있었습니다)

class oopDesc {
  friend class VMStructs;
  friend class JVMCIVMStructs;
 private:
  volatile markWord _mark;
  union _metadata {
    Klass*      _klass;
    narrowKlass _compressed_klass;
  } _metadata;

 public:
  inline markWord  mark()          const;
  inline markWord  mark_raw()      const;
  inline markWord* mark_addr_raw() const;

  inline void set_mark(markWord m);
  inline void set_mark_raw(markWord m);
  static inline void set_mark_raw(HeapWord* mem, markWord m);
  ...
}

인스턴스가 생성될 때 마다 인스턴스에 대한 정보를 담은 OOP 또한 같이 생성되어 메모리에 저장됩니다.

OOP를 사용하여 Java의 객체를 구현했을 때 성능상에 문제는 없을까?

C 를 공부한 사람은 malloc 이라는 메서드를 아시는 분이 계실 것 같습니다. 이는 메모리 할당을 할 때 공간을 확보하기 위해서 사용하는 메서드입니다. 이 함수를 호출하면 최종적으로 시스템콜이 호출되어 메모리가 프로세스에 할당됩니다.

그러나 Oop를 생성할 때는 JVM 이 확보한 메모리 영역 안에서 생성하기 때문에 새로운 메모리 할당을 위한 시스템 콜을 호출할 필요가 없습니다. 즉, 메모리 할당을 위한 "시스템콜"을 부르지 않기 때문에 Oop 라는 것을 이용하는게 성능상 문제가 되는 부분이 없다. (= 시스템콜 사용으로 인한 오버헤드는 없다.)

시스템콜을 호출하면 프로세스를 실행 중이던 CPU에 interrupt가 발생하게 되고, 이 후"사용자 모드"에서 "커널 모드"로 변경된다. 이 때 컨텍스트 스위칭이 일어나서 오버헤드가 발생하게 된다.

조금 더 깊게 파보자면 JVM 이 OOP 를 생성하는데 있어서, 메모리 주소에 직접 접근하지 않고 메모리 주소의 이정표 역할을 하는 "페이지 테이블"이라는 것을 보고 해당 위치에 OOP 를 생성하기 때문에 이미 시스템이 할당 받은 메모리 내에만 OOP 를 올리게 된다.

OOP 는 어떻게 이루어져 있을까?

OOP 에는 instanceOOP 와 Klass OOP 가 있습니다. 이름에서 알 수 있듯 instanceOOP 는 인스턴스와 관련이 있는 OOP 이고 Klass OOP 는 클래스 메타 정보와 관련이 있는 OOP 입니다.

instanceOOP 는 Mark Word 와 Klass Word 라고 부르는 두가지 헤더 + 실제 데이터로 구성됩니다. (물리적인 단위가 아니라 논리적인 단위로 생각됩니다)

instanceOOP

Mark Word

인스턴스의 메타데이터를 가리키는 포인터 입니다. 해시코드를 포함하고 있습니다. 32 비트 JVM 에서 다음과 같은 정보로 이루어져 있습니다.

• 25 비트 : 해시코드
• 4 비트 : age (GC 에서 몇번 살아 남았는지에 대한 정보)
• 1 비트 : biased_lock
• 2 비트 : lock

JDK 8 버전 Mark 의 소스를 보고 싶다면 여기 JDK 15 버전 Mark 의 소스를 보고 싶다면 여기

Klass Word

클래스의 메타 데이터를 가리키는 포인터. 즉, 클래스의 메타 정보에 대한 참조를 저장해둔 데이터 단위이고 C++ (기계어)로 작성된 포인터입니다.

instance oop 의 Mark Word 와 Klass Word 두 헤더 다음에 실제 데이터가 위치합니다. 이 데이터는 primitive 타입, reference 타입으로 참조할 수 있는 실제 데이터를 의미합니다.

예제

예를 들어서 Entry 인스턴스를 생성한다고 가정하고 위 두가지 헤더를 고려해서 OOP 의 크기를 계산해볼 예정입니다. 이 인스턴스가 총 사용하는 메모리 크기를 계산할 것입니다. 이 때 기준이 되는 것은 32-bit JVM 입니다.

static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;
    final int hash;

// methods...

}

Mark word 와 Klass word 는 각각 4바이트 짜리 기계어 입니다. (64-bit JVM 에서는 8바이트) 따라서 헤더의 크기는 8 바이트입니다. 전체 크기는 다음과 같습니다.

2개의 기계어 + 모든 인스턴스 필드의 크기

즉, 크기를 계산하면

2 개의 header word (8바이트) + 1 개의 int word (hash 필드 4바이트) + 3 개의 pointer word (나머지 필드 12바이트)

24 바이트가 됩니다.

Klass OOP

모든 Java 인스턴스가 메소드의 세부사항을 저장하고 있는 것은 매우 비효율 적입니다. 메서드는 정적인 자원, 즉 해당 코드가 변한다거나 하지 않기 때문에 모든 인스턴스의 메서드는 동일합니다. 즉, 인스턴스가 호출할 수 있는 메서드는 모두 동일하게 동작하기 때문에 공통된 장소에 메소드를 올려두고(공유) 이를 참조하는 것이 좋은 방법입니다.

klass word 는 Virtual Method Table (일명 vtable, 메서드에 대한 참조 값을 저장해둔 배열) 이라고 불리는 자료를 내부적으로 가지고 있습니다. vtable 은 메서드에 대한 참조정보를 가지고 있는 자료구조입니다. 이를 통해서 메서드를 호출할 수 있게 됩니다.

Klass OOP 와 Class 객체와 다르다는 것을 주의!

• Class 객체 : 예를 들어 getClass()로 얻을 수 있는 인스턴스가 있다. 이는 자바의 객체이다. 다른 Java 인스턴스와 동일하게 instanceOops 로 취급되고 동일한 동작을 가지며 Java 변수로 참조할 수도 있습니다.
• KlassOOP 는 JVM이 클래스 메타데이터를 표현(저장)하기 위해서 사용하는 개념. vtable 이라는 구조를 이용해서 클래스의 메소드 정보를 참조합니다.

가상디스패치

디스패치란 런타임 중에 호출될 메서드를 결정하는 과정이다. 이는 다형성과 관련이 깊은 개념이다.

다형성

다형성은 쉽게 말하면 여러 타입의 인스턴스를 하나의 요소(여기서는 변수)에 집어 넣을 수 있는 성질 변수가 여러 타입의 인스턴스를 참조할 수 있기 때문에 변수의 타입만 보고는 해당 인스턴스가 실제로 가진 메서드가 어떤 것인지 정확하게 할 수 없다. 특히 부모 클래스의 메서드를 오버라이드 한 경우 그렇다. 따라서 실제 어떤 메서드를 호출할 것인지 결정하는 디스패치라는 개념이 필요하다.

Java 메서드를 호출할 때 점연산자 (offset 연산자)를 사용합니다.

public static void main(String[] args) {
    TestClass testClass = new TestClass();
    testClass.run(); // offset 연산자를 통해 run 이라는 메서드 호출
}

offset 연산자 (점연산자, .)를 이용해 메서드를 호출하면 변수와 관계 없이 실제 인스턴스가 가진 메서드가 호출이 되는 방식으로 동작하는데 이는 메서드 이게 디스패치가 일어나는 방식이다.

vtable

KlassOop 에는 vtable 이라는 배열 공간을 가지고 있다. 여기에는 해당 객체가 실제로 바라보는 메서드에 대한 참조 정보가 들어있습니다. vtable 구조는 Java 의 메소드 디스패치 및 단일 상속과 직접적인 관련이 있는데 이에 대해서 설명해보려고 합니다.

JVM 은 메모리에 올라간 메서드에 대한 참조정보를 vtable 의 특정 offset (=인덱스) 에 저장합니다. 예를 들어서 4번 offset (배열의 인덱스)에 toString() 이라는 메서드에 대한 참조정보를 저장할 수 있습니다.

한편, 메서드는 오버라이드 될 수 있습니다. 앞서 언급한 toString() 메서드로 예시를 들어보겠습니다. 모든 클래스는 Object 를 상속 받습니다. 부모 클래스의 toString() 메서드를 A 참조라고 부르고 자식 클래스의 toString() 메서드를 B 참조라고 부르겠습니다.

Object의 인스턴스가 4번 인덱스에 A 참조를 저장해두었다고 가정하면 부모 클래스의 인스턴스와, 자식 클래스의 인스턴스 모두 4번 인덱스에 참조(A,B)를 저장합니다. 이렇게 같은 인덱스에 오버라이드 된 메서드 정보를 저장하기 때문에 자바의 "상속" 계층 구조를 쉽게 구현할 수 있는 것입니다. 즉, 인스턴스가 바라볼 하나의 정보만 저장하기 때문에 자식 클래스의 인스턴스 입장에서 A 참조와 B 참조 중 어떤 것을 실제로 호출할지 고민할 필요가 없어집니다.

한편, 오버라이드 된 메서드는 이렇게 하나의 배열공간에 같은 offset 에 저장되기 때문에 단일 상속밖에 지원할 수가 없습니다. 참조인 인덱스를 vtable에 덮어쓰기 하는 방법으로 상속을 구현했기 때문입니다.

그리고 이 구조는 JIT 컴파일이 동작할 때 매우 강력한 최적화가 가능하게 합니다. (위 그림에서 Object 의 toString 메서드와 Child 의 toString 메서드 중 어떤 것을 호출하는지 알기 때문에 정확하게 counting 할 수 있고, 이런 counting 정보는 성능최적화의 일종인 JIT 컴파일을 하기 위한 참고 자료로 사용되는데 counting 정보가 정확할수록 성능최적화에 유리할 것이기 때문으로 추측)

• 참고 1

문제는 링크를 참고하세요.

소스

소스는 깃허브에 올려두었습니다.

풀이

문제의 핵심은 participant 배열에는 존재하고 completion 배열에는 존재하지 않는 한명의 이름을 찾아내는 것

쉽게 생각할 수 있는 풀이 방법은 participant 배열에 들어있는 사람의 이름을 반복하면서 completion 에 있는 사람 이름이 존재하는지 검사하는 방법입니다.

문제점 - 검사방법

participant 배열을 반복하면서 지금 찾아야 되는 대상의 이름이 A 라고 가정하겠습니다. completion 배열을 반복하면서 A 라는 이름이 나오면 존재하는 것으로 생각할 수 있지만 그렇지 않습니다. 만약 A 라는 이름을 가진 사람이 2명이고 이 사람 중 한명이 마라톤을 완주하지 못했다고 가정하면 이 방법으로는 문제를 풀 수 없습니다. 왜냐면 처음 A를 검사 한 후에도 completion 배열에 A라는 이름을 포함하고 있기 때문입니다.

▶️ 위에서 A를 이미 한번 찾았지만 이후 A 를 또 찾은 것으로 판단

이런 단점을 보완하기 위해서 한명을 찾을 때 마다 하나씩 지워가는 방법(null 처리하는 방법)을 사용할 수 있습니다.

문제점 - 시간복잡도

다만, 이 방법에도 단점이 있습니다. 바로 시간복잡도인데요. participant 의 크키가 n 이라고 가정하면 completion 는 n - 1 이 됩니다. 따라서 시간복잡도를 계산하면

O (n * (n - 1)) = O (n^2)

제곱 단위의 시간복잡도는 보통 좋지 않은 알고리즘으로 분류되기 때문에 다른 방법을 고민했습니다. 만약 completion 배열을 검사하는데에 시간복잡도가 O(1) 이 된다면 이 알고리즘은 다음과 같은 시간복잡도를 가질 수 있습니다.

O (n * 1) = O (n)

개선하기 - 적절한 자료구조 선택

조회에 시간복잡도 O (1) 을 가지는 자료형은 몇가지가 있습니다. 예를 들어서 ArrayList 를 조회할 때 시간복잡도가 O (1) 이고, HashMap 또한 조회 할 때 시간복잡도가 O (1) 입니다. 이 때 사람이름으로 조회할 때 시간복잡도가 O (1) 이어야 한다는 점에 주의해야 합니다. ArrayList 같은 경우 value 로 값을 찾을 때는 모든 배열을 하나하나 찾아봐야 하기 때문에 배열의 크기가 n 이라고 가정하면 O(n) 의 시간복잡도를 가집니다. 따라서, HashMap 을 사용하기로 했습니다.

participant 를 반복하면서 map 에 다음과 같은 형태로 값을 넣습니다.

이름 : 참가자수 (count)

즉, A 라는 사람이 마라톤 참여자 명단에 있다면 A 가 총 몇명 참가했는지 기록해두는 것이죠. 그리고 completion 를 반복하면서 해당 이름의 count 수를 하나씩 뺍니다. 이렇게 하면 최종적으로 count 가 1인 사람 1명이 마라톤을 완주하지 못한 사람이겠죠.

코드

public String solution(String[] participant, String[] completion) {
    // map 에서 사용할 수 있는 공간을 넘기려는 경우 크기 확장이 일어나는데, 이 때 연산의 비용이 크므로 초기 공간을 설정해주는 것이 좋다
    // 로드팩터가 1이 아니기 때문에 1번 정도는 공간 확장이 일어날 수 있지만, 뭐 1번 정도야..
    Map<String, Integer> map = new HashMap(participant.length);

    // 참가자 count
    for (String p : participant) {
        map.put(p, map.getOrDefault(p, Integer.valueOf(0)) + 1);
    }

    // 완주자 체크
    for (String c : completion) {
        map.put(c, map.get(c) - 1);
    }

    // count 가 1인 사람이 완주하지 못한 사람
    Integer one = 1;
    for (Map.Entry<String, Integer> entry : map.entrySet()) {
        if (one.equals(entry.getValue())) {
            return entry.getKey();
        }
    }
    return null;
}