GC for HotSpot Java, V8 Nodejs, PHP and Python

Java

  • Java is using Generation strategy for GC.
  • The memory will be divided into 3 sections: Young generation, old generation, and metaSpace
  • The young generation contains: Eden, from, to with space 8:1:1

V8 Nodejs

  • v8 is using generation GC as well
  • the difference is young generation is small
  • young generation only contains 2 spaces: from and to
  • there is no metaspace

PHP

  • session (live time) and the reference count

Python

  • reference count
  • 3 generations

Java Container Class

Collection & Map

Collection – A collection represents a group of objects, known as its elements.Some collections allow duplicate elements and others do not. Some are ordered and others unordered.

Map – An object that maps keys to values. A map cannot contain duplicate keys; each key can map to at most one value.

3 ways to loop map:

  • Set keySet()
  • Collection values()
  • Set< Map.Entry< K, V>> entrySet()

List Set & Queue

List Set & Queue inherit Collection
Difference:

  • List: an ordered collection, the element can be duplicated
  • Set: elements can not be duplicated

List

The list provides a special iterator called ListIterator.

ListIterator<E> listIterator();

ListIterator<E> listIterator(int index);

public interface ListIterator<E> extends Iterator<E> {
    // Query Operations

    boolean hasNext();

    E next();

    boolean hasPrevious();

    E previous();

    int previousIndex();

    void remove();

    void set(E e);

    void add(E e);
}

ArrayList

  • ArrayList implements List with array.
  • It allows inserting null.
  • size, isEmpty, get, set, iterator, add are all O(1), if add N, it will be O(N)
  • ArrayList is not synchronized for threads
  • By default, the first time we insert the element the size of it is 10.
  • if exceed, the size will increase 50%

source code:

transient Object[] elementData;

private int size;

All elements are saved within the object array and size is used for length control.

source code of add:

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

The add operation will check the length. If not match then it will call grow (Arrays.copyOf)

source code of remove:

public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

It will use System.arraycopy to move all elements behind the target index and remove the last element.

That’s why the cost of adding and removing is expensive 🙂

It alos has a function trimToSize() which can be used for compressing the size of array

public void trimToSize() { 
    modCount++; 
    if (size < elementData.length) { 
        elementData = Arrays.copyOf(elementData, size); 
    } 
}

Besides, it implements RandomAccess. RandomAccess also includes: ArrayList, AttributeList, CopyOnWriteArrayList,RoleList, RoleUnresolvedList, Stack, Vector

There is one comment within the RandomAccess:

for (int i=0, n=list.size(); i < n; i++) {     
    list.get(i);
}
runs faster than this loop:
for (Iterator i=list.iterator(); i.hasNext(); ) { 
   i.next();
}

Compared with Vector

  • almost the same. Only different is Vector is synchronized so it’s more expensive
  • Vector grows 2 times while ArrayList grows 1.5 times
  • Vector also contains Stack

LinkedList

LinkedList is also an ordered container class. LinkedList implements List with Link

ArrayList V.S LinkedList

  • Get: ArrayList can use index to get. LinkedList have to find from the beginning
  • Add & Remove: LinkedList can easily add and remove by breaking the link. ArrayList have to copy all data and move position
  • Grow: ArrayList has to apply for a larger array and move the data. LinkedList can dynamically create new link node

source code:

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

A two way link

transient int size = 0;

transient Node<E> first;

transient Node<E> last;

Each linkedList will have first and last point

Add and Delete:

private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

private E unlinkLast(Node<E> l) {
    // assert l == last && l != null;
    final E element = l.item;
    final Node<E> prev = l.prev;
    l.item = null;
    l.prev = null; // help GC
    last = prev;
    if (prev == null)
        first = null;
    else
        prev.next = null;
    size--;
    modCount++;
    return element;
}

E unlink(Node<E> x) {
    // assert x != null;
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    return element;
}

LinkedList also implements the Deque interface which inheirts from Queue. So it also supports pop, push and peek

Set

Set doesn’t implement any function like colleciton. Set is just a concept: elements cannot be duplicated

e.g. HashSet, LinkedHashSet, TreeSet

HashSet

  • HashSet implements Set and it is based on HashMap.
  • Disorderd
  • Allow null element

source code:

private transient HashMap<E,Object> map;

private static final Object PRESENT = new Object();

So all add, reomve etc are the operaion of HashMap. The Iterator is just the keySet of HashMap

public Iterator<E> iterator() {
    return map.keySet().iterator();
}

public boolean contains(Object o) {
    return map.containsKey(o);
}

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

public void clear() {
    map.clear();
}

LinkedHashSet

LinkedHashSet can use Link to keep the order of set elements.
LinkedHashSet is based on LinkedHashMap

TreeSet

The order of TreeSet is ( e1.compareTo(e2) == 0 ) TreeSet is based on TreeMap and the element must implement Comparable interface ( e1.compareTo(e2) == 0 )

