How to shuffle songs?
http://labs.spotify.com/2014/02/28/how-to-shuffle-songs/
요약:
random이란? 정말로 랜덤하게 음악을 섞어서 보여주는것
Fisher-Yates shuffle
그러나 실 사용자들은 랜덤을 그렇게 받아들이지 않는다. 예를 들어 같은 가수의 음악이 연속으로 들린다면 사용자들은 랜덤이 아니라고 여긴다.
사용자가 랜덤이라고 느낄 수 있도록 알고리즘을 수정할 필요가 있다.
Martin Fiedler 라는 사람의 The art of shuffling music 라는 블로그 내용이 있다. 앞에서 말한 문제를 해결해주는 알고리즘이지만 너무 복잡하다.
이에 따라 여기에 Floyd-Steinberg dithering 같은 알고리즘을 써서 같은 종류로 구분되는(예를 들면 같은 작곡가 또는 같은 가수) 음악을 흐트려 놓는 수정을 가하였다.
2014년 3월 11일 화요일
2014년 3월 2일 일요일
Pinterest에서의 ZooKeeper의 SPOF문제 해결하기
ZooKeeper Resilience at Pinterest
http://engineering.pinterest.com/post/77933733851/zookeeper-resilience-at-pinterest
=> 위 내용에의 요약
* ZooKeeper도 fail 할 수 있다.
Too many connections
Too many transactions
Protocol bugs
Human errors
Network partitions
* ZooKeeper의 SPOF를 해결하기 위한 초기 방법
- Add capacity
- Add observers: vote에는 관여하지 않는 ZooKeeper host를 두는 것. vote는 하지 않지만 watch등 다른 것은 가능하게 한다(proxy).
- Use multiple ZooKeeper clusters for isolation
- Fallback to static files: ZooKeeper가 죽으면 static host file과 configuration file을 사용한다.
* Decouple out applications from ZooKeeper
개개의 머신에 있는 daemon이 ZooKeeper에 접속하여 watch하고 data를 받아와서 로컬에 저장한다. 각가의 application들은 로컬에 있는 data를 사용한다.
http://engineering.pinterest.com/post/77933733851/zookeeper-resilience-at-pinterest
=> 위 내용에의 요약
* ZooKeeper도 fail 할 수 있다.
Too many connections
Too many transactions
Protocol bugs
Human errors
Network partitions
* ZooKeeper의 SPOF를 해결하기 위한 초기 방법
- Add capacity
- Add observers: vote에는 관여하지 않는 ZooKeeper host를 두는 것. vote는 하지 않지만 watch등 다른 것은 가능하게 한다(proxy).
- Use multiple ZooKeeper clusters for isolation
- Fallback to static files: ZooKeeper가 죽으면 static host file과 configuration file을 사용한다.
* Decouple out applications from ZooKeeper
개개의 머신에 있는 daemon이 ZooKeeper에 접속하여 watch하고 data를 받아와서 로컬에 저장한다. 각가의 application들은 로컬에 있는 data를 사용한다.
2014년 3월 1일 토요일
애플 iMessage의 보안 설명
Apple Explains Exactly How Secure iMessage Really Is
http://techcrunch.com/2014/02/27/apple-explains-exactly-how-secure-imessage-really-is/
=> 간단 요약
iMessage의 동작 방식
1. iMessage를 처음 사용하면 두개의 private/public key 셋을 만든다.
2. private key는 디바이스에 놔두고(나중에 decrypt에 사용) public key는 애플의 서버에 보낸다.
3. 내 친구가 나와 채팅하고자 하면 친구의 장비는 내 public key를 애플 서버로부터 받아온다. 친구가 메시지를 작정하고 send를 하면 받아온 public key로 encrypt를 한 후 내보낸다.
4. 각각의 메시지별로 암호화가 된다. 예를 들어 내가 아이폰과 아이패드를 가지고 있다면 나는 아이폰용 pri/pub key 셋, 아이패드용 pri/pub key 셋을 가지고 있을 것이므로 각각의 장비별로 암호화된 후 보내진다.
5. timestamp나 APN routing data같은 일부분의 데이타는 암호화하지 안는다.
6. 암호화된것과 암호화되지 않은 전체를 모아 또 암호화를 한다.
7. 사진이나 긴 메시지같은 양이 큰 경우: 랜덤 키를 만들어 사진을 이것으로 암호화한다. 그리고 암호화된 사진을 애플의 서버에 저장한다(URI). 키와 사진의 URI를 암호화하여 보내고자 하는 쪽에 전달한다. 받은 쪽은 URI에서 사진을 받아온 후 키로 복호화하여 사진을 볼 수 있게 된다.
8. 사용자가 메시지를 받으면 애플을 서버에서 메시지를 지운다. 받아가지 않는 경우 최대 7일동안 저장한다.
http://techcrunch.com/2014/02/27/apple-explains-exactly-how-secure-imessage-really-is/
=> 간단 요약
iMessage의 동작 방식
1. iMessage를 처음 사용하면 두개의 private/public key 셋을 만든다.
2. private key는 디바이스에 놔두고(나중에 decrypt에 사용) public key는 애플의 서버에 보낸다.
3. 내 친구가 나와 채팅하고자 하면 친구의 장비는 내 public key를 애플 서버로부터 받아온다. 친구가 메시지를 작정하고 send를 하면 받아온 public key로 encrypt를 한 후 내보낸다.
4. 각각의 메시지별로 암호화가 된다. 예를 들어 내가 아이폰과 아이패드를 가지고 있다면 나는 아이폰용 pri/pub key 셋, 아이패드용 pri/pub key 셋을 가지고 있을 것이므로 각각의 장비별로 암호화된 후 보내진다.
5. timestamp나 APN routing data같은 일부분의 데이타는 암호화하지 안는다.
6. 암호화된것과 암호화되지 않은 전체를 모아 또 암호화를 한다.
7. 사진이나 긴 메시지같은 양이 큰 경우: 랜덤 키를 만들어 사진을 이것으로 암호화한다. 그리고 암호화된 사진을 애플의 서버에 저장한다(URI). 키와 사진의 URI를 암호화하여 보내고자 하는 쪽에 전달한다. 받은 쪽은 URI에서 사진을 받아온 후 키로 복호화하여 사진을 볼 수 있게 된다.
8. 사용자가 메시지를 받으면 애플을 서버에서 메시지를 지운다. 받아가지 않는 경우 최대 7일동안 저장한다.
페이스북에서의 사진 캐싱에 대하여
An analysis of Facebook photo caching
https://code.facebook.com/posts/220956754772273/an-analysis-of-facebook-photo-caching
=> 위 내용에의 요약
사진의 사용에는 네부분의 캐싱이 있다.
Browser cache -> Edge cache -> Origin cache -> Haystack(Backend)
Browser cache: 사용자가 사진을 봤다면 브라우저의 캐시(로컬)에 저장될 것이다.
Edge cache: 브라우저의 캐시에 사진이 없다면 CDN이나 edge cache로 사진을 요청한다. edge cache는 internet points of presence(PoPs)에 위치해 있다.
Origin cache: 여러 data center에 위치해 있는 하나의 캐시이다. 사진의 id 기준으로 캐시하고 있기 때문에 같은 사진을 요청하는 경우에는 항상 같은 서버에 요청하게 된다.
Haystack: 실제 사진을 저장하고 있는 backend store. origin cache는 같은 data center에 있는 haystack에게 사진을 요청한다(만약 같은 data center에 있는 haystack이 죽었다면 다른 data center에 있는 haystack에게 요청한다.).
사진에 대한 hit ratio를 확인해 보니 haystack으로 가는 request는 9.9%정도 밖에 되지 않았다.
그래도 이걸 또 향상시켜 보자.
1. 캐시의 양을 증가시킨다.
=> 인기가 많은 사진의 경우 brower cache와 edge cache에서 중요한 역할을 하고 인기가 적은 사진의 경우 origin이나 backend에서 중요하다.
2. 캐싱 알고리즘의 변경
많이 사용되는 캐싱 알고리즘으로 FIFO, LRU, LFU, S4LRU가 있다. 우리의 테스트에서 S4LRU가 가장 성능이 좋게 나왔다.
papger: http://www.cs.cornell.edu/~qhuang/papers/sosp_fbanalysis.pdf
https://code.facebook.com/posts/220956754772273/an-analysis-of-facebook-photo-caching
=> 위 내용에의 요약
사진의 사용에는 네부분의 캐싱이 있다.
Browser cache -> Edge cache -> Origin cache -> Haystack(Backend)
Browser cache: 사용자가 사진을 봤다면 브라우저의 캐시(로컬)에 저장될 것이다.
Edge cache: 브라우저의 캐시에 사진이 없다면 CDN이나 edge cache로 사진을 요청한다. edge cache는 internet points of presence(PoPs)에 위치해 있다.
Origin cache: 여러 data center에 위치해 있는 하나의 캐시이다. 사진의 id 기준으로 캐시하고 있기 때문에 같은 사진을 요청하는 경우에는 항상 같은 서버에 요청하게 된다.
Haystack: 실제 사진을 저장하고 있는 backend store. origin cache는 같은 data center에 있는 haystack에게 사진을 요청한다(만약 같은 data center에 있는 haystack이 죽었다면 다른 data center에 있는 haystack에게 요청한다.).
사진에 대한 hit ratio를 확인해 보니 haystack으로 가는 request는 9.9%정도 밖에 되지 않았다.
그래도 이걸 또 향상시켜 보자.
1. 캐시의 양을 증가시킨다.
=> 인기가 많은 사진의 경우 brower cache와 edge cache에서 중요한 역할을 하고 인기가 적은 사진의 경우 origin이나 backend에서 중요하다.
2. 캐싱 알고리즘의 변경
많이 사용되는 캐싱 알고리즘으로 FIFO, LRU, LFU, S4LRU가 있다. 우리의 테스트에서 S4LRU가 가장 성능이 좋게 나왔다.
papger: http://www.cs.cornell.edu/~qhuang/papers/sosp_fbanalysis.pdf
피드 구독하기:
글 (Atom)