Jins' Dev Inside

분산처리 환경을 구축하는 데 있어서 로드밸런서의 역할은 핵심적이다.

클라우드 환경에서 분산처리를 위한 아키텍처를 설계한다면, AWS 의 Load Balancer 를 이용해볼 수 있다.

Amazon Web Service 가 Provisioning 하는 Load Balancer 는 ELB(Elastic Load Banacing) 서비스라 하며, 기본적으로 Logging, Cloud Watch 를 통한 지표, 장애 복구, Health Check 와 같은 기능들을 제공한다.

ELB 서비스의 종류로는 2019년 8월 기준으로 3가지 종류가 있다.

 (1) Classic Load Balancer

가장 기본적인 형태이자 초기에 프로비저닝되던 서비스로, 포스팅 등에 나오는 설명에 단순히 ELB 라고 나와있으면 Classic Load Balancer 를 말하는 경우가 많다.

L4 계층부터 L7 계층 까지 포괄적인 로드밸런싱이 가능하며, 따라서 TCP, SSL, HTTP, HTTPS 등 다양한 형태의 프로토콜을 수용할 수 있고 Sticky Session 등의 기능도 제공해준다.

특징적으로 Classic Load Balancer 는 Health Check 를 할 때, HTTP 의 경우 /index.html 경로를 참조한다.

즉, 웹서버 인스턴스의 경로에 /index.html 가 포함되어있지 않다면(404) Health Check 를 실패한다는 뜻이다...

따라서 이럴 때에는 Health Check 를 위한 프로토콜만 TCP 로 바꾸고 포트만 80 으로 체크하게 하는 방법이 있다.

중요한 특징으로... CLB 는 로드밸런서가 url 하나를 가질 수 있다. 즉, CLB 로 매핑되어있는 인스턴스들은 무조건 하나의 URL 을 통해 접근하게 된다.

 (2) Application Load Balancer

Classic Load Balancer 이후 출시된 서비스로 HTTP 및 HTTPS 트래픽 로드밸런싱에 최적화되어있다.

L7 계층에서 작동하며 Micro Service Architecture 와 같은 Modern 환경을 겨냥한 많은 강점들이 있는데, WebSocket 이나 HTTP/1.1 이상의 프로토콜에 대한 지원, 향상된 라우팅 정책과 사용자의 인증 까지도 지원을 해준다.

웹서비스를 목적으로 한다면 기존 Classic Load Balancer 가 갖고 있던 장점 이상의 강점들을 많이 포함하고 있다.

단 L7 계층에서 작동하기 때문에 TCP 등에 대한 밸런싱은 지원되지 않는다.

직접 사용해서 구축 할때에 Classic Load Balancer 에 비해 좀 더 구축이 편하고 웹서버 밸런싱에 있어서는 확실히 다양한 옵션이 있다. Health Check 경로 또한 지정할 수 있으며, 기본이 / 로 정해져있다.

CLB와 다르게 ALB 는 host-based Routing 과 path-based Routing 을 지원한다. Content Based Routing 이라고도 하며 ALB 에 연결된 인스턴스들은 여러개의 URL 과 path 를 가질 수 있다.

 (3) Network Load Balancer

Load Balancer 중 성능적으로 최적의 로드밸런싱을 지원한다. TCP, UDP 등의 서버를 구축할 때 해당 프로토콜 들에 대해 굉장히 낮은 지연 시간으로 최적의 성능을 보여준다고 한다. 

사용해본적이 없는데... 사용해본다면 좀 더 포스팅 내용을 보강해야겠다.

로드밸런서에 EIP 를 직접 붙일 수는 없고, 필요하다면 DNS 의 도메인 네임 대신 CNAME 을 사용하거나 Route53 서비스와 같이 사용해야 한다. 그 이유는... ELB 역시 서버이기 때문에, 부하 상황에서 오동작의 위험이 있고 그에 따라 자체적으로 Scale In - Scale Out 을 수행하기 때문이다. (즉, IP 를 지정할 서버가 한대가 아니게 될 수 있다.)