Map

HashMap

It’s stored by hash table.

transient Node<K,V>[] table;

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

table is used for saving element. If any conflicts, save it to the next link table.

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

LinkedHashMap

It’s similar to hashmap. The difference is it also have the following link tables:

transient LinkedHashMap.Entry<K,V> head;

transient LinkedHashMap.Entry<K,V> tail;

TreeMap

it’s based on red-black tree.

WeakHashMAp

if only the weakHashMap has the reference of an element, it will automatically remove the element

Few issues for Java LTI integration

Recently I began to work on an LTI integration with Java. I haven’t used Java for almost 1 year so it takes some time to pick it up. I’m happy that Java doesn’t change so quickly like javascript 😛

Welcome back to the world of Java with Hibernate and Spring MVC and Maven

Anyway, I will record all issues I met during the implementation. Later I will write down sth about LTI.

Fix for java.lang.IllegalArgumentException: No converter found for return value of type

I met this issue after adding a new maven dependency. I did some quick research. A lot of people saying that you can solve it by adding the JSON dependency. I tried and it’s not working.

Then I figured out I should add the getter for that class and problem solved.

Example of generating key and secret

I found this code online. It’s good to start with it. But this guy is using encodeBase64String within Base64 and I cannot find it within that class. So it should be replaced with sth like new String(the byte result from Base64)

import javax.crypto.Cipher;
import javax.crypto.spec.IvParameterSpec;
import javax.crypto.spec.SecretKeySpec;

import org.apache.commons.codec.binary.Base64;

public class Encryptor {
    public static String encrypt(String key, String initVector, String value) {
        try {
            IvParameterSpec iv = new IvParameterSpec(initVector.getBytes("UTF-8"));
            SecretKeySpec skeySpec = new SecretKeySpec(key.getBytes("UTF-8"), "AES");

            Cipher cipher = Cipher.getInstance("AES/CBC/PKCS5PADDING");
            cipher.init(Cipher.ENCRYPT_MODE, skeySpec, iv);

            byte[] encrypted = cipher.doFinal(value.getBytes());
            System.out.println("encrypted string: "
                    + Base64.encodeBase64String(encrypted));

            return Base64.encodeBase64String(encrypted);
        } catch (Exception ex) {
            ex.printStackTrace();
        }

        return null;
    }

    public static String decrypt(String key, String initVector, String encrypted) {
        try {
            IvParameterSpec iv = new IvParameterSpec(initVector.getBytes("UTF-8"));
            SecretKeySpec skeySpec = new SecretKeySpec(key.getBytes("UTF-8"), "AES");

            Cipher cipher = Cipher.getInstance("AES/CBC/PKCS5PADDING");
            cipher.init(Cipher.DECRYPT_MODE, skeySpec, iv);

            byte[] original = cipher.doFinal(Base64.decodeBase64(encrypted));

            return new String(original);
        } catch (Exception ex) {
            ex.printStackTrace();
        }

        return null;
    }

    public static void main(String[] args) {
        String key = "Bar12345Bar12345"; // 128 bit key
        String initVector = "RandomInitVector"; // 16 bytes IV

        System.out.println(decrypt(key, initVector,
                encrypt(key, initVector, "Hello World")));
    }
}

Build an OAuth Provider

There are many OAuth client libs on the internet. But it’s difficult to find some libs as an OAuth Provider.

The first step of it is to generate a good customer key and secret. I found the following example last night.

import java.io.IOException;
import java.io.UnsupportedEncodingException;
import java.security.AlgorithmParameters;
import java.security.GeneralSecurityException;
import java.security.NoSuchAlgorithmException;
import java.security.spec.InvalidKeySpecException;
import java.util.Base64;
import javax.crypto.Cipher;
import javax.crypto.SecretKey;
import javax.crypto.SecretKeyFactory;
import javax.crypto.spec.IvParameterSpec;
import javax.crypto.spec.PBEKeySpec;
import javax.crypto.spec.SecretKeySpec;

public class ProtectedConfigFile {

    public static void main(String[] args) throws Exception {
        String password = System.getProperty("password");
        if (password == null) {
            throw new IllegalArgumentException("Run with -Dpassword=<password>");
        }

        // The salt (probably) can be stored along with the encrypted data
        byte[] salt = new String("12345678").getBytes();

        // Decreasing this speeds down startup time and can be useful during testing, but it also makes it easier for brute force attackers
        int iterationCount = 40000;
        // Other values give me java.security.InvalidKeyException: Illegal key size or default parameters
        int keyLength = 128;
        SecretKeySpec key = createSecretKey(System.getProperty("password").toCharArray(),
                salt, iterationCount, keyLength);

        String originalPassword = "secret";
        System.out.println("Original password: " + originalPassword);
        String encryptedPassword = encrypt(originalPassword, key);
        System.out.println("Encrypted password: " + encryptedPassword);
        String decryptedPassword = decrypt(encryptedPassword, key);
        System.out.println("Decrypted password: " + decryptedPassword);
    }

