두 달정도 전 쯤에 키보드에 콜라를 쏟았던 적이 있다. 우측 Ctrl 키 부근에 쏟았는데, 작동도 잘 되고 딱히 불편함이 없어서 A/S를 보내지 않고 계속 쓰고 있었다.
음료를 쏟은지 한 달이 지나자 Ctrl 키를 눌러도 올라오지 않는 증상이 생겼다.
눌러도 올라오지 않는 Ctrl 키..
레오폴드 키는 특히 '한자' 키가 우측 Ctrl키와 함께 동작하는데, 내가 '한자'를 얼마나 자주 쓰는지 이 경험을 통해 알게 됐다.
불편함을 느끼게 되자 매우 신경쓰이고, 도저히 못쓰겠다 싶어서 레오폴드 공식 홈페이지에서 A/S를 신청하였고, 택배를 보낸지 2주쯤 지나자 수리된 제품을 받아볼 수 있게 됐다. (레오폴드는 우체국을 통해 택배를 보내니, A/S를 맡기고 연락이 없다면 우체국 앱을 통해 조회해 보자.)
레오폴드 A/S는 추가금이 발생할 때만 연락 온다고 알려져있는데, 이번주 월요일 레오폴드로부터 연락을 받아 속으로 많이 놀랐었다. (콜라 특성에 의해 기판이 부식되어 추가금이 발생하는건가..?ㅠㅠ)
전화를 받아보니, 내가 증상으로 첨부한 동영상의 기간이 만료되어 증상 확인이 불가능해 확인차 연락주신것 이었다.
A/S 언박싱!
레오폴드의 A/S는 키보드의 삼성급이라 알려져 있던 만큼 꽤 기대하고 있었다. (다른 분들의 후기를 보면 보낸지 3일만에 받은 사람도 있어서 시간적으로도 금방 될거라 기대했지만..ㅠㅠ 2주가 걸렸다. 기간은 레오폴드 공식 홈페이지에 매번 공지되니 잘 확인하면 좋을것 같다.)
뽁뽁이는 가지런하게 잘 싸여 왔고, 뽁뽁이를 뜯은 박스의 상태가 꽤 깨끗해서 새 박스인가? 하는 착각이 들 정도였다.
박스를 열면 키보드 위에 뽁뽁이를 올려주신 후기도 봐서 나도 그러면 좋겠다는 생각을 했지만, 나는 그냥 키보드만 왔다. ㅠㅠ (그런데 박스 내부가 보낼 때 닦아서 보냈는데 먼지가 많이 쌓여서 왔다. 2주간의 기다림 때문인가..?)
키보드는 정상적으로 동작하는 것을 모두 확인했다. 무엇보다 전보다 키들이 더 부드러워 진 것 같은 착각도 든다.
키보드 수리기간 동안 블루투스 키보드를 사용하면서 손목이 꽤 많이 아팠는데, 이제 안아파도 된다는 생각에 너무 좋다.
중앙화 블록체인을 만들면서 Transaction을 효율적으로 검색할 수 있는 시스템을 개발하던 중, ElasticSearch라는 기술을 알게됐다. 기존에는 파일 형태로 Transaction을 저장하려 했으나, 이후 주어진 Transaction을 검증하는데 있어 오랜 시간이 소모될 것 같아 해결법을 강구하던 중 알게된 기술이다. ElasticSearch는 기본적으로 REST API 통신으로 데이터를 조작할 수 있었고, 여기에 Transaction 저장방식을 객체형 DB인 MongoDB에 저장하기로 했다.
File로 저장할 때에도 JSON 타입으로 저장하여 ElasticSearch를 연계할 수 있었지만, 그냥 파일로 저장 안하고 MongoDB에 저장하기로 결정했다. (MongoDB에만 Transaction을 저장하는건 문제가 될 수 있지만, 개발하고 있는 블록체인에서는 Authenticator라는 역할이 몇명 존재하기 때문에, 여기에 약간의 분산저장을 하고 있어서 크게 신경쓰지 않기로 했다.)
Linux와 관련된 글은 많았으나, 이번에 개발하는 서버가 Windows 기반이기에 관련 자료가 거의 없다싶이 하여 글을 쓰게 됐다.
구현하고자 하는 기능은 다음과 같다. MongoDB에 어떤 데이터가 저장되면 ElasticSearch의 데이터로 동기화시켜 데이터를 구할때는 MongoDB가 아닌 Elastic Search에서 가져올 것이다.
사용된 MongoDB와 ElasticSearch 그리고 Logstash의 버전은 다음과 같다.
Logstash를 설치한 이후에, mongodb input 플러그인을 설치해줘야 하는데, 정말 쉽게 cmd로 설치할 수 있었다. (관련된 글들이 모두 linux 기반이고, 명령어 또한 linux의 그것과 닮았기에 윈도우에서 동작 안할 줄 알았는데, 된다. 이걸로 이틀은 날려먹은 것 같다.)
cmd 명령 프롬프트 창을 관리자 권한으로 실행시킨 뒤, 다음 명령어를 입력하면 logstash-input-mongodb가 설치된다.
cd \path\to\logstash\bin\logstash-plugin install logstash-input-mongodb
만약 Success to installation( 정확히 기억 나지는 않지만 )과 같이 설치에 성공했다는 문구가 안뜨면, 오류가 함께 출력되니 그에 맞춰서 대응하면 된다.
이후 logstash를 이용하여 mongodb로부터 데이터를 가져와 elasticsearch로 넘겨주는 설정이 필요하다. 해당 설정은 다음과 같다.
# Sample Logstash configuration for receiving # UDP syslog messages over port 514 input { mongodb { uri => '몽고DB 주소' placeholder_db_dir => '입력 저장할 파일 경로' placeholder_db_name => '저장할 파일 이름' collection => '가져올 collection 이르' batch_size => 2000 generateId => false parse_method => "simple" } } filter { mutate { copy => { "_id" => "[@metadata][_id]"} remove_field => ["_id"] } } output { elasticsearch { hosts => ["엘라스틱 서치 주소"] index => "데이터를 삽입할 index 명" document_id => "%{[@metadata][_id]}" } stdout { } }
batch_size: 한번에 가져올 수 있는 최대 양 이다. placeholder_db_dir에 저장된 placeholder_db_name을 지운다고 해서 Elastic Search에 동기화된 내용이 삭제되는 것은 아니다. 따라서 데이터의 삭제를 위해서는 elastic search에서 직접 제거해주어야 한다.
filter같은 경우에 엘라스틱 서치의 _id와 몽고db의 _id가 겹쳐서 오류가 발생할 수 있기 때문에, 몽고db의 _id를 나는 제거해주었다.
파일 명은 mongodb.conf 이며, 저장 위치는 logstash가 설치된 폴더의 config 폴더 내에 저장했다. ( \logstash\config\mongodb.conf\ )
이후 logstash를 실행 시켰을 때 정상적으로 실행된다면 성공이다.
사실 몽고DB와 엘라스틱 서치는 따로 건드리는 것 없이 logstash만 잘 설정해주면 작동해야만 한다. 몽고DB와 엘라스틱 서치가 정상적으로 동작하지만, sync가 안된다면 logstash의 설정에서 무엇인가 잘못된 것이니 logstash에서 찍히는 log를 잘 읽어보면 해결할 수 있을것이다.
프로그래밍에서 의존성이라고 하면, 예를 들어 A라는 객체를 만들 때 A의 원형태라고 생각하면 쉽다. 즉, A 객체는 A 클래스에 의존하여 생성되는 것이다.
Car myCar = new Hyndai();
위 코드에서는 myCar가 Hyndai에 의존한다는 것을 알 수 있다.
프로그램을 만들고, 이후에 코드를 업데이트 해야하는 경우가 발생하면, A와 연관된 클래스를 모두 수정해야 하는 일이 발생한다. 즉 의존성을 일일이 모두 변경해줘야 하는 것이다.
만약 내가 현대차에서 Kia차로 바꾼다면 어떻게 해야할 까? myCar가 사용되는 모든 곳에 대해 Hyundai를 Kia로 바꿔줘야 하는 상황이 발생하는 것이다.
Car myCar = new Kia();
Car myCar = new Hyundai();
...
class Hyundai extends Car{
...
}
class Car implements Vehicle{
...
}
interface Vehicle{
...
}
기존에는 위와 같이 코드를 작성한다 할 때, myCar를 만드는 순서는 다음과 같다.
Hyundai -> Car -> Vehicle
Class Diagram으로 설명하면, 위 코드는 다음과 같은 그림을 갖는다.
즉 myCar를 만들기 위해 Hyundai를 만들고, Hyundai를 만들기 위해 Car, Car를 위해 Vehicle이 만들어 지는 것이다.
위처럼 Car myCar = new Hyundai()처럼 직접 객체를 만들고 의존하는 방식을 Composition has a 라고 하는데, 우리는 연결형, 즉 Association has a를 만들려고 한다.
Composition has a는 위에서 언급 했듯이, Kia차로 차를 바꾼다면 모든 myCar를 Kia로 바꿔줘야 하기 때문이다.
Association has a를 한 코드로 예를 들면, 다음과 같다.
...
class Car{
Car car;
...
void setCar(Car car){
this.myCar = car;
}
}
...
Hyundai hyundai = new Hyundai();
Car myCar;
myCar.setCar(hyundai);
...
Car를 연결하는 Hyundai를 따로 만들고, 이를 setter 등을 이용하여 myCar의 Car에 연결하는 것이다. 이렇게 되면 myCar를 바꿀 필요 없이 Hyundai의 선언만 Kia로 바꿔주면 된다.
하지만 스프링은 이를 xml 등을 이용하여 소스를 직접 수정하지않고, 구성 파일만 수정함으로써 의존성을 변경할 수 있게 해준다.
이를 의존성을 주입한다고 하는데, 영어로는 Dependency Injection다.
Inversion of Control ?
갑자기 Inversion of Control이 나와서 이게 뭘까 싶을 수 있다. IoC는 자바의 DI를 이해하기 위해서 알아야 하는 속성인데, 구글 번역기를 돌려보면 "제어 반전"이라는 해석이 나온다. 제어??? 반전??? 도대체 무슨말이야??
위에 Class Diagram으로 Composition has a의 순서와 반대로 생성되는 것이다.
Vehicle -> Car -> Hyundai
이 순서로 생성되는 것인데, 이는 이미 스프링의 어떤 xml 파일에서 beans로 정의되어 있기 때문에 가능한 것이다.
xml에 정의되어있는 어떤 컨트롤을 내 소스에 주입 하는 것인데, 쉽게 말하면 만들어진 Hyundai, Kia를 내 myCar.setCar(hyundai) 혹은 myCar.setCar(kia)와 같은 방식으로 자동으로 설정되게 하는 것이다.
이를 이용하면 소스파일의 수정 없이 의존성을 주입할 수 있다.
직접 주입해보자!
이러한 스프링 xml파일을 만들기 위해서는 springframework의 spring-context를 이용하여야 한다. 이를 pom.xml에 넣어주자. 이는 maven을 이용한다면, maven에서 dependency를 추가해주면되고, 그렇지 않다면 직접 코드를 추가해주면 된다. 나의 경우 maven repository에서 추가했고, 추가된 코드는 다음과 같다.
이후에 src폴더에 xml만 모아놓은 폴더여도 좋고, DI를 이용하는 소스가 있는 폴더에 넣어도 좋다. 개인적으로는 DI xml을 넣는 폴더를 따로 만들어 관리하기를 추천한다.
이클립스에서 새로 추가하기 -> Other -> Spring -> Spring Bean Configuration File을 추가해 주고 이름을 적절히 설정하면 name.xml파일이 생성된다.
나는 myCar.xml이라 하겠다.
우선, Car 클래스와 관련된 소스는 아래와 같다.
public interface Vehicle {
int getWheels();
String getNames();
}
public class Car implements Vehicle {
String name;
int wheels;
public Car(String name, int wheels) {
this.name = name;
this.wheels = wheels;
}
@Override
public int getWheels() { return wheels; }
@Override
public String getNames() { return this.name; }
public void setWheels(int wheels) { this.wheels = wheels; }
public void setName(String name) { this.name = name; }
@Override
public String toString() {
return "Car [name=" + name + ", wheels=" + wheels + "]";
}
}
public class Hyundai implements CarUI {
private Car car;
public Hyundai() {
}
@Override
public void print() {
System.out.println("*************");
System.out.println("HYUNDAI " + car.toString());
System.out.println("*************");
}
public void setCar(Car car) {
this.car = car;
}
}
public class Kia implements CarUI {
private Car car;
public Kia() {
}
@Override
public void print() {
System.out.println("=============");
System.out.println("KIA " + car.toString());
System.out.println("=============");
}
public void setCar(Car car) {
this.car = car;
}
}
public interface CarUI {
void print();
}
Spring을 사용하지 않을때 myCar를 설정한다면, 다음과 같이 해야 했다.
public class MyOwnCar {
public static void main(String[] args) {
Car hyundai = new Car("SUV", 4);
Hyundai myCar = new Hyundai();
myCar.setCar(hyundai);
myCar.print();
}
}
즉, 내 차가 Kia차로 바뀐다면, 아래와 같이 바뀌어야 했다.
public class MyOwnCar {
public static void main(String[] args) {
/*
Car hyundai = new Car("SUV", 4);
Hyundai myCar = new Hyundai();
*/
Car kia = new Car("SUV", 4);
Kia myCar = new Kia();
myCar.setCar(kia);
myCar.print();
}
}
이제는 myCar.xml을 통해 이러한 행동을 하지 않으려고 한다.
스프링에서는 xml과 같은 DI 지시서를 이용하기 위해서는 Spring context를 이용하여야 하는데, 코드로 다음과 같이 작성한다.
ApplicationContext context = new ClassPathXmlApplicationContext("spring/di/myCar.xml");
ApplicationContext를 xml로부터 가져오는데, "spring/di/myCar.xml"이 내가 불러오고자 하는 DI 지시서의 경로인 것이다.
이후 context.getBean을 통해 해당 DI 지시서에 등록되어있는 beans를 이용할 수 있다.
bean을 이용하는 방법은 다음과 같다.
<bean id="의존성 주입할 객체의 변수명" class="해당 객체의 형태를 나타내는 class경로" />
즉, 내 myCar의 경우에는
<bean id="myCar" class="spring.di.entity.Car" />
이 된다.
만약 의존성을 주입할 때 그냥 설정만 하는거라면 우리가 일일이 변수를 다 변경해줘야 하고, 그렇다면 스프링은 지금처럼 많이 쓰이지 않았을 것이다. 한마디로 스프링은 변수와 같은 속성 설정도 지원하는데, 다음과 같은 속성을 사용할 수 있다.
1. index : n번째 index를 설정한다. 2. name : name과 동일한 이름을 갖는 변수를 설정한다. 3. p : p:"NAME" 에서 "NAME"과 동일한 변수를 설정한다. 이 때, xmlns:p="http://www.springframework.org/schema/p" 를 추가하여야 한다. 4. setter를 직접 사용한다.
각각 사용하는 방법은 다음과 같다.
<bean id="myCar" class="spring.di.entity.Car">
<!-- 1번. index를 이용하는 경우 -->
<constructor-arg index="0" value="SUV" />
<constructor-arg index="1" value="4" />
<!--
만약 생성자가 2개 이상이고, 자료형만 다른 parameter를 전달 받는다면 type을 이용해 구분할 수 있다.
<constructor-arg index="0" type="int" value="4" />
<constructor-arg index="0" type="String" value="SUV" />
-->
<!-- 2번 name을 이용하는 경우 -->
<property name="name" value="SUV" />
<property name="wheels" value="4" />
<!-- 3번 p 속성을 이용하는 경우 -->
<bean id="myCar" class="spring.di.entity.Car" p:name="SUV" p:wheels="4" />
<!-- 4번. 직접 setter를 이용하는 경우 -->
myCar.setName("SUV");
</bean>
나머지 경우는 모두 직접 해보시길 바라고, 나는 2번 name을 이용하였을 때의 결과를 보여주겠다.
JSP 혹은 서블릿을 이용해 웹 서버를 개발할 때 파일 입출력 관련 프로그래밍을 해야하는 경우가 있다. 이 때, 출력 파일의 권한을 수정할 때, 수정되지 않는 경우가 있다. 이번 게시글에 작성할 문제의 경우, 파일을 생성할 때는 정상적으로 권한이 변경됐으나, 폴더를 생성할 때는 권한이 정상적으로 변경되지 않았다. 아무리 생각해봐도 톰캣의 권한 문제라면 생성되는 파일또한 권한이 정상적으로 변경되지 않아야 했으나, 정상적으로 출력되는 바람에 꽤 많이 헤매었다.
2021.11.23 추가
만약에, 아래 문단의 방법으로 안될 경우 아래 명령어를 통해 ReadWritePaths가 정상적으로 수정되었는지 확인해보자. 아직까지 왜 파일이 설정한대로 안바뀌는지 이유는 찾지 못했다. 이유를 찾으면 게시글을 업데이트 하겠당.
$ systemctl edit --full tomcat#.service
...
ReadWritePaths=대상폴더 ...
이 명령어를 통해 어떤 폴더에 권한을 줄 경우, 해당 폴더는미리 생성되어 있어야 한다. 뿐만 아니라, 아래 방식의 tomcat9.service에도 똑같은 내용을 적어놓는 것을 추천한다.
Tomcat 버전 9 이상의 경우, 톰캣이 실행할 웹앱 디렉토리의 소유자에 대하여 tomcat 계정, 혹은 tomcat이 추가된 그룹으로 바꾸고, 아래 루트로 이동하여 ReadWritePaths에 해당 웹앱의 ROOT 디렉토리를 추가한다.
인터페이스를 한 단어로 표현하면 '규약'이다. 개발하면서 꼭 지켜야 할 '규약'같은 존재로, 바꿔말하면 개발할 때 반드시 포함해야하는 멤버를 모아놓은것이 인터페이스다. 이렇게 말하면, 추상 클래스와 다른점이 무엇인지 헷갈릴 수 있다. 추상 클래스는 쉽게 말해 개발이 들어간 시점에서 공통된 속성을 모아놓은 클래스이며, 해당 추상 클래스를 '상속'하는 클래스는 해당 추상 메소드들을 모두 구현하여야 한다. 인터페이스는 이와 다르게 개발이 들어가기 전에 만들어질 메소드들에 대해 '규칙'을 정해놓은 것이고, 이를 '구현'하는 클래스들은 해당 메소드들을 모두 내용을 담아 만들어야 한다.
규칙? 그게 뭔데?
아직까지 이해가 안되는가? 그렇다면 경우를 들어 설명해 보자면, A와 B가 함께 자동차 객체를 생성하는 클래스를 만든다고 하자. 이 때, A는 자동차의 구동을 담당하고, B는 자동차의 프레임을 담당한다고 하자. 결국 자동차는 프레임과 구동부가 결합되어야 하는데, 만약 결합부가 일치하지 않는다면 설계에 실패했다고 볼 수 있고, 즉 자동차 객체를 생성 못한다고 볼 수 있다. 이를 위해 결합부에 대해 어떻게 설계하겠다는 약속을 정해야 하는데, 이를 인터페이스를 이용해 약속하는 것이다.
인터페이스 생김새
인터페이스는 이렇게 생겼다.
interface CarInterface{
public void move();
public void setSpeed(int speed);
}
CarInterface는 move와 setSpeed에 대해 설계 방식을 정하고 있고, 해당 인터페이스를 구현하는 클래스들은 두 함수에 대해 실질적인 내용을 담아야한다. 즉, 인터페이스는 함수내부가 어떻게 생겼을 지 모르겠지만, return 타입, 받아들일 파라미터 등 함수가 어떻게 생겼는지를 정해놓은 것이다. 따라서 A와 B가 같은 자동차를 설계하기 전에 인터페이스를 만들어 놓고, 결합부에 대해 약속을 정한다면 결합부가 일치하지 않아 자동차를 만들 수 없는 일은 발생하지 않을것이다.
왜 하필 인터페이스? 추상 클래스로는 안돼?
인터페이스가 가지는 추상클래스와의 가장 큰 다른점은 재사용성이다. 클래스는 다중상속이 불가능하지만, 인터페이스는 다중상속이 가능하다.
interface Vehicle{
public void move();
}
interface WheelObjects{
public void setWheels();
public void getWheels();
}
interface Car extends Vehicle, WheelObjects{
public void setHorsePower(float horsePower);
}
interface Airplane extends Vehicle{
public void setMaha(float Maha);
}
위와 같은 다중상속이 가능해짐으로써, Car라는 인터페이스를 만들기 위해 Vehicle과 WheelObjects의 인터페이스를 상속받아 각 인터페이스가 갖는 규칙을 모두 가질 수 있는 것이다. 뿐만 아니라, Vehicle 인터페이스를 Car에만 사용하는 것이 아니라 Airplane이라는 움직이는 방법이 전혀 다른 이동수단이 상속받을 수 있게 설계할 수 있다. 만약 추상클래스였다면, Car가 갖는 속성들을 Airplane은 가질수 없는게 당연한것과는 반대되는 성질이다. Java 8이 넘어가면서 추상클래스와 인터페이스의 관계는 많이 모호해지긴 했지만, 인터페이스의 특징을 잘 살리면 인터페이스 나름의 이용성이 큰 녀석이기 때문에 잘 이해해두면 좋은 친구다.
블록체인의 작업증명은 거래(트랜잭션)이 주어지면, 해당 거래를 가지고 블록을 만들 수 있는지 확인해야 한다. 주어진 거래와 같은 블록을 이루는 거래들을 이용하여 해당 블록의 Hash값과 일치하는지 확인해야 하는데, 이 때 머클트리를 활용한다.
머클트리
머클트리는 위 이미지와 같이 생겼는데, 거래 정보는 Leaf Nodes를 구성하고, 해당 거래 정보의 부모들은 각 자식들을 Hash 한 값이 된다. 이렇게 쭉쭉 타고 올라가 결국 root값 또한 root의 자식들을 hash한 값으로 이루어진다. 또한 Merkle Tree는 생성된 후에 값이 변조되면 안되기 때문에, 오직 getRoot()라는 method만 가진다. (블록체인에서 블록의 수정은 불가능하기 때문이다.) Merkle Tree를 정말 트리로 구성하여 삽입, 수정, 삭제 등의 기능을 구현해도 되지만, 이는 Java의 자료구조에서 다룰 것이고, 오늘은 블록체인의 Merkle Tree이기 때문에 단순 삽입을 통한 merkle Tree를 구성하게 하겠다.
블록으로 만들려고 하는 상황중 가장 좋은 경우는 트랜잭션의 갯수가 2^n꼴로, 이진트리를 만들었을 때 모든 leaf노드들을 트랜잭션으로 만들 수 있을때는 가장 편하다. 받아들인 트랜잭션(거래)들을 모두 leaf 노드로 설정하고, 부모를 만들어 나가며 root값을 찾으면 되기 때문이다.
거래의 수가 홀수라면 어떻게?
내가 가지고 있는 홀수 개의 수로 머클트리를 만들어야 할때는, 간단하게 다음과 같이 해결할 수 있다.
짝이 없는 거래(마지막 홀수번째)는 자신을 이용하여 해쉬한다.
짝이 없는 거래, 마지막 홀수번째 거래의 경우에는 자기 자신을 한번 더 사용하여 해시값을 만들면 된다. 이 아이디어를 응용해 보면, 2^n꼴이 아닌, 짝수개의 트랜잭션은 어떻게 하면 될까? 다음 그림을 보고 힌트를 찾길 바란다.
짝수개 머클트리
그림상 2번 Hash가 (1, 2)라 되어 있는데 오타다. Hash(3, 4)가 2번 동그라미가 되어야 한다.
머클트리 구현 아이디어
머클트리는 Binary Tree형 자료구조이다. 그리고 실제 데이터 삽입은 단말 노드에서만 이루어진다. 즉 머클트리는 기존 트리처럼 Top-Down 형식의 구현이 아니라 Bottom-Up 형식으로 구현하면 된다. 그리고 블록체인의 각 블록은 머클트리의 루트값만 가지고 있으면 된다. 바꿔 생각해보면, 만약 블록체인이 머클트리를 이루는 모든 해쉬값을 갖고 있으면 추적할 수 있게 되는것이고, 이는 보안상 구멍이 될 수 있는 것이다. 누구든 해당 블록을 만드는 각 트랜잭션을 만들 수 있게 되고, 그를 바탕으로 누가 어떤 거래를 했는지 알 수 있게 되는 것이다. 따라서 머클트리는 각 depth간 모든 해쉬 정보를 갖고 있을 필요가 없으며, 머클트리를 검증하기 위한 각 계층의 해쉬값을 Peer들에게 요청하면 되는것이다. 다시 본론으로 돌아와서 머클트리는 따라서 Root값만 가지고 있으면 된다. 그렇기 때문에 Tree의 모든 특성을 반드시 갖고 있어야 하는것은 아니다. Bottom-Up 구현을 따라서 ArrayList를 이용해 구현해 볼 것이다.
위 사진을 보고 어느정도 이해가 가는가?
머클트리와 관련하여 어떻게 머클트리가 생겼는지 알 수 있지만, 실제로 구현하는데에는 어려움이 있을 수 있다. 이전에 작성한 ArrayList와 마찬가지로 기본 아이디어만 본 포스트에서 구현하고, 활용과 응용은 직접 하시길 바란다.
위 이미지를 보면 알겠지만, ArrayList에 거래를 집어 넣고, 2개씩 끊어 Hash를 진행하면 된다. 함수 하나로 서론에서 말한 세가지 경우를 모두 처리하는 코드를 만들 수 있지만, 세 방향 모두 나눠서 진행할 것이다. 우선 완벽히 Full Binary Tree를 이룰 수 있을때에 대한 구현 방법이다. 이 경우는 정말 쉬운데, 아래 사진에서 처럼 두개 씩 끊어 Hash를 진행하고, List의 가장 마지막에 오는 녀석이 머클트리의 Root 값이 된다.
본 코드는 정말 "아이디어의 기초"를 표현하기 위한 코드이다. depth를 구해서 얼마만큼 Hash를 진행하여야 머클트리가 완성되는지를 표현하였다. depth를 다른시각으로 보면 level이 되고, level만큼 부모를 만들어야 root가 되는지 알 수 있기 때문이다. (이진 트리는 log2n 만큼의 depth를 갖고, 따라서 getDepth 함수는 정말 수학식을 나타낸 것이다.) i가 depth부터 시작하는 이유는 bottomUp 이기 때문에, 아래에서부터 위로 만들기 위함이다. j는 현재 내가 만들고 있는 List의 사이즈를 2^depth로 나누었을때 나머지인데, 그 이유는 다음과 같다.
총 depth가 4인 트리에서, depth 2에 대해 만들기 시작했을 때, depth 3에는 데이터가 8개 존재한다.
또한 hash를 시작해야 하는 List의 인덱스는 0인데, 그 이유는 List에는 방금 막 만든 해시값들만 담겨있기 때문이다. Depth 2에 대해서 해시가 모두 끝났으면, depth 1로 올라오게 되고, 이 때 hash를 시작해야 하는 인덱스는 9이다. 이 때 List의 사이즈는 12이고, i는 2(최초 depth는 4이고, i가 2번 반복했다. 따라서 4-2=2)가 된다.
즉 12 % 4 = 8이 되고, 0~8에 존재하는 원소는 9개이기 때문에 우리가 찾고자하는 인덱스 9가 된다.
for(int j~) 부분을 보게되면, 우리가 만든 List에서 해당하는 index에 대해 Hash를 진행하고 있는것을 확인할 수 있다. if(i == 1)인 부분은, i가 1, 즉 root의 자식 노드들이 되고, 따라서 hash를 진행할 때 size -2, size -1을 통해 마지막 두 Hash값에 대해 Hash를 진행하면 Root 값이 나오게 된다.
거래가 홀수개
private String createOddRoot(ArrayList<MerkleNode<Object>> merkleNodes) { int size = 0; int depth = getDepth(merkleNodes.size())+1; System.out.println("depth: " + depth); ArrayList<String> datas = new ArrayList<String>(); datas.clear(); int start = 0; int last = merkleNodes.size(); for(int i = depth; i > 0; i--) { start = (i == depth || (i == depth-1) ? 0 : last); last = (i == depth ? merkleNodes.size() : datas.size()); for(int j = start; j < last; j += 2) { if(i == depth) { datas.add( new Crypto().doHash(merkleNodes.get(j).getData().toString() + merkleNodes.get(( (j==last-1 ? (j) : (j+1)) )).getData().toString()) ); } else { datas.add( new Crypto().doHash(datas.get(j) + datas.get( (j==last-1 ? (j) : (j+1)) )) ); } } } size = datas.size(); return datas.get(size-1); }
거래가 홀수일 때는 j의 반복자 시작과 마지막을 잘 설정해주면 된다. 홀수개에 대하여 시작 부분은 최초 트랜잭션을 받아오는 부분과, 그 다음 부분은 모두 0부터 시작하면 된다. 그 이유는 최초 List가 비어있고, 전달받은 거래들에서 데이터를 가져오기 때문이고, 최초 부모들을 만들기 성공했다면, 우리가 만든 List의 0번부터 해시를 진행해야 하기 때문이다. 그 이외의 경우에는 이전 반복자의 last값이 시작값이 되는데, 해시를 시작해야하는 인덱스 번호가 곧 지난번의 마지막 인덱스 이후이기 때문이다. 또한 해당하는 인덱스의 값은 이전 반복자에서 분명히 만들어 졌기 때문에, 이렇게 사용할 수 있는 것이다. last의 경우, 최초에는 내가 가지고 있는 거래의 수 만큼 해시를 진행해야하고, 그게 아니라면 만들어진 List의 사이즈만큼 만들어야 하기 때문이다. 중요한것은, Hash를 만들 때, 원소가 한개이냐(마지막 홀수번째 원소)만 확인하면 된다. 만약 그렇다면, 본인을 한번 더 사용하면 된다.
머클트리는 생각보다 간단하지만, 간단한 만큼 자료가 많지 않아서 어떻게 접근해야 할까 고민하는 사람이 많은 것 같다. 따라서 본 게시글에서는 머클트리는 이루는 기초적인 방향과 이를 바탕으로 한 기초적인 방법을 다루어봤다. Full Binary Tree가 아닌 짝수 개를 갖는 코드는 위에서 준 힌트와 Odd를 확인해보면 쉽게 만들 수 있다.\ 머클트리를 만드는 자세한 방법은 JAVA에서 다루도록 하겠다.