또한, ELB 는 Multi-AZ 환경에서 "내부적으로는" 각 Availability Zone 별로 구성된다. 이 때 트래픽의 분배는 AZ 당 ELB 사정에 맞게 분배되므로... Multi AZ 환경에서는 각 Availability Zone 별 인스턴스의 숫자를 동일하게 맞춰주는 것이 좋다. (동일하게 맞추지 않으면 특정 Zone 의 인스턴스들에 트래픽이 몰릴 수 있다.)

로드밸런서를 통해 Cloud 환경에서 아키텍처를 설계할 때에는 Private Subnet 들에 EC2 인스턴스들을 배치해둔 상태에서, ELB로 트래픽을 연결할 수 있도록 인스턴스들을 연결시켜주고, Public 영역에 위치시켜 놓는 식으로 구성을 한다.

혹은, ELB 자체는 VPC 내부에 형성시켜 두고, ELB로 들어온 트래픽을 Private Subnet 으로 전개시켜주며, 인터넷에 연결을 위한 Public NAT 를 두고 출력을 해당 NAT 를 거치게 하는 방식도 있다.

다음은 AWS 공식 홈페이지의 Well architectured 를 위한 5가지 성질을 정의한 내용이다.

https://aws.amazon.com/ko/architecture/well-architected/

1. 운영 우수성(Operational Excellence)

비즈니스 가치를 제공하고 시스템을 실행 및 모니터링하는 데 중점을 둔다.

변경관리 및 자동화, 이벤트 응답, 일상적인 운영의 성공적인 관리 와 같은 항목들이 고려되어야 한다.

Operational Excellence 를 위한 다음과 같은 원칙들이 있다.

 - Perform operations as code : Cloud 환경에서도 일반 어플리케이션 코드를 만들 때처럼 작업의 프로시저와 이벤트에 대한 동작을 구현해야 한다. 휴먼 에러를 배제하고 이벤트 중심으로 구동되게끔 설계해야 한다.

 - Annotate documentation : 매빌드 이후에 Document 를 만들도록 자동화시키는 것이 중요하다. Cloud 환경에서는 documentation 을 자동화시킬 수 있다.

 - Make frequent, small, reversible changes : Component 들의 주기적 업데이트를 가능하게 하고, 실패 시 Rollback 이 가능해야 한다.

 - Refine operations procedures frequently : 주기적으로 프로세스를 향상시킬 방법을 고안해야 한다.

 - Anticipate failure : 프로세스가 실패로 이어질 상황을 시뮬레이션 해보는 것이 필요하다.

 - Learn from all operational failures : Operation failure 에 대해 정리하고 학습해야 한다.

* Operational Excellence 를 위해 AWS Config 를 통해 테스트를 준비하고, Amazon CloudWatch 를 통해 모니터링하며, Amazon ES(Elastic Search Service) 를 통해 로그를 분석하는 것이 좋다.

2. 보안(Security)

정보 및 시스템을 보호하는 중점가치이다.

데이터 기밀성 및 무결성, 권한 관리를 통한 사용자 작업 식별 및 관리, 시스템 보호와 보안 이벤트 제어와 같은 항목들이 고려되어야 한다.

Security 요소를 위해 다음과 같은 원칙들이 있다.

 - Implement a strong identity foundation : 최소 권한의 원칙과 의무에 대한 권한을 AWS Resources단위로 부여한다.

 - Enable traceability : 모든 동작은 모니터링과 알람이 가능하게끔 해야한다. 로그 시스템을 통합시켜놓음으로써 자동화가 가능하다.

 - Apply security at all layers : 모든 계층에 보안 요소를 포함시킨다. (edge network, VPC, subnet, Load Balancer, instances, OS, application)

 - Automate security best practices : Security mechanism 을 자동화시킨다. 버전관리를 하듯 템플릿을 관리한다.

 - Protect data in transit and at rest : 데이터에 대해서도 Encryption, Tokenization, Access control 등을 적용한다.

 - Prepare for security events : 갑작스런 보안 사고에 대비해 simulation 해보고, 탐지 속도, 탐지력, 복원력 을 측정해보는 것이 좋다.

* Security 를 위해 IAM, CloudTrail(API Call 추적), Amazon VPC, Amazon CloudFront(CDN 데이터의 보안), 데이터 보안을 위한 RDS, S3, AWS KMS(Key management system), CloudFormation / CloudWatch(시뮬레이션 및 모니터링) 등을 이용하는 것이 좋다.

3. 안정성(Reliability)