    private static SecretKeySpec createSecretKey(char[] password, byte[] salt, int iterationCount, int keyLength) throws NoSuchAlgorithmException, InvalidKeySpecException {
        SecretKeyFactory keyFactory = SecretKeyFactory.getInstance("PBKDF2WithHmacSHA512");
        PBEKeySpec keySpec = new PBEKeySpec(password, salt, iterationCount, keyLength);
        SecretKey keyTmp = keyFactory.generateSecret(keySpec);
        return new SecretKeySpec(keyTmp.getEncoded(), "AES");
    }

    private static String encrypt(String property, SecretKeySpec key) throws GeneralSecurityException, UnsupportedEncodingException {
        Cipher pbeCipher = Cipher.getInstance("AES/CBC/PKCS5Padding");
        pbeCipher.init(Cipher.ENCRYPT_MODE, key);
        AlgorithmParameters parameters = pbeCipher.getParameters();
        IvParameterSpec ivParameterSpec = parameters.getParameterSpec(IvParameterSpec.class);
        byte[] cryptoText = pbeCipher.doFinal(property.getBytes("UTF-8"));
        byte[] iv = ivParameterSpec.getIV();
        return base64Encode(iv) + ":" + base64Encode(cryptoText);
    }

    private static String base64Encode(byte[] bytes) {
        return Base64.getEncoder().encodeToString(bytes);
    }

    private static String decrypt(String string, SecretKeySpec key) throws GeneralSecurityException, IOException {
        String iv = string.split(":")[0];
        String property = string.split(":")[1];
        Cipher pbeCipher = Cipher.getInstance("AES/CBC/PKCS5Padding");
        pbeCipher.init(Cipher.DECRYPT_MODE, key, new IvParameterSpec(base64Decode(iv)));
        return new String(pbeCipher.doFinal(base64Decode(property)), "UTF-8");
    }

    private static byte[] base64Decode(String property) throws IOException {
        return Base64.getDecoder().decode(property);
    }
}

I properly need to ask someone to see if there is a best practice for this.

For Java base64

It’s good to know that from java8 they include base64 into java.util

import java.util.Base64;
byte[] encodedBytes = Base64.getEncoder().encode("Test".getBytes());
System.out.println("encodedBytes " + new String(encodedBytes));
byte[] decodedBytes = Base64.getDecoder().decode(encodedBytes);
System.out.println("decodedBytes " + new String(decodedBytes));

Previously, we have to use sth like:

import org.apache.commons.codec.binary.Base64;
byte[] encodedBytes = Base64.encodeBase64("Test".getBytes());
System.out.println("encodedBytes " + new String(encodedBytes));
byte[] decodedBytes = Base64.decodeBase64(encodedBytes);
System.out.println("decodedBytes " + new String(decodedBytes));

Reading Note 05/01/2017

kubernates

A framework based on docker which can be used in a production scenario.

Problem may have for using kubernates

Storage

Dockers provide data volume. However, this data volume cannot be used for production env directly. It will cause a lot of issues such as data backup, data recovery and distribution data storage.
The blog recommended a method call NAS(Network Attached Storage). The advantages of NAS are:

  • even if the application server down, we still can get the data
  • nas only contains the service about storage, no application service. So it reduces the risk of server crashes

There is another term called SAN (Storage Area Network). SAN is treated as the direct connection with the server, while NAS (e.g. NFS) is a remote storage solution.

SAN is often used as a disaster backup.


System design

Standard Rules

Monitor

It’s essential to clearly describe the status of the entire service system.

Interface standard

There should be a clear standard for the interface, such as naming, meaning, and functionality.

Error handler

Following the standard rule to define error handler and error message

Create code example with real scenario

If the developer can have an example to follow, then they will have less chance to make mistakes.


PHP OpCode

What’s OpCode

OpCode is a cache which can be used to improve the performance of PHP. It can cache the compiled result during the php life cycle. Sometimes it can improve the performance 3 times.

How does it work? Example: Zend OpCode

php life cycle with zend OpCode


Data visualization Standard

a standard


Developer career

One of the issues for developers is that they only focus on the latest technologies such as latest frameworks, Memcache, Nginx load balances and distribution sys, etc.

However, they all ignore the basic knowledge. If you don’t have a good understanding of the basic knowledge, you cannot join some large companies with the huge distribution system. If you don’t improve yourself, you could only work in small companies.

So relearn the knowledge about the computer system, operating system, C & C++, Unix, Object oriented programming.

Move to New Server, Hello World Again!

Since the previous one had an old operating sys (ubuntu 13) and old version of wordpress, I decided to move the current new server (with 1G memory finally!).

It took some time to config the domain last night. But now it works well.