비즈니스 및 고객 요구를 충족시키기 위해 장애를 예방하고 신속하게 복구할 수 있는 능력에 중점을 둔다.

기본요소, 복구계획 및 변경 처리와 같은 항목들이 고려되어야 한다.

Reliability 를 위해 고려해야할 원칙들은 다음과 같다.

 - Test recovery procedures : System fail 및 fail 에 대한 recovery 상황을 테스팅하고 전략을 수립할 수 있기 때문에, 시나리오에 알맞게 recover 동작을 테스트해보는 것이 필요하다.

 - Automatically recover from failure : Key Performance Indicator(KPI) 를 모니터링함으로써 이상상태에 대한 Threshold 값을 세팅할 수 있고 복구를 자동화할 수 있다.

 - Scale horizontally to increase aggregate system availability : Horizontal scaling 은 Single Failure 가 전체 시스템에 영향이 미치지않게끔 구성할 수 있게 한다. 구조를 수평적으로 작게 나누고 합치는 형태의 구조를 사용한다.

 - Stop guessing capacity : 온프레미스 환경의 흔한 오류 원인은 Resource 포화상태이다. 클라우드 환경에서는 Load 를 모니터링하고 System utilization 을 통해 Provisioning 을 자동화할 수 있다. (Under/Over provisioning 의 방지)

 - Manage change in automation : 인프라 구성의 변화는 자동화되어야 한다.

* 사용가능한 AWS 서비스들로 AWS IAM, AWS CloudTrail, AWS Config, AWS CloudFormation, AWS KMS 등의 서비스가 있다.

4. 성능 효율성(Performance Efficiency)

IT 및 컴퓨팅 리소스를 효율적으로 사용하는데 중점을 둔다.

요구사항에 적합한 리소스 유형 및 크기, 성능 모니터링 정보를 바탕으로 한 효율성 유지와 같은 항목들이 고려되어야 한다.

Performance Efficiency 를 위해 고려해야할 원칙들은 다음과 같다.

 - Democratize advanced technologies : 새로운 기술이 있을 때, 클라우드 환경에서는 쉽게 적용시킬 수 있다.

 - Go global in minutes : Multiple Region 에 몇번의 클릭만으로 배포가 가능하다. 이는 고객 입장에서도 적은 비용으로 만족감을 느낄 수 있는 서비스의 특성이 된다.

 - Use serverless architecture : 클라우드의 서버리스 아키텍쳐는 서버를 직접 구동하고 운용할 필요성을 크게 줄여준다. 

 - Experiment more often : 가상의 자동화된 환경에서 테스트는 좀 더 빠르게 이루어질 수 있다.

 - Mechanical sympathy : 기술적 접근 방법을 고려한다.

* Performance Efficiency 를 위해, Auto Scaling, Amazon EBS, Amazon RDS, Amazon Route53, ElastiCache, CloudFront 와 같은 서비스들이 활용될 수 있다.

5. 비용 최적화(Cost Optimization)

불필요한 비용의 발생을 방지하고 지출 내용을 파악하여 가장 적합한 수의 적절한 리소스 사용에 초점을 둔다.

지출분석을 통해 초과비용 없이 비즈니스 요구사항을 만족시키는 조정 항목들이 고려되어야 한다.

Cost Optimization 을 위해 다음 원칙들이 고려되어야 한다.

 - Adopt a consumption model : 필요한 만큼의 컴퓨팅 리소스에 대해서만 비용이 지출되어야 하고 비즈니스 요구에 따라 사용량이 조절되어야 한다. (예측해서 많이 잡거나 해서는 안된다.)

 - Measure overall efficiency : 비즈니스의 전체 workload 와 output 을 측정해야 한다.

 - Stop spending money on data center operations : 인프라 관리비용 자체에 돈을 더 쓰면 안된다.

 - Analyze and attribute expenditure : Cloud 환경에서는 시스템의 사용량을 조회하고 비용을 산정하기 쉽다. ROI 를 측정하고 Resource 를 최적화하자.

 - Use managed services to reduce cost of ownership : Cloud 환경을 이용하면 email 을 보낸다던지하는 운영의 비용이 감축된다.

* AWS Cost Explorer 를 사용해서 비용 산정량을 확인할 수 있다. AWS Budget 은 사용량에 따라 향후 사용량을 예측할 수 있게 지원한다.

또한 Resource 를 Amazon Aurora 와 같은 것을 사용하면 라이센스 비용을 절감할 수 있고, Auto Scaling 은 스케일링의 효율성을 증가시켜준다.

처음 클라우드 기반 아키텍처를 설계할 때 상당히 도움이 되었었던 내용들이다.

클라우드 기반 아키텍처 설계를 담당하게 되었다면 꼭 알아두고 복습하자.

프로그램 언어를 해석하고 실행시키는 대표적인 방법으로 Compile 과 Interpret 방식이 있다.

Compile 작업은 Compiler 에 의해 실행되고, Interpret 작업은 Interpreter 에 의해 실행되는데, 두 컨셉이 명확하게 다르기 때문에 

많은 프로그래밍 언어들은 둘 중 한가지 방식을 통해 언어를 실행하도록 설계된다. (Java 와 같이 두가지를 모두 채용하는 경우도 있다!)

그렇기 때문에 Compiler 와 Interpreter 를 이해하는 것은 어떤 언어를 배우던지간에 해당 언어의 구동원리를 배울 수 있는 중요한 선행학습이라할 수 있겠다.


컴파일 (Compile)

프로그래밍 언어를 Runtime 이전에 기계어로 해석하는 작업 방식이다.
이때 원래의 소스를 원시 코드, 바뀐 코드를 목적 코드(Object Code) 라 한다.

런타임 이전에 Assembly 언어로 변환하기 때문에 구동 시간이 오래걸리지만, 구동된 이후는 하나의 패키지로 매우 빠르게 작동하게 된다.
구동시에 코드와 함께 시스템으로부터 메모리를 할당받으며 할당받은 메모리를 사용하게 된다.

런타임 이전에 이미 해석을 마치고 대게 컴파일 결과물이 바로 기계어로 전환되기 때문에 OS 및 빌드 환경에 종속적이다.
그러므로 OS 환경에 맞게 호환되는 라이브러리와 빌드환경을 구분해서 구축해줘야 한다.

Compile 언어의 대표격으로 C / C++ 와 같은 언어들을 들 수 있으며, Java 역시 Byte Code 로 바꾸기 위한 과정에서 컴파일을 수행한다.


인터프릿 (Interpret)

런타임 이전에 기계어로 프로그래밍 언어를 변환하는 컴파일 방식과 다르게, 런타임 이후에 Row 단위로 해석(Interpret) 하며 프로그램을 구동시키는 방식이다.

프로그래밍 언어를 기계어로 바로 바꾸지않고 중간 단계를 거친 뒤, 런타임에 즉시 해석하기 때문에 바로 컴팩트한 패키지 형태로 Binary 파일을 뽑아낼 수 있는 Compile 방식에 비해 낮은 퍼포먼스를 보이게 된다.

런타임에 직접 코드를 구동시키는 특징이 있기 때문에 실제 실행시간은 느리며, 대신 런타임에 실시간 Debugging 및 코드 수정이 가능하다.

또한 메모리를 별도로 할당받아 수행되지 않으며, 필요할 때 할당하여 사용한다. 이와 관련되어 코드의 흐름 자체도 실제 필요할 때, 실제 수행되어야하는 시점에 수행되기 때문에 덕타이핑(Duck Typing) 이 가능한 측면이 있으나, 반대로 정적 분석이 되지않는 Trade off 를 갖고 있다.

대표적인 Interpreter 언어로는 Javascript 와 같은 스크립팅 언어들이 있다. 하지만, 스크립트 언어 뿐 아니라 컴파일 이후의 동작에서 Interpret 을 수행하는 언어들도 많이 존재한다.

많은 프로그래밍 언어들의 인터프리터는 해석을 위한 Virtual Machine 을 두고, Machine 위에서 Interpret 을 수행하게 되는데, 이 때 해석의 기반이 되는 머신들이 OS 환경들을 지원해줌으로써, 해당 방식으로 인터프리터는 OS 및 플랫폼 에 종속되지않는 프로그램 구동이 가능하게 된다.
(이런 특징을 지닌 Interpreter 는 Java 의 JVM 과 Python 의 Analyzer 가 있겠다.)


컴파일러와 인터프리터의 차이는 잘 이해하고 언어와 환경을 파악하는데 활용하는 것이 중요하다.

HTTP 와 HTTPS 의 차이점에 대해 면접 볼 때 질문 받은 적이 있었다.
당시 많이 긴장하고 해당 면접에 대해 Deep 한 질문들이 나오던 와중에 받은 질문이어서 보안을 위한 HTTP 라는 정도로 얼버무린 기억이 있는데,
만약 다음에 질문받게되면 깔끔하고 완벽하게 답변할 수 있도록 정리해보았다.


HTTP 란 일반적으로 웹 서버 통신을 위한 프로토콜이다.
HTTPS 란 정확히 어떤 것일까?
간략하게 정리하자면, HTTPS 란 "암호화된 통신을 제공하는 HTTP" 를 일컫는다.

HTTP 를 이용해 클라이언트와 서버가 통신을 할때, 암호화 통신을 위한 키를 설정하고 통신을 하게 된다.

이 때 사용되는 암호화 방식은 공개키 암호화방식을 사용하며, 데이터를 암호화하는데 2개의 키를, 복호화하는데 한개의 키를 사용한다.

HTTP 프로토콜을 사용하면 공격자가 패킷을 가로챌 경우, 평문이기 때문에 해당 데이터를 갈취하고, 변조해서 공격이 가능하다. (Man in the middle)
이에 반해 HTTPS 프로토콜을 사용하면, 패킷이 중간에 탈취되더라도 공격자가 메시지를 알아내고 암호화까지 하여 변조하는데, 일반적으로 천문학적인 시간을 소모하게 된다.

이처럼 암호화된 통신을 함으로써 안전한 구조를 가져갈 수 있지만, 공개키 암호화와 복호화 과정은 많은 비용을 수반한다.
따라서 HTTPS 통신은 HTTP 에 비해 느릴 수밖에 없으며, 보통 선택적으로 사용하게 된다.

예를들어 금융정보 및 기밀 또는 민감한 개인정보들의 경우에는 HTTPS 로, 그와 상관없는 UI 처리 및 일반 컨텐츠 관련 정보는 HTTP 로 처리하는게 정석적이다.

OLTP 와 OLAP 는 개발자로서 생각보다 친숙한 개념임에도 불구하고 실제로 많이 사용되는 단어가 아니다보니 생소한 경우가 많다.

* OLTP (Online Transaction Processing)

 OLTP 란 온라인 트랜잭션 처리를 말하며, 네트워크 상의 온라인 사용자들의 Database 에 대한 일괄 트랜잭션 처리를 의미한다. 

흔히 말하는 "트랜잭션(Transaction) 처리" 를 OLTP 라 부른다. 트랜잭션이라 부르는 용어의 의미 자체가 OLTP 의 의미를 포함하고 있다고 할 수 있겠다. 

Transaction 에 대한 보다 자세한 설명은 다음 포스팅을 참조해보자.

https://jins-dev.tistory.com/entry/Database-%ED%8A%B8%EB%9E%9C%EC%9E%AD%EC%85%98%EC%9D%84-%EC%9C%84%ED%95%9C-ACID-%EC%9D%98-%EA%B0%9C%EB%85%90

트랜잭션의 주 특징은 그루핑된 연산의 실패시, Rollback 이 지원된다는 점이다.

주로 기술적 특성상, 대규모의 처리보다는 소규모의 정교한 데이터 구성이 필요한 데이터의 처리가 중점이 된다.

* OLAP (Online Analytical Processing)

 OLAP 란 Database 자체적으로 운용되는 시스템이라기 보다는 데이터 웨어하우스 등의 시스템과 연관되어 Data 를 분석하고 의미있는 정보로 치환하거나, 복잡한 모델링을 가능하게끔 하는 분석 방법을 말한다.

기능 자체에 중심을 두는 OLTP 와는 다르게 사용하는 목적과 주제에 보다 중점을 둔다.

그렇기 때문에 주로 대용량의 데이터에 대해 처리하고 보다 복잡한 Data processing 으로 의미를 추출하는데 중점을 둔다.

대부분의 경우 OLAP 연산을 수행한다 라고 하면 적재된 데이터에 대한 분석 또는 SELECT Query 를 통한 데이터 스캔 Operation 이 주가 된다. 이는 OLTP 가 Transaction 의 과정에서 INSERT/UPDATE 를 중점적으로 수행하는 것과 대조되게 된다.

(하지만 언급했듯이, 쿼리의 읽기냐 쓰기냐 에 따라 구분되는 개념이라고 보기는 애매하다!)

면접에서 물어보면 트랜잭션은 알아도 OLTP 는 모르는 경우가 많다..

용어 자체가 중요하다고 보지는 않지만 알아둘 필요가 있겠다.

CIDR(사이더) 기법이란, 기존의 IP 주소 할당방식인 Network Class 방식을 대체하기 위해 개발된 도메인간 라우팅 기법으로 최신 IP 할당 방법이다.

CIDR 기법은 사이더 블록이라 불리는 그룹으로 IP 주소들을 그루핑하고 그룹들을 계층적으로 관리함으로써 기존의 Network Class 방식에 비해 유연하게 동작할 수 있도록하며, IP 주소 체계를 보다 효율화한다.

(더 많은 IP 주소를 이용할 수 있도록 한다.)

또한, 계층적 구조이기 때문에 Routing 에 있어서 부담이 최소화되는 장점이 있다.

기존의 네트워크 클래스 방식의 기법은 IP 주소에 범위를 정하고 해당 범위대로 Class 를 분류한다.

가령, 나뉘는 클래스의 범위는 다음과 같아진다.

- A Class : 0 ~ 127

- B Class : 128 ~ 191

- C Class : 192 ~ 223

- D Class : 224 ~ 239

- E Class : 240 ~ 245

위와 같은 방식에서, Class 의 범주에 딱맞지않는다면, 호스트 주소공간을 할당하기 위해 클래스를 선택할 때 문제가 발생한다. 즉, 더 높은 클래스를 선택함으로써 남은 주소 블록들을 낭비할것인지, 아니면 낮은 클래스를 사용해서 주소의 부족함을 감수할 것인지에 대한 문제가 생기게 된다.

CIDR 은 이에 비해 보다 유연성을 제공하고, 그 덕분에 더 많은 IP 주소 공간의 운용을 가능하도록 한다.

CIDR(사이더)을 이용한 주소 체계는 다음과 같이 지정될 수 있다.

이는 해당 IP 주소의 첫 24비트를 네트워크 라우팅을 위한 주소로 사용한다는 의미이다.

따라서 해당 주소의 표현은 위와 같이 이진수로 나타낼 수 있고, 네트워크 주소로 표현되는 부분과 네트워크 주소 뒤에 호스트 번호가 포함되게 된다. 

다음은 예시로 나타낸 주소에 대해 IP 주소 체계를 분석해본 것이다.

비트연산을 이용해 Subnet Mask 와 Broadcast Address 를 어렵지않게 구해낼 수 있고, 해당 정보를 바탕으로 Host 의 가용 범위 역시 구해낼 수 있다.

즉, 위의 주소 192.168.0.15/24 의 의미는 192.168.0.1 부터 192.168.0.255 까지의 주소 범위를 의미하는 CIDR 표기법이라 할 수 있다. (앞의 24 bit가 Masking 이기 때문이다.)

이를 192.168.0.15/32 로 표기하면 이는 192.168.0.15 주소 그 자체를 의미한다.

CIDR 는 네트워크를 이해하는 데 있어 필수적인 기초개념이고, 생각나지않을 때마다 정리해보면 IP 주소 체계를 이해하는데 도움이 될 수 있다.

보통 트리의 순회를 구현하게되면, 간단한 재귀함수의 호출 형태로 구현하게 되는데, 이 때 고려해야할 점은 재귀함수의 호출은 Stack 메모리의 희생을 요구한다는 점이다.

즉, 순회만으로도 노드의 갯수가 많아진다면 Stack Overflow 에러가 발생하게 된다.

의외로 Tree 의 Traversal 을 Recursion 이 아닌 Iteratation 로 구현하는데 어려움을 겪을 수 있어 정리해보았다.

public class Algorithm {

	/***
    	TreeMap 은 index 를 키값으로하는 Map 의 형식으로 저장된 n-Ary tree
        TreeValues 는 index 에 따라 트리의 Value 를 저장한 리스트
    **/
	public void postOrderTraversal(Map<Integer, List<Integer>> treeMap, List<Integer> treeValues) {
		Stack<Integer> returnStack = new Stack<>();		//순회할 노드들의 인덱스를 저장하는 스택
		Stack<Integer> resultStack = new Stack<>();		//순회하고 나온 Return 값을 저장하는 스택
		returnStack.push(0);					//0번 노드를 루트로 가정하고 루트부터 순회
		while (!returnStack.isEmpty()) {
			int next = returnStack.pop();
			resultStack.push(treeValues.get(next));
			if(treeMap.containsKey(next)) {
				List<Integer> children = treeMap.get(next);
				for(int child : children) {
					returnStack.push(child);
				}
			}
		}
		while (!resultStack.isEmpty()) {
			System.out.println(resultStack.pop());		//후위 순서대로 출력
		}
	}
}

귀찮아서 별도의 노드 클래스 없이 Map 과 List 를 활용해 트리 구조를 제공하였으나 ;;

위와 같이하면 저장된 비선형 트리를 재귀구조없이 후위 순회할 수 있다.

Binary Search Tree란, 검색과 삽입을 모두 O(logN) 이라는 빠른 시간 내에 수행할 수 있는 매우 효과적인 비선형 자료구조(Non-Linear Data Structure) 이다.

Binary Search Tree 를 구현하는 건 어렵지않지만, 의외로 만들어져있는 트리가 BST 인지 아닌지 판별하는 알고리즘은 애를 먹는 개발자들이 많다.

만들어져있는 트리가 BST 인지 파악하려면 다음을 고려해야 한다.

1. 왼쪽 자식 노드가 루트보다 작고, 오른쪽 자식 노드가 루트보다 큰지

2. 왼쪽 서브트리의 최댓값이 루트보다 작고, 오른쪽 서브트리의 최솟값이 루트보다 작은지

문제에서 정의하는 바의 판별을 위해 간단히 재귀(Recursion) 를 이용해서 문제를 해결할 수 있다.

재귀적으로 트리를 Preorder Search 하면서 lower bound 와 upper bound 를 잡고, 해당 노드의 값이 그 사이에 포함되는 지를 확인해주면 된다.

   private boolean checkValidBST(TreeNode root, long low, long high) {
      if (root.val <= low || root.val >= high) {
         return false;
      }
      boolean result = true;
      if (root.left != null) {
         result &= checkValidBST(root.left, low, Math.min(high, root.val));
      }
      if (root.right != null) {
         result &= checkValidBST(root.right, Math.max(low, root.val), high);
      }
      return result;
   }

   public boolean isValidBST(TreeNode root) {
      if(root == null) {
         return true;
      }
      return checkValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
   }

위의 알고리즘을 통해 O(N) 의 복잡도에 해결해낼 수 있다.

Cache 알고리즘 중에 가장 유명한 알고리즘 중 하나로 LRU 알고리즘 이라는 것이 있다.

LRU 알고리즘이란 Least Recently Used Algorithm 의 약자로, 캐시에서 메모리를 다루기 위해 사용되는 알고리즘이다.

캐시가 사용하는 리소스의 양은 제한되어 있고, 캐시는 제한된 리소스 내에서 데이터를 빠르게 저장하고 접근할 수 있어야 한다.

이를 위해 LRU 알고리즘은 메모리 상에서 가장 최근에 사용된 적이 없는 캐시의 메모리부터 대체하며 새로운 데이터로 갱신시켜준다.

알고리즘의 주요 동작은 다음과 같다.

가장 최근에 사용된 항목은 리스트의 맨 앞에 위치하고 가장 최근에 사용되지않은 항목 순서대로 리스트에서 제거된다.

LRU 알고리즘의 구현은 위의 그림에서도 볼 수 있듯이 Linked List 를 이용한 Queue 로 이루어지고, 접근의 성능 개선을 위해 Map 을 같이 사용한다.

다음 예제코드를 참조하자.

public class LRUCacheImpl {

	private class ListNode {
		private int key;
		private int val;
		private ListNode prev;
		private ListNode next;

		public ListNode(int key, int val) {
			this.key = key;
			this.val = val;
			this.prev = null;
			this.next = null;
		}
	}

	private Map<Integer, ListNode> nodeMap;
	private int capacity;
	private ListNode head;
	private ListNode tail;

	public LRUCacheImpl(int capacity) {
		this.nodeMap = new HashMap<>();
		this.capacity = capacity;
		head = new ListNode(0, 0);
		tail = new ListNode(0, 0);
		head.next = tail;
		tail.prev = head;
	}

	private void remove(ListNode node) {
		node.prev.next = node.next;
		node.next.prev = node.prev;
		nodeMap.remove(node.key);
	}

	private void insertToHead(ListNode node) {
		this.head.next.prev = node;
		node.next = this.head.next;
		node.prev = this.head;
		this.head.next = node;
		nodeMap.put(node.key, node);
	}

	public int get(int key) {
		if (!nodeMap.containsKey(key)) {
			return -1;
		}
		ListNode node = nodeMap.get(key);
		remove(node);
		insertToHead(node);
		return node.val;
	}

	public void put(int key, int value) {
		ListNode newNode = new ListNode(key, value);
		if (nodeMap.containsKey(key)) {
			ListNode oldNode = nodeMap.get(key);
			remove(oldNode);
		} else {
			if (nodeMap.size() >= capacity) {
				ListNode tailNode = tail.prev;
				remove(tailNode);
			}
		}
		insertToHead(newNode);
	}
}

여기서 테크닉적으로 중요한 부분은, Linked List 처리의 효율성과 코딩상의 이점을 위해 Head 와 Tail 을 단순히 포인터로만 둔 상태에서 중간에 노드들을 배치시키는 더블 링크드리스트 형태를 취한다는 점이다.

즉, Head 가 가리키는 head.next 값이 실제 리스트의 첫 원소가 되고, Tail 이 가리키는 Tail.prev 값이 실제 리스트의 마지막 원소가 된다.

이렇게 Linked List 와 Map 을 이용해서 구현 시, Get 연산에 O(1), Put 연산에도 O(1) 의 성능을 가져올 수 있다.

쉬우면서도 효과적인 알고리즘이자 자료구조이므로 잘 익혀두자.

Spring AOP(Aspect Of Control) 란, DI(Dependency Injection), PSA(Portable Service Abstraction) 와 같이 Spring Framework 의 주요 Feature 이다.

AOP 란 공통된 관심사(Aspect)로 구분된 로직을 필요한 위치에 동적으로 삽입할 수 있게 해주는 기술로,

Advice, JoinPoint, PointCut, Advisor 등의 용어가 사용되며, 비즈니스 로직과 연계되어 공통적으로 사용하는 부분(Transaction 이나 Filter, Security 등의 Layer)을 코드를 특정시점에 코드에 삽입하는 기술이다.

이러한 핵심 로직 코드에의 적용을 Weaving 이라 하며 Compile 시, Class Loading 시, Runtime 시 AOP의 구현이 가능하다.

다음은 몇가지 AOP 에 사용되는 용어들에 대한 정리이다.

- Aspect : 핵심기능에 부가될 수 있는 모듈을 말한다. 재사용 가능하며 핵심적인 기능에 부가되어 의미를 가질 수 있는 모듈이다.

- Advice : Aspect 에 대한 구현체가 된다. 주로 어느시점에 어떤 동작을 할지가 기술된다.

- Point Cut : 핵심 모듈을 분리할 선이자, 어드바이스를 적용할 시점(Join Point)을 정의하는 모듈이 된다.

- Proxy : 타겟은 프록시를 통해 호출되며 타겟 메서드 실행에 대한 전처리 후처리를 담당해줌과 동시에 AOP 추상화에 있어서 인터페이스를 제공한다.

- Weaving : 핵심 로직 코드에의 적용을 말하며, Aspect 가 적용됨으로써 새로운 Proxy 객체가 생성된다.

- Cross Cut : 공통 로직을 비즈니스 로직에서 추출해내는 것을 Cross Cutting 이라 한다.

하지만 위의 내용들은 사실 용어와 사용하는 기술들에 대한 내용으로 실제 Spring 에서 추구하는 AOP 의 개념 그 자체는 서버의 기능을 비즈니스 기능과 공통 기능으로 나누고, 공통 기능을 코드 밖에서 필요한 시점에 재사용 가능하도록 적용시켜 주겠다는 개념이다.

결국 공통 기능을 따로 분리해서 재사용하겠다는 관점을 말하는 것이다.